mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2011-08-24, 07:46   #1
JohnFullspeed
 
May 2011
France

7·23 Posts
Default 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
JohnFullspeed is offline   Reply With Quote
Old 2011-08-24, 08:56   #2
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2·19 Posts
Default

Quote:
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
Old 2011-08-24, 12:00   #3
JohnFullspeed
 
May 2011
France

7×23 Posts
Default

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
JohnFullspeed is offline   Reply With Quote
Old 2011-08-24, 12:42   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
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
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.
science_man_88 is offline   Reply With Quote
Old 2011-08-24, 14:12   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×317 Posts
Default

This question is already well debated on the forum, see fenderbender's posts, with bloom filters and all the stuff.
LaurV is offline   Reply With Quote
Old 2011-08-24, 15:57   #6
JohnFullspeed
 
May 2011
France

7·23 Posts
Default 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
JohnFullspeed is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Down to a perfect number fivemack Aliquot Sequences 0 2014-12-23 09:47
Odd Perfect Number is 36k+9 ? isaac Miscellaneous Math 5 2014-07-22 22:18
Next perfect square after 2^n. soumya Miscellaneous Math 1 2013-03-28 02:06
Perfect square or not? jnml Puzzles 12 2012-04-28 21:33
Odd Perfect Numbers Zeta-Flux Math 1 2003-05-28 19:41

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

Sat Oct 31 07:19:10 UTC 2020 up 51 days, 4:30, 2 users, load averages: 1.66, 1.64, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.