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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 5:35 pm

Heater wrote:
Wed Jun 19, 2019 5:16 pm
ejolson,
I thought we decided earlier that no memory leaks are possible in Linux because all user memory is freed by the operating system after the program crashes.
Ha!

Depends what you mean by memory leak. I took a look under my PC and did not find any memory puddles on the floor.
I wonder whether this problem occurs only with strings returned from the GMP extension or whether the same thing happens with all subroutines that have local string variables.
A very good question.

To investigate that I wrote a forum thread debate simulator in ScriptBasic:

Code: Select all

function debate(depth)
  if depth = 0 then
      debate = "true"
  else if depth = 1 then
      debate = "false"
  else
      debate = "("  & debate(depth - 1) & " is " &  debate(depth - 2) & ")"
  end if
end function

while 1
   print debate(20), "\n"
wend
It generates realistic looking forum threads like so (ignoring details like posters names or actual topic etc)
true
false
(false is true)
((false is true) is false)
(((false is true) is false) is (false is true))
I'll leave as an exercise to the reader to determine the truth or falsity of the generated forum posts. As we see it depends on depends on who gives up posting last.

So far I see no memory leaking as it loops forever generating the same discussion over and over.
An example of code that keeps all those megabyte-sized big numbers on the stack would be parallel.c and fibompi.c.
Yes, the neat thing about keeping them on the stack is the automatic garbage collection, as you say, and it also pretty much ensures cache friendly code.
That's a very realistic forum simulator and seems to imply the strings generated by the GMP extension are treated differently or that there is a leak in the extension itself.

I wonder if the iterative computation also leaks memory but just not so fast.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 5:40 pm

ScriptBasic,
And you don't see that as a problem?
Only in ScriptBasic. I have the same algorithm in Python, Javascript. Some of the Fibo Challenge entries in other languages are very similar.
How many WHILE loops do you think AIR's Fibo takes to come up with an answer?
Well, there is only one WHILE loop in AIR's 1millfibo.sb, it loops around 4,784,969 times

So, my fibo loops (via recursion) only about twice as often as AIR's iterative code. Hardly a problem.

My fibo has a recursion depth of only 24. Also nothing like a problem.

Still the AIR iterative algorith is slower in Javascript than that recursive algorithm in JS. No doubt the same in other languages. And would get worse if we wanted ten million digits or a hundered or...

But that algorithmic performance difference is not the issue here. The problem is that ScriptBasic has a severe memory explosion if one uses the recursive algorithm. It should not.

I suspect that strings returned by GMP or a copies by the GMP extsion are not being released.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 5:54 pm

Heater wrote:Well, there is only one WHILE loop in AIR's 1millfibo.sb, it loops around 4,784,969 times
Are you sure? Theoretically the doubling formulas should take about 23 iterations when n=4784969 and the second case in that while loop adds no more than double that. For all algorithms it would be interesting to instrument the code with an additional counter or two to see exactly what's going on.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 6:35 pm

ejolson wrote:
Wed Jun 19, 2019 5:54 pm
Heater wrote:Well, there is only one WHILE loop in AIR's 1millfibo.sb, it loops around 4,784,969 times
Are you sure? Theoretically the doubling formulas should take about 23 iterations when n=4784969 and the second case in that while loop adds no more than double that.
Fibo(4784969) using Fast Doubling algorithm needs just one loop and exactly 23 iterations (that is number of bits in 4784969 in binary).

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 6:50 pm

ejolson,
Are you sure? Theoretically the doubling formulas should iterate somewhere between 22 and 46 times when n=4784969. In both cases it would be interesting to instrument the code with an additional counter or two to see exactly what's going on.
I'm sure that the simple fibo in JS, that the ScriptBasic recursive version is based on, calls itself that many times and has that depth of recursion.

As it happens I did instrument the my JS version to get those figures. Like so:

Code: Select all

let calls = 0

