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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 6:10 am

The Python wrappings for GMP are in the repository, both for Python 2 and 3:

Code: Select all

sudo apt-get install python-gmpy2 python3-gmpy2
We do not have to change the fibo code at all, just add imports and redefine the fibs dictionary and the string conversion for printing.
At the bottom of the script I have added the timing for the fib() function built into GMP.

Code: Select all

import time
import gmpy2
from gmpy2 import mpz

fibs = {0:mpz(0), 1:mpz(1), 2:mpz(1)}

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 you want to print the result directly:
##print(fibo(4784969).digits(10))

# Timing for fibo(4784969) and string conversion
t = time.time()
res = fibo(4784969)
print(time.time()-t)
t = time.time()
restr = res.digits(10)
print (time.time()-t)

# The same, but using the fib() function built into gmp
print('')
t = time.time()
res = gmpy2.fib(4784969)
print(time.time()-t)
t = time.time()
restr = res.digits(10)
print (time.time()-t)
The timings are about the same for Python 2 and 3.

Code: Select all

$ python3 fibogmp.py
0.43183255195617676
1.2910902500152588

0.26486945152282715
1.2686548233032227
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: 3568
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 6:28 am

Heater wrote:
Mon Jun 10, 2019 9:47 pm
All challenges have rules. There is no challenge without rules.
One of the liberating aspects of personal computing is that the rules are decided individually between each person and their computer. Anything else would violate the principle of subsidiarity. One of the signs of the digital apocalypse is when all the rules are decided by a single emotional but powerful deep-learning neural network.

The fourth Fibonacci roundup compares three codes based on taking powers of the golden ratio for the purpose of laughing out loud to the simplest algorithm possible. Since no new PL/I or C codes were available, Python did a double shift: first as Python 2 labeled fibo_phi2 and then as Python 3 labeled fibo_phi3.

Image

All timings were performed using the Raspberry Pi zero.

The Python code, though based on the fibo_phi.py code in the GitHub repository, was heavily modified as

Code: Select all

import math
from decimal import *

def fibo_phi(n):
    digits=int((n*math.log((1.0+math.sqrt(5.0))/2.0)\
        -math.log(math.sqrt(5.0)))/math.log(10.0)+1)
    extra=int(2*math.log(n)/math.log(2)+1)
    getcontext().prec=digits+extra
    sqrt5=Decimal.sqrt(Decimal(5))
    phi=(Decimal(1)+sqrt5)/Decimal(2)
    approx=(phi**Decimal(n))/sqrt5
    return Decimal.to_integral_value(approx)

while 1:
    n = int(input('? '))
    if n == 0:
        break
    print(fibo_phi(n))
The exact same code was used for fibo_phi2 and fibo_phi3. Under Python 2 the asymptotic time complexity appears to be O(n^2.8) which is astounding. It is differently surprising that the Python 3 code behaves as O(n^2) for intermediate values of n. This may indicate that the crossover point between schoolbook multiplication and fast multiplication was chosen suboptimally. Alternatively, the strange shapes of the Python curves could reflect the computational time used in computing the high-precision floating-point approximations for sqrt(5) and its reciprocal that are needed for the numerical approach when using the golden ratio.

Only the main routine of the Pascal code golden.pas required changes to be compatible with fibench. The main routine was changed as follows:

Code: Select all

var n:longint;
var phinum,z:ring5;

begin
    setlength(phinum.a,1); phinum.a[0]:=1;
    setlength(phinum.b,1); phinum.b[0]:=1;
    while true do begin
        write('? ');
        read(n);
        if n=0 then halt(0);
        z:=goldpow(phinum,n);
        pwrite(z.b)
    end
end.
The LOLCODE haifibo.lol is not based on the golden ratio. Neither did it employ the doubling formulas, Karatsuba multiplication nor any other fast algorithm. The code posted here was used unmodified. Although haifibo is the slowest code of the roundup for the values of n and Tn which appear on the graph, it would likely win over fibo_phi2 for larger values of n.
Last edited by ejolson on Tue Jun 11, 2019 7:33 am, edited 5 times in total.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 6:51 am

That is motivation to expand the ScritBasic GMP extension module.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 7:47 am

ScriptBasic,

If I understand correctly, you want to represent big integers in ScriptBasic with strings and use GMP under the hood to do the big arithmetic on them.

