Suggestion : Use sieve to speed up
log in

Advanced search

Message boards : Science : Suggestion : Use sieve to speed up

Previous · 1 · 2 · 3 · 4 · 5
Author Message
Profile sosiris
Send message
Joined: 11 Dec 13
Posts: 123
Credit: 55,800,869
RAC: 0
Message 23942 - Posted: 1 Apr 2017, 9:59:11 UTC
Last modified: 1 Apr 2017, 9:59:46 UTC

It's me again. After some personal things, I was able to sit down and think about more optimizations I could do for this project.
The first one is to get the glide steps correctly and efficiently and we don't have to go all way down to the full stopping time (aka delay steps). My first attempt was a failure because of inaccuracies within floating point numbers. This time I used a sliding window of cumulative parity vector, against a minimal requirement one. The kernel drops the numbers of which requirements are not met. Because all of them are integer ops, it should be accurate.
The second one is to increase look-ahead steps of the sieve. Currently, the 32-step sieve lets 1% of the numbers passing through. The 256-step one only allows 4 per 10 million. The more look-ahead steps of the sieve, the fewer numbers we need to check. While the running time goes up linearly (proportional to the bits of value), the problem size goes down approximately exponentially., which is great. (See lemma 6 of And since we only need a couple of residues
instead of the entire sieve to get the kernels working, being farsighted should not cause storage issues.
Right now I'm writing a collatz glide kernel which utilizes a 5000-step sieve with an 8192-bit value. Each thread holds 32-bit so there are 256 threads in a thread block. It would be slower to compute one single value, but each value is now a trillion worth.
And it's not April Fools. Believe me :)
Sosiris, team BOINC@Taiwan

Previous · 1 · 2 · 3 · 4 · 5
Post to thread

Message boards : Science : Suggestion : Use sieve to speed up

Main page · Your account · Message boards

Copyright © 2018 Jon Sonntag; All rights reserved.