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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 10:00 am

Awesome.

I was there the day they delivered a new ICL 2960 to our uni CS department. A few giant trucks turned up. They laid down an aluminium plate road way from the trucks into the building. Then rolled out a lot of very big sexy looking bright orange boxes, drives, processor, etc. Most impressive.

jahboater
Posts: 4595
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 10:08 am

Heater wrote:
Thu Jun 13, 2019 10:00 am
Awesome.

I was there the day they delivered a new ICL 2960 to our uni CS department. A few giant trucks turned up. They laid down an aluminium plate road way from the trucks into the building. Then rolled out a lot of very big sexy looking bright orange boxes, drives, processor, etc. Most impressive.
Mainframes were always large and impressive, something the credit card sized Raspberry Pi cannot compete with despite being more powerful!

I once worked at BRA01 a large ICL building. Most of the ground floor was the machine hall for the mainframes, the largest in Europe, with a raised viewing gallery all around the edge which took a long time to walk around. Over the years more and more of the hall was converted to offices as mainframes got smaller.

User avatar
PeterO
Posts: 4882
Joined: Sun Jul 22, 2012 4:14 pm

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 11:10 am

I forgot to add the link to the George 3 Emulator if anyone wants to try it... It's quite a challenge to get anything done though :-)

https://www.icl1900.co.uk/preserve/g3ee.html

PeterO
Discoverer of the PI2 XENON DEATH FLASH!
Interests: C,Python,PIC,Electronics,Ham Radio (G0DZB),1960s British Computers.
"The primary requirement (as we've always seen in your examples) is that the code is readable. " Dougie Lawson

User avatar
rpdom
Posts: 14770
Joined: Sun May 06, 2012 5:17 am
Location: Chelmsford, Essex, UK

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 12:04 pm

jahboater wrote:
Thu Jun 13, 2019 10:08 am
Heater wrote:
Thu Jun 13, 2019 10:00 am
Awesome.

I was there the day they delivered a new ICL 2960 to our uni CS department. A few giant trucks turned up. They laid down an aluminium plate road way from the trucks into the building. Then rolled out a lot of very big sexy looking bright orange boxes, drives, processor, etc. Most impressive.
Mainframes were always large and impressive, something the credit card sized Raspberry Pi cannot compete with despite being more powerful!

I once worked at BRA01 a large ICL building. Most of the ground floor was the machine hall for the mainframes, the largest in Europe, with a raised viewing gallery all around the edge which took a long time to walk around. Over the years more and more of the hall was converted to offices as mainframes got smaller.
I used to work in a 21000 square foot datacentre with a large mainframe. That got replaced by a PC sitting under a desk running emulation software. The tape drives were replaced by a Unix box with a load of disks and a tape autoloader for long term storage. The banks of modems were replaced by another Unix box with an Ethernet link. The only things that stayed were the high speed printers (3000 pages in 10-15 minutes)

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 1:59 pm

Heater wrote:
Thu Jun 13, 2019 7:53 am
That leaks memory. Every call to mpz_init() should have a corresponding mpz_clear()

What does "besRETURN_STRING(buf);" do? Hope it's not returning a pointer to a buffer on the stack.
Is t hat a guess or did you try running it and noticed the leak?

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 2:11 pm

ScriptBasic wrote:
Thu Jun 13, 2019 1:59 pm
Heater wrote:
Thu Jun 13, 2019 7:53 am
That leaks memory. Every call to mpz_init() should have a corresponding mpz_clear()

What does "besRETURN_STRING(buf);" do? Hope it's not returning a pointer to a buffer on the stack.
Is t hat a guess or did you try running it and noticed the leak?
It's by definition.

For the first, if you call something which reserves memory and don't then free that memory for re-use you are "leaking memory".

For the second, if it does just return a pointer to where 'buf' is within the function, that will have been on the stack, and may well have been overwritten or altered whenever you come to access what that pointer points to.

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 2:58 pm

If it is leaking, I can add a static function to do the clear before exiting the function. It's always been a mystery what is freed when exiting a function and what manually needs to be freed. Strings seem to be the major concern.

