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

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 11:10 pm

I converted Airr's 1milfob.sb to javascript.

It runs in 61 seconds. That's 3 seconds slower than the hfibo.js. As noted most of that time is spent formatting the result for printing. The actual calculation time is less than 10 seconds with 1milfibo being 3 seconds slower.

So we see the recursive solution is faster than the iterative. Which is what we expected to see and contrary to popular opinion here. All this talk of "overheads of recursive function calls etc" is just wrong in many situations.

Quite why script basic is having such difficulty with this would be interesting to know.

Code: Select all

let count = 4784969

let a = BigInt(1)
let b = BigInt(0)
let p = BigInt(0)
let q = BigInt(1)

while (count > 0) {
    if ((count % 2) == 0) {
        let psq   = p * p
        let qsq   = q * q
        let twopq = p * q
        twopq = twopq * 2n
        p     = psq + qsq
        q     = twopq + qsq
        count = count / 2
    } else {
        let bq    = b * q
        let aq    = a * q
        let ap    = a * p
        let bp    = b * p
        a     = bq + aq
        a     = a + ap
        b     = bp + aq
        count = count - 1
    }
}
console.log(b)

Code: Select all

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

real    1m0.885s
user    1m0.734s
sys     0m0.141s

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

Re: A Final Fibonacci Challenge

Mon Jun 17, 2019 11:39 pm

If bending over hurts, try squatting. :D

Remember what we are doing to languages by abusing them with Fibonacci isn't real world so when features start acting like pigs is because they weren't designed to be tortured in this way.

I'm using Fibonacci as a ScriptBasic stress tester. ARRAYS passed now we need to see what are the practical limits when using recursion in ScriptBasic.

We are asking ScriptBasic to put on BIGINT clothes with no pior warning. Luckily ScriptBasic's variant variables work well with numeric strings to make the GMP interface more seemless.

I'm curious how JavaScript stores its recursive state that makes it more efficient than ScriptBasic?

In the hfibo version is there unneeded data sitting in variables between recursions?

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 1:13 am

ScriptBasic wrote:
Mon Jun 17, 2019 11:39 pm
Remember what we are doing to languages by abusing them with Fibonacci isn't real world so when features start acting like pigs is because they weren't designed to be tortured in this way.
From my point of view using a computer to compute things seems very normal. At the same time, the real-world fashion of turning cars, telephones, televisions, light bulbs and refrigerators into computers seems abnormal. Though on the same planet, people clearly live in different worlds.

As stated in the original post, one of the goals of this thread is to compare how suitable various programming languages are for a beginner. A focus on what makes a good first and only programming language is why this thread is under the topic
General programming discussion
General programming chat and advice for beginners.
The reason for computing big Fibonacci numbers is because it is unreasonable to compare programming languages without actually using them.

Surprisingly, a number of bugs have been found in the available implementations of the various languages. These bugs have included crashing, performance problems, memory leaks and getting wrong answers. From a beginner's point of view, there is not much point in learning a particular language unless inexpensive high-quality compilers or interpreters exist for that language. In a way this was the point of Bill Gates' famous open letter concerning Microsoft Basic in which
Bill Gates wrote:Without good software and an owner who understands programming, a hobby computer is wasted.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 3:10 am

I think a language to learn programming should have intuitive syntax and strive for simplicity yet easy to extend with common libraries.

I'm looking at building a ScriptBsaic Extension Module Builder that would read a C header file(s) as input.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 4:54 am

Native integer fibo(78) doesn't seem to suffer from recursive activity but does give the wrong answer..

Code: Select all

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
    fk = hfibo(k)
    fk1 = hfibo(k + 1)
    if n and 1 = 0 then
      a = fk1 + fk1
      b = a - fk
      r = fk * b
    else
      a = fk * fk
      b = fk1 * fk1
      r = a + b
    end if
  end if
  hfibo = r
end function

print format("%.f\n",hfibo(78))

jrs@jrs-laptop:~/sb/GMP$ time scriba nfibo.sb
28174687879107533504249856

real	0m0.011s
user	0m0.011s
sys	0m0.000s
jrs@jrs-laptop:~/sb/GMP$ 
Doing the same with GMP HFIBO doesn't seem to matter and give the correct answer.

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 hfibo(78),"\n"


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

