User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sun Jun 16, 2019 12:21 am

AIR@AllBasic wrote: I was wondering how porting the fib2 function I posted previously to a more native SB code base would look/work:

Code: Select all

IMPORT gmp2.bas

count = 4784969

a = 1
b = 0
p = 0
q = 1

WHILE count > 0
    IF (count % 2) = 0 THEN
        psq   = gmp2::mul(p, p)
        qsq   = gmp2::mul(q, q)
        twopq = gmp2::mul(p, q)
        twopq = gmp2::mul_si(twopq, 2)
        p     = gmp2::add(psq, qsq)
        q     = gmp2::add(twopq, qsq)
        count = count / 2
    ELSE
        bq    = gmp2::mul(b, q)
        aq    = gmp2::mul(a, q)
        ap    = gmp2::mul(a, p)
        bp    = gmp2::mul(b, p)
        a     = gmp2::add(bq, aq)
        a     = gmp2::add(a, ap)
        b     = gmp2::add(bp, aq)
        count = count - 1
    END IF
WEND
PRINT b,"\n"

On my RasPi:

Code: Select all

riveraa@dpi:~/sb $ time ./AppRun newfib.sb >fib.txt

real    0m38.965s
user    0m38.733s
sys    0m0.224s

On my Mac Mini:
riveraa@mini ~/sb] $ time ./AppRun newfib.sb >fib.txt

real    0m3.159s
user    0m3.094s
sys    0m0.051s
Module Source:

Code: Select all

/*
READ THIS FILE AND CHANGE THE SOURCE WHEREVER YOU SEE COMMENTS STARTING
WITH THE WORD *TODO*

WHEN YOU ARE FINISHED YOU CAN

  FILE   : interface.c
  HEADER : interface.h
  BAS    : gmp2.bas
  AUTHOR : *TODO*

  DATE:

  CONTENT:
  This is the interface.c file for the ScriptBasic module gmp2
----------------------------------------------------------------------------

Remove the two characters // from following line(s) if this module is supposed to
be compiled under specific OS's. If there is a need for some library to successfully
compile the module under Windows specify the names of the libraries on the line
as it is listed for the linker application. This is usually something like

WINDOWS: libname1.lib libname2.lib ... libnameX.lib
LINUX/MACOS: -lm -ldl

If there are no libraries, but still the module is to be compiled under Windows
do remove the // characters so that the program setup.pl will know that the
module is meant for Windows.

//NTLIBS:
UXLIBS: -lgmp
DWLIBS: -lgmp -macosx_version_min 10.12

*/

/*
*TODO*
INCLUDE HERE THE SYSTEM HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
*/

#ifdef WIN32
/*
*TODO*
INCLUDE HERE THE WIN32 SPECIFIC HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
*/
#else
/*
*TODO*
INCLUDE HERE THE UNIX SPECIFIC HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
*/
#endif

/*
*TODO*
INCLUDE HERE THE LOCAL HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../../basext.h"
#include <gmp.h>

/*
*TODO*
INSERT THE BASIC CODE THAT WILL GET INTO THE FILE gmp2.BAS
AFTER THE LINE 'TO_BAS:' AND BEFORE THE LINE END OF THE COMMENT

NOTE THAT SUB AND COMMAND DECLARATIONS ARE CREATED AUTOMATICALLY
FROM THE FUNCTION DEFINTIONS WHEN THE MODULE IS CONFIGURED BEFORE
COMPILATION

TO_BAS:
*/

/*
*TODO*
DECLARE HERE THE MODULE OBJECT TYPE. THIS STRUCTURE SHOULD HOLD THE
DATA AVAILABLE FOR EACH INTERPRETER THREAD. USE THIS STRUCTURE TO
STORE GLOBAL VALUES INSTEAD OF USING GLOBAL VARIABLES.
*/
typedef struct _ModuleObject {
  char a; /* You may delete this. It is here to make the initial interface.c compilable. */
  }ModuleObject,*pModuleObject;