jahboater
Posts: 4595
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 3:07 pm

ScriptBasic wrote:
Thu Jun 13, 2019 2:58 pm
If it is leaking, I can add a static function to do the clear before exiting the function. It's always been a mystery what is freed when exiting a function and what manually needs to be freed. Strings seem to be the major concern.
If you are talking about C then it is simple (though it may not appear so!)
Anything on the stack (arguments and local variables) is freed when a function is exited.

Anything originating from malloc (the heap) remains.

Any static data remains of course.

A array or string may have a pointer to its start that is on the stack.

Code: Select all

foo( void )
{
  char *ptr = malloc(42);
}
So when the function exits here, the "ptr" is freed and the block of memory returned from malloc() remains but can never be accessed again - this is called a memory leak. The block should be released before ptr goes out of scope with free(ptr).

An mpz_t is a small structure (probably) on the stack that will have pointers to the real arrays.

Of course nowadays most small local objects are held in registers, but the behavior is the same.

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 3:17 pm

jahboater wrote:
Thu Jun 13, 2019 3:07 pm
If you are talking about C then it is simple (though it may not appear so!)
It's got me mystified, how one can concatenate strings and return that from a function -

Code: Select all

char * GetErrorMessage(int n)
{
  char * errorMessage = ConcatenateStrings("Error ", intToString(n));
  return errorMessage;
}
Probably off topic for this thread, but it had me stymied when I tried to create my own bigint implementation for the fibo challenge.

jahboater
Posts: 4595
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 3:24 pm

hippy wrote:
Thu Jun 13, 2019 3:17 pm
jahboater wrote:
Thu Jun 13, 2019 3:07 pm
If you are talking about C then it is simple (though it may not appear so!)
It's got me mystified, how one can concatenate strings and return that from a function -

Code: Select all

char * GetErrorMessage(int n)
{
  char * errorMessage = ConcatenateStrings("Error is: ", intToString(n));
  return errorMessage;
}
Probably off topic for this thread.
That looks fine!

"errorMessage" is a 4 or 8 byte value which is stored on the stack or more likely in a register.
You have sensibly, and safely, returned that value to be used by the caller of your function.
That's all fine, because a copy of "errorMessage" was returned.
"errorMessage" itself will vanish of course, but who cares?

What is mega dangerous is:

Code: Select all

int * foo( void )
{
   int num = 42;
   int *ptr = #
   return ptr;
}
If you clearly understand why that is bad news, then you have nothing to worry about!

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 3:38 pm

I'm surprised no one commented on how ScriptBasic works transparently with integers and string integers doing math. The fibo function started off passing two integers to BI_ADD and returned a numeric string. As long as the size of the integer is within range, standard SB math operators can be use even if GMP created the variable.

If someone with better debugging skills than PRINT "Got Here" can verify a memory leak with my direction, it would be appreciated.

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 5:44 pm

PeterO wrote:
Thu Jun 13, 2019 11:10 am
I forgot to add the link to the George 3 Emulator if anyone wants to try it... It's quite a challenge to get anything done though :-)

https://www.icl1900.co.uk/preserve/g3ee.html

PeterO
It may be time for an emulated Fibonacci roundup that includes Algol, PL/I, Basic and other languages running in emulators on the Raspberry Pi.

On the website you linked I saw a binary download for the Pi. Is the source code for the emulator included?

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 6:25 pm

I did a fibo(78000) in 16 seconds. That's 1000 times greater than fibo(78) that was my max using double precision.

I reworked the code to clear op1, op2 and res with each call to the library.

If you thought undef was cute, get use to inf when trying to use those crazy numbers with standard SB math operators.

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 7:25 pm

I'm still unable to do a million digit Fibonacci with the current design. I believe I run out of resources before it's able to finish. The disk light is solid towards the end so I'm guessing it's using swap space to emulate memory. That said I couldn't be happier with what the extension module has provided in just 3 functions and seamless with variable type interaction.