real	0m0.013s
user	0m0.008s
sys	0m0.004s
jrs@jrs-laptop:~/sb/GMP$ 
AIR's fibo at 78 without GMP.

Code: Select all

count = 78
a = 1
b = 0
p = 0
q = 1

WHILE count > 0
    IF (count % 2) = 0 THEN
        psq   = p * p
        qsq   = q * q
        twopq = p * q
        twopq = twopq * 2
        p     = psq + qsq
        q     = twopq + qsq
        count = count / 2
    ELSE
        bq    = b * q
        aq    = a * q
        ap    = a * p
        bp    = b * p
        a     = bq + aq
        a     = a + ap
        b     = bp + aq
        count = count - 1
    END IF
WEND

PRINT FORMAT("%.f\n",b)


jrs@jrs-laptop:~/sb/GMP$ time scriba fibo-78.sb
8944394323791464

real	0m0.009s
user	0m0.005s
sys	0m0.005s
jrs@jrs-laptop:~/sb/GMP$ 
And finally the GMP fibo function.

Code: Select all

DECLARE SUB fibo ALIAS "fibofunc" LIB "gmp"

PRINT fibo(78),"\n"


jrs@jrs-laptop:~/sb/GMP$ time scriba fibo.sb
8944394323791464

real	0m0.005s
user	0m0.001s
sys	0m0.004s
jrs@jrs-laptop:~/sb/GMP$ 
Even hfibo(7800) is respectable.

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 hfibo(7800),"\n"


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

real	0m0.127s
user	0m0.123s
sys	0m0.004s
jrs@jrs-laptop:~/sb/GMP$ 
Last edited by John_Spikowski on Tue Jun 18, 2019 6:35 am, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 6:19 am

ScriptBasic,
Native integer fibo(78) doesn't seem to suffer from recursive activity.
I would hope it doesn't.

fibo(78) with "normal" numbers only requires 6 local variables on the stack, 48 bytes. And it only needs to recur to a depth of about 6 or so
.That's about 300 bytes of stack plus whatever scriptbasic needs for return address etc.

That is very different to starting with a bunch of 1 million digit numbers, no doubt on the allocation heap, and recurring to a depth of 20 or so.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 8:26 am

Heater wrote:
Tue Jun 18, 2019 6:19 am
That is very different to starting with a bunch of 1 million digit numbers, no doubt on the allocation heap, and recurring to a depth of 20 or so.
If you compute the 4784969th Fibonacci number twice or thrice before exiting, does the memory use stabilise at 500MB, or does it continue to increase?

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 8:31 am

I would like to try some of these fibos with ScriptBasic running single threaded and using malloc as the memory manager.
SB Docs wrote: In single thread environment there is no need to use the locking mechanism. To get a single-thread version either you can edit this file (myalloc.c) or compile is using the option -DMTHREAD=0 The default compilation is multi threaded.
Update:

I compiled a single threaded version of ScriptBasic and there were no improvements in performance. I'm not sure if that is good or bad.

Code: Select all

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

real	0m4.790s
user	0m4.693s
sys	0m0.028s
jrs@jrs-laptop:~/sb/GMP$ 

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 5:16 pm

ScriptBasic,
I'm curious how JavaScript stores its recursive state that makes it more efficient than ScriptBasic?
Good question. I have no idea of the internal of Javascript engines but from what I have gathered:

JS uses a stack for return addresses and local variables, just like most other languages. Certainly we can rucurse too much and bomb out with a stack exhausted error.

But what is on the stack for those local variables? Probably some little object holding the type of the variable and a pointer to it's actual data.

Don't forget JS is dynamically typed, a variable can be changed from number to array to object to string etc on the fly.

By way of optimization JS engines treat all numbers as 64 bit floats, unless they become BigInts. Not only that it will store integers as 32 bits unless it determines they have overflowed 32 bits. Quite likely regular numbers are stored directly on the stack, bigger things like objects, arrays, strings being on the heap.

So, at the end of the day, it's not the stack and the recursive state here that is the problem. The actual state per call required is not very big and the recursion depth is only about 20. No, the problem is managing the memory allocation of all those huge numbers and strings. (Unless of course one is trying to keep megabyte sized objects on the stack itself!)
In the hfibo version is there unneeded data sitting in variables between recursions?
That is perhaps a key question.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 5:44 pm

