Question about the client algoritm...
log in

Advanced search

Message boards : Science : Question about the client algoritm...

Author Message
czwr1d
Send message
Joined: 15 Jan 11
Posts: 1
Credit: 1,440,309
RAC: 0
Message 11143 - Posted: 25 Jan 2011, 23:47:07 UTC

I'm new to the project...

Do the client data packets carry with them the maximum known value that still follows the pattern, and then stop computation when the calculated value falls below that value?

In other words, if we've calculated large values that meet the criteria, and I assume we are doing it in numerical order, then we don't have to reduce each value itself to one, but we can "short circuit" the process when we fall into a state that is known to reduce to one. Does the client take advantage of such short circuits?

Craig C. Capen
Capen324@Comcast.net

Profile mikey
Avatar
Send message
Joined: 11 Aug 09
Posts: 3242
Credit: 1,685,089,826
RAC: 6,450,268
Message 11148 - Posted: 26 Jan 2011, 11:13:33 UTC - in response to Message 11143.
Last modified: 26 Jan 2011, 11:14:26 UTC

I'm new to the project...

Do the client data packets carry with them the maximum known value that still follows the pattern, and then stop computation when the calculated value falls below that value?

In other words, if we've calculated large values that meet the criteria, and I assume we are doing it in numerical order, then we don't have to reduce each value itself to one, but we can "short circuit" the process when we fall into a state that is known to reduce to one. Does the client take advantage of such short circuits?

Craig C. Capen


I don't know but DO NOT put your email in a public place or you will start to get TONS of spam!!

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: 2
Message 11151 - Posted: 26 Jan 2011, 15:18:27 UTC

Check out the optimizations section of the Collatz Wiki page. The example given looks ahead 5 steps. For speed, our app looks ahead 20 steps which means 2^20 calculations are cached. Each additional step doubles the size of the lookup table, so 21 steps would require 2^21 calculations. In order to cache all the previous numbers, it would take something like 2,251,799,813,685,248 or 2 quintillion times the memory. Let's assume we could stop when we got to a number that was already checked. How do you know which numbers those are? At any given moment, there are 107,195,786,638,393,344 (107 quadrillion) numbers in the process of being checked. There is no guarantee that they are sequential. Some workunits are a month or two old (or more?). So knowing which have been checked would require a database of all of them. That would require returning the steps for every number. That would require output files for each workunit to be 16TB in size. Sorry, but I don't have the network bandwidth or the disk space to store 150,000 files that are 16TB each.

So, in short, the answer is that once the value gets below 2^20, we stop because we have pre-calculated all of those. Why not cache all? The fast GPUs can check over 500 million numbers per second. The time it would take to look up the steps from a database for 500 million numbers is slower than actually doing the calculations unless the database was stored in RAM. When I last checked, even the new machines don't support 32 quintillion megabytes of RAM. :-)

ccappel
Avatar
Send message
Joined: 22 Mar 10
Posts: 6
Credit: 509,348
RAC: 0
Message 11563 - Posted: 24 Feb 2011, 16:25:30 UTC

I think what the OP is asking is the highest contiguous number that has been checked stored somewhere so that even if the WU is not sequential, it could hold the highest known contiguous checked number at the time the WU was generated. Once the checking falls below that highest known number, it could stop.

Of course, doing this would not allow for identifying the total steps for any given number, and thus keeping track of record-high step totals would cease.

Also, it is known that any 3x+1 step will produce an even number n where n mod 6 = 4, so if the project is only checking odd numbers, it could switch to checking even numbers that satisfy n mod 6 = 4, thus reducing the numbers to be checked by a factor of 3, and tripling the WU processing rate.

Profile Ethian
Volunteer tester
Send message
Joined: 29 Oct 09
Posts: 20
Credit: 6,649,825
RAC: 0
Message 11658 - Posted: 3 Mar 2011, 15:49:48 UTC - in response to Message 11563.
Last modified: 3 Mar 2011, 15:50:15 UTC

That has already been suggested (by me, and others), but since it cannot keep track of the amount of steps, it might be less beneficial to mathematicians ;)
(however, it does speed up calculations, since you only have to check up to current n, if the number drops below that, it has already been checked. Also, (repeated) division by 2 is incredibly easy in binary, simply slash all trailing zeroes, and there you go.
Multiplying by 3 and adding one can be done by shuffling your bits around and 1 addition, too
(11011 * 3 + 1 =

0110111 (times 2 + 1, aka add a 1 in the last place)
0011011 (original number)
--------+
1010010 (per definition a 0 on last spot, so it can be removed straight away if you feel like it)

Hmmm, maybe you can even build a checker in Minecraft if you feel like it :D


Post to thread

Message boards : Science : Question about the client algoritm...


Main page · Your account · Message boards


Copyright © 2018 Jon Sonntag; All rights reserved.