I ran the system monitor while running the fibo(78000) and the memory slowly did increase but as soon as the program ended it returned to the level it was at before running fibo. I'm wondering if that 1.5 meg buffer I'm assuming is freed when the function returns is really happening or is it something with ScriptBasic's memory manager that is resource hungry?

interface.c

Code: Select all

/* GMP Extension Module
UXLIBS: -lc -lgmp
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <gmp.h>
#include "../../basext.h"

static mpz_t op1;
static mpz_t op2;
static mpz_t res;

static void gmp_clear(void){
  mpz_clear(op1);
  mpz_clear(op2);
  mpz_clear(res);
  return 0;
}

/**************************
 Extension Module Functions
**************************/


typedef struct _ModuleObject {
  void *HandleArray;
}ModuleObject,*pModuleObject;


besVERSION_NEGOTIATE
  return (int)INTERFACE_VERSION;
besEND


besSUB_START
  pModuleObject p;
  besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  if( besMODULEPOINTER == NULL )return 0;
  p = (pModuleObject)besMODULEPOINTER;
  return 0;
besEND


besSUB_FINISH
  pModuleObject p;
  p = (pModuleObject)besMODULEPOINTER;
  if( p == NULL )return 0;
  return 0;
besEND


/*************
 GMP Functions
*************/


besFUNCTION(fibo)
  int fval;

  besARGUMENTS("i")
    &fval
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  mpz_init(res);

  mpz_fib_ui(res, fval);

  gmp_snprintf( buf,sizeof(buf),"%Zd", res );
  mpz_clear(res);

  besRETURN_STRING(buf);

besEND


besFUNCTION(bi_add)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  mpz_init(op1);
  mpz_init(op2);
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);
  mpz_init(res);

  mpz_add(res, op1, op2);
  gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  gmp_clear();

  besRETURN_STRING(buf);

besEND


besFUNCTION(bi_sub)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  mpz_init(op1);
  mpz_init(op2);
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);
  mpz_init(res);

  mpz_sub (res, op1, op2);
  gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  gmp_clear();

  besRETURN_STRING(buf);

besEND


besFUNCTION(bi_mul)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  mpz_init(op1);
  mpz_init(op2);
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);
  mpz_init(res);

  mpz_mul (res, op1, op2);
  gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  gmp_clear();

  besRETURN_STRING(buf);

besEND
sfibo.sb

Code: Select all

DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"

FUNCTION sfibo (n)
  IF n < 2 THEN
    sfibo = 1
  ELSE
    m = 0
    p = 1
    q = 0
    FOR i = 2 TO n
      m = BI_ADD(p, q)
      q = p
      p = m
    NEXT i
    sfibo = m
  END IF
END FUNCTION

PRINT sfibo(78000),"\n"
Output

Code: Select all

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

real	0m44.118s
user	0m43.093s
sys	0m0.937s
jrs@jrs-laptop:~/sb/GMP$ ls -l sfibo.out
-rw-r--r-- 1 jrs jrs 16302 Jun 13 12:23 sfibo.out
jrs@jrs-laptop:~/sb/GMP$ tail -c64 sfibo.out
840773259352868233566983589379711278754520073189001074454696000
jrs@jrs-laptop:~/sb/GMP$ 
I would love to see a better design or improve what I have running.

gkreidl
Posts: 5999
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 8:31 pm

Here is my final Python Fibonacci challenge script (fibo_final.py). It can be used with Python 2 or 3 and also with pypy and uses the fastest available method (if not told otherwise) without cheating (using the fibo function built into GMP). That means, it will use GMP, if gmpy2 is available. Otherwise it will fall back to Python's builtin BIGINT. This will always happen with pypy, as this is not compatible with gmpy2.

By default it will print fibo(4784969), but it can take any Fibonacci index as argument. I have tested it up to fibo(1000000000) with different options (see below). With a special options combination and enough swap space I could also calculate fibo(2000000000).

Code: Select all

Usage: python fibo_final.py [options] [index]
or
       python3 fibo_final.py [options] [index]
