I've got it down to 5m49s now (for the primes up to 10 million) and I'm guessing that's it for straight-up thinBasic.
I removed the need for an SQR in the main calculating loop, replacing it by an addition, a multiplication and a compare (the bit with srt and prd). This is also very useful if (when?) I convert the main loop to assembler. After having done some 330 million numbers the checking runs at some 6,000 numbers per second. Almost another 4 billion numbers to do...
The program is more complicated than it needs to be because it works with a variable number of assumed primes (variable nap). Be careful changing that number of assumed primes because if you do it will delete any work done with another number of assumed primes. Decoding the primes file with a higher number of assumed primes is slower, but you win a lot of memory.
I'm working on an include script that can use/process the file generated with this program. Once that's finished I'll put it in a topic in the math subforum. I will definitely complete the entire 32-bits primes file, possibly with the main bit in assembler. I'll make the primes file (102,976,561 bytes, 98.2 MB) available through P2P (.torrent) then.
'----------------------------------------------------------------------------
' !All32BitPrimes
'
' Create a file with all 32-bit prime numbers.
'
' ©2011 Johannes
'----------------------------------------------------------------------------
Uses "Console","File"
' Number of assumed primes. Must be between 3 and 6.
Word nap = 6
' File name for prime number file.
String fn_primes = APP_SourcePath+"Primes.primes"
' Auto-save interval in seconds.
Quad svi = 60
' Some initialisations.
DoEvents(Off)
PrintL "DETERMINE ALL 32-BIT PRIMES"
PrintL "==========================="
DWord i,j,k,n,nbr
Word srt,prd
Quad che,mxi = 4294967296
HiResTimer_Init
nap=Min(Max(nap,3),6)
' Check work done so far.
If Not FILE_Exists(fn_primes) Then FILE_Save(fn_primes,Chr$(nap))
Integer hnd=FILE_Open(fn_primes,"BINARY")
String chk=FILE_Get(hnd,1)
FILE_Close(hnd)
If chk<>Chr$(nap) Then FILE_Save(fn_primes,Chr$(nap))
' Determine all 16-bit primes using Euler's Sieve.
Print "Determining all 16-bit prime numbers: "
Word sieve(65535)
For i=2 To 65535
sieve(i)=i
Next i
n=65534
For i=2 To 255
If sieve(i) Then
For j=Int(65535/i) To i Step -1
If sieve(j) Then sieve(i*j)=0:n-=1
Next j
EndIf
Next i
Word p16b(n)
j=0
For i=2 To 65535
If sieve(i) Then
j+=1
p16b(j)=sieve(i)
EndIf
Next i
ReDim sieve()
PrintL TStr$(n)+" primes found."
' Print assumed primes and prime storage information.
Print "Working with"+Str$(nap)+" assumed primes:"
Ext fract = 100.0
For i=1 To nap
j=p16b(i)
fract*=(j-1)/j
Print Str$(j)
Next i
PrintL "."
PrintL "Fraction of stored numbers is "+Format$(fract,"0.000")+"%."
' Determine sizes of number block and bit mask.
Word blk,bts,msk = 1
If nap Then
For i=1 To nap
blk*=p16b(i)
bts*=p16b(i)-1
Next i
EndIf
msk=bts/8
' Check number of already considered numbers.
Quad hgh = (FILE_Size(fn_primes)-1)*blk/msk
fract=Min(100,hgh/42949672.96)
Print "Every":If msk>1 Then Print Str$(msk)
Print " byte":If msk>1 Then Print "s"
Print " define":If msk=1 Then Print "s"
PrintL Str$(blk)+" numbers."
PrintL "Total file size for all 32-bit primes is"+Str$(msk*Ceil(mxi/blk)+1)+" bytes."
PrintL "Currently"+Str$(hgh)+" numbers have been considered."
PrintL "Overall progress is "+Format$(fract,"0.000")+"%."
' Check if all work has been done.
If hgh>=mxi Then
PrintL "All 32-bit primes have been determined."
WaitKey
Stop
EndIf
' Construct offset table.
Long ofs(bts)
Boolean prm
k=0
PrintL "Creating offset table ("+TStr$(bts)+" entries)."
For i=1 To blk
prm=TRUE
For j=1 To nap
If Mod(i,p16b(j))=0 Then prm=FALSE:Exit For
Next j
If prm Then k+=1:ofs(k)=i
Next i
' Reserve (a whole lotta) memory for primes list and load existing data.
Byte dta(msk*Ceil(mxi/blk))
If FILE_Size(fn_primes)>1 Then Poke$ VarPtr(dta(1)),Mid$(FILE_Load(fn_primes),2)
' Append 16-bit primes if necessary.
Byte byt
If hgh<65536 Then
PrintL "Appending 16-bit primes."
For i=1 To msk*Ceil(65536/blk)
dta(i)=0
Next i
For i=1 To n
j=Array Scan ofs, =Mod(p16b(i),blk)
If j Then
j-=1
k=msk*Int(p16b(i)/blk)+Int(j/8)+1
j=Mod(j,8)
byt=1
SHIFT LEFT byt,j
dta(k)=(dta(k) Or byt)
EndIf
Next i
hgh=blk*Int(65536/blk)
EndIf
' Main loop for checking successive numbers.
PrintL "Autosaving every"+Str$(svi)+" seconds."
svi*=1000000
Print "Determining further primes"
k=msk*hgh/blk+1
byt=1
Quad ctr
srt=Int(Sqr(hgh))
HiResTimer_Get
While hgh<mxi
For i=1 To bts
che=hgh+ofs(i)
If che>=mxi Then Exit For
nbr=che
If srt<65535 Then
prd=srt+1
If prd*prd<=nbr Then srt=prd
EndIf
prm=TRUE
j=1
While p16b(j)<=srt And j<=n
If Mod(nbr,p16b(j))=0 Then prm=FALSE:Exit While
j+=1
Wend
If prm Then dta(k)=(dta(k) Or byt)
SHIFT LEFT byt,1
If byt=0 Then byt=1:k+=1
Next i
hgh+=blk
ctr+=HiResTimer_Delta
If ctr>=svi Then ctr=0:SavePrimes():Print "."
Wend
PrintL
' Save primes list at program end.
PrintL "Saving primes list."
SavePrimes()
PrintL "All 32-bits primes have been determined."
DoEvents(On)
WaitKey
Sub SavePrimes()
FILE_Save(fn_primes,Chr$(nap)+Peek$(VarPtr(dta(1)),msk*Int(hgh/blk)))
End Sub
Bookmarks