mpz_t g_Op1, g_Op2, g_Res;

/*
*TODO*
ALTER THE VERSION NEGOTIATION CODE IF YOU NEED
*/
besVERSION_NEGOTIATE
  return (int)INTERFACE_VERSION;
besEND

/*
*TODO*
ALTER THE ERROR MESSAGE FUNCTION
*/
besSUB_ERRMSG

  switch( iError ){
    case 0x00080000: return "ERROR HAS HAPPENED";
    }
  return "Unknown gmp2 module error.";
besEND

/*
*TODO*
ALTER THE MODULE INITIALIZATION CODE
*/
besSUB_START
  pModuleObject p;

  besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  if( besMODULEPOINTER == NULL )return 0;

  mpz_init(g_Op1);
  mpz_init(g_Op2);
  mpz_init(g_Res);

/*
*TODO*
INSERT HERE ANY CODE THAT YOU NEED TO INITIALIZE THE MODULE FOR THE
ACTUAL INTERPRETER THREAD
*/

besEND

/*
*TODO*
ALTER THE MODULE FINISH CODE IF NEEDED
*/
besSUB_FINISH
  pModuleObject p;

  /*
    YOU CERTAINLY NEED THIS POINTER TO FREE ALL RESOURCES THAT YOU ALLOCATED
    YOU NEED NOT CALL besFREE TO FREE THE MEMORY ALLOCATED USING besALLOC
    CLOSE ANY FILE THAT REMAINED OPEN, RELEASE DATABASE HANDLES AND ALL
    OTHER RESOURCES INCLUDING MEMORY *NOT* ALLOCATED CALLING besALLOC
  */
  p = (pModuleObject)besMODULEPOINTER;
  if( p == NULL )return 0;

  return 0;
besEND


/*
*TODO*
WRITE YOUR MODULE INTERFACE FUNCTIONS FOLLOWING THIS SKELETON

NOTE THAT THIS IS A SAMPLE FUNCTION, YOU CAN ALSO DELETE
LINES FROM IT IF NEEDED
*/
/**
=section mpz
=H mpz

Returns new mpz_t object
*/
besFUNCTION(mpz)
  pModuleObject p;
  mpz_t r;

  p = (pModuleObject)besMODULEPOINTER;

  // besARGUMENTS("i[s]")
  //   &r
  // besARGEND

  besRETURN_POINTER(r);
besEND

/**
=section init
=H mpz

Initializes mpz_t object
*/
besFUNCTION(init)
  pModuleObject p;
  mpz_t r;
  char * res;

  p = (pModuleObject)besMODULEPOINTER;

  // besARGUMENTS("p")
  //   &r
  // besARGEND

  mpz_init(r);
  res = mpz_get_str(NULL,10,r);
  besSET_RETURN_STRING(res);
  free(res);

  besRETURN_POINTER(r);
besEND


/**
=section init_set
=H mpz

Initializes mpz_t object
*/
besFUNCTION(init_set)
  pModuleObject p;
  char *s, *res;
  int i;

  p = (pModuleObject)besMODULEPOINTER;

  besARGUMENTS("z")
    &s
  besARGEND

  // mpz_set_str(g_Op1, s, 10);
  mpz_init_set_str(g_Res,s,10);
  res = mpz_get_str(NULL,10,g_Res);
  besSET_RETURN_STRING(res);
  free(res);
besEND

/**
=section mul
=H mpz

Multiplies mpz_t objects
*/
besFUNCTION(mul)
  pModuleObject p;
  char *s, *t, *res;
  int i;

  p = (pModuleObject)besMODULEPOINTER;

  besARGUMENTS("zz")
    &s,&t
  besARGEND

 mpz_set_str(g_Op1, s, 10);
 mpz_set_str(g_Op2, t, 10);
  mpz_mul(g_Res, g_Op1, g_Op2);
  res = mpz_get_str(NULL,10,g_Res);
  besSET_RETURN_STRING(res);
  free(res);
