Recent

Author Topic: how to determine whether a number is perfect square or not?  (Read 5913 times)

rabbit_dance

  • Full Member
  • ***
  • Posts: 152
how to determine whether a number is perfect square or not?
« on: October 01, 2015, 10:50:25 am »
how to determine whether a number is perfect square or not?

mdalacu

  • Full Member
  • ***
  • Posts: 205
    • dmSimpleApps
Re: how to determine whether a number is perfect square or not?
« Reply #1 on: October 01, 2015, 10:56:22 am »
if sqrt(x) = Trunc(sqrt(x)) then ...whatever  ;)

rabbit_dance

  • Full Member
  • ***
  • Posts: 152
Re: how to determine whether a number is perfect square or not?
« Reply #2 on: October 01, 2015, 11:01:41 am »
have you ever considered the transform deviation?

Eugene Loza

  • Hero Member
  • *****
  • Posts: 566
    • My "almost daily" development blog
Re: how to determine whether a number is perfect square or not?
« Reply #3 on: October 01, 2015, 11:16:05 am »
if sqrt(x) = Trunc(sqrt(x)) then ...whatever  ;)
I think a more accurate way to would be something like:
if abs(sqr(trunc(sqrt(x))-x)<1e-15 then... //due to double digit noise limit.
Lazarus 1.9 + FPC 3.1.1 Debian Jessie 64 bit.

My Free and Open Source games in Lazarus/FreePascal/CastleGameEngine:
https://decoherence.itch.io/
(and some ancient games in Turbo Pascal too)
Sources are here: https://github.com/eugeneloza?tab=repositories

MathMan

  • Full Member
  • ***
  • Posts: 196
Re: how to determine whether a number is perfect square or not?
« Reply #4 on: October 01, 2015, 03:22:47 pm »
how to determine whether a number is perfect square or not?

Are you looking for a solution for float or integer? If integer then arbitrary sized integers or 64 bit integers only?

Bart

  • Hero Member
  • *****
  • Posts: 3808
    • Bart en Mariska's Webstek
Re: how to determine whether a number is perfect square or not?
« Reply #5 on: October 01, 2015, 04:54:51 pm »
Easy solution: Sqr(Trunc(Sqrt(X))) = X (where X is some Integer type).

Bart
« Last Edit: October 01, 2015, 06:07:14 pm by Bart »

MathMan

  • Full Member
  • ***
  • Posts: 196
Re: how to determine whether a number is perfect square or not?
« Reply #6 on: October 02, 2015, 09:03:23 am »
Easy solution: Sqr(Trunc(Sqrt(X))) = X (where X is some Integer type).

Bart

Unfortunately not :-( Internal precision of float is 56 bit mantissa. Converting a qword to float will loose the least significant 8 bit and thus provide false results in chunks of 256 consecutive numbers e.g. There is only one way to do it correct - calculate the square root with an integer based algorithm, then square it back and compare the results. The trick here is that a lot of numbers can be discarded initially just looking at the least significant n bit of the integer. Perfect squares can only have certain bit patterns in the least significant bits, so deviations can easily be discarded. However - one still needs to apply the fully check to the remaining numbers.

Background - take an integer N / then N has (in a simple case) the form 2k or 2k+1 / when squared this gives 4k^2 or 4k^2+2k+1 which leads to the bit pattern of "00" or "01" as possible least significant bits of a perfect square - so you already excluded 50% of all numbers under test. However 8 e.g. would still be considered "candidate" by this and still require the full test to be eliminated. This scheme can be expanded if one consideres N as 4k, 4+1, 4k+2, 4k+3 etc.

If you google a bit you'll probably find several implementations taking this scheme to various Levels.

Hope I made myself clear.

Cheers,
MathMan

Bart

  • Hero Member
  • *****
  • Posts: 3808
    • Bart en Mariska's Webstek
Re: how to determine whether a number is perfect square or not?
« Reply #7 on: October 02, 2015, 03:53:58 pm »
Easy solution: Sqr(Trunc(Sqrt(X))) = X (where X is some Integer type).

Bart

Unfortunately not :-( Internal precision of float is 56 bit mantissa. Converting a qword to float will loose the least significant 8 bit and thus provide false results in chunks of 256 consecutive numbers e.g.

(Trunc(Sqrt(X))) will give an Integer
Sqr(this integer) will give yet another integer
Comparing this "yet another integer" to X will either evaluate to True, in which case (Trunc(Sqrt(X))) is indeed the true square root of X, or it will be False, in which case (Trunc(Sqrt(X))) is NOT the true square root of X.

But I can see how my post might have been confusing.
I should have written it like:

Code: [Select]
var
  X, Y: UInt64;
  FoundSqrtThatIsAnIntegerOfX: Boolean;
begin
  Y := Trunc(Sqrt(X));
  FoundSqrtThatIsAnIntegerOfX := Sqr(Y) = X;
end.

Bart

julkas

  • Hero Member
  • *****
  • Posts: 598
  • KISS principle / Lazarus 2.0.6 / FPC 3.0.4
Re: how to determine whether a number is perfect square or not?
« Reply #8 on: May 29, 2020, 08:46:17 am »
how to determine whether a number is perfect square or not?
Other (more interesting) - if a integer number is perfect cube (has corners ...) ?
B.T.W.  Python perfect square for integer x - int(x**0.5)**2 == x   
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

 

TinyPortal © 2005-2018