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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:52 pm

Feel free to bring this up with AIR. He wrote the GMP extension module not I.

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:57 pm

Heater wrote:
Thu Jul 11, 2019 8:48 pm
ejolson,

4784971964, what a sweet and enticing number.

So eerily similar to the now famous 4784969.

My C++ bint class is calling to me, it can handle a paltry 4784971964 as a parameter for n.

I must resist...I must resist...
I could be wrong, but my impression is that Karatsuba multiplication is not asymptotically fast enough to reasonably compute a billion-digit Fibonacci number. I think GMP switches to an FFT-based algorithm pretty early in the run, but again am not sure.

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 9:01 pm

Is there some place to report an issue. Like the issue tracker on Github?

Otherwise, the issue is reported here (above) and you know where Air is to notify him.

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 9:21 pm

ejolson,
I could be wrong, but my impression is that Karatsuba multiplication is not asymptotically fast enough to reasonably compute a billion-digit Fibonacci number. I think GMP switches to an FFT-based algorithm pretty early in the run, but again am not sure.
I don't think you are wrong. I think it's a valid concern.

A billion digits is a 1000 times bigger problem.

I might naively guess that it would take 10000 times longer. Of order 10000 seconds or three hours.

I am no doubt naively wrong!

But hey, if it took a week or a month and got the right answer I would be happy.

Given the way things work in my bint class I'd also be worried about running out of RAM. Even on my PC.

You may have noticed that I checked some FFT code into the C++ directory of the fibo challenge a long time ago. Just in case I wanted to experiment with FFT-based multiplication at some point. Not that I have much of a clue how that works just now.

I must resist... I'm supposed to be thinking about real work and putting bread on the table.... I must resist...

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 10:14 pm

I ran the AIR fibo you posted for over and hour in a BASH while loop and memory was straight
lined at 60% and never budged.

Code: Select all

import gmp2.bas

function fibo(n)
    a = 1
    b = 0
    p = 0
    q = 1

    while n > 0
        if (n % 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)
            n = n / 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)
            fibo  = b
            n = n - 1
        end if
    wend
end function

PRINT LEN(fibo(4784969)),"\n"

Code: Select all

while true; do
  time scriba testfibo.sb
done


1000000

real	0m5.669s
user	0m5.598s
sys	0m0.065s
1000000

real	0m5.683s
user	0m5.620s
sys	0m0.057s
1000000

real	0m5.713s
user	0m5.654s
sys	0m0.053s
1000000

real	0m5.962s
user	0m5.906s
sys	0m0.049s
1000000

real	0m6.036s
user	0m5.995s
sys	0m0.033s
[email protected]:~/sb/heater$ 

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 10:41 pm

@ejolson

My run matches, but a little slower.

Code: Select all

$ gcc -O3 -s fibo_gmp.c -o fibo -lgmp
$ time ./fibo >/tmp/f4784971964.out

real	8m0.614s
user	7m58.164s
sys	0m1.704s

$ head -c32 /tmp/f4784971964.out ; echo
11726845151952222692730258923866
$ tail -c32 /tmp/f4784971964.out       
6906960656263025463452143611773
$ md5sum /tmp/f4784971964.out 
3a4b122de35c728b0c212edc4ca95884  /tmp/f4784971964.out
$ 

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 11:35 pm

ScriptBasic,
I ran the AIR fibo you posted for over and hour in a BASH while loop and memory was straight
lined at 60% and never budged.
No. You did not. Look again. The code I posted has the while loop in the ScriptBasic.
https://www.raspberrypi.org/forums/view ... 5#p1497965

What you have done is to run your 1milfibo, which only calculates fibo once then exits, repeatedly. So of course no memory can be lost, it's all cleaned up every time your fibo finishes and exits ScriptBasic.

By the way, if that is 60% of 1G of RAM on a PI it's absurdly huge!

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 12:03 am

I started with a 52% use on my overloaded dev box. That's 8% use for the task. (3.8 GB of system memory)

