## Liberation through Computer Literacy

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

### Re: A Final Fibonacci Challenge

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)
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

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.

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('? ');
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.

John_Spikowski
Posts: 1391
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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

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
\$
``````

John_Spikowski
Posts: 1391
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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+.

John_Spikowski
Posts: 1391
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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

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_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
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

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

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

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.

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

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

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

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

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

### Re: A Final Fibonacci Challenge

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

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

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.

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

### Re: A Final Fibonacci Challenge

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

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

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.

John_Spikowski
Posts: 1391
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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

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)
#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

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

John_Spikowski
Posts: 1391
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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

### Re: A Final Fibonacci Challenge

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)
#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

ScriptBasic wrote:
Tue Jun 11, 2019 5:38 pm

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

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.