You are not logged in or registered. Please login or register to use the full functionality of this board...
SIGN IN Join Our Community For FREE


Sieving primes with wheels
09-16-2017, 01:33 AM (This post was last modified: 09-16-2017 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) 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 Snippet: [Select]
' 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 += _
Find all posts by this user
Like Post
09-16-2017, 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) 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."
Find all posts by this user
Like Post
09-16-2017, 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 += _
Find all posts by this user
Like Post
09-16-2017, 03:56 PM (This post was last modified: 09-16-2017 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.
Find all posts by this user
Like Post
09-16-2017, 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) 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 += _
Find all posts by this user
Like Post
09-16-2017, 06:57 PM (This post was last modified: 09-16-2017 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)

                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.
Find all posts by this user
Like Post
09-17-2017, 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 likely-hood of repeating.

B += _
Find all posts by this user
Like Post
09-17-2017, 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
Find all posts by this user
Like Post
09-17-2017, 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.
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 += _
Find all posts by this user
Like Post



Forum Jump:


User(s) browsing this thread: 1 Guest(s)




QB64 Member Project - Martin Fractals version three
QB64 Member Project - 9 Board
QB64 Member Project - Martin Fractals version one
QB64 Member Project - Pivot version two
QB64 Member Project - Qubic
QB64 Member Project - Exit
QB64 Member Project - Splatter
QB64 Member Project - Color Rotating Text
QB64 Member Project - Red Scrolling LED Sign
QB64 Member Project - Dakapo
QB64 Member Project - Blokus
QB64 Member Project - Kobolts Monopoly
QB64 Member Project - OpenGL Triangles
QB64 Member Project - Kings Vallery version two
QB64 Member Project - Full Color LED Sign
QB64 Member Project - Point Blank
QB64 Member Project - Connect Four
QB64 Member Project - Rotating Background
QB64 Member Project - RGB Color Wheel
QB64 Member Project - Algeria Weather
QB64 Member Project - MAPTRIANGLE
QB64 Member Project - Pivet version one
QB64 Member Project - Othello
QB64 Member Project - Sabotage
QB64 Member Project - Kings Court
QB64 Member Project - Spinning Color Wheel
QB64 Member Project - STxAxTIC 3D World
QB64 Member Project - Bowditch curve
QB64 Member Project - Foursight
QB64 Member Project - Amazon
QB64 Member Project - Domain
QB64 Member Project - Color Triangles
QB64 Member Project - Kings Valley verion one
QB64 Member Project - Quarto
QB64 Member Project - Martin Fractals version four
QB64 Member Project - Martin Fractals version two
QB64 Member Project - Overboard
QB64 Member Project - ARB Checkers
QB64 Member Project - Isolation
QB64 Member Project - Score 4
QB64 Member Project - Input
QB64 Member Project - Inside Moves
QB64 Member Project - Rubix's Magic
QB64 Member Project - Dreamy Clock
QB64 Member Project - Touche
QB64 Member Project - Basic Dithering
QB64 Member Project - Spiro Roses
QB64 Member Project - Line Thickness
QB64 Member Project - Swirl