ejolson,
If you compute the 4784969th Fibonacci number twice or thrice before exiting, does the memory use stabilise at 500MB, or does it continue to increase?
As a quick and simple experiment I put this:

Code: Select all

count = 0
WHILE count < 100
    PRINT "count", ": ", count, "\n"
    PRINT hfibo(4784969),"\n"
    count = count + 1
WEND
At the end of hfibo.sb

After count reached 17 iterations I could see it had consumed 75% of my 8GB RAM according to top.

Then my browser crashed. Then hfibo exited:

Code: Select all

count: 17
Segmentation fault (core dumped)
Conclusion: scribtbasic is not freeing the memory it allocates in a function when the function exits.

Possibly, I guess all those fibo results are not being freed as the loop goes around as well.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 6:13 pm

It might be interesting to see what the lengths of the variables are before dropping into another layer of recursion .

I feel AIR is properly freeing resouces in the GMP2 extension module.

To me the hfibo is like traveling in a motorhome with 5 miles to the gallon mileage rating.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 6:24 pm

At every level of recursion a fibo(n) is making calls to fibo(n/2) and fibo(n/2 + 1)

So the number of digits of the result of each recursion is half as many as the caller is calculating. 500000, 250000, 125000, 62500, 31250....etc.

They get small pretty fast.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 7:12 pm

Heater wrote:
Tue Jun 18, 2019 6:24 pm
At every level of recursion a fibo(n) is making calls to fibo(n/2) and fibo(n/2 + 1)

So the number of digits of the result of each recursion is half as many as the caller is calculating. 500000, 250000, 125000, 62500, 31250....etc.

They get small pretty fast.
That's not very precise. Here is a list of all fibonacci indexes used by the recursion to calculate fibo(4784969)
[0, 1, 2, 3, 4, 5, 8, 9, 10, 17, 18, 19, 35, 36, 37, 72, 73, 74, 145, 146, 147, 291, 292, 293, 583, 584, 585, 1167, 1168, 1169, 2335, 2336, 2337, 4671, 4672, 4673, 9344, 9345, 9346, 18690, 18691, 18692, 37381, 37382, 37383, 74764, 74765, 74766, 149529, 149530, 149531, 299059, 299060, 299061, 598120, 598121, 598122, 1196241, 1196242, 1196243, 2392484, 2392485, 4784969]
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: 1308
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 7:22 pm

It might be interesting to look at the source for the GMP fibo() function. It has become our gold standard so we should know what it's made of.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 7:46 pm

Why does it matter what GMP is made of?

We know it does not leak memory when used as prescribed.

Don't you recall the code I offered to help create the ScriptBasic extension to use GMP via decimal strings:
integer_string.c

Code: Select all

$ cat integer_strings.c
//
// An experiment in doing integer arithmetic using GMP with all numbers represented by strings.
//
// By heater.
// Modified June 11, 2019 to use base 32 strings for intermediate results.
//
#include <gmp.h>
#include <string.h>

#include "integer_strings.h"

// Functions letis, addis, subis and mulis do large integer arithmetic on integers represented by strings.
// WARNING: Not thread safe due to use of global op1, op2, res.

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

char* is_base(const char *s, int base) {
    mpz_set_str (op1, s, IS_BASE);
    char* res_string = mpz_get_str (0, base, op1);
    return res_string;
}

char* is_let(const char* s) {
    return strdup(s);
}

char* is_add(const char* s1, const char* s2) {
    mpz_set_str (op1, s1, IS_BASE);
    mpz_set_str (op2, s2, IS_BASE);
    mpz_add (res, op1, op2);  // result = x * y
    char* res_string = mpz_get_str (0, IS_BASE, res);
    return res_string;
}

char* is_sub(const char* s1, const char* s2) {
    mpz_set_str (op1, s1, IS_BASE);
    mpz_set_str (op2, s2, IS_BASE);
    mpz_sub (res, op1, op2);  // result = x * y
    char* res_string = mpz_get_str (0, IS_BASE, res);
    return res_string;
}

char* is_mul(const char* s1, const char* s2) {
    mpz_set_str (op1, s1, IS_BASE);
    mpz_set_str (op2, s2, IS_BASE);
    mpz_mul (res, op1, op2);  // result = x * y
    char* res_string = mpz_get_str (0, IS_BASE, res);
    return res_string;
}