Maybe the trick is to set max memory in the basic.conf file rather than unlimited. Then scriba won't be free to extend its caching of unused memory based on its internal reallocation usage.

Give that a try and see if you still see seg faults.

Since you're probably sourcing sb.sh, edit that script to set scriba's max memory value.

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 1:12 am

ScriptBasic wrote:
Fri Jul 12, 2019 12:03 am
Give that a try and see if you still see seg faults.
Even if it still leaks, with strict memory limits Script Basic will hopefully abort more gracefully and not risk that the Linux out-of-memory daemon deletes the wrong process.

Instead of buying a Pi 4B, I boarded a refurbished Boeing 747 and played Plants and Zombies for almost 7 hours straight--a different kind of digital apocalypse.

While beginning programmers of all levels are viewing this thread, it is worth remembering that many views are from web crawlers gathering big data to be processed by deep-learning neural networks. Therefore, it is essential to hide all plans for a second age of personal computing in the numerology of big Fibonacci numbers. Because, without a new apocrypha, the failing digital landlords may come to understand the freedom and individual liberation that comes from knowing how to code and subvert our discussion to re-establish their feudal order. This immediately leads to the question whether classic line-numbered Basic is expressive enough to compute billion-digit Fibonacci numbers or whether the golden age was doomed from the start.
Last edited by ejolson on Fri Jul 12, 2019 1:21 am, edited 3 times in total.

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 1:17 am

I gave my theory a shot and no joy.

I guess this will always remain a mystery.

Airr
Posts: 19
Joined: Sun Jun 16, 2019 5:17 pm

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 1:32 am

Heater wrote:
Thu Jul 11, 2019 11:35 pm
ScriptBasic,
I ran the AIR fibo you posted for over and hour in a BASH while loop and memory was straight
lined at 60% and never budged.
No. You did not. Look again. The code I posted has the while loop in the ScriptBasic.
https://www.raspberrypi.org/forums/view ... 5#p1497965

What you have done is to run your 1milfibo, which only calculates fibo once then exits, repeatedly. So of course no memory can be lost, it's all cleaned up every time your fibo finishes and exits ScriptBasic.

By the way, if that is 60% of 1G of RAM on a PI it's absurdly huge!
As configured, the module initializes 3 global variables via mpz_init()

Those are reused by the various calls to GMP:* as needed.

When the script exits, the 3 variables are cleared via mpz_clear().

So when you run your 'killer' loop, the mpz_clear() calls aren't invoked.

I'll be honest, I never anticipated someone running a test like you're doing, Heater.

Reading the gmp doc, I see that if mpz_clear() isn't called on a variable that is being re-used, it will (as far as I understand) leak.

So I'm thinking that I should call mpz_clear() at the end of each function in the module, to address this.

Before I do that, does this make sense? I won't be able to work on this until tomorrow evening my time.

AIR.

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 2:18 am

AIR,

Remember my first go at a GMP extension module I did the clear with each call?

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(fibofunc)
  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(fiboair)
  int fval, count;
  mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp;

  besARGUMENTS("i")
    &fval
  besARGEND

  count = fval;

  mpz_init_set_si(a, 1);
  mpz_init_set_si(b, 0);
  mpz_init_set_si(p, 0);
  mpz_init_set_si(q, 1);
  mpz_init(psq);
  mpz_init(qsq);
  mpz_init(twopq);
  mpz_init(bq);
  mpz_init(aq);
  mpz_init(ap);
  mpz_init(bp);

 while(count > 0) {
  if ((count % 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);
    count/=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);

    count--;
    }

}

char* res_string = mpz_get_str (0, 10, b);
besSET_RETURN_STRING(res_string);
free(res_string);

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
Paeryn
Posts: 2561
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 3:10 am

Airr wrote:
Fri Jul 12, 2019 1:32 am
Reading the gmp doc, I see that if mpz_clear() isn't called on a variable that is being re-used, it will (as far as I understand) leak.

So I'm thinking that I should call mpz_clear() at the end of each function in the module, to address this.

