Largest number checked?
log in

Advanced search

Message boards : Science : Largest number checked?

Previous · 1 · 2
Author Message
Profile Death
Avatar
Send message
Joined: 13 Jul 09
Posts: 9
Credit: 7,195,061
RAC: 0
Message 11346 - Posted: 7 Feb 2011, 14:03:51 UTC

Good day.

Just read this thread and have some idea

this one

while z > 1:
i = i + 1
if z % 2:
z = 3 * z + 1
else:
z = z / 2
return (zin, i)

can be replaced by

while z >= 2:
i = i + 1
if z % 2:
z = 3 * z + 1
else:
z = z / 2
return (zin, i)

right?

because if it 2, then it will definitely divided / 2

and if it's = then it comes into 4-2-1 way. so on with 8, etc

so what's the current algorithm of counting?

we must hit any 2^n to get it into 4-2-1, right?
____________
===
wbr, Me. Dead J. Dona

fruehwf
Send message
Joined: 13 Apr 10
Posts: 2
Credit: 11,171,666
RAC: 0
Message 11878 - Posted: 29 Mar 2011, 19:36:16 UTC

we have to look if a reached number ist a power of 2.
In the decimal system this is not very obvious for high numbers. But in the binary system all numbers which are a power of 2 has something unique : the sum of digits is 1.

I'm sure there is a way to find the out very effective for CPU's and also for GPU's .

But mayby that is allready done. ;-)

Profile Dave
Avatar
Send message
Joined: 16 Jun 11
Posts: 10
Credit: 706,504
RAC: 0
Message 12821 - Posted: 9 Oct 2011, 11:56:28 UTC

Somewhere above in this thread the question was asked if we check each number, it was answered "yes".

BUT...

IF all numbers up to n have been proved to conform to the conjecture then :-

a) all even numbers up to 2n can be ignored as they will immediatly divide to yeild a tested number. No list of tested numbers is needed here.

b) Alternate odd numbers (x) when processed as (3x+1)/2 will yeild a tested number and so do not need to be tested further for x < 3n/2, again no list is needed.

c) Alternate even numbers between 2n and 4n will yeild numbers proven by a) above.

Therefore IF a complete sequence of proven numbers is known we can speed up the testing by better than 4 times as over 3/4 numbers do not need to be tested.

Has a complete sequence up to the starting point of CC been confirmed? If so then why do we still waste time testing numbers that cannot fail?

If no such complete list exists then would it be worth the time to test those numbers less than the CC start point to establish such a sequence or would this take too long to be worth while in terms of time saving?

Please do not take this as a complaint about the CC method, it is a real question. I simply want to know what the reasons are for testing each number when it seems unneeded.
____________

Profile Slicker
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist
Avatar
Send message
Joined: 11 Jun 09
Posts: 2525
Credit: 740,580,099
RAC: 1
Message 12822 - Posted: 11 Oct 2011, 23:19:55 UTC - in response to Message 12821.

Somewhere above in this thread the question was asked if we check each number, it was answered "yes".

BUT...

IF all numbers up to n have been proved to conform to the conjecture then :-

a) all even numbers up to 2n can be ignored as they will immediatly divide to yeild a tested number. No list of tested numbers is needed here.

b) Alternate odd numbers (x) when processed as (3x+1)/2 will yeild a tested number and so do not need to be tested further for x < 3n/2, again no list is needed.

c) Alternate even numbers between 2n and 4n will yeild numbers proven by a) above.

Therefore IF a complete sequence of proven numbers is known we can speed up the testing by better than 4 times as over 3/4 numbers do not need to be tested.

Has a complete sequence up to the starting point of CC been confirmed? If so then why do we still waste time testing numbers that cannot fail?

If no such complete list exists then would it be worth the time to test those numbers less than the CC start point to establish such a sequence or would this take too long to be worth while in terms of time saving?

Please do not take this as a complaint about the CC method, it is a real question. I simply want to know what the reasons are for testing each number when it seems unneeded.