Here is a little experiment in C that does fibo exactly that way:

Code: Select all

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

int BASE = 10;

// Functions letis, addis, subis and mulis do large integer arithmetic on integers represented by strings.

char* letis(const char* s) {
    size_t size = strlen(s) + 1;
    char* res = malloc(size);
    strncpy (res, s, size);
    return res;
}

char* addis(const char* s1, const char* s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_add (res, op1, op2);  // result = x * y
    return mpz_get_str (0, 10, res);
}

char* subis(const char* s1, const char* s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_sub (res, op1, op2);  // result = x * y
    return mpz_get_str (0, 10, res);
}

char* mulis(const char* s1, const char* s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_mul (res, op1, op2);  // result = x * y
    return mpz_get_str (0, 10, res);
}

char* memo[3];

void init_memo() {
    memo[0] = letis("0");
    memo[1] = letis("1");
    memo[2] = letis("1");
}

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

    int k = (n / 2);
    char* fk = fibois(k);
    char* fk1 = fibois(k + 1);
    if ((n % 2) == 0) {
        res = mulis(fk, subis(mulis(fk1, "2"), fk));
    } else {
        res = addis(mulis(fk, fk), mulis(fk1, fk1));
    }
    free(fk);
    free(fk1);
    return res;
}

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

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

    init_memo();

    f = fibois(n);
    printf("%s\n", f);
    free(f);

    return (0);
}
It's a tad slower than using GMP directly:

Code: Select all

$ gcc -Wall -O3 -o fibo_strings fibo_strings.c -lgmp
$ time ./fibo_strings | head -c 32; time ./fibo_strings | tail  -c 32
10727395641800477229364813596225
real    0m9.014s
user    0m5.734s
sys     0m3.250s
4856539211500699706378405156269

real    0m9.137s
user    0m5.703s
sys     0m3.438s
$

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 8:00 am

Thanks Heater!

That is exactly what I needed to build out the GMP extension module for ScriptBasic.

Sure will be nice to do a 1 mil digit fibo in less than 5 hours on the RPi 3B+. :oops:

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 9:51 am

I got the GMP extension module built for ScriptBasic but at the moment it seg faults. I'm tired and going to bed.

My guess is I need to return the string like it's done in the fibo function which works.

interface.c

Code: Select all

/* GMP Extension Module
UXLIBS: -lgmp
*/

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


int BASE = 10;
char* memo[3];