Before I do that, does this make sense? I won't be able to work on this until tomorrow evening my time.

AIR.
Calling mpz_clear() on those three variables won't help much, when a new value is assigned to one it will use whatever memory was already allocated, if the new value is too big it will reallocate enough to hold it. The only thing it won't do is reallocate to a smaller size.

So at worst those three variables could take up memory for a million digit number each, after that they would stay at a constant size until they are finally cleared. A second run of fibo(4784969) should require no extra memory for them as they already have enough memory allocated to hold their maximum values.

I started looking in to it but the code is so macro heavy it's hard to keep track of what's happening. I can feel a good session with gdb is looming. Conjunctivitis isn't helping and neither are these hot days.
She who travels light — forgot something.

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 4:59 am

Airr,
I'll be honest, I never anticipated someone running a test like you're doing, Heater.
That is what the engineers from Boeing said when I reported that their design of the Primary Flight Computers of the 777 fly by wire system could be made to lose control of all three of the the planes rudder actuators. They did not fix the problem until the test pilot lost control of the rudder on the second test flight of the plane. He was mad as hell. No really, true story.

I am almost certain that not calling mpz_clear() on those three globals should not be the problem. GMP will use them a again, reusing or reallocating the memory they hold onto as required. I vaguely remember making a simple little test of this already, can't find it just now. It should be easy fro you to do that test on a small test case.

I suspect there is some thing up with the allocation of memory for all those long strings holding the returned numbers. I suspect that custom allocator thing is "caching" loads of memory it has forgotten to reuse. I can imagine an ever growing linked list (or whatever structure) of returned results in there somewhere.

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

Re: A Final Fidonacci Challenge

Fri Jul 12, 2019 5:10 am

jojopi wrote:
Thu Jul 11, 2019 6:17 pm
I have not followed all of the past discussion on this problem, so apologies if this idea has been proposed before.

Without mentioning names, I recently became aware of a solution in BBC BASIC V on RISC OS. It does not give a fully correct result do to a slight bug in the carry handling. But what really stuck me was that it may be 53500 times faster than it should be.

It has also been very hot here; though certainly not 320 kelvins; I may be delirious; I think this idea originally came to me in a fever dream. It is only about 37 times faster than my first attempt, but it does have the advantage of not requiring gmpy2, so I think it is finally a legal solution for this thread.

Without further adon't, I present fido.py on a Pi2B:

Code: Select all

[email protected]:~ $ time python3 fido.py 4784969 |head -c32; time python3 fido.py 4784969 |tail -c32
10727395641800477229364813596225
real    0m1.312s
user    0m1.177s
sys     0m0.092s
4856539211500699706378405156269

real    0m1.229s
user    0m1.174s
sys     0m0.067s
And the code:

Code: Select all

import sys, math
n = int(sys.argv[1]) if len(sys.argv) > 1 else 4784969

from decimal import *
getcontext().prec = 2560
sqrt5 = Decimal(5).sqrt()
prep = ((sqrt5 + 1) / 2) ** n / sqrt5
limbs, getcontext().prec = 10**getcontext().prec, 1+int(Decimal.logb(prep))

cache = {x:x for x in range(2)}
def fido(n):
  if n in cache: return cache[n]
  k = (n + 1) // 2
  fj, fk = fido(k-1), fido(k)
  if n & 1: cache[n] = pow(fj,2,limbs) + pow(fk,2,limbs)
  else: cache[n] = (2*fj + fk) * fk % limbs
  return cache[n]

try: print((prep+fido(n)).quantize(Decimal(1)))
except IOError as e: pass # BrokenPipeError
I really hoped that this technique would allow for the calculation of much larger fidonacci numbers, but I found that Python's decimal module is not a true arbitrary-precision implementation. Actually it is intended for producing textbook-compatible results, and a million digits seems to be close to its limit.

