Author Topic: Prime Time  (Read 14934 times)

Offline John

  • Forum Support / SB Dev
  • Posts: 3510
    • ScriptBasic Open Source Project
Prime Time
« on: August 08, 2015, 03:51:26 PM »
Quote from: Tomaaz
Perl. Several times faster than Ruby, but not as easy to read.

Here is a prime example in Perl but run as a Script BASIC Perl extension module function. (primes in one million)

Note: I remarked the printing of each derived prime. This isn't a printing benchmark.

Code: ScriptBasic
  1. DECLARE SUB pl_Init ALIAS "pl_Init" LIB "sbperl"
  2. DECLARE SUB pl_Eval ALIAS "pl_Eval" LIB "sbperl"
  3. DECLARE SUB pl_GetInt ALIAS "pl_GetInt" LIB "sbperl"
  4. DECLARE SUB pl_GetDbl ALIAS "pl_GetDbl" LIB "sbperl"
  5. DECLARE SUB pl_GetStr ALIAS "pl_GetStr" LIB "sbperl"
  6. DECLARE SUB pl_Destroy ALIAS "pl_Destroy" LIB "sbperl"
  7.  
  8. pl_Init
  9.  
  10. pl_code = """
  11. $n = 1000000;
  12. for($i=3;$i<=$n;$i++)
  13. {
  14.    $is_prime = 1;
  15.    for($j=2;$j<=sqrt($i);$j++){
  16.        if($i % $j == 0){
  17.            $is_prime = 0;
  18.            break;
  19.        }
  20.    }
  21. #   if($is_prime == 1) {
  22. #       print $i." ";
  23. #   }
  24. }
  25. print "\n";
  26. """
  27. PRINTNL
  28.  
  29. pl_Eval pl_code
  30.  
  31. pl_Destroy
  32.  


jrs@laptop:~/sb/sb22/test$ time scriba perlprime.sb



real   3m13.416s
user   3m12.710s
sys   0m0.188s
jrs@laptop:~/sb/sb22/test$


Quote from: Tomaaz
Can someone translate my posts to Croatian and then translate Aurel's answer to English?

 :)
« Last Edit: August 08, 2015, 04:12:53 PM by John »

Offline John

  • Forum Support / SB Dev
  • Posts: 3510
    • ScriptBasic Open Source Project
Re: Prime Time
« Reply #1 on: August 08, 2015, 08:30:24 PM »
Here is the Script BASIC native version of finding all the primes from 1 to a million.

Code: ScriptBasic
  1. FOR i = 3 TO 1000000
  2.   is_prime = 1
  3.   FOR j = 2 TO SQR(i)
  4.     IF i % j = 0 THEN
  5.       is_prime = 0
  6.       GOTO Done
  7.     END IF
  8.   NEXT
  9.   Done:
  10.   ' IF is_prime = 1 THEN PRINT i," "
  11. NEXT
  12. PRINTNL
  13.  


jrs@laptop:~/sb/sb22/test$ time scriba pnumsqrt.sb


real   0m40.040s
user   0m39.845s
sys   0m0.051s
jrs@laptop:~/sb/sb22/test$


I would like to see other languages doing the primes to a million challenge. Please post your code.

Mike Lobanovsky

  • Guest
Re: Prime Time
« Reply #2 on: August 09, 2015, 03:26:10 AM »
Hi John,

Printing restored to monitor the consistency of calc results.

Script BASIC code:
Code: ScriptBasic
  1. FOR i = 3 TO 1000000
  2.   is_prime = 1
  3.   FOR j = 2 TO SQR(i)
  4.     IF i % j = 0 THEN
  5.       is_prime = 0
  6.       GOTO Done
  7.     END IF
  8.   NEXT
  9.   Done:
  10.   IF is_prime = 1 THEN PRINT i, "\n"
  11. NEXT
  12. PRINTNL

