Sieving primes with wheels bplus B = B + ... Offline This member has written at least 1,268 posts and created at least 154 threads on this forum since joining inApr 2017. 09-16-2017, 03:33 PM This post was last modified: 09-16-2017, 03:43 PM by bplus.Edited 0 times 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:```' 30 wheel sieve Owen deluxe.bas for QB64 fork (B+=MGA) 2017-08-30 copy and trans to QB64 'translated from: First Factors.bas for SmallBASIC 11/27/14 (bpf.org post) '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 '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 _DEFINE A-Z AS _INTEGER64 OPTION BASE 1 COMMON SHARED ff(), topN topN = 1223 'first 200 primes test topN = 100000000 testlimitN = SQR(topN) 'First Factors array, ff(index), is 0 if index is a prime number ' if index is composite then ff(index) contains the index's lowest factor DIM ff(topN + 30) tStart# = TIMER(.001) FOR i = 0 TO topN STEP 30     ff(i + 2) = 2: ff(i + 3) = 3: ff(i + 4) = 2: ff(i + 5) = 5: ff(i + 6) = 2: ff(i + 8) = 2: ff(i + 9) = 3     ff(i + 10) = 2: ff(i + 12) = 2: ff(i + 14) = 2: ff(i + 15) = 3: ff(i + 16) = 2: ff(i + 18) = 2     ff(i + 20) = 2: ff(i + 21) = 3: ff(i + 22) = 2: ff(i + 24) = 2: ff(i + 25) = 5     ff(i + 26) = 2: ff(i + 27) = 3: ff(i + 28) = 2: ff(i + 30) = 2 NEXT ff(2) = 0: ff(3) = 0: ff(5) = 0 'fix first 3 factors pattern(1) = 4: pattern(2) = 2: pattern(3) = 4: pattern(4) = 2 pattern(5) = 4: pattern(6) = 6: pattern(7) = 2: pattern(8) = 6 pcand = 7 patternI = 0 WHILE pcand < testlimitN     IF ff(pcand) = 0 THEN         FOR i = pcand * pcand TO topN STEP 2 * pcand             IF ff(i) = 0 THEN ff(i) = pcand         NEXT     END IF     patternI = patternI + 1     IF patternI = 9 THEN patternI = 1     pcand = pcand + pattern(patternI) WEND 'count primes FOR i = 2 TO topN     IF ff(i) = 0 THEN p = p + 1 NEXT tStop# = TIMER(.001) tTime# = tStop# - tStart# PRINT "For "; topN; " numbers there are "; p; " primes in "; tTime#; " secs."```  My original 30 wheel code: Code:```' 30 wheel sieve.bas for QB64 fork (B+=MGA) 2017-08-30 copy and trans to QB64 'translated from: First Factors.bas for SmallBASIC 11/27/14 (bpf.org post) '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 _DEFINE A-Z AS _INTEGER64 OPTION BASE 1 COMMON SHARED ff(), topN topN = 1223 'first 200 primes test topN = 100000000 testlimitN = SQR(topN) 'First Factors array, ff(index), is 0 if index is a prime number ' if index is composite then ff(index) contains the index's lowest factor DIM ff(topN + 30) tStart# = TIMER(.001) FOR i = 0 TO topN STEP 30     ff(i + 2) = 2: ff(i + 3) = 3: ff(i + 4) = 2: ff(i + 5) = 5: ff(i + 6) = 2: ff(i + 8) = 2: ff(i + 9) = 3     ff(i + 10) = 2: ff(i + 12) = 2: ff(i + 14) = 2: ff(i + 15) = 3: ff(i + 16) = 2: ff(i + 18) = 2     ff(i + 20) = 2: ff(i + 21) = 3: ff(i + 22) = 2: ff(i + 24) = 2: ff(i + 25) = 5     ff(i + 26) = 2: ff(i + 27) = 3: ff(i + 28) = 2: ff(i + 30) = 2 NEXT ff(2) = 0: ff(3) = 0: ff(5) = 0 'fix first 3 factors FOR pcand = 7 TO testlimitN STEP 2     IF ff(pcand) = 0 THEN         FOR i = pcand * pcand TO topN STEP 2 * pcand             IF ff(i) = 0 THEN ff(i) = pcand         NEXT     END IF NEXT 'count primes FOR i = 2 TO topN     IF ff(i) = 0 THEN p = p + 1 NEXT tStop# = TIMER(.001) tTime# = tStop# - tStart# PRINT "For "; topN; " numbers there are "; p; " primes in "; tTime#; " secs."``` 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 += x owen Registered Offline This member has written at least 130 posts and created at least 13 threads on this forum since joining inMay 2017. 09-17-2017, 12:22 AM owen's deluxe x 2 modified inner loop as well what are the new time comparisons on your computer? Code:```' 30 wheel sieve Owen deluxe.bas for QB64 fork (B+=MGA) 2017-08-30 copy and trans to QB64 'translated from: First Factors.bas for SmallBASIC 11/27/14 (bpf.org post) '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 '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 _DEFINE A-Z AS _INTEGER64 OPTION BASE 1 COMMON SHARED ff(), topN topN = 1223 'first 200 primes test topN = 100000000 testlimitN = SQR(topN) 'First Factors array, ff(index), is 0 if index is a prime number ' if index is composite then ff(index) contains the index's lowest factor DIM ff(topN + 30) tStart# = TIMER(.001) FOR i = 0 TO topN STEP 30     ff(i + 2) = 2: ff(i + 3) = 3: ff(i + 4) = 2: ff(i + 5) = 5: ff(i + 6) = 2: ff(i + 8) = 2: ff(i + 9) = 3     ff(i + 10) = 2: ff(i + 12) = 2: ff(i + 14) = 2: ff(i + 15) = 3: ff(i + 16) = 2: ff(i + 18) = 2     ff(i + 20) = 2: ff(i + 21) = 3: ff(i + 22) = 2: ff(i + 24) = 2: ff(i + 25) = 5     ff(i + 26) = 2: ff(i + 27) = 3: ff(i + 28) = 2: ff(i + 30) = 2 NEXT ff(2) = 0: ff(3) = 0: ff(5) = 0 'fix first 3 factors pattern(1) = 4: pattern(2) = 2: pattern(3) = 4: pattern(4) = 2 pattern(5) = 4: pattern(6) = 6: pattern(7) = 2: pattern(8) = 6 pcand = 7 patternI = 0 WHILE pcand < testlimitN     IF ff(pcand) = 0 THEN         'FOR i = pcand * pcand TO topN STEP 2 * pcand         '    IF ff(i) = 0 THEN ff(i) = pcand         'NEXT         i = pcand * pcand         patternI2 = patternI         DO             IF ff(i) = 0 THEN ff(i) = pcand             patternI2 = patternI2 + 1             IF patternI2 = 9 THEN patternI2 = 1             i = i + pattern(patternI2) * pcand             IF i > topN THEN EXIT DO         LOOP     END IF     patternI = patternI + 1     IF patternI = 9 THEN patternI = 1     pcand = pcand + pattern(patternI) WEND 'count primes FOR i = 2 TO topN     IF ff(i) = 0 THEN p = p + 1 NEXT tStop# = TIMER(.001) tTime# = tStop# - tStart# PRINT "For "; topN; " numbers there are "; p; " primes in "; tTime#; " secs."``` bplus B = B + ... Offline This member has written at least 1,268 posts and created at least 154 threads on this forum since joining inApr 2017. 09-17-2017, 04:15 AM 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 += x owen Registered Offline This member has written at least 130 posts and created at least 13 threads on this forum since joining inMay 2017. 09-17-2017, 05:56 AM This post was last modified: 09-17-2017, 05:57 AM by owen.Edited 0 times 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. bplus B = B + ... Offline This member has written at least 1,268 posts and created at least 154 threads on this forum since joining inApr 2017. 09-17-2017, 06:14 AM 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:```' Twin primes from 30 wheel.bas for QB64 fork (B+=MGA) 2017-09-16 ' I have a theory that most Twin Primes come in form of ' 30n + 11, 30n + 13   call this r11, remainder 11 (and remainder 13) ' 30n + 17, 30n + 19   call this r17, remainder 17 (and remainder 19) ' 30n + 29, 30(n+1) + 1  call this r29, remainder 29 (and remainder 1 that comes after 29) ' call 3, 5 and 5, 7 twins rOther _DEFINE A-Z AS _INTEGER64 'load ff() with first factor data, if ff(i) = 0 then prime OPTION BASE 1 COMMON SHARED ff(), topN topN = 100000000 testlimitN = SQR(topN) DIM ff(topN + 30) FOR i = 0 TO topN STEP 30     ff(i + 2) = 2: ff(i + 3) = 3: ff(i + 4) = 2: ff(i + 5) = 5: ff(i + 6) = 2: ff(i + 8) = 2: ff(i + 9) = 3     ff(i + 10) = 2: ff(i + 12) = 2: ff(i + 14) = 2: ff(i + 15) = 3: ff(i + 16) = 2: ff(i + 18) = 2     ff(i + 20) = 2: ff(i + 21) = 3: ff(i + 22) = 2: ff(i + 24) = 2: ff(i + 25) = 5     ff(i + 26) = 2: ff(i + 27) = 3: ff(i + 28) = 2: ff(i + 30) = 2 NEXT ff(2) = 0: ff(3) = 0: ff(5) = 0 'fix first 3 factors FOR pcand = 7 TO testlimitN STEP 2     IF ff(pcand) = 0 THEN         FOR i = pcand * pcand TO topN STEP 2 * pcand             IF ff(i) = 0 THEN ff(i) = pcand         NEXT     END IF NEXT 'file twin primes data DIM dat\$(1000) OPEN "Twin primes mod 30.txt" FOR OUTPUT AS #1 lastp = -1 FOR i = 2 TO topN     IF ff(i) = 0 THEN         IF i - lastp = 2 THEN             'collect some stats             SELECT CASE (lastp MOD 30)                 CASE 11: r11 = r11 + 1                 CASE 17: r17 = r17 + 1                 CASE 29: r29 = r29 + 1                 CASE ELSE: rOther = rOther + 1             END SELECT             'This is filed already             'PRINT #1, STR\$(lastp) + ", " + STR\$(i) + "   Mod 30: " + STR\$(lastp MOD 30) + ", " + STR\$(i MOD 30)             tCount = tCount + 1         END IF         lastp = i     END IF     IF i MOD 100000 = 0 THEN         dat\$(i \ 100000) = STR\$(i) + ": " + STR\$(r11 - lastr11) + ", " + STR\$(r17 - lastr17) + ", " + STR\$(r29 - lastr29) + ", " + STR\$(rOther - lastrOther)         lastr11 = r11: lastr17 = r17: lastr29 = r29: lastrOther = rOther     END IF NEXT CLOSE #1 PRINT "Found "; tCount; " Twin Primes in first "; topN; " integers." PRINT STR\$(r11) + ", " + STR\$(r17) + ", " + STR\$(r29) + ", " + STR\$(rOther) PRINT dat\$(1) display dat\$() IF 0 THEN     'test some factoring of numbers     factorMe = 10     WHILE factorMe > 1         INPUT "Enter a number to factor, 0 quits "; factorMe         IF factorMe < 2 THEN EXIT WHILE ELSE PRINT factors\$(factorMe)     WEND END IF FUNCTION factors\$ (n)     IF n > topN THEN factors\$ = "Error: too high a number.": EXIT FUNCTION     f\$ = ""     WHILE ff(n) <> 0         f\$ = f\$ + STR\$(ff(n)) + " "         n = n / ff(n)     WEND     factors\$ = f\$ + STR\$(n) END FUNCTION SUB display (arr() AS STRING)     lb = LBOUND(arr): ub = UBOUND(arr)     IF ub - lb + 1 < 21 THEN top = ub ELSE top = lb + 19     CLS: PRINT "press any key to quit scroller..."     LOCATE 2, 1     FOR i = lb TO top         PRINT arr(i)     NEXT     DO         IF ub - lb + 1 > 20 THEN             DO WHILE _MOUSEINPUT                 IF row >= lb THEN row = row + _MOUSEWHEEL ELSE row = lb 'prevent under scrolling                 IF row > ub - 19 THEN row = ub - 19 'prevent over scrolling                 IF prevrow <> row THEN 'look for a change in row value                     IF row >= lb AND row <= ub - 19 THEN                         CLS: PRINT "press any key to quit scroller..."                         LOCATE 2, 1                         FOR n = row TO row + 19                             PRINT arr(n)                         NEXT                     END IF                 END IF                 prevrow = row 'store previous row value             LOOP         END IF     LOOP UNTIL INKEY\$ > "" END SUB``` That doesn't give me any ideas for what's next either but happy to have a way to classify Twins. B += x owen Registered Offline This member has written at least 130 posts and created at least 13 threads on this forum since joining inMay 2017. 09-17-2017, 08:57 AM This post was last modified: 09-17-2017, 08:58 AM by owen.Edited 0 times 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:```            SELECT CASE (lastp MOD 30)                 CASE 11: r11 = r11 + 1                 CASE 17: r17 = r17 + 1                 CASE 29: r29 = r29 + 1                 CASE ELSE: rOther = rOther + 1             END SELECT``` 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. bplus B = B + ... Offline This member has written at least 1,268 posts and created at least 154 threads on this forum since joining inApr 2017. 09-17-2017, 11:30 PM 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 likely-hood of repeating. B += x owen Registered Offline This member has written at least 130 posts and created at least 13 threads on this forum since joining inMay 2017. 09-18-2017, 05:06 AM i think primes (to include twin primes) are the remnants of interwoven waves. http://www.thejoyfulprogrammer.com/qb64/...n=lastpost bplus B = B + ... Offline This member has written at least 1,268 posts and created at least 154 threads on this forum since joining inApr 2017. 09-18-2017, 10:41 AM (09-18-2017, 05:06 AM)owen Wrote: i think primes (to include twin primes) are the remnants of interwoven waves. http://www.thejoyfulprogrammer.com/qb64/...n=lastpost Absolutely! primes are what's left when all the composites (in the area of question) are accounted for. B += x « Next Oldest | Next Newest » 