or
       pypy fibo_final.py [options] [index]
       Note: pypy cannot use gmpy2

index: Fibonacci number to be calculated, default = 4784969

Options:
-t don't print result, only time needed for Fibonacci calculation and string conversion
-n don't convert result to string in timing mode 
-i use Python internal BIGINTS, even if gmpy2 is installed
-c cheat = use GMP's internal Fibonacci function if possible
-h, --help print this text
Examples (RPi 3B+, Raspbian Stretch):

Code: Select all

pi@raspberrypi4:~ $ time python fibo_final.py | tail -c 32
4856539211500699706378405156269

real	0m1,795s
user	0m1,732s
sys	0m0,042s

pi@raspberrypi4:~ $ python fibo_final.py -t
Fibonacci calculation took 0.42829990387 seconds
String conversion took 1.28486704826 seconds
Fibonacci Number has 1000000 digits
Fibonacci calculation needed 59 recursive calculations

pi@raspberrypi4:~ $ python3 fibo_final.py -t -c
Fibonacci calculation took 0.26346707344055176 seconds
String conversion took 1.265275478363037 seconds
Fibonacci Number has 1000000 digits

pi@raspberrypi4:~ $ python fibo_final.py -t 10000000
Fibonacci calculation took 0.814356803894 seconds
String conversion took 3.36349606514 seconds
Fibonacci Number has 2089877 digits
Fibonacci calculation needed 56 recursive calculations

pi@raspberrypi4:~ $ pypy fibo_final.py -t
Fibonacci calculation took 6.37379097939 seconds
String conversion took 75.8342139721 seconds
Fibonacci Number has 1000000 digits
Fibonacci calculation needed 59 recursive calculations

pi@raspberrypi4:~ $ python3 fibo_final.py -t -i -n
Fibonacci calculation took 10.611706018447876 seconds
Fibonacci calculation needed 59 recursive calculations
The script (edited June 15th, 2019)

Code: Select all

## Fibonacci challenge script fibo_final.py

import time, sys

use_gmp = True
use_gmp_fibo = False
timing_only = False
string_conversion = True
fibs = {0:0, 1:1, 2:1}
index = 4784969

usage = '''Usage: python fibo_final.py [options] [index]
or
       python3 fibo_final.py [options] [index]
or
       pypy fibo_final.py [options] [index]
       Note: pypy cannot use gmpy2

index: Fibonacci number to be calculated, default = 4784969

Options:
-t don't print result, only timing for Fibonacci calculation and string conversion
-n don't convert result to string in timing mode 
-i use Python internal BIGINTS, even if gmpy2 is installed
-c cheat = use GMP's internal Fibonacci function if possible
-h, --help print this text
'''

def fibo(n):
    if n in fibs:
        return fibs[n]
    k = (n + 1) // 2
    fk = fibo(k)
    fk1 = fibo(k - 1)
    if n & 1:
        result = fk ** 2 + fk1 ** 2
    else:
        result = (2 * fk1 + fk) * fk
    fibs[n] = result
    return result

if len(sys.argv) > 1:
    for arg in sys.argv[1:]:
        if arg in ['-h','--help']:
            print(usage)
            sys.exit(0)
        if arg in ['-t', '-i', '-c', '-n']:
            if arg == '-t':
                timing_only = True
            elif arg == '-i':
                use_gmp = False
            elif arg == '-c':
                use_gmp_fibo = True
            elif arg == '-n':
                string_conversion = False
        else:
            try:
                index = int(arg)
            except:
                pass

if use_gmp:
    try:
        import gmpy2
        from gmpy2 import mpz
        fibs = {0:mpz(0), 1:mpz(1), 2:mpz(1)}
    except:
        use_gmp = False
        use_gmp_fibo = False