static char* let(const char* s) {
    size_t size = strlen(s) + 1;
    char* res = malloc(size);
    strncpy (res, s, size);
    return 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[fval+1];
  memset(buf,0,1);
  mpz_t res;
  mpz_init(res);

  mpz_fib_ui(res, fval);

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

  besRETURN_STRING(buf);
besEND


besFUNCTION(letis)
  const char* s;

  besARGUMENTS("z")
    &s
  besARGEND

  size_t size = strlen(s) + 1;
  char* res = malloc(size);
  strncpy (res, s, size);
  besRETURN_STRING(res);

besEND


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

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

  mpz_t op1;
  mpz_t op2;
  mpz_t res;
  mpz_init(op1);
  mpz_init(op2);
  mpz_init(res);

  mpz_set_str (op1, s1, BASE);
  mpz_set_str (op2, s2, BASE);
  mpz_add (res, op1, op2);  // result = x * y
  besRETURN_STRING(mpz_get_str (0, 10, res));

besEND


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

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

  mpz_t op1;
  mpz_t op2;
  mpz_t res;
  mpz_init(op1);
  mpz_init(op2);
  mpz_init(res);

  mpz_set_str (op1, s1, BASE);
  mpz_set_str (op2, s2, BASE);
  mpz_sub (res, op1, op2);  // result = x * y
  besRETURN_STRING(mpz_get_str (0, 10, res));

besEND


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

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

  mpz_t op1;
  mpz_t op2;
  mpz_t res;
  mpz_init(op1);
  mpz_init(op2);
  mpz_init(res);

  mpz_set_str (op1, s1, BASE);
  mpz_set_str (op2, s2, BASE);
  mpz_mul (res, op1, op2);  // result = x * y
  besRETURN_STRING(mpz_get_str (0, 10, res));

besEND


besFUNCTION(init_memo)
  memo[0] = let("0");
  memo[1] = let("1");
  memo[2] = let("1");
  besRETURNVALUE = NULL;

besEND
gmp.bas

Code: Select all

MODULE GMP

DECLARE SUB ::FIBO     ALIAS "fibo"       LIB "gmp"
DECLARE SUB ::BI_LET   ALIAS "letis"      LIB "gmp"
DECLARE SUB ::BI_ADD   ALIAS "addis"      LIB "gmp"
DECLARE SUB ::BI_SUB   ALIAS "subis"      LIB "gmp"
DECLARE SUB ::BI_MUL   ALIAS "mulis"      LIB "gmp"
DECLARE SUB ::BI_MEMO  ALIAS "init_memo"  LIB "gmp"

END MODULE
gmpfibo.sb

Code: Select all

' Return the n'th Fibonacci number as a decimal string for integer n

IMPORT gmp.bas

SPLITA STRING(4,"0") BY "" To memo

FUNCTION fibois(n)
  IF n <= 2 THEN
    fibis = GMP::BI_LET(memo[n])
  END IF

  k = (n / 2)
  fk = fibois(k)
  fk1 = fibois(k + 1)
  IF n % 2 = 0 THEN
    res = GMP::BI_MUL(fk, GMP::BI_SUB(GMP::BI_MUL(fk1, "2"), fk))
  ELSE
    res = GMP::BI_ADD(GMP::BI_MUL(fk,fk), GMP::BI_MUL(fk1, fk1))
  END IF
  fibois = res
END FUNCTION


n = 4784969
res = ""

GMP::BI_MEMO()

k = (n / 2)
f = fibois(n)
PRINT LEN(f),"\n"

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 12:13 pm

Heater wrote:
Tue Jun 11, 2019 7:47 am
If I understand correctly, you want to represent big integers in ScriptBasic with strings and use GMP under the hood to do the big arithmetic on them.
As recommended in the posts

viewtopic.php?f=62&t=227343&start=1825#p1458373
viewtopic.php?f=31&t=240287&start=250#p1478372

it is faster to store intermediate results as base-2^k strings and only convert to base 10 when printing them. Here is a slight modification of the previous code to use base 32.

Code: Select all

//
// 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 <stdio.h>
#include <gmp.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>

int BASE = 32;

// Functions letis, addis, subis and mulis do large integer arithmetic on integers represented by strings.

void writeis(const char *s) {
    mpz_t op1;
    mpz_init(op1);
    mpz_set_str (op1, s, BASE);
    char *buf=mpz_get_str (0, 10, op1);
    puts(buf);
    free(buf);
}

char* letis(const char* s) {
    size_t size = strlen(s) + 1;
    char* res = malloc(size);
    strncpy (res, s, size);
    return res;
}

char* addis(const char* s1, const char* s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_add (res, op1, op2);  // result = x * y
    return mpz_get_str (0, BASE, res);
}

char* subis(const char* s1, const char* s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_sub (res, op1, op2);  // result = x * y
    return mpz_get_str (0, BASE, res);
}

char* mulis(const char* s1, const char* s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_mul (res, op1, op2);  // result = x * y
    return mpz_get_str (0, BASE, res);
}

char* memo[3];

void init_memo() {
    memo[0] = letis("0");
    memo[1] = letis("1");
    memo[2] = letis("1");
}

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

    int k = (n / 2);
    char* fk = fibois(k);
    char* fk1 = fibois(k + 1);
    if ((n % 2) == 0) {
        res = mulis(fk, subis(mulis(fk1, "2"), fk));
    } else {
        res = addis(mulis(fk, fk), mulis(fk1, fk1));
    }
    free(fk);
    free(fk1);
    return res;
}

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

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

    init_memo();

    f = fibois(n);
    writeis(f);
//  printf("%s\n", f);
    free(f);

    return (0);
}
Running on an AMD A6-9225, this modification results in a program that runs in 64% of the time needed by the original.

Code: Select all

$ time ./original >original.txt

real    0m7.675s
user    0m6.833s
sys     0m0.806s
$ time ./base32 >base32.txt

real    0m4.955s
user    0m4.159s
sys     0m0.769s
$ diff original.txt base32.txt
$ md5sum base32.txt 
c926caa99ed1e30fe0d3c966da901738  base32.txt
Similar results can be obtained for base 16 and base 8.

I had expected a much greater performance increase. Does anyone know where the rest of the overhead comes from?
Last edited by ejolson on Tue Jun 11, 2019 2:42 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 2:19 pm