void is_init() {
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

}

void is_clear() {
    mpz_clear(op1);
    mpz_clear(op2);
    mpz_clear(res);
}
fibo_strings.c

Code: Select all

//
// An experiment in doing integer arithmetic using GMP with all numbers represented by strings.
//
// By heater.
//
#include <stdio.h>
#include <stdlib.h>

#include "integer_strings.h"

char* fibos[3];

// Return the n'th Fibonacci number as a decimal string for integer n
char* fibo (int n) {
    char* res;
    if (n <= 2) {
        return is_let(fibos[n]);
    }

    int k = (n / 2);
    char* fk = fibo(k);
    char* fk1 = fibo(k + 1);
    char* a;
    char* b;
    if ((n % 2) == 0) {
        a = is_add(fk1, fk1);
        b = is_sub(a, fk);
        res = is_mul(fk, b);
    } else {
        a = is_mul(fk, fk);
        b = is_mul(fk1, fk1);
        res = is_add(a, b);
    }
    free(a);
    free(b);
    free(fk);
    free(fk1);
    return res;
}

int main(int argc, char* argv[]) {
    int n = 4784969;               // The first Fibonacci number with a million digits

    if (argc >= 2) {
        n = atoi(argv[1]);
    }

    is_init();

    fibos[0] = is_let("0");
    fibos[1] = is_let("1");
    fibos[2] = is_let("1");

    char* f = fibo(n);
    char* f10 = is_base(f, 10);
    puts(f10);
    free(f10);
    free(f);

    free(fibos[0]);
    free(fibos[1]);
    free(fibos[2]);

    is_clear();

    return (0);
}
And the discussion about memory leaks that provoked and the final leak free results (from the code above)

Code: Select all

$ valgrind ./fibo_strings
...
1815964864885353407167474856539211500699706378405156269
==2097==
==2097== HEAP SUMMARY:
==2097==     in use at exit: 0 bytes in 0 blocks
==2097==   total heap usage: 14,946,909 allocs, 14,946,909 frees, 100,979,959 bytes allocated
==2097==
==2097== All heap blocks were freed -- no leaks are possible
==2097==
==2097== For counts of detected and suppressed errors, rerun with: -v
==2097== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
All the GMP extension needs to do is ensure it does all the above.

And Scriba itself needs to free the returned strings appropriately of course.

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 7:53 pm

gkreidl,
That's not very precise.
I believe what I posted is very precise.

There are 1000000 digits in fibo(4784969)

There are 500000 digits in fibo(4784969 / 2)

There are 250000 digits in fibo(4784969 / 2 / 2)

There are 125000 digits in fibo(4784969 / 2 / 2 / 2)

...

That accounts for the sizes of the results of the fibo(k) calls in the algorithm.

The fibo(k + 1) calls will require pretty similar sized results.

I'll leave it as an exercise for the reader to calculate those.
Hint: http://www.maths.surrey.ac.uk/hosted-si ... section2.3

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 8:09 pm

Heater wrote:
Tue Jun 18, 2019 7:53 pm
gkreidl,
That's not very precise.
I believe what I posted is very precise.

There are 1000000 digits in fibo(4784969)

There are 500000 digits in fibo(4784969 / 2)

There are 250000 digits in fibo(4784969 / 2 / 2)

There are 125000 digits in fibo(4784969 / 2 / 2 / 2)

...

That accounts for the sizes of the results of the fibo(k) calls in the algorithm.

The fibo(k + 1) calls will require pretty similar sized results.

I'll leave it as an exercise for the reader to calculate those.
Hint: http://www.maths.surrey.ac.uk/hosted-si ... section2.3
Of course they are getting smaller, but there are more of them, not just "20 or so (recursions)" as you wrote some posts above. And usually 3 numbers of about half the size are required (not for the first recursion).
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

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

Re: A Final Fibonacci Challenge

Tue Jun 18, 2019 8:38 pm

Heater wrote:
Tue Jun 18, 2019 7:46 pm
And Scriba itself needs to free the returned strings appropriately of course.
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. In fact, since the out-of-memory killer also killed the web browser, even more memory was freed. People spend too much time browsing the web anyway.

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.
Last edited by ejolson on Wed Jun 19, 2019 2:31 pm, edited 2 times in total.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 12:32 am