if timing_only:
    if use_gmp and use_gmp_fibo:
        t = time.time()
        res = gmpy2.fib(index)
        fibt = time.time()-t
    else:
        t = time.time()
        res = fibo(index)
        fibt = time.time()-t
    if string_conversion:
        t = time.time()
        restr = str(res)
        strcvt = time.time()-t
    print('Fibonacci('+str(index)+') calculation took '+str(fibt)+' seconds')
    if string_conversion:
        print('String conversion took '+str(strcvt)+' seconds')
        print('Fibonacci Number has '+str(len(restr))+' digits')
    if not use_gmp_fibo:
        print(str(len(fibs)-3) + ' Fibonacci numbers have been calculated')
else:
    if use_gmp_fibo:
        print(gmpy2.fib(index))
    else:
        print(fibo(index))
 
Last edited by gkreidl on Sat Jun 15, 2019 9:16 am, edited 1 time in total.
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer

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

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 11:28 pm

I cleaned up the code a bit. No improvements as far as resource reduction.

Can someone suggest what GMP divide function would be best. There seems to be a few options for the operator.

Code: Select all

/* GMP Extension Module
UXLIBS: -lc -lgmp
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <gmp.h>
#include "../../basext.h"

static mpz_t op1;
static mpz_t op2;
static mpz_t res;

static void gmp_clear(void){
  mpz_clear(op1);
  mpz_clear(op2);
  mpz_clear(res);
  return 0;
}

static void gmp_init(void){
  mpz_init(op1);
  mpz_init(op2);
  mpz_init(res);
  return 0;
}


/**************************
 Extension Module Functions
**************************/


typedef struct _ModuleObject {
  void *HandleArray;
}ModuleObject,*pModuleObject;


besVERSION_NEGOTIATE
  return (int)INTERFACE_VERSION;
besEND


besSUB_START
  pModuleObject p;
  besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  if( besMODULEPOINTER == NULL )return 0;
  p = (pModuleObject)besMODULEPOINTER;
  return 0;
besEND


besSUB_FINISH
  pModuleObject p;
  p = (pModuleObject)besMODULEPOINTER;
  if( p == NULL )return 0;
  return 0;
besEND


/*************
 GMP Functions
*************/


besFUNCTION(fibo)
  int fval;

  besARGUMENTS("i")
    &fval
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  mpz_init(res);

  mpz_fib_ui(res, fval);

  gmp_snprintf( buf,sizeof(buf),"%Zd", res );
  mpz_clear(res);

  besRETURN_STRING(buf);

besEND


besFUNCTION(bi_add)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  gmp_init();
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);


  mpz_add(res, op1, op2);
  gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  gmp_clear();

  besRETURN_STRING(buf);

besEND


besFUNCTION(bi_sub)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  gmp_init();
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);

  mpz_sub (res, op1, op2);
  gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  gmp_clear();

  besRETURN_STRING(buf);

besEND


besFUNCTION(bi_mul)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  gmp_init();
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);

  mpz_mul (res, op1, op2);
  gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  gmp_clear();

  besRETURN_STRING(buf);

besEND

jahboater
Posts: 4595
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Thu Jun 13, 2019 11:39 pm

ScriptBasic wrote:
Thu Jun 13, 2019 11:28 pm
Can someone suggest what GMP divide function would be best. There seems to be a few options for the operator.
I suggest the "tdiv" functions for truncating integer division (that is, they truncate towards zero like normal hardware integer divide works). mpz_tdiv_q() etc.

7/2 == 3 and -7/2 == -3
4/5 == 0 and -4/5 == 0

As it says, the q functions calculate only the quotient, the r functions only the remainder, and the qr functions calculate both.

The "fdiv" versions do floor division which is what the Python3 // operator does.
7/3 == 2 and -7/3 == -3

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 12:48 am

Thanks for the suggestion and helpful explanation.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 3:35 am

ScriptBasic,

I just noticed, you are using the schoolboy's Fibonacci algorithm rather than any optimized method. That will be an orders of magnitude slower and is only exercising BI_ADD.

It's time to step up the game and use a better fibo algorithm. Perhaps the simplest we have so far is my original effort which as JS looks like this:

Code: Select all

function isEven(n) {
  return (n & 1) === 0;
}

