Thread: Perfect sqquare
View Single Post
Old 2011-08-24, 08:56   #2
Gammatester's Avatar
Mar 2009

2×19 Posts

Originally Posted by JohnFullspeed View Post
When you search a perfzct square the first step is to test the last digit

I need tto find value with 3 like last didit
Id ity possible to make one or two tests like
(n & 7 == 1) or (n & 31 == 4) or (n & 127 == 16) or (n & 191 == 0) then John
As usual you are far too vague for a precise direct answer.

First of all: Do you want to test multi-precision numbers or single precision numbers (for single precision in the FPU range a simple check if floor(sqrt(n))^2 = n is quite efficient).

If you want to test multi-precision numbers there is a second question: Do you really mean "digit" = decimal digit or do you mean bit.

Since most implementations use a power-of-2 base, a mod 1000 is not very effective as a first step. More effective is e.g. a first test mod 128, i.e. use the least significant limb & 127 for a table lookup, this has a rejection rate of about 82%.

As a reference see e.g. H. Cohen, A Course in Computational Algebraic Number Theory, 4th printing, 2000. IIRC Cohen uses mod 64 instead of 128 (see also the Pari source function carremod in arith1.c)

Last fiddled with by Gammatester on 2011-08-24 at 09:40
Gammatester is offline   Reply With Quote