ejolson,
As recommended in the posts ... it is faster to store intermediate results as base-2^k strings and only convert to base 10 when printing them.
Oh man. Giii's a break. I wrote that first thing in the morning, before morning coffee, with my eyes still half closed, more concerned about optimizing breakfast. Here we are, speeding up ScriptBasic's fibo from 5 hours to 9 seconds and you are fussing about 64% ! :)

Anyway, cool. I'm only seeing a 23% speed up, to 6.9 seconds on my PC.

Code is in the repo: https://github.com/ZiCog/fibo_4784969/b ... _strings.c

Before anyone questions that, its there as an experiment in helping ScriptBasic perform properly.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 3:03 pm

Heater wrote:
Tue Jun 11, 2019 2:19 pm
ejolson,
As recommended in the posts ... it is faster to store intermediate results as base-2^k strings and only convert to base 10 when printing them.
Oh man. Giii's a break. I wrote that first thing in the morning, before morning coffee, with my eyes still half closed, more concerned about optimizing breakfast. Here we are, speeding up ScriptBasic's fibo from 5 hours to 9 seconds and you are fussing about 64% ! :)

Anyway, cool. I'm only seeing a 23% speed up, to 6.9 seconds on my PC.
Since you already had the BASE define in place, I assumed you had done the experiment with different bases already.

It seems I misspoke, the base-32 code is not 64% faster in my test but instead finishes in 64% the run-time needed by the original. That's even less of a speedup than it sounded before. I've updated my previous post to make this clear. Actually, I'm surprised the base-32 code isn't 10 to 100 times faster and am thinking of profiling it.

It is interesting that almost a second of time is spent in system mode during the run, presumably because of memory allocation overhead. I see the code attempts to free the memory it allocates. Have you checked for memory leaks?

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 3:14 pm

Memory leaks?

I can't get any sanitizer to run this without crashing out after it has printed the result:

Code: Select all

$ gcc -fsanitize=leak -Wall -O0 -o fibo_strings fibo_strings.c -lgmp
$ ./fibo_strings 12
144
==26326==LeakSanitizer has encountered a fatal error.
==26326==HINT: For debugging, try setting environment variable LSAN_OPTIONS=verbosity=1:log_threads=1
==26326==HINT: LeakSanitizer does not work under ptrace (strace, gdb, etc)
$

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 3:31 pm

