Author Topic: Prime scripting language runoff  (Read 3037 times)

Offline John

  • Forum Support / SB Dev
  • Posts: 2999
    • ScriptBasic Open Source Project
Prime scripting language runoff
« on: December 05, 2013, 03:25:45 PM »
Ed Davis from the BASIC Programming forum started a thread to compare interpreters (scripting languages) with his prime numbers benchmark code. Here is my runs of the popular scripting languages I have installed on my Toshiba Satellite L645-S4104 laptop. (dual core 64 bit running Ubuntu 12.04 LTS)

Note: My focus was to test each scripting language with a script that worked the same way. I acomlished that and the thread continues with improvements to the original presented code. C seems to be the gold standard on Linux and these numbers may not be valid on Windows depending how well the language was ported to that platform. I think this test basically shows which languages does loop structures the best.

Lua

Code: [Select]
local pr = 0
local x, y
for x = 3, 5000000, 2 do
  isprime = true
  for y = 3, math.floor(math.sqrt(x)), 2 do
    if x % y == 0 then
      isprime = false
      break
    end
  end
  if isprime then
    pr = pr + 1
  end
end
print(pr)

jrs@laptop:~/primes$ time lua primes.lua
348512

real  0m13.216s
user  0m13.201s
sys 0m0.000s
jrs@laptop:~/primes$


Euphoria (eui interpreter - while method)

Code: [Select]
integer n, lim, k, p, pc

pc  = 0
n   = 1
lim = 5000000

while n < lim do
    k = 3
    p = 1
    n = n + 2
    while k * k <= n and p do
        p = floor(n / k) * k != n
        k = k + 2
    end while
    if p then
        pc = pc + 1
    end if
end while
? pc

jrs@laptop:~/primes$ time eui primes.eu
348512

real   0m36.817s
user   0m35.314s
sys   0m0.264s
jrs@laptop:~/primes$

Quote from: Tomaaz
I translated my code to Euphoria and it takes... 22 min.

I also tried Tomaaz's FOR/sqrt version for Euphoria and after 5 min. or so I aborted the run. No need to repeat absurdity. To me this is a red flag and should be investigated further. (calling a math library makes Euphoria unusable ???)

Python

Code: [Select]
import math
nop = 0
for x in  range (3, 5000000, 2):
  isprime = 1
  for y in range (3, int(math.sqrt(x)) + 1, 2):
    if x % y == 0:
      isprime = 0
      break
  if isprime == 1:
    nop = nop + 1
print nop

jrs@laptop:~/primes$ time python primes.py
348512

real  1m11.850s
user  1m11.752s
sys 0m0.048s
jrs@laptop:~/primes$


Perl

Code: [Select]
use strict;
use warnings;

my $isprime;
my $nop = 0;
for (my $x = 3; $x < 5000000; $x += 2) {
  $isprime = 1;
  for (my $y = 3; $y <= int(sqrt($x)) + 1; $y += 2) {
    if ($x % $y == 0) {
      $isprime = 0;
      last;
    }
  }
  if ($isprime == 1) {
    $nop++;
  }
}
print "$nop\n";

jrs@laptop:~/primes$ time perl primes.pl
348512

real  2m7.664s
user  2m7.580s
sys 0m0.004s
jrs@laptop:~/primes$


Ruby

Code: [Select]
include Math
nop = 0
for x in (3..5000000).step(2)
  isprime = true
  for y in (3..sqrt(x).floor).step(2)
    if x % y == 0 then
      isprime = false
      break
    end
  end
  if isprime then
    nop = nop + 1
  end
end
puts nop

jrs@laptop:~/primes$ time ruby primes.rb
348512

real  3m22.771s
user  3m22.533s
sys 0m0.008s
jrs@laptop:~/primes$


ScriptBasic (FOR & SQR)

Code: [Select]
nop = 0
for x = 3 to 5000000 step 2
  isprime = 1
  for y = 3 to sqr(x) step 2
    if (x % y = 0) then
      isprime = 0
      goto exit_for
    end if
  next
  exit_for:
  if (isprime = 1) then
    nop = nop + 1
  end if