besEND


/**
=section mul_si
=H mpz

Multiplies mpz_t objects
*/
besFUNCTION(mul_si)
  pModuleObject p;
  char *s,*res;
  long i;

  p = (pModuleObject)besMODULEPOINTER;

  besARGUMENTS("zi")
    &s,&i
  besARGEND

  mpz_set_str(g_Op1, s, 10);
  mpz_mul_si(g_Res, g_Op1, i);

  res = mpz_get_str(NULL,10,g_Res);
  besSET_RETURN_STRING(res);
  free(res);
besEND


/**
=section add
=H add

Adds mpz_t objects
*/
besFUNCTION(add)
  pModuleObject p;
  char *s, *t, *res;

  int i;

  p = (pModuleObject)besMODULEPOINTER;

  besARGUMENTS("zz")
    &s,&t
  besARGEND

  mpz_set_str(g_Op1, s, 10);
  mpz_set_str(g_Op2, t, 10);
  mpz_add(g_Res, g_Op1, g_Op2);

  res = mpz_get_str(NULL,10,g_Res);
  besSET_RETURN_STRING(res);
  free(res);
besEND


/**
=section test
=H add

Adds mpz_t objects
*/
besFUNCTION(test)
  pModuleObject p;
  mpz_t r, s, t;
  int i;

  p = (pModuleObject)besMODULEPOINTER;

  // besARGUMENTS("ppp")
  //   &r,&s,&t
  // besARGEND

  // mpz_add(r, s, t);
  i=12345;

  besRETURN_LONG(i);
besEND

/**
=section get_string
=H add

Adds mpz_t objects
*/
besFUNCTION(get_string)
  pModuleObject p;
  mpz_t r, s, t;
  int i;
  char * retstring;

  p = (pModuleObject)besMODULEPOINTER;

  besARGUMENTS("p")
    &r
  besARGEND

  retstring = mpz_get_str(0,10,r);

  besSET_RETURN_STRING(retstring);
  free(retstring);
besEND

/*
*TODO*
INSERT HERE THE NAME OF THE FUNCTION AND THE FUNCTION INTO THE
TABLE. THIS TABLE IS USED TO FIND THE FUNCTIONS WHEN THE MODULE
INTERFACE FILE IS COMPILED.
*/

SLFST GMP2_SLFST[] ={

{ "versmodu" , versmodu },
{ "bootmodu" , bootmodu },
{ "finimodu" , finimodu },
{ "emsgmodu" , emsgmodu },
{ "mpz" , mpz },
{ "init" , init },
{ "init_set" , init_set },
{ "mul" , mul },
{ "mul_si" , mul_si },
{ "add" , add },
{ "get_string" , get_string },
{ NULL , NULL }
  };
  
AIR.
@Heater,

You're looking at the official ScriptBasic GMP extension module. (with a couple TODO functions to add)
Last edited by John_Spikowski on Sun Jun 16, 2019 5:04 am, edited 2 times in total.

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sun Jun 16, 2019 1:11 am

ScriptBasic has joined the under 5 seconds club. This is a huge difference from Heaters recursive code. Lets call this the wiz kid fibo. 8-)

Amazing journey. From an hour and 15 minutes to under 5 seconds. It doesn't get much better than that.

Code: Select all

jrs@jrs-laptop:~/sb/GMP$ time scriba gmp2fibo.sb > fibo2.out

real	0m4.785s
user	0m4.738s
sys	0m0.032s
jrs@jrs-laptop:~/sb/GMP$ ls -l fibo2.out
-rw-r--r-- 1 jrs jrs 1000001 Jun 15 18:05 fibo2.out
jrs@jrs-laptop:~/sb/GMP$ tail -c64 fibo2.out
330930391815964864885353407167474856539211500699706378405156269
jrs@jrs-laptop:~/sb/GMP$ 