FBSL code:
Code: Text
  1. #AppType Console
  2. #Option Implicit
  3.  
  4. gtc = GetTickCount()
  5.  
  6. For i = 3 To 1000000
  7.   is_prime = 1
  8.   For j = 2 To SqR(i)
  9.     If i Mod j = 0 Then
  10.       is_prime = 0
  11.       Exit For
  12.     End If
  13.   Next
  14.   If is_prime = 1 Then Print i
  15. Next
  16.  
  17. Print
  18. Print "Uptime: ", (GetTickCount() - gtc) / 1000
  19. Pause

Console output under XP Pro SP3:

Offline John

  • Forum Support / SB Dev
  • Posts: 3510
    • ScriptBasic Open Source Project
Re: Prime Time
« Reply #3 on: August 09, 2015, 01:29:33 PM »
Thanks Mike for the FBSL comparison. Your baby is a screamer.  8)

Offline John

  • Forum Support / SB Dev
  • Posts: 3510
    • ScriptBasic Open Source Project
Re: Prime Time
« Reply #4 on: August 09, 2015, 11:54:55 PM »
Here is the C BASIC version.

Code: C
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include "cbasic.h"
  4.  
  5. MAIN
  6. BEGIN_FUNCTION
  7. DIM AS int is_prime, j, i;
  8.  
  9. DEF_FOR (i = 3 TO i <= 1000000 STEP INCR i)
  10. BEGIN_FOR
  11.   is_prime = 1;
  12.   DEF_FOR (j = 2 TO j <= sqrt(i) STEP INCR j)
  13.   BEGIN_FOR
  14.     IF (i % j EQ 0) THEN
  15.       is_prime = 0;
  16.       EXIT_FOR
  17.     END_IF
  18.   NEXT
  19.   IF (is_prime EQ 1) THEN_DO PRINT ("%i\n",i);
  20. NEXT
  21. END_FUNCTION
  22.  


Offline John

  • Forum Support / SB Dev
  • Posts: 3510
    • ScriptBasic Open Source Project
Re: Prime Time
« Reply #5 on: August 10, 2015, 01:37:27 AM »
Here is the Python version but only to 100000. I thought Perl was slow. I didn't want to burn up my CPU going the whole million.

Code: Python
  1. lower = int(3)
  2. upper = int(100000)
  3.  
  4. for num in range(lower,upper + 1):
  5.    if num > 1:
  6.        for i in range(2,num):
  7.            if (num % i) == 0:
  8.                break
  9.        else:
  10.            print(num)
  11.  
« Last Edit: August 10, 2015, 01:40:12 AM by John »

Mike Lobanovsky

  • Guest
Re: Prime Time
« Reply #6 on: August 10, 2015, 04:01:28 AM »
That's why I'm saying that devil's advocacy for a number of lame non-BASIC "alternatives" so cosily nested and narcissizing quite happily on certain BASIC programming sites in recent times looks like reptiloid conspiracy against common human sense to me, John.

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: Prime Time
« Reply #7 on: August 10, 2015, 06:40:09 PM »
EDIT:  CODE WASN'T ACTUALLY SHOWING ONLY PRIMES

It's the code you wrote, not the language.

Code: [Select]
def primes(n):
""" returns a list of prime numbers from 2 to < n """
if n < 2: return []
if n == 2: return [2]
# do only odd numbers starting at 3
s = range(3, n, 2)
# n**0.5 may be slightly faster than math.sqrt(n)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s[i]:
j = (m * m - 3)//2
s[j] = 0
while j < half:
s[j] = 0
j += m
i = i + 1
m = 2 * i + 3
# make exception for 2
return [2]+[x for x in s if x]

print '-' * 50 # print 50 dashes, cosmetic
num = 1000000
primeList = primes(num)
print "List of prime numbers from 2 to < %d:" % num
print primeList

Without printing:

Quote
[riveraa@Blossom ~] $ time ./primes2.py
--------------------------------------------------
List of prime numbers from 2 to < 1000000:

real   0m0.306s
user   0m0.261s
sys   0m0.033s

With printing:

Quote
99667, 999671, 999683, 999721, 999727, 999749, 999763, 999769, 999773, 999809, 999853, 999863, 999883, 999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]

real   0m0.403s
user   0m0.311s
sys   0m0.038s

Found that function on the net. 