Another, more obvious, drawback is that this kind of optimization does not convert well to trancendental problems such as the approximation of pi. I have to consider that a defect of this particular challenge, really.
Fast, but the results are all wrong. And it crashes on some numbers like 5 or 101, for example.
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: 3034
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fidonacci Challenge

Fri Jul 12, 2019 5:45 am

jojopi wrote:
Thu Jul 11, 2019 6:17 pm
I really hoped that this technique would allow for the calculation of much larger fidonacci numbers, but I found that Python's decimal module is not a true arbitrary-precision implementation. Actually it is intended for producing textbook-compatible results, and a million digits seems to be close to its limit.
As there appears to be some interest in the Fidonacci numbers, perhaps due to the possibility of a tasty rabbit pie, I've quoted the definition from earlier in this thread and provided a simple program to compute the first 20 such numbers.
ejolson wrote:
Sun Jun 16, 2019 3:19 pm
Heater wrote:
Sat Jun 15, 2019 6:25 pm
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.
Unfortunately, FidoBasic is not yet production quality (it may take 9 more years), so here is a program written in C.

Code: Select all

/*  fido.c -- Compute the first 20 Fidonacci numbers
    Written July 12, 2019  by Eric Olson  */

#include <stdio.h>
int main(){
    int v[3]={1,0,0};
    printf("%22s\n","age in months");
    printf("%5s %5s %5s %5s %9s\n",
        "n","new","one","two","fido(n)");
    for(int n=1;n<=20;n++){
        printf("%5d %5d %5d %5d %6d\n",
            n,v[0],v[1],v[2],v[0]+v[1]+v[2]);
        int s=v[1]+v[2];
        v[2]=v[1]; v[1]=v[0]; v[0]=s;
    }
    return 0;
}
The output follows:

Code: Select all

$ gcc fido.c 
$ ./a.out 
         age in months
    n   new   one   two   fido(n)
    1     1     0     0      1
    2     0     1     0      1
    3     1     0     1      2
    4     1     1     0      2
    5     1     1     1      3
    6     2     1     1      4
    7     2     2     1      5
    8     3     2     2      7
    9     4     3     2      9
   10     5     4     3     12
   11     7     5     4     16
   12     9     7     5     21
   13    12     9     7     28
   14    16    12     9     37
   15    21    16    12     49
   16    28    21    16     65
   17    37    28    21     86
   18    49    37    28    114
   19    65    49    37    151
   20    86    65    49    200
Note that each pair of rabbits only breed twice--at one and at two months--before being eaten at three months. If the next generation of Raspberry Pi computers were called Rabbit Pi, would that avoid the digital apocalypse or make it come sooner?
Last edited by ejolson on Fri Jul 12, 2019 3:54 pm, edited 8 times in total.

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 5:53 am

An observation I would like to point out is when I limited the amount of memory ScriptBasic could use, the program didn't run out of memory but system memory was still being consume. That points to GMP hogging the memory. IMHO

I think the best way to resolve this is take ScriptBasic out of the mix and do the fibo in C using GMP and see if it leaks.

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 6:24 am

ScriptBasic,
I think the best way to resolve this is take ScriptBasic out of the mix and do the fibo in C using GMP and see if it leaks.
Recall the example C code I provided for you that calculates using GMP but returns all results to the calling program (The fibo routine) as C strings. The code I suggested as an example to base the ScriptBasic extesion on.

It does not leak memory.

Therfore I very much doubt the problem is with GMP.

Do run that example C code for yourself if you are not convinced.

User avatar
davidcoton
Posts: 3780
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Digital Apocalypse and Fidonacci Rabbits

Fri Jul 12, 2019 9:43 am

ejolson wrote:
Fri Jul 12, 2019 5:45 am
If the next generation of raspberry pi computers were called rabbit pi, would that avoid the digital apocalypse or make it come sooner?
It depends on whether the Fidonacci rabbits are computer literate.
  1. If literate, the breeding rate will be slowed, so there will be fewer rabbits for the computers to control, so the Apocalypse will be delayed but not avoided.
  2. If not, more rabbits, more computer control of rabbits, Apocalypse sooner.