next
print nop,"\n"

jrs@laptop:~/primes$ time scriba primes.sb
348512

real  3m29.504s
user  3m29.373s
sys 0m0.000s
jrs@laptop:~/primes$


ScriptBasic (WHILE method)

Code: [Select]
pc = 0
n = 1
lim = 5000000

while (n < lim)
  k = 3
  p = 1
  n = n + 2
  while (k * k <= n and p)
    p = int(n / k) * k <> n
    k = k + 2
  wend
  if p then
    pc = pc + 1
  endif
wend
print pc,"\n"

jrs@laptop:~/primes$ time scriba prime_while.sb
348512

real   7m16.211s
user   7m15.903s
sys   0m0.008s
jrs@laptop:~/primes$


C BASIC (FOR & sqrt)

Code: [Select]
#include <stdio.h>
#include <math.h>
#include "cbasic.h"

MAIN
BEGIN_FUNCTION
  DIM AS int nop, x, y, isprime;
  nop = 0;
  FOR (x = 3 TO x <= 5000000 STEP x += 2)
  BEGIN_FOR
    isprime = 1;
    FOR (y = 3 TO y <= sqrt(x) STEP y += 2)
    BEGIN_FOR
      IF (x % y EQ 0) THEN
        isprime = 0;
        break;
      END_IF
    NEXT
    IF (isprime EQ 1) THEN_DO nop += 1;
  NEXT
  PRINT ("%i\n", nop);
  RETURN_FUNCTION(0);
END_FUNCTION

jrs@laptop:~/primes$ gcc -O3 primes_for.c -lm -o p4
jrs@laptop:~/primes$ time ./p4
348512

real   0m1.935s
user   0m1.928s
sys   0m0.000s
jrs@laptop:~/primes$


C BASIC (WHILE method)

Code: [Select]
#include <stdio.h>
#include "cbasic.h"

MAIN
BEGIN_FUNCTION
  DIM AS int n, lim, k, p, pc;
  pc = 0;
  n  = 1;
  lim = 5000000;
  WHILE (n < lim)
  BEGIN_WHILE
    k = 3;
    p = 1;
    n += 2;
    WHILE (k * k <= n AND p)
    BEGIN_WHILE
      p = n / k * k != n;
      k += 2;
    WEND
    IF (p) THEN_DO INCR pc;
  WEND
  PRINT ("%d\n", pc);
  RETURN_FUNCTION(0);
END_FUNCTION

jrs@laptop:~/primes$ time ./cbprimes
348512

real   0m1.904s
user   0m1.900s
sys   0m0.000s
jrs@laptop:~/primes$
« Last Edit: December 08, 2013, 06:00:57 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 781
Re: Prime scripting language runoff
« Reply #1 on: December 06, 2013, 10:52:18 PM »
Code: Python
  1. def isPrime(n):
  2.   if n == 2 or n == 3: return True
  3.   if n < 2 or n%2 == 0: return False
  4.   if n < 9: return True
  5.   if n%3 == 0: return False
  6.   r = int(n**0.5)
  7.   f = 5
  8.   while f <= r:
  9.     if n%f == 0: return False
  10.     if n%(f+2) == 0: return False
  11.     f +=6
  12.   return True
  13.  
  14.  
  15. nop = 0
  16. for x in  range (3, 5000000, 2):
  17.   if isPrime(x):
  18.     nop += 1
  19. print nop

time python p3.py
348512

real   0m34.139s
user   0m34.049s
sys   0m0.088s

Algorithm found at: http://stackoverflow.com/questions/15285534/isprime-function-for-python-language, see second answer for explanation.

The original examples check every number, which the link above explains is not actually required.

A.

Offline John

  • Forum Support / SB Dev
  • Posts: 2999
    • ScriptBasic Open Source Project