There are lots of messages like this, an error I have not seen before (that's without any warning options)
Looks perfectly correct to me, but strdup() instead of letis() might be simpler.
gcc -O3 fibo_strings.c -o fibo -lgmp

In function 'letis',
inlined from 'fibois' at fibo_strings.c:88:10,
inlined from 'fibois.part.0' at fibo_strings.c:93:14:
fibo_strings.c:30:2: warning: '__builtin_strncpy' specified bound depends on the length of the source argument [-Wstringop-overflow=]
30 | strncpy (res, s, size);
| ^~~~~~~
fibo_strings.c: In function 'fibois.part.0':
fibo_strings.c:28:16: note: length computed here
28 | size_t size = strlen(s) + 1;
| ^~~~~~~~~

Also its complaining about atol() in main (narrowing), probably atoi() is better.
Last edited by jahboater on Tue Jun 11, 2019 3:36 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 3:36 pm

jahboater ,
strdup() might be simpler
Oh yeah. Durp, durp, dup dup.

Change adopted.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 3:39 pm

That's an odd message. It compiles cleanly with strdup() instead of letis() - yet its doing exactly the same thing.
And should it produce warnings like that when no -W options are in use?

Running it with valgrind ...

Still running it with valgrind ...

Clean.

Code: Select all

==4806== HEAP SUMMARY:
==4806==     in use at exit: 607,744,744 bytes in 41,100,305 blocks
==4806==   total heap usage: 82,201,881 allocs, 41,101,576 frees, 940,636,321 bytes allocated
==4806== 
==4806== LEAK SUMMARY:
==4806==    definitely lost: 607,744,423 bytes in 41,100,299 blocks
==4806==    indirectly lost: 83 bytes in 1 blocks
==4806==      possibly lost: 216 bytes in 1 blocks
==4806==    still reachable: 22 bytes in 4 blocks
==4806==         suppressed: 0 bytes in 0 blocks
==4806== Rerun with --leak-check=full to see details of leaked memory
==4806== 
==4806== For counts of detected and suppressed errors, rerun with: -v
==4806== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:24 pm

jahboater wrote:
Tue Jun 11, 2019 3:39 pm
Running it with valgrind ...

Still running it with valgrind ...

Clean.

Code: Select all

==4806== HEAP SUMMARY:
==4806==     in use at exit: 607,744,744 bytes in 41,100,305 blocks
==4806==   total heap usage: 82,201,881 allocs, 41,101,576 frees, 940,636,321 bytes allocated
==4806== 
==4806== LEAK SUMMARY:
==4806==    definitely lost: 607,744,423 bytes in 41,100,299 blocks
==4806==    indirectly lost: 83 bytes in 1 blocks
==4806==      possibly lost: 216 bytes in 1 blocks
==4806==    still reachable: 22 bytes in 4 blocks
==4806==         suppressed: 0 bytes in 0 blocks
==4806== Rerun with --leak-check=full to see details of leaked memory
==4806== 
==4806== For counts of detected and suppressed errors, rerun with: -v
==4806== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
I've never used valgrind. How does
valgrind wrote:definitely lost: 607,744,423 bytes in 41,100,299 blocks
indicate no memory leaks? Or was your declaration of "clean" meant to be humorous?
Last edited by ejolson on Tue Jun 11, 2019 5:26 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:25 pm

How did you get that warning " warning: '__builtin_strncpy' specified bound depends on the length of the source argument ..."? I can't get GCC to 8.2 to do that.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:27 pm

There'll be leaks abound due to code like this

Code: Select all

    res = mulis(fk, subis(mulis(fk1, "2"), fk));
Where the inner mulis allocates a string for the result which is passed to subis, when subis returns nobody has freed the string and its address is lost. Same with the string that subis returns and passes to mulis.
She who travels light — forgot something.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:28 pm

Heater wrote:
Tue Jun 11, 2019 5:25 pm
How did you get that warning " warning: '__builtin_strncpy' specified bound depends on the length of the source argument ..."? I can't get GCC to 8.2 to do that.
I'm getting that warning in 9.1 and ignoring it because that's not the problem. Do you think declaring the mpz_t variables static might help?

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:32 pm

ejolson wrote:
Tue Jun 11, 2019 5:24 pm
I've never used valgrind. How does
valgrind wrote:definitely lost: 607,744,423 bytes in 41,100,299 blocks
indicate no memory leaks? Or was your declaration of "clean" meant to be humorous?
See the first line (the heap summary):

in use at exit: 607,744,744 bytes in 41,100,305 blocks

When a process exits all allocated memory is discarded and reclaimed by the OS; the address space dissapears. True for all operating systems except Novel's Netware.
Few programs bother to release memory before calling exit as may add considerably to the complexity and achieves nothing.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:35 pm

Oh man. Giii's a break. I wrote that first thing in the morning, before morning coffee, with my eyes still half closed, more concerned about optimizing breakfast. Here we are, speeding up ScriptBasic's fibo from 5 hours to 9 seconds and you are fussing about 64% ! 
Did you get the ScriptBasic extension module to run or was your comment based on your C code and assuming once the code runs SB will be looking at 9 seconds? I see you added a new function. writeis.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:35 pm

What is this all about? From clang 8.0:

Code: Select all

$ clang -fsanitize=memory -fno-omit-frame-pointer -g -o fibo_strings -O0 fibo_strings.c -lgmp
$ ./fibo_strings 100
Uninitialized bytes in __interceptor_strlen at offset 0 inside [0x701000000080, 2)
==26486==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0x7f7aabf946f4 in __gmpz_set_str (/usr/lib/x86_64-linux-gnu/libgmp.so.10+0x246f4)
    #1 0x4a1298 in addis /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:42:5
    #2 0x4a1d8a in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:97:15
    #3 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #4 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #5 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #6 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #7 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #8 0x4a201d in main /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:114:9
    #9 0x7f7aab0802e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #10 0x41e219 in _start (/mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings+0x41e219)

SUMMARY: MemorySanitizer: use-of-uninitialized-value (/usr/lib/x86_64-linux-gnu/libgmp.so.10+0x246f4) in __gmpz_set_str
Exiting
$
That seems to be inside GMP.

I get the same error as GCC wen using asan with clang.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:36 pm

ejolson wrote:
Tue Jun 11, 2019 5:28 pm
Heater wrote:
Tue Jun 11, 2019 5:25 pm
How did you get that warning " warning: '__builtin_strncpy' specified bound depends on the length of the source argument ..."? I can't get GCC to 8.2 to do that.
I'm getting that warning in 9.1 and ignoring it because that's not the problem. Do you think declaring the mpz_t variables static might help?
Remove the letis() function and replace all the calls to it with strdup(), then it compiles cleanly with GCC 9.1

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:38 pm

Can you post your code?

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:39 pm

Heater wrote:
Tue Jun 11, 2019 5:35 pm
What is this all about? From clang 8.0:

Code: Select all

$ clang -fsanitize=memory -fno-omit-frame-pointer -g -o fibo_strings -O0 fibo_strings.c -lgmp
$ ./fibo_strings 100
Uninitialized bytes in __interceptor_strlen at offset 0 inside [0x701000000080, 2)
==26486==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0x7f7aabf946f4 in __gmpz_set_str (/usr/lib/x86_64-linux-gnu/libgmp.so.10+0x246f4)
    #1 0x4a1298 in addis /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:42:5
    #2 0x4a1d8a in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:97:15
    #3 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #4 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #5 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #6 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #7 0x4a1ab0 in fibois /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:92:16
    #8 0x4a201d in main /mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings.c:114:9
    #9 0x7f7aab0802e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #10 0x41e219 in _start (/mnt/c/Users/heater/Documents/fibo_4784969/c/fibo_strings+0x41e219)

SUMMARY: MemorySanitizer: use-of-uninitialized-value (/usr/lib/x86_64-linux-gnu/libgmp.so.10+0x246f4) in __gmpz_set_str
Exiting
$
That seems to be inside GMP.

I get the same error as GCC wen using asan with clang.
Interesting. The sanitizers should not be checking GMP, only your code that's been instrumented by the compiler????

Its not like valgrind, that blindly checks everything.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:43 pm

ScriptBasic wrote:
Tue Jun 11, 2019 5:38 pm
Can you post your code?

Code: Select all

//
// 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 <stdio.h>
#include <gmp.h>
#include <stdlib.h>
#include <string.h>

// Number base used for GMP
static const int BASE = 32;

// Functions addis, subis and mulis do large integer arithmetic on integers represented by strings.

static void writeis(char const * const s) {
    mpz_t op1;
    mpz_init(op1);
    mpz_set_str (op1, s, BASE);
    char * const buf = mpz_get_str(0, 10, op1);
    puts(buf);
    free(buf);
}

static char* addis(char const * const s1, char const * const s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_add (res, op1, op2);  // result = x * y
    return mpz_get_str (0, BASE, res);
}

static char* subis(char const * const s1, char const * const s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_sub (res, op1, op2);  // result = x * y
    return mpz_get_str (0, BASE, res);
}

static char* mulis(char const * const s1, char const * const s2) {
    mpz_t op1;
    mpz_t op2;
    mpz_t res;
    mpz_init(op1);
    mpz_init(op2);
    mpz_init(res);

    mpz_set_str (op1, s1, BASE);
    mpz_set_str (op2, s2, BASE);
    mpz_mul (res, op1, op2);  // result = x * y
    return mpz_get_str (0, BASE, res);
}

static char* memo[3];

static void init_memo() {
    memo[0] = strdup("0");
    memo[1] = strdup("1");
    memo[2] = strdup("1");
}

// Return the n'th Fibonacci number as a decimal string for integer n
static char* fibois ( const int n ) {
    char* res;
    if (n <= 2) {
        return strdup(memo[n]);
    }

    int k = (n / 2);
    char* const fk = fibois(k);
    char* const fk1 = fibois(k + 1);
    if ((n % 2) == 0) {
        res = mulis(fk, subis(mulis(fk1, "2"), fk));
    } else {
        res = addis(mulis(fk, fk), mulis(fk1, fk1));
    }
    free(fk);
    free(fk1);
    return res;
}

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

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

    init_memo();

    char * const f = fibois(n);
    writeis(f);
}

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 5:45 pm

ScriptBasic,

This is all with the experimental.demo C code I made. Better to check that out properly before going down the ScriptBasic extension rabbit hole.

Return to “General programming discussion”