davidcoton wrote:
Tue Jul 09, 2019 10:27 pm
ejolson wrote:
Tue Jul 09, 2019 5:48 pm
What can be done to avoid the digital apocalypse?
There are two options.
  1. Use computers, learn to get the best out of them by, dare I mention the P word, programming.
  2. Ignore computers.
There are two outcomes. I think there is a 1 to 1 correspondance between the options above and these outcomes, but further research is needed.
  1. The computers will end up controlling the users
  2. The computers will end up controlling the non-users.
tl;dr Conclusion
Nothing.
Maybe RPF should start a campaign to boost the computer education of Rabbits?
Signature retired

User avatar
Paeryn
Posts: 2561
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 2:44 pm

I've done preliminary testing on scriba's memory usage on the fibo programs, it is definitely scriba that is keeping the memory, after 15 iterations gmp had only 3 big allocations (expected) but scriba had at least 68 1 million digit strings allocated. Got to go out now, I'll look into it later.
She who travels light — forgot something.

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

Re: Project Digital Apocalypse Not Now

Fri Jul 12, 2019 3:32 pm

Thanks for taking a developer interest in ScriptBasic!

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

Re: Digital Apocalypse and Fidonacci Rabbits

Fri Jul 12, 2019 8:42 pm

davidcoton wrote:
Fri Jul 12, 2019 9:43 am
ejolson wrote:
Fri Jul 12, 2019 5:45 am
If the next generation of Raspberry Pi computers were called Rabbit Pi, would that avoid the digital apocalypse or make it come sooner?
It depends on whether the Fidonacci rabbits are computer literate.
Indeed, but I suspect the more educated rabbits multiply faster, they might even use the Karatsuba algorithm.

I wrote a program in C to compute big Fidonacci numbers that looked like

Code: Select all

/*  bigfido.c -- Compute big Fidonacci numbers the slowest way possible.
    Written July 12, 2019 by Eric Olson */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//#define N 8188431
#define N 7499
#define SIZE 1048576

typedef struct {
    char *p; int n;
} fidonum;

fidonum fidosum(fidonum a,fidonum b){
    char c=0,*ap=a.p+a.n-1,*bp=b.p+b.n-1;
    while(*bp){
        if(*ap){
            *ap+=(*bp-'0')+c;
        } else {
            *ap+=*bp+c; a.p--; a.n++;
        }
        if(*ap>'9') {
            c=1; *ap-=10;
        } else {
            c=0;
        }
        ap--; bp--;
    }
    while(c){
        if(*ap){
            *ap+=c;
        } else {
            *ap+='0'+c; a.p--; a.n++;
        }
        if(*ap>'9') {
            c=1; *ap-=10;
        } else {
            c=0;
        }
        ap--;
    }
    return a;
}

fidonum fidoset(fidonum a,char *s){
    bzero(a.p,a.n);
    int n=strlen(s);
    a.p+=a.n-n; a.n=n;
    strcpy(a.p,s);
    return a;
}

int main(){
    fidonum v[4];
    for(int i=0;i<4;i++){
        char *p=malloc(SIZE); bzero(p,SIZE);
        v[i].p=p+(SIZE-1); v[i].n=0;
    }
    v[0]=fidoset(v[0],"1");
    v[1]=fidoset(v[1],"0");
    v[2]=fidoset(v[2],"0");
    for(int n=1;n<N;n++){
        fidonum s=fidosum(v[2],v[1]);
        v[2]=v[1]; v[1]=v[0]; v[0]=s;
    }
    v[3]=fidoset(v[3],"0");
    for(int i=0;i<3;i++){
        v[3]=fidosum(v[3],v[i]);
    }
    printf("%s\n",v[3].p);
    return 0;
}
The lead developer of FidoBasic took one look and growled, why didn't you use a fast doubling algorithm! The digital apocalypse will be over before that C code finishes. I replied, since FidoBasic is not production ready, I'm planning to do the optimized version in LOLCODE, the LOLCAT-inspired programming language.