Most so-called benchmarks like this have a fatal flaw:  They don't take into account language contructs/features, and instead try to write the same code for each language tested. 
« Last Edit: August 10, 2015, 07:08:16 PM by AIR »

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: Prime Time
« Reply #8 on: August 10, 2015, 09:59:23 PM »
MBC

Code: [Select]
$EXECON "-O3"
$EXESTRIP


Function IsPrime(Num) AS BOOLEAN
  If Num = 1 OR Num = 2 OR Mod(Num, 2) = 0 Then Function = True
  For INTEGER X = 2 To sqrt(Num)
    If Mod(Num, X) = 0 Then Exit Function
  Next X
  Function = TRUE  ' return true if it's a Prime Number
End Function

DIM ret AS BOOLEAN

For integer A = 1 To 1000000 step 2
  If IsPrime(A) Then Print A
Next

Quote
999931
 999953
 999959
 999961
 999979
 999983

real   0m1.557s
user   0m0.843s
sys   0m0.137s

Mike Lobanovsky

  • Guest
Re: Prime Time
« Reply #9 on: August 11, 2015, 01:24:59 AM »
Hi Armando,

Thank you for sharing the topic though in my opinion,
Quote
... try to write the same code for each language tested ...
is not a drawback, but rather a merit, of synthetic benchmarking. It doesn't really matter if the algo chosen prints primes correctly, it only matters if it prints the exact same results over the entire range of languages to benchmark, which is an indication that all the languages understand and interpret the task in the exact same way. This helps us to evaluate the efficiency of implementation of this or that  feature in a given language, in this particular case, nested For/Next loops and Mod operator. Tweaking the algo with Step to eliminate even numbers or While/Wend in place of For/Next would blur the consistency of benchmarking if done selectively in one language but not in the others. Which clearly rules Python out of the range of instruments preferable for resolving even such a trivial task.

Exactly which MBC results have you submitted BTW? Is it Linux GCC v5.+ -O3 or Mac OSX GCC v4.2.1 -O3?

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: Prime Time
« Reply #10 on: August 11, 2015, 07:05:00 AM »
Which clearly rules Python out of the range of instruments preferable for resolving even such a trivial task.

Well, if you're going to benchmark slow code, then you'll get slow results.

I believe I've shown that your statement above is not correct:  Done properly, Python is actually pretty fast at this task.

Another implementation (from Rosetta):

Code: [Select]
def primes_upto(limit):
    is_prime = [False] * 2 + [True] * (limit - 1)
    for n in xrange(int(limit**0.5)): # stop at ``sqrt(limit)``
        if is_prime[n]:
            for i in xrange(n*n, limit+1, n):
                is_prime[i] = False
    return [i for i, prime in enumerate(is_prime) if prime]
   
print primes_upto(1000000)

Quote
99853, 999863, 999883, 999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]

real   0m0.651s
user   0m0.414s
sys   0m0.043s

Is it technically cheating compared to the other code?  Perhaps.

Does it prove that Python is up to the task.  Definitely.

That is the point I'm making.  :D

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: Prime Time
« Reply #11 on: August 11, 2015, 09:22:33 AM »
Okay, hopefully this satisfies your requirements, Mike:

Code: [Select]
for A in xrange(1, 1000000):
    if A % 2 == 0 and A > 2: continue
    for i in xrange(3, int(A**0.5) + 1):
        if A % i == 0: break
    else: print A

Regarding the MBC version, g++ (clang++) 4.2.1 on MacOS.

AIR.

Offline John

  • Forum Support / SB Dev
  • Posts: 3510
    • ScriptBasic Open Source Project
Re: Prime Time
« Reply #12 on: August 11, 2015, 12:07:24 PM »
Thanks AIR!

This is definitely an improvement. (never heard my CPU fan come on once  :) )

Code: Python
  1. for A in xrange(1, 1000000):
  2.     if A % 2 == 0 and A > 2: continue
  3.     for i in xrange(3, int(A**0.5) + 1):
  4.         if A % i == 0: break
  5.     else: print A
  6.  


   

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: Prime Time
« Reply #13 on: August 11, 2015, 05:43:48 PM »
Cool, glad it works for you without frying your system.  ;D

