mersenneforum.org Perfect sqquare
 Register FAQ Search Today's Posts Mark Forums Read

 2011-08-24, 07:46 #1 JohnFullspeed   May 2011 France 7·23 Posts 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 (n & 7 == 1) or (n & 31 == 4) or (n & 127 == 16) or (n & 191 == 0) then John
2011-08-24, 08:56   #2
Gammatester

Mar 2009

2·19 Posts

Quote:
 Originally Posted by JohnFullspeed 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

 2011-08-24, 12:00 #3 JohnFullspeed   May 2011 France 7×23 Posts 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: Your answer is the demonstration of your incompetence 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 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 THEN 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
2011-08-24, 12:42   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by JohnFullspeed 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
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.

 2011-08-24, 14:12 #5 LaurV Romulan Interpreter     Jun 2011 Thailand 100100101011102 Posts This question is already well debated on the forum, see fenderbender's posts, with bloom filters and all the stuff.
 2011-08-24, 15:57 #6 JohnFullspeed   May 2011 France 101000012 Posts 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 (n & 7 == 1) or (n & 31 == 4) or (n & 127 == 16) or (n & 191 == 0) the 3 was tested with the 1 and 2 test or the 2 and 4 or ... first N must be odd!!!! (n & 1 == 1) J

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Aliquot Sequences 0 2014-12-23 09:47 isaac Miscellaneous Math 5 2014-07-22 22:18 soumya Miscellaneous Math 1 2013-03-28 02:06 jnml Puzzles 12 2012-04-28 21:33 Zeta-Flux Math 1 2003-05-28 19:41

All times are UTC. The time now is 07:40.

Fri Apr 23 07:40:56 UTC 2021 up 15 days, 2:21, 0 users, load averages: 2.26, 2.40, 2.33

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.