Code: Select all

IMPORT gmp2.bas

count = 4784969

a = 1
b = 0
p = 0
q = 1

WHILE count > 0
    IF (count % 2) = 0 THEN
        psq   = gmp2::mul(p, p)
        qsq   = gmp2::mul(q, q)
        twopq = gmp2::mul(p, q)
        twopq = gmp2::mul_si(twopq, 2)
        p     = gmp2::add(psq, qsq)
        q     = gmp2::add(twopq, qsq)
        count = count / 2
    ELSE
        bq    = gmp2::mul(b, q)
        aq    = gmp2::mul(a, q)
        ap    = gmp2::mul(a, p)
        bp    = gmp2::mul(b, p)
        a     = gmp2::add(bq, aq)
        a     = gmp2::add(a, ap)
        b     = gmp2::add(bp, aq)
        count = count - 1
    END IF
WEND
PRINT b,"\n"
There isn't much difference if I just print the length of the result rather than output the million characters to a file.

Code: Select all

jrs@jrs-laptop:~/sb/GMP$ time scriba 1milfibo.sb
1000000

real	0m4.717s
user	0m4.684s
sys	0m0.028s
jrs@jrs-laptop:~/sb/GMP$ 
Last edited by John_Spikowski on Sun Jun 16, 2019 7:02 am, edited 4 times in total.

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sun Jun 16, 2019 2:12 am

Heater,

AIR added subtraction and divide to the GMP2 official extension module and pushed it to the ScriptBasic repo.

Code: Select all

Import gmp2.bas

a = gmp2::sub(1000000,500000)

print a,"\n"

b = gmp2::divide(a,5)

print b,"\n"

[riveraa@mini ~/sb] $ ./sb math.sb
500000
100000
We did our part to meet your requirements so can you push the ScriptBasic submission to the Fibo challenge repo?

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Sun Jun 16, 2019 9:06 am

Edit: Content deleted.

Moved to the ScriptBasic thread so as to avoid clutter here.
Memory in C++ is a leaky abstraction .

ejolson
Posts: 3838
Joined: Tue Mar 18, 2014 11:47 am

A New Fidonacci Challenge

Sun Jun 16, 2019 3:19 pm

Heater wrote:
Sat Jun 15, 2019 6:25 pm
ejolson,
While real-world experience may suggest otherwise, mathematically, if your breeding experiment starts with zero pairs of rabbits, then no baby rabbits will ever be produced.
But, but, the resolution of that apparent paradox is in the very description of the rabbit breading experiment you quoted above.
The primary developer of FidoBasic seems very excited about the idea of a rabbit breading experiment. According to Fido, rabbits don't live forever and are actually quite tasty after three months, even when not breaded. If only they weren't so difficult to catch.

The Fidonacci numbers describe how many pairs of rabbits remain in the field under the assumption adult rabbits are eaten after three months rather than living forever. The resulting Fidonacci challenge is to compute the first such number that has a million digits or show such a number doesn't exist.

According to the list of features, one of the important advantages that FidoBasic has over LOLCAT-based programming languages is a built-in fido(n) function for computing the n-th Fidonacci number.
Last edited by ejolson on Sun Jul 14, 2019 7:08 pm, edited 2 times in total.

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sun Jun 16, 2019 8:47 pm

Heater got ScriptBasic and the GMP2 extension module running on his PC. I hope he will return with his findings.

Other good news is AIR join the forum. Now you have 2 ScriptBasic resoucecs to answer your questions.

Even more good news is AIR switched the cleanup and MASTER repos. Let us know what is left to get ScriptBasic's submission in the repo.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Sun Jun 16, 2019 11:47 pm

Luckily you mean "merged the clean up branch into the master branch"

Switching them around would be chaotic and nuts.
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sun Jun 16, 2019 11:55 pm

Disclaimer:

I'm as green as a bean when it comes to git. That is why we have a sandbox so I don't hurt anyone. :D

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 7:04 am

I converted Heater's hfibo.sb to use AIR's gmp2 extension module.

Heater (hfibo.sb)

Code: Select all

IMPORT gmp2.bas

function hfibo(n)
local a, b, fk, fk1, k, r
SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1
  if n <= 2 THEN
    r = 1
  else
    k = (n / 2) OR 0
    fk = hfibo(k)
    fk1 = hfibo(k + 1)
    if (n and 1) = 0 then
      a = gmp2::add(fk1, fk1)
      b = gmp2::sub(a, fk)
      r = gmp2::mul(fk, b)
    else
      a = gmp2::mul(fk, fk)
      b = gmp2::mul(fk1, fk1)
      r = gmp2::add(a, b)
    end if
  end if
  hfibo = r
end function

PRINT LEN(hfibo(4784969)),"\n"
AIR (1milfibo.sb)

Code: Select all

IMPORT gmp2.bas

count = 4784969

a = 1
b = 0
p = 0
q = 1

WHILE count > 0
    IF (count % 2) = 0 THEN
        psq   = gmp2::mul(p, p)
        qsq   = gmp2::mul(q, q)
        twopq = gmp2::mul(p, q)
        twopq = gmp2::mul_si(twopq, 2)
        p     = gmp2::add(psq, qsq)
        q     = gmp2::add(twopq, qsq)
        count = count / 2
    ELSE
        bq    = gmp2::mul(b, q)
        aq    = gmp2::mul(a, q)
        ap    = gmp2::mul(a, p)
        bp    = gmp2::mul(b, p)
        a     = gmp2::add(bq, aq)
        a     = gmp2::add(a, ap)
        b     = gmp2::add(bp, aq)
        count = count - 1
    END IF
WEND
PRINT len(b),"\n"
Here are the comparative results to AIR's fibo. I'm only printing the LEN of the result string in both examples.

Code: Select all

jrs@jrs-laptop:~/sb/GMP$ time scriba hfibo.sb
1000000

real	1m6.677s
user	1m5.865s
sys	0m0.772s
jrs@jrs-laptop:~/sb/GMP$ time scriba 1milfibo.sb
1000000

real	0m4.282s
user	0m4.217s
sys	0m0.037s
jrs@jrs-laptop:~/sb/GMP$ 

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 7:27 am

ScriptBasic,
I converted Heater's hfibo.sb...
No. You did not. I have never written a fibo in BASIC. Please don't do that.

Looks good anyway.

Why is the extension called "gmp2" ?

As far as I know there is no GMP2.

Besides as a standard part of the language the name should not reflect the implementation details. In this case the fact that big integers are done with GMP. What if the implementation changes one day.

I liked "BI" better.
Memory in C++ is a leaky abstraction .

ejolson
Posts: 3838
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 10:58 am

ScriptBasic wrote:
Mon Jun 17, 2019 7:04 am
I converted Heater's hfibo.sb to use AIR's gmp2 extension module.

Heater (hfibo.sb)

Code: Select all

IMPORT gmp2.bas

function hfibo(n)
local a, b, fk, fk1, k, r
SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1
  if n <= 2 THEN
    r = 1
  else
    k = (n / 2) OR 0
    fk = hfibo(k)
    fk1 = hfibo(k + 1)
    if (n and 1) = 0 then
      a = gmp2::add(fk1, fk1)
      b = gmp2::sub(a, fk)
      r = gmp2::mul(fk, b)
    else
      a = gmp2::mul(fk, fk)
      b = gmp2::mul(fk1, fk1)
      r = gmp2::add(a, b)
    end if
  end if
  hfibo = r
end function

PRINT LEN(hfibo(4784969)),"\n"
AIR (1milfibo.sb)

Code: Select all

IMPORT gmp2.bas

count = 4784969