Here's another approach (it has the dual for-loops, but no MOD/SQR and uses an array - surprised you haven't done something like this in SB yet)

Code: Python
  1. #!/usr/bin/env python
  2.  
  3. size = 1000000
  4. flags = [0]*size
  5.  
  6. for i in xrange( 2, size):
  7.     for k in xrange(i*i, size, i):
  8.         flags[k] = True
  9.     if flags[i] == False: print i
  10.  

I know, not in the spirit of your original post, but just wanted to put it out there...it's a lot faster than what I posted previously:

Quote
999883
999907
999917
999931
999953
999959
999961
999979
999983

real   0m1.639s
user   0m1.307s
sys   0m0.063s

AIR.

Mike Lobanovsky

  • Guest
Re: Prime Time
« Reply #14 on: August 11, 2015, 08:19:25 PM »
Hi Armando,

Okay, hopefully this satisfies your requirements, Mike:

Yes, this code seems to be viable in all the languages in question and it also makes Python a definitive winner in the interpreter race. Unfortunately it does seem to be sort of an overkill for John's SB.

But first things first. In order to have something to lean on against the background of your non-Windows MBC submission, I've cooked up a short C language script and compiled it with a -O3 switch using TDM GCC 4.3.3 (that's the fastest and most compact one I'm usually working with under Windows). Then I benchmarked it in the non-printing and printing modes against the Dynamic C and Dynamic Asm JIT compilers that are built in FBSL alongside its BASIC interpreter. Here are the scripts, and the respective timings can be seen in screenshots 1 and 2 below. Note that I've added the limit variable to compute the pow() limit of inner for() loop only once, because otherwise it'll be recalculated again and again. This however shouldn't be necessary in BASICs because a standard BASIC must do it by definition.

C script:
Code: C
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <windows.h>
  5.  
  6. int main()
  7. {
  8.     int A, i, limit, gtc = GetTickCount();
  9.  
  10.     for (A = 1; A <= 1000000; A++) {
  11.       if (A % 2 == 0 && A > 2) continue;
  12.       limit = pow(A, 0.5) + 1;
  13.       for (i = 3; i <= limit; i++)
  14.         if (A % i == 0) goto iterate;
  15.       // comment this out for non-printable version
  16.       printf("%d\n", A);
  17.       iterate:;
  18.     }
  19.  
  20.     printf("\nUptime: %.3f\n\nPress any key to continue...", (GetTickCount() - gtc) / 1000.0);
  21.     getchar();
  22.     return 0;
  23. }

Dynamic C script:
Code: C
  1. #AppType Console
  2. #Option Implicit
  3.  
  4. gtc = GetTickCount()
  5.  
  6. testC()
  7.  
  8. Print
  9. Print "Uptime: ", (GetTickCount() - gtc) / 1000
  10. Pause
  11.  
  12. DynC testC()
  13.   double pow(double, double);
  14.  
  15.   void main()
  16.   {
  17.     int A, i, limit;
  18.    
  19.     for (A = 1; A <= 1000000; A++) {
  20.       if (A % 2 == 0 && A > 2) continue;
  21.       limit = pow(A, 0.5) + 1; // avoid recalc in each iteration
  22.       for (i = 3; i <= limit; i++)
  23.         if (A % i == 0) goto iterate;
  24.       // comment this out for non-printable version
  25.       printf("%d\n", A);
  26.       iterate:;
  27.     }
  28.   }
  29. End DynC