That made the canine developer barking mad. Fido got to work and in 1 minute 37 seconds the file fido8188431.txt appeared on my Raspberry Pi Zero.

Code: Select all

$ ls -l fido8188431.txt 
-rw-r--r-- 1 ejolson users 1000001 Jul 12 13:00 fido8188431.txt
$ md5sum fido8188431.txt 
a795d70a0f7a2dc4a17fc898386c8eb6  fido8188431.txt
$ head -c32 fido8188431.txt ; echo
12160478847682398654606699316074
$ tail -c32 fido8188431.txt 
2299728056698240780649446110624
What better way is there to avoid the digital apocalypse other than eating rabbit pie while creating a fast Fidonacci code?

Airr
Posts: 19
Joined: Sun Jun 16, 2019 5:17 pm

Re: Project Digital Apocalypse Not Now

Sat Jul 13, 2019 12:55 am

ScriptBasic wrote:
Fri Jul 12, 2019 5:53 am
An observation I would like to point out is when I limited the amount of memory ScriptBasic could use, the program didn't run out of memory but system memory was still being consume. That points to GMP hogging the memory. IMHO

I think the best way to resolve this is take ScriptBasic out of the mix and do the fibo in C using GMP and see if it leaks.

Code: Select all

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

int main()
{
  int n = 78000;
  unsigned long  cnt=1;
  char *res;

  mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp;
  int count = n;

  mpz_init_set_si(a, 1);
  mpz_init_set_si(b, 0);
  mpz_init_set_si(p, 0);
  mpz_init_set_si(q, 1);
  mpz_init(psq);
  mpz_init(qsq);
  mpz_init(twopq);
  mpz_init(bq);
  mpz_init(aq);
  mpz_init(ap);
  mpz_init(bp);

  for(;;) {
    while(count > 0) {
        if ((count % 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);
          count/=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);

          count--;
        }

    }

    res = mpz_get_str(NULL,10,b);
    printf("Iteration: %lu\n",cnt);
    free(res);
    cnt++;
  }
  return 0;
}
Compiled with: gcc -O0 -s fib.c -ldl -lgmp -o fib

I let this run for 500747 iterations on my Pi (roughly 50 minutes). Memory usage remained more or less constant at around 55592, with minor fluctuations as sshd and avahi-daemon did their periodic 'thing'. (I'm running DietPi 'headless' btw).

My Pi got a bit hot (peaking at 77C) which is why I only let it go for a half million iterations (I was going to go for a million, but didn't want to fry the Pi in the process).

Please note that I gave full attribution to the original author in my post over at the allbasic forum, but here it is for posterity (and because it's the right thing to do):

Original code attribution: https://codegolf.stackexchange.com/a/9444 by Erik Haliewicz.

I realize that this isn't a line for line implementation of the SB module code (there are no mpz_set_str calls) but I think it shows that the cause of the leak is not the GMP library itself. And I tried to make it leak by not calling mpz_clear anywhere...it would probably show up in a debugger though.

AIR.

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

Re: Project Digital Apocalypse Not Now

Sat Jul 13, 2019 3:21 am

It is going to be interesting to find out what isn't getting released. I wonder if Peter creates a new memory block when a string size changes rather than using existing memory and adding blocks?

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

Re: Project Digital Apocalypse Not Now

Sat Jul 13, 2019 3:50 am

This doesn't appear to be be leaking. Maybe the problem is in the exchange of strings with GMP?

Code: Select all

SUB mk1mil
  LOCAL mb
  mb = ""
  FOR x = 1 TO 1000
    IF EVEN(x) THEN
      mb &= STRING(1000,"1")
    ELSE
      mb &= STRING(1000,"0")
    END IF
  NEXT
	PRINT LEN(mb),"\n"
END SUB


WHILE TRUE
  mk1mil()
WEND
Hippy approached this interface using the GMP pointer call set of functions. Maybe that is a better way?

Return to “General programming discussion”