Sieving primes with wheels
#21
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
Reply
#22
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."
Reply
#23
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
Reply
#24
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.
Reply
#25
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 Wink but happy to have a way to classify Twins.
B += x
Reply
#26
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.
Reply
#27
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
Reply
#28
i think primes (to include twin primes) are the remnants of interwoven waves.
http://www.thejoyfulprogrammer.com/qb64/...n=lastpost
Reply
#29
(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
Reply