Should we compare ?

[RobbeK]

Hi all,

Maybe something interesting to compare written in different languages (script / p-code / native )  -- execution speed / developing time / is the syntax adaptive , readily capable towards the solution etc ...
(with the abundance of Guru's here, there should be no problem to get a fairly correct answer  ...  )

The exercise (as a benchmark)  : the perfect numbers below 10000 printed with their sums.
A perfect number is such that it is the same as the sum of its dividers (1 always included)
so :  6 is perfect because = 1 + 2 + 3
(for the moment maybe less than 50 perfect numbers are known )
The code should go by Brute Force (and including scanning the odd numbers (no odd perfect number is known, but it is not proven they do not exist --   so no "step 2") )   --  no Mersenne number tricks , just brute force ...

Running on an old computer it took almost 8 sec in NewLisp (script).
I'll port to CLisp (p-code) , Steel Bank CL (native) , Haskell (Glasgow Haskell Compiler) and tB script [opt + O2], FreeBasic ..

(took less than 10' to write/test/eval in NewLisp )


best Rob




.

[Aurel]

Why this code is not written in Oxygen
Someone might think that this forum is new forum for Lisp 

[JRS]

Ubuntu 12.04 LTS 64 bit Script BASIC 2.2

Code: [Select]

FUNCTION perf(n)
  sum = 0
  FOR i = 1 TO n - 1
    IF n % i = 0 THEN
      sum = sum + i
    END IF
  NEXT i
  IF sum = n THEN
    perf = 1
  ELSE
    perf = 0
  END IF
END FUNCTION

FOR n = 2 TO 10000 STEP 2
  IF perf(n) THEN PRINT n,"\n"
NEXT

jrs@laptop:~/sb/sb22/test$ time scriba perfnum.sb
6
28
496
8128

real   0m15.891s
user   0m15.873s
sys   0m0.004s
jrs@laptop:~/sb/sb22/test$

... so no "step 2"

jrs@laptop:~/sb/sb22/test$ time scriba perfnum.sb
6
28
496
8128

real   0m31.748s
user   0m31.706s
sys   0m0.004s
jrs@laptop:~/sb/sb22/test$

[JRS]

C BASIC Ubuntu 64 bit

Code: [Select]

#include <stdio.h>
#include "cbasic.h"

MAIN
BEGIN_FUNCTION
  DIM AS int i, n, sum;
  DEF_FOR (n = 1 TO n <= 10000 STEP INCR n)
  BEGIN_FOR
    sum = 0;
    DEF_FOR (i = 1 TO i <= n-1 STEP INCR i)
    BEGIN_FOR
      IF (n MOD i EQ 0) THEN_DO sum = sum + i;
    NEXT
    IF (sum EQ n) THEN_DO PRINT ("%i\n", n);
  NEXT 
  RETURN_FUNCTION(0);
END_FUNCTION

jrs@laptop:~/C_BASIC/bench$ time ./perfnum
6
28
496
8128

real   0m0.261s
user   0m0.256s
sys   0m0.000s
jrs@laptop:~/C_BASIC/bench$

Here is the same C BASIC programming running on Koding.com.

scriptbasic@vm-0:~/Applications/C_BASIC$ time ./perfnum
6
28
496
8128
 
real    0m0.317s
user    0m0.311s
sys     0m0.004s
scriptbasic@vm-0:~/Applications/C_BASIC$ 

[Mike Lobanovsky]

Hi John,

Your equivalent code doesn't correspond to the original Lisp in full. You will get more overhead storing individual i's into a list or array and printing them out later on as summands.

Let me have a good sleep and then I'll try my hand at FBSL's BASIC, DynAsm, and DynC.

(Aurel, isn't this an Open Forum board, after all?)

[Aurel]

(Aurel, isn't this an Open Forum board, after all?)

Yes Mike it is.That is why i am so nice..
And i don't have nothing against Rob posting about lisp..it is somehow funny.

BUT why ?
I am wondering why some people on BASIC-s forums like to post about some other languages
I have never seen on this forums any post about BASIC .
If i see that would be not in a positive light and that is a truth.

[JRS]

Aurel,

This is an open source BASIC compiler project. Charles is trying new things and improving on others. Seeing how other languages might do something better gives Charles more options to refine his BASIC.

[Charles Pegge]

I think the most efficient way to build the factor lists, is to restrict them to proven perfect numbers.

Thus:

Code: [Select]

'OxygenBasic

include "$/inc/console.inc"

function perf(sys n) as sys
  sum = 0
  for i = 2 to <n
    if mod(n,i) = 0
      sum += i
    end if
  next
  if sum = n-1 'PERFECT NUMBER
    ls=n ":" tab "1"
    for i = 2 to <n
      if mod(n,i) = 0
        ls+=" "+i
      end if
    next
    printl ls
    return n
  end if
end function

for n = 2 to 10000
  perf(n)
next

printl "done"
waitkey


[RobbeK]

Thank you all !!

Aurel : "I am wondering why some people on BASIC-s forums like to post about some other languages"  -- imho , O2 is an embeddable (and dll - capable) language , not ?  & that's the way I use it (all the time, in every time-critical application ). However, to have an idea about the gain I try every combination  and starting from "zero oxygen" -- other languages like Python, Ruby etc.. already mix Lisp-like mechanisms (lists, tuples , variadic arguments, etc .. ) ; while it is imo certainly correct that Basic is one of the most underestimated  languages (with on top a "cinderella treatment/respect" from academici , it will not hurt to pick up some ideas.
On the Lisp side the situation at this moment is such, that there are a lot of "mastodon" packages -- Mbytes in size, which are easy replaced by some oxygen code of 10-30 Kb in size.  (they even will run faster ).  (there are some other serious problems making stand-alones from these mega-packages btw ).

-- 
Factoring out the divider-extraction (and calculating their sum) by O2 delivers not much gain ...  7.5sec   (attached)
more oxygen is needed  (too many calls - main iteration loop should be inside the DLL - maybe better working in pieces with a static counter ? )

.

[Charles Pegge]

This particular task, is not kind to Lisp, or  any other interpreter. It is one of those problems which require a dose of Assembler. only the the central iteration requires strong optimisation. It is simple enough to perform entirely inside the CPU, using registers only.

Code: [Select]

'OxygenBasic

include "$/inc/console.inc"

function perf(sys n) as sys
  sum = 0
  i   = 2
  mov ecx,n
  sub ecx,2
  mov edi,i
  mov esi,sum
  (
    (
      mov eax,n
      mov edx,0
      div edi
      cmp edx,0
      jnz exit
      add esi,edi
    )
    inc edi
    dec ecx
    jg repeat
  )
  mov sum,esi
  'for i = 2 to <n
  '  if mod(n,i) = 0
  '    sum += i
  '  end if
  'next
  if sum = n-1 'PERFECT NUMBER
    ls=n ":" tab "1"
    for i = 2 to <n
      if mod(n,i) = 0
        ls+=" "+i
      end if
    next
    printl ls
    return n
  end if
end function

for n = 2 to 10000
  perf(n)
next

printl "done"
waitkey


[RobbeK]

Thanks Charles ( from the past I remember FORTH which was very fast doing such things .. but the language seems vanished ?!)

That's seriously fast, John ... maybe you can reach the 5th perfect number within hours(?)  it's somewhere between 33 000 000 and 34 000 000  (iirc).

The other languages tested are :  (on a slow computer)
CLisp interpreted 57sec - compiled 5 sec (but these are big (unlimited) integers )
Racket Scheme 6 sec (bytecode + GNU lightning JIT)
Steel Bank Common Lisp (native x86)  1 sec
thinBasic script 28 sec
the fastest I get :  thinBasic  O2 (however, O2 checks the condition and tB builds the output - O2 runs till a perfect number is found, tB prints and O2 is called again .., so almost all iterations  , be it interupted a few times are done in oxygen )    pre-JIT  (the O2 function are built on forehand )

;----------------------------------

' Empty thinBasic CONSOLE file template

Uses "Console"  , "oxygen"

Dim As Long pnext
Dim As Long pFinish 
Dim t As Long
Dim src As String



src="
  Function nextperfect( Long a, Long b) As Long  link #pnext
   dim i , j , sumdiv as long
   for i=a to b 
      sumdiv=0
      for j=1 to i/2
        if mod(i,j) = 0 then
          sumdiv += j
        end if
      next
      if sumdiv = i then
        return i
      endif
   next         
  End Function

  Sub finish() link #pFinish
  terminate
  End Sub
"


   

O2_Basic src
If O2_Error Then
  MsgBox 0,O2_Error
  Stop
Else
  O2_Exec
End If

Declare Function nextperfect(ByVal a As Long, ByVal b As Long) As Long At pnext
Declare Sub Finish() At pFinish


 
 

         
Function printperfect ( n As Long )
 Dim i As Long
 For i = n/2 To 2 Step -1
   If Mod(n,i)=0 Then
     Print Str$(i) & "+"
   EndIf
 Next
 PrintL " 1 "
End Function


Function findthenumbers ( x As Long)
 Dim i , n As Long
 i=1
   Do 
    n=nextperfect(i,x)
    If n=0 Then Exit Do
    Print Str$(n) & "="
    printperfect(n)
    i=n+1
   Loop 
   
End Function
   
 
PrintL "Perfect numbers tB+O2"
PrintL "=====================" & $CRLF
 

t=GetTickCount
findthenumbers(10000)
PrintL
PrintL Str$(GetTickCount -t ) & " mSec"
finish()
WaitKey

;-----------------------------------------------------------

around 0.55 sec (an up-to-date computer could be +1.5x faster? ).
The code is not similar with the Lisp memory manipulations - I have an idea how to do it with dynamic arrays , but I don't think it makes any sense. (?)

best, Rob






.

[JRS]

but I don't think it makes any sense. (?)

Once you know what the perfect number is, extracting the values that make it perfect shouldn't be the focus of the task. I think we have enough flawed numbers roaming around, we don't need to exacerbate it.

[RobbeK]

Yep, John

However, suddenly I realised I overlooked something extremely obvious :
If we have one divisor, we automatically have the other - (if a divides N then then obviously N/a is another one ) ;
while this speeds things up twice , there something much more important , we only have to look for numbers till squareroot (N).

And in the Scheme I worked with Lists i.o. streams , that's another 2x slow down --   

- got it under  0.1 sec using bytecode + JIT , should be a lot faster on your C Basic ...

best Rob

[JRS]

Great!

Can you repost my C BASIC code with your discovery?

[RobbeK]

Sure,

Is that C-Basic downloadable somewhere, so I can (run this code)/test  it .
The gain is enormous - for N=10000 only 100 numbers have to be scanned - what I overlooked is that in this specific case :
a*b=10000 , either a or b is < than 101 , and  (call this number a)  then b = 10000/a.
In the attached file I don't start with 1 because then N will be a divisor , as 1 is always a divisor I can do this in general , but I have to compare the divSum with N-1  (it's all marked)

best Rob  -- the 46 mSec includes the printing to console and a tB do..loop (however, the code runs it only 4 times )

.