let memo = [BigInt(0), BigInt(1), BigInt(1)]

//
// This is a fast and big Fibonacci number calculator based on the suggestions here:
// https://www.nayuki.io/page/fast-fibonacci-algorithms
//
function fibo (n) {
  if (typeof memo[n] != 'undefined') {
    return memo[n]
  }
  let k = Math.floor(n / 2)
  let a = fibo(k);
  let b = fibo(k + 1);
  if (isEven(n)) {
    return memo[n] = a * ((b * 2n) - a)
  }
  return memo[n] = a ** 2n + b ** 2n
}
That should be clear enough as pseudo code for a ScriptBasic version. Runs in less than 10 second as Javascript on my PC and consumes only 0.2% of my 8GB RAM.

We have increasingly more complicated fibos that will perhaps double that performance but this is a good place to start.

You are so close to the fibo challenge solution, I'd love to see it working!

Edit: Fixed the code !
Last edited by Heater on Sat Jun 15, 2019 3:48 am, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 3:58 am

With AIR's help I was able to get the GMP interface closer to your original C code. I think you're right about the .50 cent fibo I'm using. I'll give your version a try.

interface.c

Code: Select all

/* GMP Extension Module
UXLIBS: -lc -lgmp
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <gmp.h>
#include "../../basext.h"

static mpz_t op1;
static mpz_t op2;
static mpz_t res;

static void gmp_clear(void){
  mpz_clear(op1);
  mpz_clear(op2);
  mpz_clear(res);
}

static void gmp_init(void){
  mpz_init(op1);
  mpz_init(op2);
  mpz_init(res);
}


/**************************
 Extension Module Functions
**************************/


typedef struct _ModuleObject {
  void *HandleArray;
}ModuleObject,*pModuleObject;


besVERSION_NEGOTIATE
  return (int)INTERFACE_VERSION;
besEND


besSUB_START
  pModuleObject p;
  besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  if( besMODULEPOINTER == NULL )return 0;
  p = (pModuleObject)besMODULEPOINTER;
  return 0;
besEND


besSUB_FINISH
  pModuleObject p;
  p = (pModuleObject)besMODULEPOINTER;
  if( p == NULL )return 0;
  return 0;
besEND


/*************
 GMP Functions
*************/


besFUNCTION(fibo)
  int fval;

  besARGUMENTS("i")
    &fval
  besARGEND

  char buf[1500000];
  memset(buf,0,1);
  mpz_init(res);

  mpz_fib_ui(res, fval);

  gmp_snprintf( buf,sizeof(buf),"%Zd", res );
  mpz_clear(res);

  besRETURN_STRING(buf);

besEND


besFUNCTION(bi_add)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  gmp_init();
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);

  mpz_add(res, op1, op2);
  char* res_string = mpz_get_str (0, 10, res);
  besSET_RETURN_STRING(res_string);
  gmp_clear();
  free(res_string);

besEND


besFUNCTION(bi_sub)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  gmp_init();
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);

  mpz_sub (res, op1, op2);
  char* res_string = mpz_get_str (0, 10, res);
  besSET_RETURN_STRING(res_string);
  gmp_clear();
  free(res_string);

besEND


besFUNCTION(bi_mul)
  const char* s1;
  const char* s2;

  besARGUMENTS("zz")
    &s1, &s2
  besARGEND

  gmp_init();
  mpz_set_str(op1, s1, 10);
  mpz_set_str(op2, s2, 10);

  mpz_mul (res, op1, op2);
  char* res_string = mpz_get_str (0, 10, res);
  besSET_RETURN_STRING(res_string);
  gmp_clear();
  free(res_string);

besEND

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 4:35 am

Why I like this GMP interface.

Code: Select all

DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
DECLARE SUB BI_SUB    ALIAS  "bi_sub"  LIB "gmp"
DECLARE SUB BI_MUL    ALIAS  "bi_mul"  LIB "gmp"

a = 123456789
b = 987654321