function hfibo (n, depth) {
    calls++
    console.log ("Call:\t" + calls + ", Depth:\t" + depth + ", n:\t" + n)
    let result
    if (n <= 2 ) {
        result = BigInt((n & 3) != 0)
    } else {
        let k = (n / 2) | 0
        let fk = hfibo(k, depth + 1);
        let fk1 = hfibo(k + 1, depth + 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
}

let f = hfibo(4784969, 1)
console.log(f)
Of course my original versions of this in Python and JS used memoization which reduces the calls a lot. Turns out that for JS menoization only makes about 10% difference in run time though.It was a lot more in Python.
Last edited by Heater on Wed Jun 19, 2019 8:55 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 7:06 pm

jalih,
Fibo(4784969) using Fast Doubling algorithm needs just one loop and exactly 23 iterations (that is number of bits in 4784969 in binary).
Perhaps. I have no idea.

What you see above is my first, no doubt naive, attempt at the fast doubling algorithm based on the equations I found here under the heading of "Fast doubling" here: https://www.nayuki.io/page/fast-fibonacci-algorithms

Since then ejolson and others have presented other variants of "fast doubling". You can see some that I transcribed to JS here: https://github.com/ZiCog/fibo_4784969/b ... pt/fibo.js

They were faster but not massively so. Perhaps my transcriptions were not faithful to their creators intentions.

If you can present a more optimized Fast Doubling in Javascript or some language normal people can read, not Forth, Scheme, Smalltalk, etc, I would be very happy and grateful.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 7:22 pm

ejolson,
I wonder if the iterative computation also leaks memory but just not so fast.
Yes, it does. See my bug report here:
viewtopic.php?f=34&t=238001&p=1482285#p1482283

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 7:47 pm

Heater wrote:
Wed Jun 19, 2019 7:06 pm
If you can present a more optimized Fast Doubling in Javascript or some language normal people can read, not Forth, Scheme, Smalltalk, etc, I would be very happy and grateful.
Here is a naive Basic version without BIGINT support. Just substitude all uint's with BIGINT and you are ready to go...

Code: Select all

func log2(double n), double
  return log(n)/log(2)  
endf


func fibo(int n),uint
  uint a = 0
  uint b = 1
  int numbits = int(log2(n))
  for i = numbits to 0 step -1
    uint d = a*(b*2-a)
    uint e = a*a+b*b
    a = d
    b = e
    if (n >> i) & 1
      uint c = a+b
      a = b
      b = c
    endif
  next i
  return a
endf

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 9:14 pm

jalih,

Thank you for that. Neat, no recursion!

I transcribed it to Javascript like so:

Code: Select all

//
// A non-recusive Fast Doubling Fibonacci algorithm by jalih.
//
// Transcribed from jalih's BASIC version here: https://www.raspberrypi.org/forums/viewtopic.php?f=31&t=240287&p=1482273#p1482299
//

function fiboJalih(n) {
  let a = BigInt(0)
  let b = BigInt(1)
  let numbits = Math.log2(n)

  for (let i = numbits; i >= 0; i--) {
    let d = a * (b * 2n - a)
    let e = a * a + b * b
    a = d
    b = e
    if ((n >> i) & 1)  {
      let c = a + b
      a = b
      b = c
    }
  }
  return a
}

function timeIt (f, n) {
    let t = new Date()
    let res = f(n)
    t = new Date() - t
    return {result: res, calcTime: t}
}

let n = 4784969
let f = timeIt(fiboJalih, n)
console.log("Calculation time: " + f.calcTime + "ms")
console.log("Result:", f.result)
Sadly it is a little bit slower than my recusive implementation, as shown, above. Which is already the slowest of the fast doubling fibo's in Javascript that we have.

Code: Select all

$ time node fibo_jalih.js | head -c 100 ; time node fibo_jalih.js | tail -c 100
Calculation time: 16248ms
Result: 10727395641800477229364813596225004321907221173237350629846473383025
real    1m1.609s
user    1m0.781s
sys     0m0.094s
80149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269n

real    0m58.893s
user    0m58.688s
sys     0m0.063s
michael@monster:/mnt/c/Users/michael/Documents/fibo_4784969/javascript$ time node hfibo.js | head -c 100 ; time node hfibo.js | tail -c 100
Calculation time: 15792ms
Result: 10727395641800477229364813596225004321907221173237350629846473383025
real    0m59.341s
user    0m59.203s
sys     0m0.063s
80149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269n

real    0m57.414s
user    0m57.188s
sys     0m0.094s
Notice that the time taken by Javascript to print the result totally over shadows the fibo calculation time anyway, so this is all a bit moot.

Do you mind if I add that solution to the Fibonacci Challenge repository?
https://github.com/ZiCog/fibo_4784969

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 12:01 am

Heater wrote:
Wed Jun 19, 2019 9:14 pm
Notice that the time taken by Javascript to print the result totally over shadows the fibo calculation time anyway, so this is all a bit moot.
In a way similar to writing too many different Fibonacci codes in JavaScript, I just rounded up four distinctly different algorithms in C using the GNU Multi-precision Library. The programs are currently running on the super-cheap cluster, hopefully without leaking as I don't want to clean up a puddle of memory from the floor afterwards.

Similar to JavaScript, GMP does all calculations in base 2 and then converts to base 10 for printing. This means differences in the computational efficiency of the various Fibonacci algorithms are somewhat overshadowed by the cost of printing, though not to the same degree as with Python or JavaScript.

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 12:39 am

The ScriptBasic GMP and GMP2 extension modules use base 10. The idea is if the returned strings are small enough could be used with traditional math functions.

Bigint / 10
Do traditional math on result
New result * 10

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 1:10 am

ejolson wrote:
Thu Jun 20, 2019 12:01 am
I just rounded up four distinctly different algorithms in C using the GNU Multi-precision Library.
This post presents four different C codes implementing four different algorithms for quickly computing the n-th Fibonacci number. The codes are
  • method1.c -- optimized doubling: The optimized form of the doubling formula that was used in classic.bas, fibo.bas, fibompi.c, parallel.c, visual.bas and the PL/I code posted here.
  • method2.c -- recursive doubling: The recursive implementation of the doubling formula implemented in hfibo.sb and the Python code used for the Dramatic Fibonacci Comedy of Python Interpreters. Note that the Python code in the GitHub repository is similar but has been memoized. While memoization makes the speed of the algorithm roughly on par with the other methods presented here, for simplicity the memoized version has not been considered in this roundup. Note that slightly modified versions of recursive doubling--some with and some without memoization--have been written in Haskell, Java, JavaScript and Scheme.
  • method3.c -- golden ratio: An algebraic method based on taking powers of the golden ratio in the ring Q[sqrt(5)] that was used here in the pfibo.pas.
  • method4.c -- mystery while loop: The iterative method used here in fib2.sb.
For reference and to check for possible memory leaks, the exact C codes used for the roundup were

Code: Select all

/*  method1.c -- Compute the nth Fibonacci Number
    Written June 19, 2019 by Eric Olson

    This program uses the doubling formulas

        F(2k) = F(k)[2F(k+1)-F(k)]
      F(2k+1) = F(k+1)[2F(k+1)-F(k)]+(-1)^(k+1)

    and

      F(2k+1) = F(k)[2F(k)+F(k+1)]+(-1)^(k)
      F(2k+2) = F(k+1)[2F(k)+F(k+1)]

    The results of this code can also serve as a point of comparison
    to implementations of the doubling formulas using other languages
    that leverage GMP big numbers behind the scenes.  */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

static mpz_t a,b,t1;
void fibowork(int n){
    if(n==0){
        mpz_set_ui(a,0);
        mpz_set_ui(b,1);
        return;
    }
    fibowork(n/2);
    if(n%2==0){
        // [a,b]=[a*(2*b-a),b*(2*b-a)-(-1)^k]
        mpz_add(t1,b,b); mpz_sub(t1,t1,a);
        mpz_mul(a,a,t1); mpz_mul(b,b,t1);
        if(n%4==0) mpz_sub_ui(b,b,1);
        else mpz_add_ui(b,b,1);
    } else {
        // [a,b]=[a*(2*a+b)+(-1)^k,b*(2*a+b)]
        mpz_add(t1,a,a); mpz_add(t1,t1,b);
        mpz_mul(b,b,t1); mpz_mul(a,a,t1);
        if(n%4==1) mpz_add_ui(a,a,1);
        else mpz_sub_ui(a,a,1);
    }
    return;
}

void fibo(int n){
    if(n<2){
        mpz_set_ui(b,n);
        return;
    }
    fibowork((n-1)/2);
    if(n%2==0){
        // b=b*(2*a+b)
        mpz_add(t1,a,a); mpz_add(t1,t1,b); mpz_mul(b,b,t1);
    } else {
        // b=b*(2*b-a)-(-1)^k
        mpz_add(t1,b,b); mpz_sub(t1,t1,a); mpz_mul(b,b,t1);
        if(n%4==1) mpz_sub_ui(b,b,1);
        else mpz_add_ui(b,b,1);
    }
    return;
}

#define bits 4000000
int main(){
    mpz_init2(a,bits); mpz_init2(b,bits); mpz_init2(t1,bits);
    for(;;){
        printf("? ");
        char buf[128];
        fgets(buf,sizeof(buf),stdin);
        int n=atoi(buf);
        if(n==0) break;
        fibo(n);
        mpz_out_str(stdout,10,b);
        printf("\n");
    }
    mpz_clear(t1); mpz_clear(b); mpz_clear(a);
    return 0;
}

Code: Select all

/*  method2.c -- Compute the nth Fibonacci Number
    Written June 19, 2019 by Eric Olson

    This program recursively uses the doubling formulas

        F(2k) = F(k)[2F(k+1)-F(k)]
      F(2k+1) = F(k+1)F(k+1)+F(k)F(k)

    The results of this code can also serve as a point of comparison
    to implementations of the doubling formulas using other languages
    that leverage GMP big numbers behind the scenes.  */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

void hfibo(int n,mpz_t r){
    mpz_t fk,fk1;
    mpz_init(r);
    if(n<=2){
        mpz_set_ui(r,1);
    } else {
        int k=n/2;
        hfibo(k,fk);
        hfibo(k+1,fk1);
        if(n%2==0){
            mpz_add(r,fk1,fk1); mpz_sub(r,r,fk); mpz_mul(r,r,fk);
        } else {
            mpz_mul(r,fk,fk); mpz_mul(fk1,fk1,fk1); mpz_add(r,r,fk1);
        }
        mpz_clear(fk); mpz_clear(fk1);
    }
}

int main(){
    for(;;){
        printf("? ");
        char buf[128];
        fgets(buf,sizeof(buf),stdin);
        int n=atoi(buf);
        if(n==0) break;
        mpz_t b; hfibo(n,b);
        mpz_out_str(stdout,10,b);
        mpz_clear(b);
        printf("\n");
    }
    return 0;
}

Code: Select all

/*  method3.c -- Compute the nth Fibonacci Number
    Written June 19, 2019 by Eric Olson

    This program uses the golden ratio and the formula

        F(n) = (phi^n - (-phi)^(-n))/sqrt(5)

    The results of this code can also serve as a point of comparison
    to implementations of the doubling formulas using other languages
    that leverage GMP big numbers behind the scenes.  */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

typedef struct { mpz_t a,b; } ring5;

mpz_t t1,t2;
ring5 ring5mul(ring5 x,ring5 y){
    ring5 r;
    mpz_init(r.a); mpz_init(r.b);
    mpz_mul(t1,x.a,y.a); mpz_mul(t2,x.b,y.b); mpz_mul_ui(t2,t2,5);
    mpz_add(r.a,t1,t2);
    mpz_mul(t1,x.a,y.b); mpz_mul(t2,x.b,y.a);
    mpz_add(r.b,t1,t2);
    return r;
}

ring5 goldmul(ring5 x,ring5 y){
    ring5 r=ring5mul(x,y);
    mpz_tdiv_q_2exp(r.a,r.a,1);
    mpz_tdiv_q_2exp(r.b,r.b,1);
    return r;
}

ring5 goldpow(ring5 x, int n){
    if(n<=1){
        ring5 r;
        mpz_init(r.a); mpz_set(r.a,x.a);
        mpz_init(r.b); mpz_set(r.b,x.b);
        return r;
    } else {
        ring5 g1=goldpow(x,n/2);
        ring5 g2=goldmul(g1,g1);
        mpz_clear(g1.a); mpz_clear(g1.b);
        if(n%2==0) {
            return g2;
        } else {
            ring5 r=goldmul(x,g2);
            mpz_clear(g2.a); mpz_clear(g2.b);
            return r;
        }
    }
}

int main(){
    ring5 phinum;
    mpz_init(t1); mpz_init(t2);
    mpz_init(phinum.a); mpz_set_ui(phinum.a,1);
    mpz_init(phinum.b); mpz_set_ui(phinum.b,1);
    for(;;){
        printf("? ");
        char buf[128];
        fgets(buf,sizeof(buf),stdin);
        int n=atoi(buf);
        if(n==0) break;
        ring5 z=goldpow(phinum,n);
        mpz_out_str(stdout,10,z.b);
        mpz_clear(z.a); mpz_clear(z.b);
        printf("\n");
    }
    mpz_clear(phinum.b); mpz_clear(phinum.a); 
    mpz_clear(t2); mpz_clear(t1);
    return 0;
}

Code: Select all

/*  method4.c -- Compute the nth Fibonacci Number
    Written June 19, 2019 by Eric Olson

    This program uses a mystery iterative method, probably based on
    taking powers of a matrix such as

        F(n) = [1 1; 1 0]^n [1,2]

    The results of this code can also serve as a point of comparison
    to implementations of the doubling formulas using other languages
    that leverage GMP big numbers behind the scenes.  */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

static mpz_t a,b,p,q,psq,qsq,twopq,ap,aq,bp,bq;

void mystery(int n){
    int count=0;
    mpz_set_ui(a,1);
    mpz_set_ui(b,0);
    mpz_set_ui(p,0);
    mpz_set_ui(q,1);
    while(n>0){
        if(n%2==0){
            mpz_mul(psq,p,p);
            mpz_mul(qsq,q,q);
            mpz_mul(twopq,p,q);
            mpz_mul_si(twopq,twopq,2);
            mpz_add(p,psq,qsq);
            mpz_add(q,twopq,qsq);
            n=n/2;
        } else {
            mpz_mul(bq,b,q);
            mpz_mul(aq,a,q);
            mpz_mul(ap,a,p);
            mpz_mul(bp,b,p);
            mpz_add(a,bq,aq);
            mpz_add(a,a,ap);
            mpz_add(b,bp,aq);
            n=n-1;
        }
    }
}

#define bits 4000000
int main(){
    mpz_init2(a,bits); mpz_init2(b,bits);
    mpz_init2(p,bits); mpz_init2(q,bits);
    mpz_init2(psq,bits); mpz_init2(qsq,bits);
    mpz_init2(twopq,bits);
    mpz_init2(ap,bits); mpz_init2(aq,bits);
    mpz_init2(bp,bits); mpz_init2(bq,bits); 
    for(;;){
        printf("? ");
        char buf[128];
        fgets(buf,sizeof(buf),stdin);
        int n=atoi(buf);
        if(n==0) break;
        mystery(n);
        mpz_out_str(stdout,10,b);
        printf("\n");
    }
    mpz_clear(bq); mpz_clear(bp);
    mpz_clear(aq); mpz_clear(ap);
    mpz_clear(twopq);
    mpz_clear(qsq); mpz_clear(psq);
    mpz_clear(q); mpz_clear(p);
    mpz_clear(b); mpz_clear(a);
    return 0;
}
Last edited by ejolson on Thu Jun 20, 2019 2:19 am, edited 2 times in total.

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 1:31 am

This post is a continuation of the previous.

Here is a table showing how long it takes to compute the 4784969th Fibonacci number for the previously described methods.

Code: Select all

Method                T(4784969)
--------------------------------
recursive doubling   13.487  sec
mystery while loop    6.1586 sec
golden ratio          5.4110 sec
optimized doubling    4.2637 sec
built-in gmp          4.1311 sec
Note that all timings were made using a Pi Zero and the version of GMP that comes standard with Raspbian.

The graph showing the asymptotic behavior is

Image

Edit: It has been pointed out that n is not large enough for the red line to represent asymptotic behaviour and that eventually the slope of the red line must be the same as the others.
Last edited by ejolson on Thu Jun 20, 2019 2:24 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 2:33 am

The term golden ratio popped up shortly after I posted the Fibonacci Pinecone code. Any connection?

Is AIR's newfibo the mystery while loop version?

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 3:50 am

ScriptBasic,
The term golden ratio popped up shortly after I posted the Fibonacci pinecone code. Any connection?
Yes. High school maths!

If you take any two successive numbers of the Fibonacci sequence and divide the bigger one by the smaller one you get an approximation to the golden ratio. The bigger those numbers are the closer they become to the golden ratio.

Golden Ratio = φ = 1.618...

E.g. fibo(12) / fibo(11) = 144 / 89 = 1.6179775280898876

E.g fibo(100) / fibo(99) = 354224848179261915075 / 218922995834555169026 = 1.618033988749895

See here: https://www.quickanddirtytips.com/educa ... i-sequence

And a billion other sites around the net about it.

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 4:38 am

ejolson,

Where is that red line going?

Your graphs seem to show that the recursive doubling aka hfibo has a massive overhead compared to the others. It's 10 times slower for small n.

But the the curve goes up at a lesser slope and is converging with the others for big n. I'm guessing that slope does not stay less than the others past the end of the graph...

Interesting because in my endlessly growing Javascrip fibo collection I have:

hfibo.js - My original recursive doubling, no memoization.
1milfibo - Airr's iterative contribution, I presume the "mystery while loop"
fibo_jalih.js - jalih's iterative doubling contribution.

With the following results for fibo(4784969):

Code: Select all

$ time node hfibo.js | head -c 100 ;  time node 1milfibo.js | head -c 100 ; time node fibo_jalih.js | head -c 100
Calculation time: 14357ms
Result: 107273956418004772293648135962250043219072211732373506298464733830
real    1m12.453s
user    1m12.172s
sys     0m0.141s
Calculation time: 18649ms
Result: 107273956418004772293648135962250043219072211732373506298464733830
real    1m20.788s
user    1m20.547s
sys     0m0.109s
Calculation time: 15489ms
Result: 107273956418004772293648135962250043219072211732373506298464733830
real    1m14.597s
user    1m14.469s
sys     0m0.047s
On the cosmic scale of things they all have the same performance. But the recursive fibo is a tad ahead.

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 1:43 pm

Heater wrote:
Thu Jun 20, 2019 4:38 am
ejolson,

Where is that red line going?

Your graphs seem to show that the recursive doubling aka hfibo has a massive overhead compared to the others. It's 10 times slower for small n.

But the the curve goes up at a lesser slope and is converging with the others for big n. I'm guessing that slope does not stay less than the others past the end of the graph...
The graph seems reminiscent of

viewtopic.php?f=62&t=227343&start=1025#p1412319

The runtime of recursive doubling signified by the red line has a significant O(n) component related to the fact that without memoization the subroutine calls itself n times. However, as n gets larger the O(n^alpha) time complexity of the big-number multiplication dominates.

As the size of the numbers used in the multiplications double in each step, eventually the number of multiplications in the final step decide which Fibonacci calculating method is faster when n is large.

Since 4784969 is odd, then upon inspection
  • method1 has 1 mpz_mul
  • method2 has 2 mpz_mul
  • method3 has 8 mpz_mul
  • method4 has 7 mpz_mul
in the final step. One would expect for large enough n that the red line for method2 would cross the lines for method3 and method4 but not cross the blue line for method1 nor the grey line for the built-in gmp function.

What actually happens for values of n that are sized so F(n) can be computed on a Raspberry Pi Zero may have something to do with avoiding the digital apocalypse.

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 2:36 pm

ScriptBasic wrote:
Thu Jun 20, 2019 2:33 am
Is AIR's newfibo the mystery while loop version?
The exact C code appears as method4.c above. You can check for yourself how close it is to the newfibo ScriptBasic program. My intention was to make the codes comparable.

To determine how the extension module affects performance, you could try the following tests:

Code: Select all

$ time scriba newfibo.sb >newfibo.txt
$ gcc -O3 -omethod4 method4.c -lm -lgmp
$ time ( printf "4784969\n0\n" | ./method4 > method4.txt )
and report the times.
Last edited by ejolson on Fri Jun 21, 2019 12:13 am, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Thu Jun 20, 2019 4:22 pm

Here is a plot showing the detail of the previous graph for n>1000000.

Image

All timings were performed using the Raspberry Pi Zero.

The red line again reminds me of the fifth title scheduled for this thread: The New Paper Tape Project.

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

Re: A Final Fibonacci Challenge

Fri Jun 21, 2019 8:34 pm

After traveling I'm no longer in the high desert. There are no wild horses, only cows. I couldn't see due to clouds but suspect the phase of the moon may about be to change. Before a new title completely ruins this thread, I was looking to round up another herd of Fibonacci codes, this time in JavaScript. Any help getting Node.js installed on the Pi and where to find four different codes is welcome.

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

Re: A Final Fibonacci Challenge

Fri Jun 21, 2019 8:49 pm

Did BASIC already have its turn?

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

Re: A Final Fibonacci Challenge

Fri Jun 21, 2019 9:43 pm

ScriptBasic wrote:
Fri Jun 21, 2019 8:49 pm
Did BASIC already have its turn?
Because the original thread was called Why Avoid Basic, there have been lots of Fibonacci codes written in that language. In particular

https://www.raspberrypi.org/forums/view ... 5#p1472365

contains runs of two different line-numbered codes using FreeBasic and a structured program in Visual Basic.

https://www.raspberrypi.org/forums/view ... 0#p1472855

contains four runs of the classic line-numbered code using different Basic interpreters (including Script Basic).

https://www.raspberrypi.org/forums/view ... 0#p1476126

contains a structured FreeBasic code based on doubling that omits fast multiplication for simplicity.

I wanted to run programs in BBC Basic, Decimal Basic and QB64 (compiled for 32-bit Raspbian), but had trouble accessing these development environments through ssh and running the resulting programs under fibench.

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

Re: A Final Fibonacci Challenge

Fri Jun 21, 2019 10:26 pm

That should now reflect running AIR's fibo. 38 seconds on my RPi 3B.

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

Re: A Final Fibonacci Challenge

Fri Jun 21, 2019 10:29 pm

Being GUI only can find yourself sitting on the sidelines.

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

Re: A Final Fibonacci Challenge

Fri Jun 21, 2019 11:04 pm

ScriptBasic wrote:
Fri Jun 21, 2019 10:26 pm
That should now reflect running AIR's fibo. 38 seconds on my RPi 3B.
Unfortunately that version may leak too much memory to complete the fibench test run of computing 1000 big Fibonacci numbers without crashing. When I'm done traveling and back where I can reboot the Pi if necessary, I would be happy to run it. Unless the digital apocalypse happens first, maybe the memory leak will be plugged by then as well.

Return to “General programming discussion”