a = 1
b = 0
p = 0
q = 1

WHILE count > 0
    IF (count % 2) = 0 THEN
        psq   = gmp2::mul(p, p)
        qsq   = gmp2::mul(q, q)
        twopq = gmp2::mul(p, q)
        twopq = gmp2::mul_si(twopq, 2)
        p     = gmp2::add(psq, qsq)
        q     = gmp2::add(twopq, qsq)
        count = count / 2
    ELSE
        bq    = gmp2::mul(b, q)
        aq    = gmp2::mul(a, q)
        ap    = gmp2::mul(a, p)
        bp    = gmp2::mul(b, p)
        a     = gmp2::add(bq, aq)
        a     = gmp2::add(a, ap)
        b     = gmp2::add(bp, aq)
        count = count - 1
    END IF
WEND
PRINT len(b),"\n"
Here are the comparative results to AIR's fibo. I'm only printing the LEN of the result string in both examples.

Code: Select all

jrs@jrs-laptop:~/sb/GMP$ time scriba hfibo.sb
1000000

real	1m6.677s
user	1m5.865s
sys	0m0.772s
jrs@jrs-laptop:~/sb/GMP$ time scriba 1milfibo.sb
1000000

real	0m4.282s
user	0m4.217s
sys	0m0.037s
jrs@jrs-laptop:~/sb/GMP$ 
I'm surprised by those timings because they seem to indicate a significant performance penalty for using local variables in Script Basic.

Note the non-recursive code uses 3 to 7 big-number multiplications per doubling. Therefore, other things equal, one would expect it to run 2 to 4 times slower than a code based on the algorithm employed by the visual.bas and classic.bas programs.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 11:58 am

Anyone know where that 1milfibo.sb algorithm comes from?

In terms of algorithmic expressiveness that scores almost zero. It's as impenetrable as if it were written in assembler.

If one can use assembler why use BASIC ?
Memory in C++ is a leaky abstraction .

hippy
Posts: 6293
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 12:40 pm

Heater wrote:
Mon Jun 17, 2019 11:58 am
Anyone know where that 1milfibo.sb algorithm comes from?

In terms of algorithmic expressiveness that scores almost zero. It's as impenetrable as if it were written in assembler.
I thought it was derived from the JavaScript you presented -

viewtopic.php?f=31&t=240287&start=250#p1478131

"Today I have a new fibo.js that gets the job done in 3.8 seconds on my PC! Like so:"

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 12:44 pm

The hfibo.sb posted above is derived from my Javascript version. It is recursive.

The 1milfibo.sb above is from Airr apparently. It is iterative. That is the one I'm puzzling over
Memory in C++ is a leaky abstraction .

hippy
Posts: 6293
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 12:45 pm

Heater wrote:
Mon Jun 17, 2019 12:44 pm
The hfibo.sb posted above is derived from my Javascript version. It is recursive.

The 1milfibo.sb above is from Airr apparently. It is iterative. That is the one I'm puzzling over
I presumed that was the un-rolled, non-recursive, optimised version. But I may be wrong.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 1:37 pm

Ah, right, perhaps I have to look at it closer.

Edit: What I wrote below is incorrect gibberish. I failed to notice that the hfibo version has an extra 1m in front of the execution time. A whole minute of more run time!

Those results indicate that the recursive version is twice as fast as the iterative.

Thus neatly contradicting SciptBasic's assertion that recursion was good for making nice looking algorithms but was bad for performance.
Last edited by Heater on Mon Jun 17, 2019 8:10 pm, edited 2 times in total.
Memory in C++ is a leaky abstraction .

jalih
Posts: 94
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 2:23 pm

Heater wrote:
Mon Jun 17, 2019 1:37 pm
Those results indicate that the recursive version is twice as fast as the iterative.
Not possible, there is something odd going on then...

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 3:31 pm

jalih,

I have no doubt something odd is going on there.

But why do you say "Not possible"?
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 5:01 pm

