mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)

 JohnFullspeed 2011-08-24 07:46

Perfect sqquare

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
([I]n[/I] & 7 == 1) or ([I]n[/I] & 31 == 4) or ([I]n[/I] & 127 == 16) or ([I]n[/I] & 191 == 0) [B]then[/B] John

 Gammatester 2011-08-24 08:56

[QUOTE=JohnFullspeed;269986]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
([I]n[/I] & 7 == 1) or ([I]n[/I] & 31 == 4) or ([I]n[/I] & 127 == 16) or ([I]n[/I] & 191 == 0) [B]then[/B] John[/QUOTE]
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)

 JohnFullspeed 2011-08-24 12:00

Like often when you don't have the answer you answer at an other question
But this time you try to show us waht to show that youare a good informaticman
Wrong! You are still not good:

My question can't be with real ou expand for numeros reasons First

Just to shows that it's stupide
[CODE]i F (n & 7 == 1) or (n & 31 == 4) or (n & 127 == 16) or (n & 191 == 0) then [/CODE]I
I remove the if (sorry rthat you don(r see)

Try to compile this code with n real,simple,ou doiuble

If you don't want like me use a AND , OR... iis easy and need only one cycle with a computer: if n%10==3[COLOR=Red][B] THEN[/B][/COLOR]
I explain you or a axn? He is waiting to terminate my calcul
(We are waiting the time of his fabulous processor).

When you go on primes numbers forums its implicit thaht you wor on Z (psotif integer) you learn when you will be n adult.Perhaps you make an estroaordinarry fif : no reals in the primes number

John
PS with axn we have not the sames ideas but ,he and I, try to give positifs elements

Thanks to keep stupid comments for you: don't answer to my thread you don't understand: I speak informatic
John

 science_man_88 2011-08-24 12:42

[QUOTE=JohnFullspeed;269986]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
([I]n[/I] & 7 == 1) or ([I]n[/I] & 31 == 4) or ([I]n[/I] & 127 == 16) or ([I]n[/I] & 191 == 0) [B]then[/B] John[/QUOTE]

if you want to check the last decimal digit of a number do mod 10 and compare to the endings of squares ( 0,1,4,9,6,5) is how I would do it. also if (x-(x mod 10 ))/10 is a certain type of number you can tell if it's a square even more.

 LaurV 2011-08-24 14:12

This question is already well debated on the forum, see [URL="http://mersenneforum.org/showpost.php?p=110896"]fenderbender's[/URL] posts, with bloom filters and all the stuff.

 JohnFullspeed 2011-08-24 15:57

3

Like you sayd a mod 10 give the result ,But on a CISC a AND is speeder than a div so with a AND the time will be the same on the two processors
and it hope than in
([I]n[/I] & 7 == 1) or ([I]n[/I] & 31 == 4) or ([I]n[/I] & 127 == 16) or ([I]n[/I] & 191 == 0)
the 3 was tested with the 1 and 2 test or the 2 and 4 or ...

first N must be odd!!!! ([I]n[/I] & 1 == 1)
J

 All times are UTC. The time now is 01:31.