Dynamic Asm script:
Code: ASM
  1. #AppType Console
  2. #Option Implicit
  3. #DllImports msvcrt
  4.  
  5. gtc = GetTickCount()
  6.  
  7. testA()
  8.  
  9. Print
  10. Print "Uptime: ", (GetTickCount() - gtc) / 1000
  11. Pause
  12.  
  13. DynAsm testA()
  14.   .DATA
  15.   @format DB "%d", &HA, 0
  16.   @divisor DD 2
  17.   @exponent REAL8 0.5
  18.  
  19.   .CODE
  20.   push ebx
  21.  
  22.   mov ecx, 1 ; initialize A
  23.   nop ; 1-byte 1-clock alignment on dword boundary
  24.  
  25.   .While ecx <= 1000000 ; A loop
  26.     mov eax, ecx
  27.     xor edx, edx
  28.     div DWORD PTR [divisor] ; get Mod in edx
  29.     .If edx = 0 .Then
  30.       .If ecx > 2 .Then
  31.         jmp iterate
  32.       .EndIf
  33.     .EndIf
  34.    
  35.     push ecx ; store volatile register
  36.     push [exponent + 4] ; high dword of (double) exponent
  37.     push [exponent] ; low dword of (double) exponent
  38.     push 0 ; make room for high dword of (double) base
  39.     push ecx ; (int) base
  40.     fild DWORD PTR [esp] ; convert in-place to (double) base
  41.     fstp QWORD PTR [esp]
  42.     call pow ; call C function
  43.     add esp, 16 ; CDECL quirk
  44.     pop ecx ; restore volatile register
  45.    
  46.     fistp DWORD PTR [esp - 4]
  47.     mov ebx, [esp - 4]
  48.     inc ebx ; initialize ebx with inner loop limit = pow(A, 0.5) + 1
  49.    
  50.     mov edx, 3 ; initialize i
  51.     mov eax, eax ; 2-byte 1-clock alignment on dword boundary
  52.    
  53.     .While edx <= ebx ; i loop
  54.       push edx ; save temporarily on stack
  55.       push ebx ; ditto
  56.       mov ebx, edx
  57.       xor edx, edx
  58.       mov eax, ecx
  59.       div ebx ; get Mod in edx
  60.       pop ebx ; restore from stack
  61.       .If edx = 0 .Then
  62.         pop edx ; ditto
  63.         jmp iterate
  64.       .EndIf
  65.       pop edx ; ditto
  66.       inc edx
  67.     .WEnd
  68.    
  69.     ; comment this out for non-printable version
  70.     push ecx ; store volatile register
  71.     Invoke printf, format, ecx ; call C function
  72.     add esp, 8 ; CDECL quirk
  73.     pop ecx ; restore volatile register
  74.     nop ; 1-byte 1-clock alignment on dword boundary
  75.    
  76.     @iterate
  77.     inc ecx
  78.   .WEnd
  79.  
  80.   pop ebx
  81.   ret
  82. End DynAsm

The asm code isn't optimized in any particular way to keep closer to BASIC and C and it also uses Windows standard msvcrt.dll C runtime calls for compatibility with the prototype. I wish Charles could find some time to submit his OxygenBasic and assembly JIT versions too.

Then I benchmarked your Python code similarly against FBSL's and SB's BASIC interpreters, which showed that Python is a winner given this particular scripting solution. Here are the scripts, and the corresponding non-printable and printable results are presented in screenshots 3 and 4 below.

Python 2 script:
Code: Python
  1. for A in xrange(1, 1000000):
  2.     if A % 2 == 0 and A > 2: continue
  3.     for i in xrange(3, int(A**0.5) + 1):
  4.         if A % i == 0: break
  5.     # comment this out for non-printable version
  6.     else: print A

FBSL script:
Code: Text
  1. #AppType Console
  2. #Option Implicit
  3.  
  4. gtc = GetTickCount()
  5.  
  6. For A = 1 To 1000000
  7.   If A Mod 2 = 0 And A > 2 Then Continue
  8.   For i = 3 To A ^ 0.5 + 1
  9.     If A Mod i = 0 Then Continue Level 2
  10.   Next
  11.   ' comment this out for non-printable version
  12.   Print A
  13. Next
  14.  
  15. Print
  16. Print "Uptime: ", (GetTickCount() - gtc) / 1000
  17. Pause

Script BASIC script:
Code: ScriptBasic
  1. FOR A = 1 TO 1000000
  2.   IF A % 2 = 0 AND A > 2 THEN GOTO Iterate
  3.   FOR i = 3 TO A ^ 0.5 + 1
  4.     IF A % i = 0 THEN GOTO Iterate
  5.   NEXT
  6.   ' comment this out for non-printable version
  7.  PRINT A, "\n"
  8.   Iterate:
  9. NEXT
  10. PRINTNL