I only consider it a complaint if there aren't suggestions on how to improve. The suggestions require coming up with quite a few new algorithms than 3sx+1 and x/2. The first versions of the app used GMP. The 2.x versions are all custom and run many times faster than GMP but are very limited in the math (multiply by 3, add 1, mod 2, and divide by 2) without the overhead of the ability to do all the other things GMP handles. That's why it is soooo much faster than GMP. That having been said, it's worth investigating.

Those shortcuts may not necessarily be good options for the GPU apps which need to run with mimimal memory. Unlike the CPU app which checks one number at a time, the GPU apps have to run in parallel. If the GPU function (aka kernel) runs for more than about 33ms, the GPU driver resets and the app crashes. It will take a little R&D to figure out whether all the additional checks for shortcuts actually perform faster than using the optimized method for calculating the number of steps.

Profile Dave
Avatar
Send message
Joined: 16 Jun 11
Posts: 10
Credit: 706,504
RAC: 0
Message 12827 - Posted: 14 Oct 2011, 2:55:25 UTC - in response to Message 12822.

OK, and thanks. I get the idea, I think.

With parallel processors (GPU) it is probably faster to test everything than to sort out the unwanted numbers.

Before someone else points it out there could have been a point 4 in that any even number that fails to meet the CC must be an even number multiple of an odd number that also fails so there is no need to test ANY even number, as such any even non CC number must have a smaller nonCC compliant odd precursor. This assumes that a complete sequence of odd numbers has been tested.

To sumarise even numbers do not need testing at all, nor do odd numbers where (3n+1)/2 is even. But sorting them out to save work may take longer than testing them!




____________

Burnham@Rhodes
Send message
Joined: 12 Jan 12
Posts: 1
Credit: 36,920
RAC: 0
Message 13295 - Posted: 13 Jan 2012, 4:21:19 UTC
Last modified: 13 Jan 2012, 5:11:17 UTC

I am new to the discussion, but I have written a piece of code which can take integers up to 50 digits in length to test. A given number only takes a few milliseconds to check, but I only made it to check one number at a time so far. No reason I couldn't expand it to 100 digits or more. Each digit is a byte so it doesn't even take up that much memory. So far I have checked it against posted results on the BOINC project and my answers are the same. Does this count as finding an arbitrarily large number to check?

Update: Okay, I did this before looking around at other posts and found the one on GMP, which I'm sure outshines mine a thousandfold. Still, it was fun to write it.

jnamath
Send message
Joined: 23 Mar 16
Posts: 1
Credit: 20,215,738
RAC: 73
Message 23068 - Posted: 9 Oct 2016, 7:41:40 UTC

Just a suggestion for the original question of this really old thread:
Would it be useful to measure the current state in terms of three numbers which can be posted on the webpage
- Leading Edge - the highest number that a WU has been sent out for
- Trailing Edge - the highest number where all numbers lower than this have been checked
- Density - the number of holes beteen the two (or a quotient: (LE-TE)/# of holes

So a full status may be (arbitrary numbers)
Leading edge 2,0 * 10^15
Trailing edge 1,5 * 10^15
Delta 0,5 * 10^15
Delta Density 85%

The naming and definitions can surely be improved, but I guess you get the idea.
Maybe Span and density are too much detail an can be left out ..
Cheers Holger

PFLIEGER Guy
Send message
Joined: 7 Oct 16
Posts: 2
Credit: 768,832,381
RAC: 4,257,602
Message 24454 - Posted: 12 Nov 2017, 21:53:50 UTC

This time i have an unexpected long computing time for one WU.
Usually the computing time is 47 minutes on Nvidia with GTX 960. But this time it will run over 2 hours
The nombers of WU name is collatzsieve 37650528643995811118464_52776558133248_0
This WU need a control

Guy PFLIEGER
Masevaux
Alsace
France

Previous · 1 · 2
Post to thread

Message boards : Science : Largest number checked?


Main page · Your account · Message boards


Copyright © 2018 Jon Sonntag; All rights reserved.