Sieving primes with wheels

09162017, 01:33 AM
(This post was last modified: 09162017 01:43 AM by bplus.)
Post: #21
(Print Post)




RE: Sieving primes with wheels
I have compared what I call Owen Deluxe 30 wheel to my original 30 wheel and find no significant difference in times.
Owen Deluxe 30 wheel Code Snippet: [Select] ' 30 wheel sieve Owen deluxe.bas for QB64 fork (B+=MGA) 20170830 copy and trans to QB64 My original 30 wheel code: Code Snippet: [Select] ' 30 wheel sieve.bas for QB64 fork (B+=MGA) 20170830 copy and trans to QB64 My code steps the pcandidate by 2 in outer loop 15 times over 30 integers. Owens deluxe code steps the pcandidate by a pattern amount 8 times over 30 integers. You'd think that would save time but while stepping 1 time you increment a 2nd variable, the Pattern Index, one time and then check to see if that has reached 9 and to reset it to 1 if it did. I think that 2nd decision blows the time saved from doing less pcandidate steps. B += _ 

09162017, 10:22 AM
Post: #22
(Print Post)




RE: Sieving primes with wheels
owen's deluxe x 2
modified inner loop as well what are the new time comparisons on your computer? Code Snippet: [Select] ' 30 wheel sieve Owen deluxe.bas for QB64 fork (B+=MGA) 20170830 copy and trans to QB64 

09162017, 02:15 PM
Post: #23
(Print Post)




RE: Sieving primes with wheels
Yep! very nice, Owen deluxe x2 showing significant time savings, here are my results:
' QB64 original 30 wheel results 'topN = 1000000, primes 78,498, .15 secs, 8169 twins last 999959, 999961 'topN = 10000000, primes 664,579, 1.81 secs, 58,980 twins last 9999971, 9999973 'topN = 100000000, primes 5,761,455, 19.65 secs, 440,312 twins last 99999587, 99999589 ' out of memory for 1 billion 'compare to bigger wheel sieve WOW the 30 wheel is faster! 'QB64 results from 2310 wheel 'topN = 1000000, primes 78,498, .18 secs, 8169 twins last 999959, 999961 'topN = 10000000, primes 664,579, 1.98 secs, 58,980 twins last 9999971, 9999973 'topN = 100000000, primes 5,761,455, 21.57 secs, 440,312 twins last 99999587, 99999589 ' out of memory for 1 billion 'Owen Deluxe 30 Wheel results, Owen's Mod apply wheel pattern on outer loop 'topN = 1000000, primes 78498, .189 sec, 8169 twins 'topN = 10000000, primes 664,579, 1.797 secs, 58,980 twins 'topN = 100000000, primes 5,761,455, 20.45 sec, 440,312 twins 'Owen Delux x2 apply 30 wheel pattern on both inner and outer loops 'topN = 1000000, primes 78498, .130 sec 'topN = 10000000, primes 664,579, 1.656 secs 'topN = 100000000, primes 5,761,455, 16.420 secs I checked some number factoring and your mods do not seem to harm that either. very good! I am impressed it didn't appear too hard to find the inner Pattern Index to start off on the right foot. B += _ 

09162017, 03:56 PM
(This post was last modified: 09162017 03:57 PM by owen.)
Post: #24
(Print Post)




RE: Sieving primes with wheels
thanks for checking the factors. cool beans man.
so what to do next? how about we take another look at the array containing the range (topN). dim ff(topN/2) ff(1) represents 1 : ff(2) reps 3 : ff(3) reps 5 etc... or dim ff(topN/8) ff(1) reps N+4 : ff(2) reps N+2 : ff(3) reps N+4 etc... this could be a way to address the "out of memory for 1 billion" issue. as far as speed, will it be faster? there's only one way to find out. 

09162017, 04:14 PM
Post: #25
(Print Post)




RE: Sieving primes with wheels
Yes! devoting half of memory for even numbers seems like great waste of memory, another 6th for 3's, and what 1/15 for 5's? The index has to be a big type but not the data type for number stored.
For me, 100 million is enough, more than enough. I am looking at Twin primes. I have them in 3 classes and a trivial 4th "Other" that counts 3, 5 and 5, 7 twins. I was last doing counts at every 100,000 up to the 100,000,000. They slowly, very slowly get less and less. This was before Owen Deluxe x2 method, mostly done last night: Code Snippet: [Select] ' Twin primes from 30 wheel.bas for QB64 fork (B+=MGA) 20170916 That doesn't give me any ideas for what's next either but happy to have a way to classify Twins. B += _ 

09162017, 06:57 PM
(This post was last modified: 09162017 06:58 PM by owen.)
Post: #26
(Print Post)




RE: Sieving primes with wheels
I think what you are interested in when you say "a way to classify twins" is where in the wheel do they appear.
and at a quick glance I think this is why you do: Code Snippet: [Select] SELECT CASE (lastp MOD 30) further, and i'm just guessing, you are interested to see if there is any rhythm to their beat. If my guess is wrong please explain your curiosity further. 

09172017, 09:30 AM
Post: #27
(Print Post)




RE: Sieving primes with wheels
Actually, it's like an old mystery about Twin primes has been solved, where do they come from?
At JB forum in early summer we did a quick little Twin prime study about the last digits, confirming an observation made by some math guys about likelyhood of repeating. B += _ 

09172017, 03:06 PM
Post: #28
(Print Post)




RE: Sieving primes with wheels
i think primes (to include twin primes) are the remnants of interwoven waves.
http://www.thejoyfulprogrammer.com/qb64/...n=lastpost 

09172017, 08:41 PM
Post: #29
(Print Post)




RE: Sieving primes with wheels
Quote: i think primes (to include twin primes) are the remnants of interwoven waves. Absolutely! primes are what's left when all the composites (in the area of question) are accounted for. B += _ 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)
Powered By MyBB, © 20022017 MyBB Group.
Most website layout graphics on this site is © 2014  Walter Whitman. All Rights Reserved.
Most website layout graphics on this site is © 2014  Walter Whitman. All Rights Reserved.