Mac:
As far as you must use doubles everything will be slow as hell...And victor refuses to add int64 support to fb...However, I suppose you re using one of the floating point patches for qb as ffix, it should triple the speed.
Running your program in the range of the results you posted and with ffix, it outputs a prime every 10-15 seconds in a P4 2,4
For a real fast thing there is the atkin sieve
http://cr.yp.to/primegen.html
that´s the fastest thing i ever saw: calculates primes from 1 to 1e10 in 50 seconds in a Pentium 4 2,4. It's supposed to be prepared for primes up to 1e15
It has only 3 defaults: it's C (gnu), the program has no comments, and the explanation is in an unreadable scientific paper. If FB had int64 i would port it...
To obtain your results, Atkin sieve needed 5 seconds to get the first prime on the list, the others were almost instantaneous...
Code:
7.00 seconds for 279 primes from 912345678901000 to 912345678910000
This is how i found your last result is wrong:
912345678901417 = 935447 x 975304511
see:
http://www.alpertron.com.ar/ECM.HTM
for a fast proof
EDITED: I discovered that result is a typo...your program does'nt give it
/EDITED
I would like to try your code against this one, but i would need to convert it to double, at the moment it stops at 2e9
Code:
'----------------------------------------------------------------------------------
'Prime number generator by Rich Geldreich 1992
'Ported to FB by Antoni Gual 2005
'Method Suggested by D.Knuth in exercise ???? of TAOCP Vol ??
'-Uses a 'sliding window' sieve combined with a priority queue.
'-Skips multiples of 2 and multiples of 3.
'-Builds a compressed list of primes saving the gaps/2, so each
' prime takes only 1 byte in the file.
'-AG modified: Factors waiting to enter the queue are saved in the
' unused part of the array, not in the file as Rich did.
'---------------------------------------------------------------------------------
'#define fileoutput
DEFINT A-Z
option explicit
CONST HeapSize = 9000
#ifdef fileoutput
open "primebuf.bin" for output as #1
close #1
open "primebuf.bin" for binary as #1
#endif
dim dd as byte
DIM SHARED LastPrime&
dim SHARED tt!
dIM HeapQ(1 TO HeapSize) AS LONG
DIM HeapQ1(1 TO HeapSize) AS LONG
DIM HeapQ2(1 TO HeapSize) AS LONG
dim mprime&
DIM SHARED candid AS LONG
DIM t AS LONG
DIM Q AS LONG, Q1 AS LONG, Q2 AS LONG
DIM TQ AS LONG, TQ1 AS LONG
DIM u AS LONG,d as long
dim r as integer,r2 as integer,i as integer, j as integer,cnt%,a as integer, b as integer
dim k$
'Initialize it
Lastprime&=5
CNT=3
d = 4
r = 1
r2=r+1
t=25
HeapQ(1) = 25
HeapQ1(1) = 10
HeapQ2(1) = 30
candid = 7
INPUT "Max prime:"; mprime&
tt! = TIMER
'main loop
DO
'Advance the window making all factors bigger or equal than the candidate
'and sorting them, the smaller first
DO
Q = HeapQ(1)
Q1 = HeapQ1(1)
Q2 = HeapQ2(1)
TQ = Q + Q1
TQ1 = Q2 - Q1
i = 1
DO
j = i shl 1
IF j <= r THEN
IF j < r THEN
IF HeapQ(j) > HeapQ(j + 1) THEN
j = j + 1
END IF
END IF
IF TQ > HeapQ(j) THEN
HeapQ(i) = HeapQ(j)
HeapQ1(i) = HeapQ1(j)
HeapQ2(i) = HeapQ2(j)
i = j
ELSE
EXIT DO
END IF
ELSE
EXIT DO
END IF
LOOP
HeapQ(i) = TQ
HeapQ1(i) = TQ1
HeapQ2(i) = Q2
'***
LOOP UNTIL candid <= Q
'all candidates up to the first factor are primes
DO WHILE candid < Q
' print candid;
dd=(candid-lastprime&) shr 1
#ifdef fileoutput
put #1,,dd
#endif
lastprime&=candid
cnt%=cnt%+1
'if (cnt% and &h1fFFF)=0 then locate 2,1: print cnt%;" primes ";candid
if r2<=Heapsize then
HeapQ(r2)=candid
r2=r2+1
end if
candid = candid + d
d = 6 - d
LOOP
'if candidate equals the square of the biggest factor, add a new factor to the queue
IF candid = t THEN
u = HeapQ(r+1)
t = u * u
'sort it to place
j = r + 1
DO
i = j shr 1
IF i = 0 THEN
EXIT DO
END IF
IF HeapQ(i) <= t THEN
EXIT DO
END IF
HeapQ(j) = HeapQ(i)
HeapQ1(j) = HeapQ1(i)
HeapQ2(j) = HeapQ2(i)
j = i
LOOP
'***
HeapQ(j) = t
IF (u MOD 3) = 2 THEN
HeapQ1(j) = u shl 1
ELSE
HeapQ1(j) = u shl 2
END IF
HeapQ2(j) = 6 * u
r = r + 1
END IF
'go for the first candidate bigger than the factor at the top of the queue
candid = candid + d
d = 6 - d
LOOP until r>= HeapSize or candid > mprime&
#ifdef fileoutput
close #1
#endif
print cnt%;" primes in "; timer-TT! ;" seconds"
sleep
end