c = a * b
PRINT c,"\n"
PRINT BI_MUL(c, STRREVERSE(c)),"\n"

Output

Code: Select all

jrs@jrs-laptop:~/sb/GMP$ scriba gmpmul.sb
121932631112635269
117364572765028660532228440042158549
jrs@jrs-laptop:~/sb/GMP$ 

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:37 am

ScriptBasic,
Why I like this GMP interface.
That is cool an all. I guess we may not have commented on this use of numbers and strings together if it were not a regular thing we can do in man other languages .

For example in my big integer class I define the operators +, -, *, << that work on numbers stored as big arrays of integers. It would be a trivial task to define the operators such that they can also work on combinations of big integers and strings, big integers and regular ints, or potentially even just regular ints and strings.

Many programmers hate this kind of sloppy typing though. They would much prefer to have strict type checking and require the user explicitly do the type conversions in their code.

Famously many "real" programmers laugh at Javascript for doing the following:
> 1111 + 1111
2222
> 1111 - 1111
0
> 1111 * 1111
1234321
> 1111 / 1111
1
> 1111 + "1111"
'11111111'
> 1111 - "1111"
0
> 1111 * "1111"
1234321
> 1111 / "1111"
1
> "1111" + 1111
'11111111'
> "1111" - 1111
0
> "1111" * 1111
1234321
> "1111" / 1111
1
> "1111" + "1111"
'11111111'
> "1111" - "1111"
0
> "1111" * "1111"
1234321
> "1111" / "1111"
1
Notice how JS gives the "wrong" answer for 1111 + "1111" and "1111" + 1111. Well of course, the + operator is used as a nice simple string concatenation operator, so that's what it does here having converted the numbers to strings. Conversely -, *, / don't make any obvious sense for strings so they are used as maths operations after converting the strings to numbers.

It all makes perfect sense. Sometimes "real" programmers are full of nonsense.

Why I don't like this GMP interface:

Code: Select all

  mpz_add(res, op1, op2);
  char* res_string = mpz_get_str (0, 10, res);
  besSET_RETURN_STRING(res_string);
  gmp_clear();
  free(res_string);
If I'm reading that correctly, SET_RETURN_STRING is allocating a string big enough to hold the result and copying res_string into it, res_string is then freed.

That a lot of redundant memory allocation and copying going on.

jahboater
Posts: 4595
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:52 am

I think people don't like

> 1111 + "1111"
'11111111'
> 1111 - "1111"
0

because of its inconsistency. "-" does arithmetic "+" does string concatenation
one operator converts the number to a string the other converts a string to a number.

There are many C++ interfaces for GMP, I see there is now one provided by the GMP library itself

https://gmplib.org/manual/C_002b_002b-C ... -Interface

Allowing stuff like

Code: Select all

int
main (void)
{
  mpz_class a, b, c;

  a = 1234;
  b = "-5678";
  c = a+b;
  cout << "sum is " << c << "\n";
  cout << "absolute value is " << abs(c) << "\n";

  return 0;
}
Last edited by jahboater on Fri Jun 14, 2019 6:55 am, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:54 am

That a lot of redundant memory allocation and copying going on.
The price of seamless integration., 8-)

Keep in mind the GMP C library has to interface with ScriptBasic's thread safe (default mode) memory manager. Rarely do you interface memory directly and must use SB's API interface. Luckily Peter wrote a high level macro interface to hide his object pointer madness.

You can compile / run ScriptBasic in single threaded mode which doesn't use the memory manager and allows a more direct C level interface. .(uses malloc instead)
Last edited by John_Spikowski on Fri Jun 14, 2019 7:42 am, edited 5 times in total.

jahboater
Posts: 4595
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 7:06 am

ScriptBasic wrote:
Fri Jun 14, 2019 6:54 am
That a lot of redundant memory allocation and copying going on.
The price of seamless integration., 8-)
The C++ integration which looks very seamless, doesn't do all that (see the example and link in my previous post).

The problem is, as always, mixing two languages where one language has a richer choice of data types than the other.

Return to “General programming discussion”