Re: Prime scripting language runoff
« Reply #2 on: December 06, 2013, 10:56:29 PM »
As a reference:

jrs@laptop:~/primes$ time python airprimes.py
348512

real   0m37.036s
user   0m36.374s
sys   0m0.212s
jrs@laptop:~/primes$

Offline AIR

  • BASIC Developer
  • Posts: 781
Re: Prime scripting language runoff
« Reply #3 on: December 07, 2013, 10:14:27 AM »
I wanted to see how that prime function would work with MBC, so:

Code: [Select]
$EXECON "-O3"

FUNCTION isPrime(n AS INTEGER) AS BOOL
  DIM r AS INTEGER, f AS INTEGER
  r = SQRT(n)
  f = 5

  IF n = 2 OR n = 3 OR n < 9 THEN FUNCTION = TRUE
  IF  n < 2 OR IMOD(n, 2) = 0 OR IMOD(n, 3) = 0 THEN FUNCTION = FALSE

  WHILE f <= r
    IF IMOD(n, f) = 0 OR IMOD(n, (f+2)) = 0 THEN FUNCTION = FALSE
    f += 6
  WEND

  FUNCTION = TRUE
END FUNCTION


DIM nop AS INTEGER

FOR INTEGER i = 3 TO 5000000 STEP 2
  IF isPrime(i) THEN nop += 1
NEXT

PRINT nop


time ./prime
 348512

real   0m0.847s
user   0m0.843s
sys   0m0.002s

Offline John

  • Forum Support / SB Dev
  • Posts: 2999
    • ScriptBasic Open Source Project
Re: Prime scripting language runoff
« Reply #4 on: December 07, 2013, 10:46:39 AM »
I converted your MBC3 example to C BASIC to see if there was an improvement using your new direction. (140 fewer lines of C code used)

Code: [Select]
#include <stdio.h>
#include <math.h>
#include "cbasic.h"

FUNCTION int isPrime(int n)
BEGIN_FUNCTION
  DIM AS int r, f;
  r = sqrt(n);
  f = 5;
  IF (n EQ 2 OR n EQ 3 OR n < 9) THEN_DO RETURN_FUNCTION(1);
  IF (n < 2 OR n MOD 2 EQ 0 OR n MOD 3 EQ 0) THEN_DO RETURN_FUNCTION(0);
  WHILE (f <= r)
  BEGIN_WHILE
    IF (n MOD f EQ 0 OR n MOD (f + 2) EQ 0) THEN_DO RETURN_FUNCTION(0);
    f += 6;
  WEND
  RETURN_FUNCTION(1);
END_FUNCTION

MAIN
BEGIN_FUNCTION
  DIM AS int nop, i;
  FOR (i = 3 TO i <= 5000000 STEP i += 2)
  BEGIN_FOR
    IF (isPrime(i)) THEN_DO nop += 1;
  NEXT
  PRINT ("%i\n",nop);
  RETURN_FUNCTION(0);
END_FUNCTION

jrs@laptop:~/primes$ time ./mb2cbprimes
348512

real   0m1.303s
user   0m1.268s
sys   0m0.012s
jrs@laptop:~/primes$


MBC3

MBC Version 3.0-Beta1v2.1 (2011/03/11)
MBC3: Based on Linux BCX by Mike Henning (c) 2009
(c) 2009-2011 Armando Rivera with additional code (c) 2009 John Jacques


********************
** 64 BIT VERSION **
********************

[Lines In: 27] [Lines Out: 166] [Statements: 30] [Time: 0 sec's]
BCX translated mbcprimes.bas to mbcprimes.c
Shelling Out To: g++  -Wformat -D_FORTIFY_SOURCE=2 -Wno-write-strings mbcprimes.c -ldl  -O3 -o mbcprimes
jrs@laptop:~/mbc$ time ./mbcprimes
 348512

real   0m1.313s
user   0m1.260s
sys   0m0.020s
jrs@laptop:~/mbc$
« Last Edit: December 07, 2013, 12:15:25 PM by John »