I proved it wasn't the MyAlloc memory manager and it may be how ScriptBasic maintains its stack and recursion state. Surely needs more investigation.

The GMP library doesn't seem to be a factor.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 4:00 pm

gkreidl,
Of course they are getting smaller, but there are more of them, not just "20 or so (recursions)" as you wrote some posts above. And usually 3 numbers of about half the size are required (not for the first recursion).
What I wrote was correct:

"That is very different to starting with a bunch of 1 million digit numbers, no doubt on the allocation heap, and recurring to a depth of 20 or so"

Note that I speak of recursion "depth" not number of times fibo() gets called. These are very different things.

To be accurate fibo() gets calls get nested to a recursion depth of 24 where as it actually gets called 7,472,783 times!

I regard "24" as a member of the set "20 or so" :)

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 4:52 pm

Heater wrote:
Tue Jun 18, 2019 5:16 pm
No, the problem is managing the memory allocation of all those huge numbers and strings. (Unless of course one is trying to keep megabyte sized objects on the stack itself!)
An example of code that keeps all those megabyte-sized big numbers on the stack would be parallel.c and fibompi.c. If nothing is allocated on the heap, then there is no danger of leaks that result from forgetting to free heap-allocated memory. Allocating local variables on the stack has further advantages in threaded applications by being lock-free, O(1) and automatically NUMA aware (assuming the execution stacks were setup properly for the individual threads).
Last edited by ejolson on Wed Jun 19, 2019 4:59 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 4:54 pm

To be accurate fibo() gets calls get nested to a recursion depth of 24 where as it actually gets called 7,472,783 times!
And you don't see that as a problem?

How many WHILE loops do you think AIR's Fibo takes to come up with an answer?

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 5:05 pm

Heater wrote:
Wed Jun 19, 2019 4:00 pm
gkreidl,
Of course they are getting smaller, but there are more of them, not just "20 or so (recursions)" as you wrote some posts above. And usually 3 numbers of about half the size are required (not for the first recursion).
What I wrote was correct:

"That is very different to starting with a bunch of 1 million digit numbers, no doubt on the allocation heap, and recurring to a depth of 20 or so"

Note that I speak of recursion "depth" not number of times fibo() gets called. These are very different things.

To be accurate fibo() gets calls get nested to a recursion depth of 24 where as it actually gets called 7,472,783 times!

I regard "24" as a member of the set "20 or so" :)
My Fibonacci function is called 121 times; in 61 cases it returns an already calculated Fibonacci number, 60 times it really calculates a fibonacci number.

A while ago I also rewote the function in a non-recursive way. It pre-calculates the required indexes and then calculates the 60 Fibonacci numbers needed from bottom up. The required indexes are:
3, 4, 5, 8, 9, 10, 17, 18, 19, 35, 36, 37, 72, 73, 74, 145, 146, 147, 291, 292, 293, 583, 584, 585, 1167, 1168, 1169, 2335, 2336, 2337, 4671, 4672, 4673, 9344, 9345, 9346, 18690, 18691, 18692, 37381, 37382, 37383, 74764, 74765, 74766, 149529, 149530, 149531, 299059, 299060, 299061, 598120, 598121, 598122, 1196241, 1196242, 1196243, 2392484, 2392485, 4784969
0,1 and 2 are predefined.

The time difference is minimal and so I stayed with the recursive version.
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

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

Re: A Final Fibonacci Challenge

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.

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

Re: A Final Fibonacci Challenge

Wed Jun 19, 2019 5:26 pm

ScriptBasic wrote:
Wed Jun 19, 2019 4:54 pm
To be accurate fibo() gets calls get nested to a recursion depth of 24 where as it actually gets called 7,472,783 times!
And you don't see that as a problem?

How many WHILE loops do you think AIR's Fibo takes to come up with an answer?
Most of those calls are to compute Fibonacci numbers for small values of n. As a result they don't contribute very much to the runtime of the calculation in many other programming languages. I think the estimate was about 10% more for JavaScript compared to using memoization to eliminate the extra function calls.

Out of curiosity, how many function calls are there for the memoized version of the same recursive algorithm?

Return to “General programming discussion”