The AIR fibo is based on the following resource. The link was included with the quoted post by AIR on AllBasic.

https://codegolf.stackexchange.com/a/9444

jalih
Posts: 94
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 5:24 pm

Heater wrote:
Mon Jun 17, 2019 3:31 pm
But why do you say "Not possible"?
Recursive call is a lot more costly than a simple loop. You have talked about tail call optimization before, let see about that: Compiler replaces recursive tail call with a jump. Is the end result now recursive or iterative, you decide?

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 7:28 pm

The more complex your recursive function gets, the resouces needed to retain state quickly become processor overwhelming. My PC fan screams at me when running the hfjbo.sb example. The AIR submission makes this fibo challenge a walk in the park.

The first thing that caught my eye is the count / 2. Dividing the iterations in half quicky makes this more manageable.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 8:49 pm

ScriptBasic,
The more complex your recursive function gets, the resouces needed to retain state quickly become processor overwhelming. My PC fan screams at me when running the hfjbo.sb example. The AIR submission makes this fibo challenge a walk in the park.

The first thing that caught my eye is the count / 2. Dividing the iterations in half quicky makes this more manageable.
A few comments:

1) Given that the vast majority of the actual work in both cases is being done by GMP which is very fast, any overheads of making recursive calls should be pretty much negligible. Hardly showing up in the noise.

2) The recursive algorithm only has to recurse to a depth of 20 or so. Almost nothing. That makes any overheads of making the recursive calls negligible compared to all the actual work being done.

3) Did you not notice that hfibo.sb divides n by 2?
That does exactly the same job in cutting down the work that needs to be done.

4) Given the fact that the recursive SB version takes 10 or 20 times longer than the iterative and 1), 2), 3) above, we can conclude that ScriptBasic has massive overheads in making function calls.

Anyway, currently my scriba won't run any of them. See report on the ScriptBasic thread.
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 9:46 pm

I compiled the GMP2 extension module on my RPi 3 B. AIR's fibo took 38 seconds to complete. The hfibo.sb never completed and locked up my system forcing a hard reset.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 10:12 pm

That is because you have something seriously wrong there.

I just manged to compile the master branch of scriba again and run those fibos with the following results:

Code: Select all

$ time scriba hfibo.sb  | tail -c 100
180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269

real    0m37.963s
user    0m35.484s
sys     0m2.453s

$ time scriba 1milfibo.sb  | tail -c 100
180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269

real    0m3.007s
user    0m2.828s
sys     0m0.172s
The killer is that hfibo uses up 550 megabytes of RAM as it runs!
Where as 1milfibo uses only 05% of my 8GB.

Contrast to the javascript version of hfibo:

Code: Select all

function hfibo (n) {
    let result
    if (n <= 2 ) {
        result = BigInt((n & 3) != 0)
    } else {
        let k = (n / 2) | 0
        let fk = hfibo(k);
        let fk1 = hfibo(k + 1);
        if ((n & 1) == 0) {
            let a = fk1 + fk1
            let b = a - fk
            result = fk * b
        } else {
            let a = fk * fk
            let b = fk1 * fk1
            result = a + b
        }
    }
    return result
}

console.log(hfibo(4784969))

Code: Select all

$ time node hfibo.js | tail -c 100
80149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269n

real    0m58.077s
user    0m57.953s
sys     0m0.156s
That takes a bit longer. Mostly to print the result. The actual calculation takes about 8 seconds.

BUT it only takes 0.3% of my RAM as it runs.

ScriptBasic is doing a terrible job of managing memory with hfibo.js.
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 10:22 pm

I rarely use recursion in ScriptBasic so all this is news to me. Maybe AIR can shed some light on this?

550 MB on a RPI explains why ScriptBasic ran out of system memory. I'm running full desktop not lite. The current GMP2 extension module isn't error trapping out of memory conditions.

Return to “General programming discussion”