12-09-2004, 02:59 AM
I have tested this old prime number generator, by Rich Geldreich.
Uses a priority queue instead of a sieve.All integer...
Timings for primes from 2 to 100,000,000
The original QB version used a buffer to write to file.
The buffer is not present in the FB and DEV C versions.
Is FreeBasic slower than QB when graphics are not involved?
This is the FB source.
Uses a priority queue instead of a sieve.All integer...
Timings for primes from 2 to 100,000,000
Code:
Freebasic 730 sec
QB4.5 191 sec
DevC++4.01 12 secThe original QB version used a buffer to write to file.
The buffer is not present in the FB and DEV C versions.
Is FreeBasic slower than QB when graphics are not involved?
This is the FB source.
Code:
'Prime number generator
DEFINT A-Z
option explicit
DECLARE SUB PutPrime (a&)
CONST HeapSize = 9000
OPEN "primebuf.bin" FOR OUTPUT AS #1: CLOSE #1
OPEN "primebuf.bin" FOR BINARY AS #1
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$
Lastprime&=5
candid = 7
CNT=3
d = 4
r = 1
r2=r+1
t=25
HeapQ(1) = 25
HeapQ1(1) = 10
HeapQ2(1) = 30
tt! = TIMER
INPUT "Max prime:"; mprime&
DO
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
DO WHILE candid < Q
' print candid;
dd=(candid-lastprime&) shr 1
put #1,,dd
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 candid = t THEN
u = HeapQ(r+1)
t = u * u
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
candid = candid + d
d = 6 - d
LOOP until r>= HeapSize or LEN(INKEY$)>0 or candid > mprime&
print cnt%;" primes in "; timer-TT! ;" seconds"
close #1
OPEN "primebuf.bin" FOR BINARY AS #1
k$=input$(1)
cls
locate 1,2:print "2"
locate 1,12:print "3"
locate 1,22:print "5"
lastprime&=5
cnt%=3
while not eof(1)
get #1,,dd
candid=lastprime&+(dd shl 1)
I=1+(cnt%\8)
j=1+10*(cnt% mod 8)
locate i,j
print candid,
lastprime&=candid
cnt%=cnt%+1
if cnt%=200 then cnt%=0
wend
close #1
k$=input$(1)
end