Since there seems to be further interest in this topic, I have posted an improved version of the my previous post. Main improvement is to skip testing even numbers in main loop and to use Repeat...Until instead of For...Next loop. Since the tests discussed in "Dave's Garage" youtube channel are for calculating primes up to one million, I changed program to do this as the default number if you enter zero. Did this 100 times to get meaningful times. On my I3-3240 pc get about 0.38 secs for regular code and 0.134 secs for assembly code. Main advantage of assembly is using R registers for variables.
Regular Code
Code: Select all
Dim Nums.a(0)
Define.l i,l, n, m, limit,limitroot,two_n
If OpenConsole()
; Ask for the limit to search, get that input and allocate a Array
Print("Enter limit for this search: ")
limit = Val(Input())
If limit=0
limit=1000000 ;default if zero input
EndIf
Define StartTime.d = ElapsedMilliseconds()
For i=1 To 100
ReDim Nums(limit) ;Initially set all numbers as prime (=0)
limitroot=Sqr(limit)
; Use a basic Sieve of Eratosthenes
; Mark even numbers, except 2 as not prime
n=4
Repeat
nums(n)+1
n=n+2
Until n>limit
;Sieve rest of the numbers
n=3
Repeat
If Nums(n) = 0 ;Find next prime
m = n * n ;All smaller multiples of n already marked so skip
two_n=n+n
;This loop is where the program spends most of its time
Repeat
Nums(m)+1 ;mark multiples of m as not prime
m = m + two_n ;can skip even multiples of m as already marked
Until m>limit
EndIf
n= n+2 ;skip next number which is even
Until n>limitroot
Next
Define EndTime.d = (ElapsedMilliseconds() - StartTime) / 1000.0
PrintN("It took " + StrD(EndTime) + " seconds to complete.")
Print("Press ENTER to list results. . . ") : Input()
PrintN(#CRLF$ + "The primes up to " + Str(limit) + " are:")
m = 0
For n = 2 To limit
If Nums(n) = #False
;PrintN(Str(n))
m = m + 1
EndIf
Next
PrintN(#CRLF$ + "The number of primes up to " + Str(limit) + " is: "+Str(m))
Dim pcount(20)
For i=0 To 9
If i=0
pcount(i)=pcount(i)-2
EndIf
For j=i*limit/10 To i*limit/10+limit/10-1
If Nums(j) = #False
;PrintN(Str(n))
pcount(i)=pcount(i)+1
EndIf
Next
PrintN("Num Primes from "+Str(i*limit/10)+" To " +Str(i*limit/10+limit/10-1)+" is "+Str(pcount(i)))
Next
Print(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf
Assembly Code
Code: Select all
Dim Nums.b(0)
Define.l i,m,n
If OpenConsole()
; Ask for the limit to search, get that input and allocate a Array
Print("Enter limit for this search: ")
limit = Val(Input())
If limit=0
limit=1000000 ;default if zero input
EndIf
Define StartTime.d = ElapsedMilliseconds()
For i=1 To 100
ReDim Nums(limit)
limitroot=Sqr(limit)
; Use a basic Sieve of Eratosthenes
;Initialize registers
! MOV rbp,qword [a_Nums]
! MOV r8,qword [v_limitroot]
! MOV r9, qword [v_limit]
;n=4
! MOV r11,4
;Repeat
! _Repeat7:
; nums(n)+1
!MOV byte [rbp+r11],1
; n=n+2
!ADD r11,2
; Until n>limit
!CMP r11,r9
!JLE _Repeat7
;n=3
! MOV r11,3
; Repeat
!_Repeat8:
; If Nums(n) = 0
!MOVSX r15,byte [rbp+r11]
!AND r15,r15
!JNE _EndIfxx
; m = n * n
!MOV r10,R11
!IMUL r10,R11
; two_n=n+n
!MOV r13,r11
!ADD r13,r11
;Note the next loop is where the program spends most of its time
;Repeat
!_Repeat11:
; Nums(m)+1
!MOV byte [rbp+r10],1
;m = m + two_n
!ADD r10,r13
;Until m>limit
!CMP r10,r9
!JLE _Repeat11
; EndIf
!_EndIfxx:
; n= n+2
!add r11,2
; Until n>limitroot
! CMP r11,r8
! JLE _Repeat8
!_Until8:
Next
Define EndTime.d = (ElapsedMilliseconds() - StartTime) / 1000.0
PrintN("It took " + StrD(EndTime) + " seconds to complete.")
Print("Press ENTER to list results. . . ") : Input()
PrintN(#CRLF$ + "The primes up to " + Str(limit) + " are:")
m = 0
For n = 2 To limit
If Nums(n) = #False
;PrintN(Str(n))
m = m + 1
EndIf
Next
PrintN(#CRLF$ + "The number of primes up to " + Str(limit) + " is: "+Str(m))
Dim pcount.l(20)
For i=0 To 9
If i=0
pcount(i)=pcount(i)-2
EndIf
For j=i*limit/10 To i*limit/10+limit/10-1
If Nums(j) = #False
;PrintN(Str(n))
pcount(i)=pcount(i)+1
EndIf
Next
PrintN("Num Primes from "+Str(i*limit/10)+" To " +Str(i*limit/10+limit/10-1)+" is "+Str(pcount(i)))
Next
Print(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf