# All BASIC

## BASIC User Group => Code Challenges => Topic started by: jalih on April 14, 2019, 09:25:39 PM

Title: fibonacci(4784969)
Post by: jalih on April 14, 2019, 09:25:39 PM
After following John on Rasberry Pi Forums and seen some people obsessed with fibonacci(4784969), I decided to try calculating that million digit number using 8th. Actually it was really easy and result is really fast. I used locals, so getting rid of those and utilizing stack should give even better performance.

Code: [Select]
`\\ Fibonacci with million digits\: fibo-loop  "a" w:@ "b" w:@ 2 n:* "a" w:@ n:- n:* "d" w:!  "a" w:@ dup n:* "b" w:@ dup n:* n:+ "e" w:!  "d" w:@ "a" w:!  "e" w:@ "b" w:!  r@ swap n:shr 1 n:band if    "a" w:@ "b" w:@ n:+ "c" w:!    "b" w:@ "a" w:!    "c" w:@ "b" w:!  then ;locals:: fibo  >r  0 "a" w:!  1 "b" w:!  ' fibo-loop 0 31 loop-  rdrop  "a" w:@ ;: app:main  d:msec >r  4784969 fibo  d:msec r> n:- >r  "%.f" strfmt \ Convert result to just an 'int' string.  s:len . " digits:" . cr  dup 40 s:lsub . " upper 40 digits" . cr  40 s:rsub . " lower 40 digits" . cr  r> . " msec" . cr  bye ;`
Result is:

Code: [Select]
`C:\temp>8th fibo.8th1000000 digits:1072739564180047722936481359622500432190 upper 40 digits3407167474856539211500699706378405156269 lower 40 digits279 msec`
Title: Re: fibonacci(4784969)
Post by: John on April 15, 2019, 08:38:20 AM
It seems you have the best time so far.

Thanks for taking on the challenge!
Title: Re: fibonacci(4784969)
Post by: jalih on April 15, 2019, 08:50:36 AM
It seems you have the best time so far.

Here is a little bit faster (a couple of msec) version. I eliminated all local variables and used just stack.

Code: [Select]
`\\ Fibonacci with million digits\: fibo-loop  >r                             \ Put loop counter on r-stack  \ a b  2dup 2 n:*                     \ a b a 2b  over n:-                       \ a b a (2b-a)  n:* -rot                       \ d=(2b-a)*a a b  dup n:* swap dup n:* n:+       \ d=(2b-a)*a e=b*b+a*a  r> r@ swap n:shr 1 n:band if    dup  \ a b b    rot  \ b b a    n:+  \ b c=b+a  then ;: fibo  \  n -- fibo(n)  >r    \ Put n on r-stack  F0 F1   \ a b  ' fibo-loop 0 31 loop-  rdrop  drop ;  \ a: app:main  d:msec >r  4784969 fibo  d:msec r> n:- >r  n:bfloat "%.f" strfmt \ Convert result to just an 'int' string.  s:len . " digits:" . cr  dup 40 s:lsub . " upper 40 digits" . cr  40 s:rsub . " lower 40 digits" . cr  r> . " msec" . cr  bye ;`
Title: Re: fibonacci(4784969)
Post by: jalih on April 19, 2019, 09:05:47 AM
I packaged a binary (https://www.dropbox.com/s/k2spqhywulp05sg/fibo_rpi32.zip?dl=0) for RPI. Could someone test it with real Rasberry Pi hardware? I would love to know how fast it is.
Title: Re: fibonacci(4784969)
Post by: John on April 19, 2019, 09:41:04 AM
Works on my Raspberry Pi 3 B.

pi@RPi3B:~/rpi8th/rpi32 \$ time ./fibo
1000000 digits:
1072739564180047722936481359622500432190 upper 40 digits
3407167474856539211500699706378405156269 lower 40 digits
1946 msec

real   0m2.090s
user   0m2.044s
sys   0m0.040s
pi@RPi3B:~/rpi8th/rpi32 \$

Title: Re: fibonacci(4784969)
Post by: John on April 19, 2019, 02:21:04 PM
I tied to convert a Python version of the Fibonacci code challenge to ScriptBasic but I keep getting a seg fault and not sure why.

Code: Python
1. fiboA = 0
2. fiboB = 0
3. def Fibonacci(n):
4.   global fiboA
5.   global fiboB
6.   if n == 0:
7.     fiboA = 0
8.     fiboB = 1
9.     return 0
10.   Fibonacci(n // 2)
11.   if (n % 2) == 0 :
12.     t = fiboB + fiboB - fiboA
13.     fiboA = fiboA * t
14.     fiboB = fiboB * t
15.     if ( n % 4 ) == 0 : fiboB = fiboB - 1
16.     else              : fiboB = fiboB + 1
17.   else:
18.     t = fiboA + fiboA + fiboB
19.     fiboA = fiboA * t
20.     fiboB = fiboB * t
21.     if (n % 4) == 1 : fiboA = fiboA + 1
22.     else            : fiboA = fiboA - 1
23.   return fiboA
24.
25. print Fibonacci(24) # => 46368
26.

jrs@jrs-laptop:~/sb/examples/test\$ time python hippy.py
46368

real   0m0.025s
user   0m0.020s
sys   0m0.005s
jrs@jrs-laptop:~/sb/examples/test\$

print(Fast_Fibonacci(4784969))

real   0m35.497s
user   0m35.186s
sys   0m0.025s
jrs@jrs-laptop:~/sb/examples/test\$

Code: Script BASIC
1. fiboA = 0
2. fiboB = 0
3. function Fast_Fibonacci(n)
4.   if n = 0 then
5.     fiboA = 0
6.     fiboB = 1
7.     Fast_Fibonacci = 0
8.   end if
9.   Fast_Fibonacci(n\2)
10.   if (n % 2) = 0 then
11.     t = fiboB + fiboB - fiboA
12.     fiboA *= t
13.     fiboB *= t
14.     if (n % 4) = 0 then
15.       fiboB -= 1
16.     else
17.       fiboB += 1
18.     end if
19.   else
20.     t = fiboA + fiboA + fiboB
21.     fiboA *= t
22.     fiboB *= t
23.     if (n % 4) = 1 then
24.       fiboA += 1
25.     else
26.       fiboA -= 1
27.     end if
28.   end if
29.   Fast_Fibonacci = fiboA
30. end function
31.
32. ' print(Fast_Fibonacci(4784969))
33.
34. print Fast_Fibonacci(24),"\n"
35.

Any ideas?
Title: Re: fibonacci(4784969)
Post by: John on April 19, 2019, 02:50:13 PM
Seems I had a typo in my code.

Code: Script BASIC
1. fiboA = 0
2. fiboB = 0
3. function Fibonacci(n)
4.   if n then
5.     Fibonacci(n \ 2)
6.     if n and 1 then
7.       t = fiboA + fiboA + fiboB
8.       fiboA *= t
9.       fiboB *= t
10.       if (n and 3) = 1 then
11.         fiboA += 1
12.       else
13.         fiboA -= 1
14.       end if
15.     else
16.       t = fiboB + fiboB - fiboA
17.       fiboA *= t
18.       fiboB *= t
19.       if n and 3 then
20.         fiboB += 1
21.       else
22.         fiboB -= 1
23.       end if
24.     end if
25.   else
26.     fiboA = 0
27.     fiboB = 1
28.   end if
29.   Fibonacci = fiboA
30. end function
31.
32. print Fibonacci(24),"\n"
33.

jrs@jrs-laptop:~/sb/examples/test\$ time scriba hippy.sb
46368

real   0m0.011s
user   0m0.007s
sys   0m0.004s
jrs@jrs-laptop:~/sb/examples/test\$ time scriba hippy.sb    <-- Fibonacci(4784969)
-nan

real   0m0.010s
user   0m0.004s
sys   0m0.006s
jrs@jrs-laptop:~/sb/examples/test\$
Title: Re: fibonacci(4784969)
Post by: AIR on April 19, 2019, 04:52:01 PM
Another way of doing it in Python.  I didn't write this, and don't fully understand all the calculations (I think it uses a MATRIX), but it's the fastest implementation I found.

Code: Python
1. #!/usr/bin/env python
2.
3. def fib(n):
4.     v1, v2, v3 = 1, 1, 0
5.     for rec in bin(n)[3:]:
6.         calc = v2*v2
7.         v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
8.         if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
9.     return v2
10.
11. res = fib(4784969)
12.

On my Macbook Pro, 2.5Ghz 4 Core i7:
\$ time ./fibo.py

real   0m1.100s
user   0m1.080s
sys   0m0.016s

On my RasPi:
\$ time ./fibo.py

real   0m25.947s
user   0m25.894s
sys   0m0.050s

AIR.
Title: Re: fibonacci(4784969)
Post by: John on April 19, 2019, 06:00:43 PM
The best ScriptBasic can do on 64 bit is Fibonacci(92) without overflowing  MAXINT.

Time:  0.009 seconds.
Title: Re: fibonacci(4784969)
Post by: AIR on April 20, 2019, 10:04:47 AM
Jali,

Can you code this so that it outputs the actual Fibonacci number for 1000000?
Title: Re: fibonacci(4784969)
Post by: jalih on April 20, 2019, 10:55:55 AM
Can you code this so that it outputs the actual Fibonacci number for 1000000?

Sure, here (https://www.dropbox.com/s/z6gg1ohdju4bdpt/fibo.zip?dl=0) is a version that takes numbers as command-line parameter to calculate fibonacci number. Included is source + binaries for most systems.
Title: Re: fibonacci(4784969)
Post by: jalih on April 20, 2019, 11:04:43 AM
Here is a REXX version that might be easier to read than my 8th version:

Code: [Select]
`numeric digits 1000000say fibo(4784969)exitfibo:  parse arg n  a = 0  b = 1  do i = 1 to length(strip(d2b(n), 'L','0'))    d = a * (b * 2 - a)    e = a * a + b * b    a = d    b = e    if substr(strip(d2b(n), 'L','0'), i, 1) = '1' then      do        c = a + b        a = b        b = c      end  end  return ad2b: return x2b(d2x(arg(1)))`
Title: Re: fibonacci(4784969)
Post by: John on April 20, 2019, 12:58:01 PM
AIR,

Attached is the output to a file of the fibonacci(4784969) challenge. (from the following C code - gmp assisted)

I tried to add this as a function to the tools extension module. I have gmp-dev installed. The desired result of the function would be a SB string.

Code: C
1. #include <stdio.h>
2. #include <gmp.h>
3. #include <stdlib.h>
4.
5. void fibo(int n) {
6.     mpz_t res;
7.     mpz_init(res);
8.
9.     mpz_fib_ui(res, n);
10.
11.     gmp_printf( "%Zd\n", res );
12. }
13.
14. int main(int argc, char* argv[] )
15. {
16.     int n = 4784969;   // The first Fibonacci number with a million digits
17.
18.     if (argc >= 2) {
19.         n = atol(argv[1]);
20.     }
21.
22.     fibo(n);
23.     return (0);
24. }
25.

Can you give me a hand with this? Maybe creating a new gmp extention module is a better way to go.

Title: Re: fibonacci(4784969)
Post by: AIR on April 20, 2019, 02:18:49 PM
The challenge is getting the output into a string that SB can understand.

This should give you an idea:

Code: C
1. void fibo(int n) {
2.     char buf[n+1];
3.     memset(buf,0,1);
4.     mpz_t res;
5.     mpz_init(res);
6.
7.     mpz_fib_ui(res, n);
8.
9.     gmp_snprintf( buf,sizeof(buf),"%Zd\n", res );
10.     printf("%s\n",buf);
11. }

So now the output is in the 'buf' char array (string).  Work on returning that and you should be okay.

AIR.
Title: Re: fibonacci(4784969)
Post by: John on April 20, 2019, 02:39:47 PM
This is what I have so far but doesn't return anything.

Code: C
1. /* GMP Extension Module
2. UXLIBS: -lgmp
3. */
4.
5. #include <stdio.h>
6. #include <stdlib.h>
7. #include <string.h>
8. #include <unistd.h>
9. #include <gmp.h>
10. #include "../../basext.h"
11.
12. /**************************
13.  Extension Module Functions
14. **************************/
15.
16. typedef struct _ModuleObject {
17.   void *HandleArray;
18. }ModuleObject,*pModuleObject;
19.
20.
21. besVERSION_NEGOTIATE
22.   return (int)INTERFACE_VERSION;
23. besEND
24.
25.
26. besSUB_START
27.   pModuleObject p;
28.
29.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
30.   if( besMODULEPOINTER == NULL )return 0;
31.
32.   p = (pModuleObject)besMODULEPOINTER;
33.   return 0;
34. besEND
35.
36.
37. besSUB_FINISH
38.   pModuleObject p;
39.
40.   p = (pModuleObject)besMODULEPOINTER;
41.   if( p == NULL )return 0;
42.   return 0;
43. besEND
44.
45.
46. /*************
47.  GMP Functions
48. *************/
49.
50.
51. besFUNCTION(fibo)
52.   mpz_t res;
53.   mpz_init(res);
54.   int fval;
55.
56.   besARGUMENTS("i")
57.     &fval
58.   besARGEND
59.
60.   mpz_fib_ui(res, fval);
61.
62.   besRETURN_STRING(res);
63. besEND
64.

Code: Script BASIC
1. declare sub fibo alias "fibo" lib "gmp"
2. PRINT fibo(24),"\n"
3.

besRETURN_STRING(&res);     Doesn't work either.
Title: Re: fibonacci(4784969)
Post by: John on April 20, 2019, 03:15:19 PM
Works!  ;D 8)

Code: C
1. /* GMP Extension Module
2. UXLIBS: -lgmp
3. */
4.
5. #include <stdio.h>
6. #include <stdlib.h>
7. #include <string.h>
8. #include <unistd.h>
9. #include <gmp.h>
10. #include "../../basext.h"
11.
12. /**************************
13.  Extension Module Functions
14. **************************/
15.
16. typedef struct _ModuleObject {
17.   void *HandleArray;
18. }ModuleObject,*pModuleObject;
19.
20.
21. besVERSION_NEGOTIATE
22.   return (int)INTERFACE_VERSION;
23. besEND
24.
25.
26. besSUB_START
27.   pModuleObject p;
28.
29.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
30.   if( besMODULEPOINTER == NULL )return 0;
31.
32.   p = (pModuleObject)besMODULEPOINTER;
33.   return 0;
34. besEND
35.
36.
37. besSUB_FINISH
38.   pModuleObject p;
39.
40.   p = (pModuleObject)besMODULEPOINTER;
41.   if( p == NULL )return 0;
42.   return 0;
43. besEND
44.
45.
46. /*************
47.  GMP Functions
48. *************/
49.
50.
51. besFUNCTION(fibo)
52.   int fval;
53.
54.   besARGUMENTS("i")
55.     &fval
56.   besARGEND
57.
58.   char buf[fval+1];
59.   memset(buf,0,1);
60.   mpz_t res;
61.   mpz_init(res);
62.
63.   mpz_fib_ui(res, fval);
64.
65.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
66.
67.   besRETURN_STRING(buf);
68. besEND
69.

Code: Script BASIC
1. DECLARE SUB fibo ALIAS "fibo" LIB "gmp"
2.
3. PRINT LEN(fibo(4784969)),"\n"
4.

jrs@jrs-laptop:~/sb/examples/test\$ scriba fibo.sb
1000000
jrs@jrs-laptop:~/sb/examples/test\$ scriba fibo.sb
46368
jrs@jrs-laptop:~/sb/examples/test\$

jrs@jrs-laptop:~/sb/examples/test\$ time scriba fibo.sb > fibout

real   0m0.212s
user   0m0.200s
sys   0m0.012s
jrs@jrs-laptop:~/sb/examples/test\$ tail -c128 fibout
6988216644330074030719891463180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269
jrs@jrs-laptop:~/sb/examples/test\$
Title: Re: fibonacci(4784969)
Post by: AIR on April 20, 2019, 03:33:51 PM
Title: Re: fibonacci(4784969)
Post by: John on April 20, 2019, 03:42:33 PM
It's working so I guess you posted before reading my last post.
Title: Re: fibonacci(4784969)
Post by: John on April 20, 2019, 05:17:00 PM
AIR,

I tried to do a VAL(fibo(1300)) and the FORMAT("%.0f", VAL(fibo(1300))) were different but the same length. Is VAL() have problems when scriba converts a integer to a REAL?
Title: Re: fibonacci(4784969)
Post by: AIR on April 20, 2019, 05:32:15 PM
Quote
25.184. VAL

[<<<] [>>>]

Converts a string to numeric value. If the string is integer it returns an integer value. If the string contains a number presentation which is a float number the returned value is real. In case the argument is already numeric no conversion is done.

GMP uses somithing along the lines of BIGNINT to handle the large numbers that it does, which scriba/c/c++ don't have.  So some sort of type conversion is probably happening when you use VAL.  The upshot is you lose precision, which probably explains the different values you're seeing.

Typically, when using GMP you use the provided functions to do stuff like this.  So you're gonna have to read the documentation and implement in the module.

AIR.
Title: Re: fibonacci(4784969)
Post by: jalih on April 20, 2019, 10:56:25 PM
Have you looked at MAPM, Mike's Arbitrary Precision Math Library? I think that is what is working behind the scenes to provide 8th a fast "big int" and "big float" support for all math operations. 8th uses int and double by default but converts numbers automatically to "big int" and "big float", if needed.
Title: Re: fibonacci(4784969)
Post by: AIR on April 21, 2019, 10:29:26 AM
GO implementation:
Code: Go
1. package main
2.
3. import (
4.     "fmt"
5.     "math/big"
6. )
7.
8. func Mul(x, y *big.Int) *big.Int {
9.     return big.NewInt(0).Mul(x, y)
10. }
11. func Sub(x, y *big.Int) *big.Int {
12.     return big.NewInt(0).Sub(x, y)
13. }
14. func Add(x, y *big.Int) *big.Int {
16. }
17.
18. func fib(n int) (*big.Int, *big.Int) {
19.     if n == 0 {
20.         return big.NewInt(0), big.NewInt(1)
21.     }
22.     a, b := fib(n / 2)
23.     c := Mul(a, Sub(Mul(b, big.NewInt(2)), a))
24.     d := Add(Mul(a, a), Mul(b, b))
25.     if n%2 == 0 {
26.         return c, d
27.     } else {
29.     }
30. }
31.
32. func main() {
33.     a, _ := fib(4784969)
34.     fmt.Println(a)
35. }
Title: Re: fibonacci(4784969)
Post by: John on April 21, 2019, 10:41:00 AM
How does execution time look?
Title: Re: fibonacci(4784969)
Post by: jalih on April 21, 2019, 11:03:37 AM
GO implementation:

AIR, can you modify your fibonacci code to be iterative instead of recursive? On my tests iterative version is easily many times faster.

Can you do GO conversion from PL/I code below using big integers, where I used fixed dec(31). Fixed bin(31) type is basic integer. PL/I code can't do fibo(4784969) but GO using big integers will, and it will be fast!!!

Code: [Select]
`*PROCESS MARGINS(1,180) LIBS(SINGLE,STATIC);*PROCESS OPTIMIZE(2) DFT(REORDER) LIMITS(FIXEDDEC(31)); test: proc options(main);   put skip list(fibo(149));   fibo: proc(n) returns(fixed dec(31));     dcl n fixed bin(31);     dcl a fixed dec(31) init(0);     dcl b fixed dec(31) init(1);     dcl i fixed bin(31);     do i=trunc(log2(n)) to 0 by -1;       dcl (d, e) fixed dec(31);       d = a*(b*2-a);       e = a*a+b*b;       a=d;       b=e;       if iand(isrl(n,i),1) ^= 0 then         do;           dcl c fixed dec(31);           c = a+b;           a=b;           b=c;         end;     end;     return(a);   end fibo; end test;`
Title: Re: fibonacci(4784969)
Post by: AIR on April 21, 2019, 11:11:06 AM
Without printing the result

real    0m0.352s
user    0m0.342s
sys    0m0.013s

With print

real    0m2.632s
user    0m2.597s
sys    0m0.021s

Test System:

system_profiler SPHardwareDataType
Hardware:

Hardware Overview:

Model Name: Mac mini
Model Identifier: Macmini6,2
Processor Name: Intel Core i7
Processor Speed: 2.3 GHz
Number of Processors: 1
Total Number of Cores: 4
L2 Cache (per Core): 256 KB
L3 Cache: 6 MB
Memory: 16 GB
Title: Re: fibonacci(4784969)
Post by: AIR on April 21, 2019, 05:59:47 PM
Here is an interative GO implementation:
Code: Go
1. package main
2.
3. import (
4.     "fmt"
5.     "math/big"
6. )
7.
8. func Mul(x, y *big.Int) *big.Int {
9.     return big.NewInt(0).Mul(x, y)
10. }
11.
12. func Add(x, y *big.Int) *big.Int {
14. }
15.
16. func fib(n int) *big.Int {
17.     v1, v2, v3 := big.NewInt(1), big.NewInt(1), big.NewInt(0)
18.     s := fmt.Sprintf("%b", n)
19.     for i := 1; i < len(s); i++ {
20.         calc := Mul(v2, v2)
22.         if s[i] == 49 {
23.             v1, v2, v3 = Add(v1, v2), v1, v2
24.         }
25.     }
26.     return v2
27. }
28. func main() {
29.
30.     result := fib(4784969)
31.     fmt.Println(result)
32. }

real    0m2.093s
user    0m2.074s
sys     0m0.018s

AIR.
Title: Re: fibonacci(4784969)
Post by: John on April 22, 2019, 12:32:18 AM
ScriptBasic 1 mil fibo challenge.

Code: Script BASIC
1. DECLARE SUB fibo ALIAS "fibo" LIB "gmp"
2.
3. PRINT LEN(fibo(4784969)),"\n"
4.

pi@RPi3Bplus:~/sbrpi/examples \$ time scriba fibogmp.sb
1000000

real   0m1.652s
user   0m1.639s
sys   0m0.010s
pi@RPi3Bplus:~/sbrpi/examples \$

Can any other scripting language top this on the RPi 3 B+?
Title: Re: fibonacci(4784969)
Post by: jalih on April 22, 2019, 12:45:28 AM
Can any other scripting language top this on the RPi 3 B+?

Can you test 8th version I posted earlier on RPi 3 B+ ? I think 3 B+ should be about 15 percent faster than 3 B.
Title: Re: fibonacci(4784969)
Post by: AIR on April 22, 2019, 08:12:11 AM
ScriptBasic 1 mil fibo challenge.

Code: Script BASIC
1. DECLARE SUB fibo ALIAS "fibo" LIB "gmp"
2.
3. PRINT LEN(fibo(4784969)),"\n"
4.

pi@RPi3Bplus:~/sbrpi/examples \$ time scriba fibogmp.sb
1000000

real   0m1.652s
user   0m1.639s
sys   0m0.010s
pi@RPi3Bplus:~/sbrpi/examples \$

Can any other scripting language top this on the RPi 3 B+?

Code: Python
1. #!/usr/bin/env python
2.
3.
4. from gmpy2 import fib
5.
6.
7. print fib(4784969).num_digits()
8.

riveraa@dpi:~/Projects/Python/gmp \$ time ./fibogmp.py
1000000

real    0m0.362s
user    0m0.362s
sys     0m0.000s

AIR.
Title: Re: fibonacci(4784969)
Post by: jalih on April 22, 2019, 08:29:07 AM
riveraa@dpi:~/Projects/Python/gmp \$ time ./fibogmp.py
1000000

real    0m0.362s
user    0m0.362s
sys     0m0.000s

Is this on PC or RPI 3 B+ ?
Title: Re: fibonacci(4784969)
Post by: AIR on April 22, 2019, 08:40:18 AM
riveraa@dpi:~/Projects/Python/gmp \$ time ./fibogmp.py
1000000

real    0m0.362s
user    0m0.362s
sys     0m0.000s

Is this on PC or RPI 3 B+ ?

RPI 3B+

riveraa@dpi: ~/Projects/Python/gmp \$ uname -a
Linux dpi 4.14.98-v7+ #1200 SMP Tue Feb 12 20:27:48 GMT 2019 armv7l GNU/Linux

AIR.

Title: Re: fibonacci(4784969)
Post by: jalih on April 22, 2019, 08:47:31 AM
RPI 3B+

Very good time! How long does it take to output the whole result?
Title: Re: fibonacci(4784969)
Post by: AIR on April 22, 2019, 08:58:29 AM
Printing is always expensive....

real    0m1.895s
user    0m1.817s
sys     0m0.050s

Title: Re: fibonacci(4784969)
Post by: John on April 22, 2019, 09:52:04 AM
GMP is the only way to fly. (with unreal numbers)
Title: Re: fibonacci(4784969)
Post by: jalih on April 23, 2019, 07:13:40 AM
Printing is always expensive....

real    0m1.895s
user    0m1.817s
sys     0m0.050s

I made a small modification that gave about 26 percent more speed to fibonacci calculation. My current 8th version on my PC calculates and prints 1000000 digit number, if output is redirected into a file in 243 msec. Not sure, how RPI 3 B+ would perform.
Title: Re: fibonacci(4784969)
Post by: AIR on April 23, 2019, 12:45:42 PM

I made a small modification that gave about 26 percent more speed to fibonacci calculation. My current 8th version on my PC calculates and prints 1000000 digit number, if output is redirected into a file in 243 msec. Not sure, how RPI 3 B+ would perform.

Are you saving as text or data?

Because if I convert the number to a byte array in GO, and save that, these are the timings I get on my MBP:

real    0m0.240s
user    0m0.232s
sys    0m0.009s

Title: Re: fibonacci(4784969)
Post by: jalih on April 23, 2019, 01:21:45 PM
Are you saving as text or data?

I format the result into string as it's a big-float and I want to display just the integer part. After that I print how many digits, followed by a carriage return and the string containing actual million digit number. Output is directed into file from command-line.
Title: Re: fibonacci(4784969)
Post by: AIR on April 23, 2019, 01:41:57 PM
Jali, you say you "format" the number into a string rather than say "convert".  Interesting.
Title: Re: fibonacci(4784969)
Post by: John on April 23, 2019, 03:39:16 PM
It's getting to the point you can't even say fibo before the results are returned.
Title: Re: fibonacci(4784969)
Post by: AIR on April 23, 2019, 06:55:01 PM
Final GO version (I'm fibonacci'd out already!):

Code: Go
1. package main
2.
3. import (
4.     "fmt"
5.     "io/ioutil"
6.
7.     big "github.com/ncw/gmp"
8. )
9.
10. func Mul(x, y *big.Int) *big.Int {
11.     return big.NewInt(0).Mul(x, y)
12. }
13.
14. func Add(x, y *big.Int) *big.Int {
16. }
17.
18. func fib(n int) *big.Int {
19.     v1, v2, v3 := big.NewInt(1), big.NewInt(1), big.NewInt(0)
20.     s := fmt.Sprintf("%b", n)
21.     for i := 1; i < len(s); i++ {
22.         calc := Mul(v2, v2)
24.         if s[i] == 49 {
25.             v1, v2, v3 = Add(v1, v2), v1, v2
26.         }
27.     }
28.     return v2
29. }
30.
31. func main() {
32.
33.     result := fib(4784969).String()
34.     fmt.Println(len(result))
35.
36.     ioutil.WriteFile("output.txt", []byte(result), 0644)
37. }

[riveraa@Kiara ~/Projects/go/Fib] \$ time ./Fib
1000000

real    0m0.130s
user    0m0.122s
sys    0m0.007s

Hardware Overview:

Model Name: MacBook Pro
Model Identifier: MacBookPro14,1
Processor Name: Intel Core i5
Processor Speed: 2.3 GHz
Number of Processors: 1
Total Number of Cores: 2
L2 Cache (per Core): 256 KB
L3 Cache: 4 MB
Memory: 16 GB

On my RasPi, the same program:

real    0m2.246s
user    0m2.218s
sys    0m0.040s

AIR.
Title: Re: fibonacci(4784969)
Post by: John on April 23, 2019, 07:13:52 PM
Nice finish!
Title: Re: fibonacci(4784969)
Post by: AIR on April 23, 2019, 08:52:30 PM
Admittedly, that laptop is pretty fast considering it's only dual core, but it's only about a year old.

Here's a more realistic type of run on my Linux server, which is running on an old Optiplex 7010 (7yr old HW, 16GB ram, 8TB storage):

riveraa@nas:~/Projects/go/Fib\$ time ./Fib
1000000

real    0m0.235s
user    0m0.216s
sys    0m0.016s

Hardware:

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 58
Model name:            Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz
Title: Re: fibonacci(4784969)
Post by: petelomax on May 18, 2019, 02:13:29 PM
Code: Text
1. include mpfr.e
2.
3. mpz res = NULL, prev, next
4. integer lastn
5. atom t0 = time()
6.
7. function fibonampz(integer n) -- resumable, works for -ve numbers, yields mpz
8. integer absn = abs(n)
9.     if res=NULL or absn!=abs(lastn)+1 then
10.         if res=NULL then
11.             prev = mpz_init(0)
12.             res = mpz_init(1)
13.             next = mpz_init()
14.         else
15.             if n==lastn then return res end if
16.         end if
17.         mpz_fib2_ui(res,prev,absn)
18.     else
19.         if lastn<0 and remainder(lastn,2)=0 then
20.             mpz_mul_si(res,res,-1)
21.         end if
23.         {prev,res,next} = {res,next,prev}
24.     end if
25.     if n<0 and remainder(n,2)=0 then
26.         mpz_mul_si(res,res,-1)
27.     end if
28.     lastn = n
29.     return res
30. end function
31.
32. string s = mpz_get_str(fibonampz(4784969))
33. integer l = length(s)
34. s[40..-40] = "..."
35. ?{l,s}
36. ?elapsed(time()-t0)
37.
Title: Re: fibonacci(4784969)
Post by: John on May 18, 2019, 06:29:19 PM
Looks good Pete!

Is this written in your BASIC?

Is the BIGINT library like GMP?

How long does it take for the 1 mil digit Fibo?
Title: Re: fibonacci(4784969)
Post by: John on June 11, 2019, 04:02:12 PM
AIR,

I'm trying to get the GMP extension module that I added Heater's routines to allow me to do the 1 mil fibo using the BIGINT math. I'm getting a seg fault with the return of the string. Your FIBO function code works great. Can you give me a hand adapting that same method to the other functions I added?

What has me confused is in your fibo() function you create a buffer the size of n but the resulting length is 1 million bytes. Should  I use the _ui versions of the function calls? I'm still a bit confused about initial buffer size.

Heater's C version
Code: C
1. //
2. // An experiment in doing integer arithmetic using GMP with all numbers represented by strings.
3. //
4. // By heater.
5. // Modified June 11, 2019 to use base 32 strings for intermediate results.
6. //
7. #include <stdio.h>
8. #include <gmp.h>
9. #include <stdlib.h>
10. #include <memory.h>
11. #include <string.h>
12.
13. // Number base used for internal calculations by GMP.
14. int BASE = 32;
15.
16. mpz_t op1;
17. mpz_t op2;
18. mpz_t res;
19.
20. // Functions letis, addis, subis and mulis do large integer arithmetic on integers represented by strings.
21.
22. void writeis(const char *s) {
23.     mpz_set_str (op1, s, BASE);
24.     char *buf=mpz_get_str (0, 10, op1);
25.     puts(buf);
26.     free(buf);
27. }
28.
29. char* letis(const char* s) {
30.     return strdup(s);
31. }
32.
33. char* addis(const char* s1, const char* s2) {
34.     mpz_set_str (op1, s1, BASE);
35.     mpz_set_str (op2, s2, BASE);
36.     mpz_add (res, op1, op2);  // result = x * y
37.     char* res_string = mpz_get_str (0, BASE, res);
38.     return res_string;
39. }
40.
41. char* subis(const char* s1, const char* s2) {
42.     mpz_set_str (op1, s1, BASE);
43.     mpz_set_str (op2, s2, BASE);
44.     mpz_sub (res, op1, op2);  // result = x * y
45.     char* res_string = mpz_get_str (0, BASE, res);
46.     return res_string;
47. }
48.
49. char* mulis(const char* s1, const char* s2) {
50.     mpz_set_str (op1, s1, BASE);
51.     mpz_set_str (op2, s2, BASE);
52.     mpz_mul (res, op1, op2);  // result = x * y
53.     char* res_string = mpz_get_str (0, BASE, res);
54.     return res_string;
55. }
56.
57. char* memo[3];
58.
59. void init_memo() {
60.     memo[0] = letis("0");
61.     memo[1] = letis("1");
62.     memo[2] = letis("1");
63. }
64.
65. void clean_memo() {
66.     free(memo[0]);
67.     free(memo[1]);
68.     free(memo[2]);
69. }
70.
71.
72. // Return the n'th Fibonacci number as a decimal string for integer n
73. char* fibois (int n) {
74.     char* res;
75.     if (n <= 2) {
76.         return letis(memo[n]);
77.     }
78.
79.     int k = (n / 2);
80.     char* fk = fibois(k);
81.     char* fk1 = fibois(k + 1);
82.     char* a;
83.     char* b;
84.     if ((n % 2) == 0) {
86.         b = subis(a, fk);
87.         res = mulis(fk, b);
88.     } else {
89.         a = mulis(fk, fk);
90.         b = mulis(fk1, fk1);
92.     }
93.     free(a);
94.     free(b);
95.     free(fk);
96.     free(fk1);
97.     return res;
98. }
99.
100. int main(int argc, char* argv[]) {
101.     char* f;
102.     int n = 4784969;               // The first Fibonacci number with a million digits
103.
104.     if (argc >= 2) {
105.         n = atoi(argv[1]);
106.     }
107.
108.     mpz_init(op1);
109.     mpz_init(op2);
110.     mpz_init(res);
111.
112.     init_memo();
113.
114.     f = fibois(n);
115.     writeis(f);
116.     free(f);
117.
118.     clean_memo();
119.
120.     mpz_clear(op1);
121.     mpz_clear(op2);
122.     mpz_clear(res);
123.
124.     return (0);
125. }
126.

interface.c
Code: C
1. /* GMP Extension Module
2. UXLIBS: -lgmp
3. */
4.
5. #include <stdio.h>
6. #include <stdlib.h>
7. #include <string.h>
8. #include <unistd.h>
9. #include <memory.h>
10. #include <gmp.h>
11. #include "../../basext.h"
12.
13.
14. int BASE = 32;
15. mpz_t op1;
16. mpz_t op2;
17. mpz_t res;
18. char* memo[3];
19.
20.
21. static char* let(const char* s) {
22.     return strdup(s);
23. }
24.
25.
26. /**************************
27.  Extension Module Functions
28. **************************/
29.
30. typedef struct _ModuleObject {
31.   void *HandleArray;
32. }ModuleObject,*pModuleObject;
33.
34.
35. besVERSION_NEGOTIATE
36.   return (int)INTERFACE_VERSION;
37. besEND
38.
39.
40. besSUB_START
41.   pModuleObject p;
42.
43.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
44.   if( besMODULEPOINTER == NULL )return 0;
45.
46.   p = (pModuleObject)besMODULEPOINTER;
47.   return 0;
48. besEND
49.
50.
51. besSUB_FINISH
52.   pModuleObject p;
53.
54.   p = (pModuleObject)besMODULEPOINTER;
55.   if( p == NULL )return 0;
56.   return 0;
57. besEND
58.
59.
60. /*************
61.  GMP Functions
62. *************/
63.
64.
65. besFUNCTION(fibo)
66.   int fval;
67.
68.   besARGUMENTS("i")
69.     &fval
70.   besARGEND
71.
72.   char buf[fval+1];
73.   memset(buf,0,1);
74.   mpz_t res;
75.   mpz_init(res);
76.
77.   mpz_fib_ui(res, fval);
78.
79.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
80.
81.   besRETURN_STRING(buf);
82. besEND
83.
84.
85. besFUNCTION(writeis)
86.   const char *s;
87.
88.   besARGUMENTS("z")
89.     &s
90.   besARGEND
91.
92.   mpz_set_str (op1, s, BASE);
93.   char *buf=mpz_get_str (0, 10, op1);
94.   puts(buf);
95.   free(buf);
96.   besRETURNVALUE = NULL;
97.
98. besEND
99.
100.
101. besFUNCTION(letis)
102.   const char* s;
103.
104.   besARGUMENTS("z")
105.     &s
106.   besARGEND
107.
108.   besRETURN_STRING(strdup(s));
109.
110. besEND
111.
112.
114.   const char* s1;
115.   const char* s2;
116.
117.   besARGUMENTS("zz")
118.     &s1, &s2
119.   besARGEND
120.
121.   mpz_set_str (op1, s1, BASE);
122.   mpz_set_str (op2, s2, BASE);
124.   char* res_string = mpz_get_str (0, BASE, res);
125.   besRETURN_STRING(res_string);
126.
127. besEND
128.
129.
130. besFUNCTION(subis)
131.   const char* s1;
132.   const char* s2;
133.
134.   besARGUMENTS("zz")
135.     &s1, &s2
136.   besARGEND
137.
138.   mpz_set_str (op1, s1, BASE);
139.   mpz_set_str (op2, s2, BASE);
140.   mpz_sub (res, op1, op2);
141.   char* res_string = mpz_get_str (0, BASE, res);
142.   besRETURN_STRING(res_string);
143.
144. besEND
145.
146.
147. besFUNCTION(mulis)
148.   const char* s1;
149.   const char* s2;
150.
151.   besARGUMENTS("zz")
152.     &s1, &s2
153.   besARGEND
154.
155.   mpz_set_str (op1, s1, BASE);
156.   mpz_set_str (op2, s2, BASE);
157.   mpz_mul (res, op1, op2);
158.   char* res_string = mpz_get_str (0, BASE, res);
159.   besRETURN_STRING(res_string);
160.
161. besEND
162.
163.
164. besFUNCTION(init_memo)
165.   memo[0] = let("0");
166.   memo[1] = let("1");
167.   memo[2] = let("1");
168.   besRETURNVALUE = NULL;
169.
170. besEND
171.
172. besFUNCTION(clean_memo)
173.   free(memo[0]);
174.   free(memo[1]);
175.   free(memo[2]);
176.   besRETURNVALUE = NULL;
177.
178. besEND
179.
180.
181. besFUNCTION(init_globals)
182.   mpz_init(op1);
183.   mpz_init(op2);
184.   mpz_init(res);
185.   besRETURNVALUE = NULL;
186.
187. besEND
188.
189.
190. besFUNCTION(clear_globals)
191.   mpz_clear(op1);
192.   mpz_clear(op2);
193.   mpz_clear(res);
194.   besRETURNVALUE = NULL;
195.
196. besEND
197.

gmp.bas
Code: Script BASIC
1.
2. MODULE GMP
3.
4. DECLARE SUB ::FIBO              ALIAS "fibo"            LIB "gmp"
5. DECLARE SUB ::BI_WRITE          ALIAS "writeis"         LIB "gmp"
6. DECLARE SUB ::BI_LET            ALIAS "letis"           LIB "gmp"
8. DECLARE SUB ::BI_SUB            ALIAS "subis"           LIB "gmp"
9. DECLARE SUB ::BI_MUL            ALIAS "mulis"           LIB "gmp"
10. DECLARE SUB ::BI_INIT_MEMO      ALIAS "init_memo"       LIB "gmp"
11. DECLARE SUB ::BI_CLEAN_MEMO     ALIAS "clean_memo"      LIB "gmp"
12. DECLARE SUB ::BI_INIT_GLOBALS   ALIAS "init_globals"    LIB "gmp"
13. DECLARE SUB ::BI_CLEAR_GLOBALS  ALIAS "clear_globals"   LIB "gmp"
14.
15. END MODULE
16.

gmpfibo.sb
Code: Script BASIC
1. ' Return the n'th Fibonacci number as a decimal string for integer n
2.
3. IMPORT gmp.bas
4.
5. SPLITA STRING(4,"0") BY "" To memo
6.
7. FUNCTION fibois(n)
8.   IF n <= 2 THEN
9.     fibis = GMP::BI_LET(memo[n])
10.   END IF
11.
12.   k = (n / 2)
13.   fk = fibois(k)
14.   fk1 = fibois(k + 1)
15.   a = ""
16.   b = ""
17.   IF n % 2 = 0 THEN
19.     b = GMP::BI_SUB(a, fk)
20.     res = GMP::BI_MUL(fk, b)
21.   ELSE
22.     a = GMP::BI_MUL(fk, fk)
23.     b = GMP::BI_MUL(fk1, fk1)
25.   END IF
26.   fibois = res
27. END FUNCTION
28.
29. ' MAIN
30.
31. n = 4784969
32. GMP::BI_INIT_GLOBALS()
33. GMP::BI_INIT_MEMO()
34. f = fibois(n)
35. GMP::BI_WRITE(f)
36. GMP::BI_CLEAN_MEMO()
37. GMP::BI_CLEAR_GLOBALS()
38.
39. PRINT LEN(f),"\n"
40.
Title: Re: fibonacci(4784969)
Post by: AIR on June 12, 2019, 10:00:21 AM
As far as the buffer:
Code: C
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4.
5. int main(int argc, char **argv) {
6.     char buf[atoi(argv[1])+1];
7.     memset(buf,0,1);
8.     printf("%lu\n",sizeof(buf));
9.     return 0;
10. }

Compile it, and pass it a number when you run it (it will segfault if you don't pass a number.  No error checking in this example).  It will output the size of the buffer.

So if you pass 4784969, the size of the buffer will be 4,784,970 bytes.  A bit of overkill, but I'd rather use more memory than deal with a buffer overflow condition.

Title: Re: fibonacci(4784969)
Post by: John on June 12, 2019, 11:10:56 AM
My eyes are going out on me. Now I see you allocated 4 MB buffer.

Hippy on the RPi forum used his Python / ScriptBasic extension module generator to create a GMP extension module. It still seg faults but his Python version is said to run.

RPi GMP (https://www.raspberrypi.org/forums/viewtopic.php?f=31&t=240287&p=1479587#p1479603)

Can you see why I'm getting seg faults?
Title: Re: fibonacci(4784969)
Post by: AIR on June 12, 2019, 06:08:35 PM
It looks like your code is not breaking out of the recursive nature of the function, and segfaults when the recursion limit is reached.
Have you tried a non-recursive approach instead?
The C version of this is slower than the GMP provided function; due to the recursive approach and the optimized math that GMP performs.
If all you're trying to do is return the sequence as a string, the function interface I provided does that.
If this is an exercise in coding more advanced stuff using libraries, then cool.  I would still suggest a non-recursive approach.
Title: Re: fibonacci(4784969)
Post by: John on June 12, 2019, 06:23:54 PM
The bigintfibo is @hippy's code not mine. I'm just trying to get an extension built. Both Heatet and Hippy's code seg fault. Any chance you can whip up an ADD, SUB, MUL and DIV GMP extension module using SB strings?
Title: Re: fibonacci(4784969)
Post by: John on June 12, 2019, 08:34:44 PM
Here is my attempt at a GMP extension module.

interface.c
Code: C
1. /* GMP Extension Module
2. UXLIBS: -lc -lgmp
3. */
4.
5. #include <stdio.h>
6. #include <stdlib.h>
7. #include <string.h>
8. #include <unistd.h>
9. #include <gmp.h>
10. #include "../../basext.h"
11.
12.
13. /**************************
14.  Extension Module Functions
15. **************************/
16.
17.
18. typedef struct _ModuleObject {
19.   void *HandleArray;
20. }ModuleObject,*pModuleObject;
21.
22.
23. besVERSION_NEGOTIATE
24.   return (int)INTERFACE_VERSION;
25. besEND
26.
27.
28. besSUB_START
29.   pModuleObject p;
30.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
31.   if( besMODULEPOINTER == NULL )return 0;
32.   p = (pModuleObject)besMODULEPOINTER;
33.   return 0;
34. besEND
35.
36.
37. besSUB_FINISH
38.   pModuleObject p;
39.   p = (pModuleObject)besMODULEPOINTER;
40.   if( p == NULL )return 0;
41.   return 0;
42. besEND
43.
44.
45. /*************
46.  GMP Functions
47. *************/
48.
49.
50. besFUNCTION(fibo)
51.   int fval;
52.
53.   besARGUMENTS("i")
54.     &fval
55.   besARGEND
56.
57.   char buf[1500000];
58.   memset(buf,0,1);
59.   mpz_t res;
60.   mpz_init(res);
61.
62.   mpz_fib_ui(res, fval);
63.
64.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
65.
66.   besRETURN_STRING(buf);
67.
68. besEND
69.
70.
72.   const char* s1;
73.   const char* s2;
74.
75.   besARGUMENTS("zz")
76.     &s1, &s2
77.   besARGEND
78.
79.   char buf[1500000];
80.   memset(buf,0,1);
81.   mpz_t res;
82.   mpz_init(res);
83.
85.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
86.
87.   besRETURN_STRING(buf);
88.
89. besEND
90.
91.
92. besFUNCTION(bi_sub)
93.   const char* s1;
94.   const char* s2;
95.
96.   besARGUMENTS("zz")
97.     &s1, &s2
98.   besARGEND
99.
100.   char buf[1500000];
101.   memset(buf,0,1);
102.   mpz_t res;
103.   mpz_init(res);
104.
105.   mpz_sub (res, s1, s2);
106.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
107.
108.   besRETURN_STRING(buf);
109.
110. besEND
111.
112.
113. besFUNCTION(bi_mul)
114.   const char* s1;
115.   const char* s2;
116.
117.   besARGUMENTS("zz")
118.     &s1, &s2
119.   besARGEND
120.
121.   char buf[1500000];
122.   memset(buf,0,1);
123.   mpz_t res;
124.   mpz_init(res);
125.
126.   mpz_mul (res, s1, s2);
127.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
128.
129.   besRETURN_STRING(buf);
130.
131. besEND
132.

Code: Script BASIC
2. DECLARE SUB BI_SUB    ALIAS  "bi_sub"  LIB "gmp"
3. DECLARE SUB BI_MUL    ALIAS  "bi_mul"  LIB "gmp"
4.
5.
6. a = "10000000000000001"
7. b = "20000000000000002"
8.
10.

Output

GNU MP: Cannot reallocate memory (old_size=8 new_size=6467715464)
Aborted (core dumped)
jrs@jrs-laptop:~/sb/GMP\$

Title: Re: fibonacci(4784969)
Post by: John on June 12, 2019, 09:18:18 PM
At least I'm not getting a GMP error. Just a 0 for the result.  >:(

Code: C
1. /* GMP Extension Module
2. UXLIBS: -lc -lgmp
3. */
4.
5. #include <stdio.h>
6. #include <stdlib.h>
7. #include <string.h>
8. #include <unistd.h>
9. #include <gmp.h>
10. #include "../../basext.h"
11.
12.
13. /**************************
14.  Extension Module Functions
15. **************************/
16.
17.
18. typedef struct _ModuleObject {
19.   void *HandleArray;
20. }ModuleObject,*pModuleObject;
21.
22.
23. besVERSION_NEGOTIATE
24.   return (int)INTERFACE_VERSION;
25. besEND
26.
27.
28. besSUB_START
29.   pModuleObject p;
30.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
31.   if( besMODULEPOINTER == NULL )return 0;
32.   p = (pModuleObject)besMODULEPOINTER;
33.   return 0;
34. besEND
35.
36.
37. besSUB_FINISH
38.   pModuleObject p;
39.   p = (pModuleObject)besMODULEPOINTER;
40.   if( p == NULL )return 0;
41.   return 0;
42. besEND
43.
44.
45. /*************
46.  GMP Functions
47. *************/
48.
49.
50. besFUNCTION(fibo)
51.   int fval;
52.
53.   besARGUMENTS("i")
54.     &fval
55.   besARGEND
56.
57.   char buf[1500000];
58.   memset(buf,0,1);
59.   mpz_t res;
60.   mpz_init(res);
61.
62.   mpz_fib_ui(res, fval);
63.
64.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
65.
66.   besRETURN_STRING(buf);
67.
68. besEND
69.
70.
72.   const char* s1;
73.   const char* s2;
74.
75.   besARGUMENTS("zz")
76.     &s1, &s2
77.   besARGEND
78.
79.   char buf[1500000];
80.   memset(buf,0,1);
81.   mpz_init(s1);
82.   mpz_init(s2);
83.   mpz_t res;
84.   mpz_init(res);
85.
87.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
88.
89.   besRETURN_STRING(buf);
90.
91. besEND
92.
93.
94. besFUNCTION(bi_sub)
95.   const char* s1;
96.   const char* s2;
97.
98.   besARGUMENTS("zz")
99.     &s1, &s2
100.   besARGEND
101.
102.   char buf[1500000];
103.   memset(buf,0,1);
104.   mpz_init(s1);
105.   mpz_init(s2);
106.   mpz_t res;
107.   mpz_init(res);
108.
109.   mpz_sub (res, s1, s2);
110.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
111.
112.   besRETURN_STRING(buf);
113.
114. besEND
115.
116.
117. besFUNCTION(bi_mul)
118.   const char* s1;
119.   const char* s2;
120.
121.   besARGUMENTS("zz")
122.     &s1, &s2
123.   besARGEND
124.
125.   char buf[1500000];
126.   memset(buf,0,1);
127.   mpz_init(s1);
128.   mpz_init(s2);
129.   mpz_t res;
130.   mpz_init(res);
131.
132.   mpz_mul (res, s1, s2);
133.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
134.
135.   besRETURN_STRING(buf);
136.
137. besEND
138.

Code: Script BASIC
2. DECLARE SUB BI_SUB    ALIAS  "bi_sub"  LIB "gmp"
3. DECLARE SUB BI_MUL    ALIAS  "bi_mul"  LIB "gmp"
4.
5. a = "10000000000000001"
6. b = "20000000000000002"
7.
9.

0
jrs@jrs-laptop:~/sb/GMP\$

Title: Re: fibonacci(4784969)
Post by: John on June 12, 2019, 10:19:09 PM
I got it to work. Testing at this time.

I can do a fibo(10000) in .5 seconds on my PoS laptop.

Code: Script BASIC
2. DECLARE SUB BI_SUB    ALIAS  "bi_sub"  LIB "gmp"
3. DECLARE SUB BI_MUL    ALIAS  "bi_mul"  LIB "gmp"
4.
5. FUNCTION sfibo (n)
6.   IF n < 2 THEN
7.     sfibo = 1
8.   ELSE
9.     m = 0
10.     p = 1
11.     q = 0
12.     FOR i = 2 TO n
14.       q = p
15.       p = m
16.     NEXT i
17.     sfibo = m
18.   END IF
19. END FUNCTION
20.
21. PRINT sfibo(10000),"\n"
22.
Title: Re: fibonacci(4784969)
Post by: John on June 13, 2019, 05:11:40 PM
AIR,

I'm unable to do a million digit Fibonacci with this code. I run out of resources and the process is killed. Other than that it works great. Can you take a peek and see what might be causing the resource usage? I ran the fibo(87000) with the system monitor and I could see the memory ramping from 50% to 83% before the script finished and release the memory. I don't think I have a leak unless the 1.5 meg buffer I allocate each call isn't getting freed until the end.

I don't understand why I can't return the result of this function rather than having to create a 1.5 meg buffer and do a string copy.

Code: [Select]
`char* res_string = mpz_get_str (0, BASE, res);`
Code: C
1. /* GMP Extension Module
2. UXLIBS: -lc -lgmp
3. */
4.
5. #include <stdio.h>
6. #include <stdlib.h>
7. #include <string.h>
8. #include <unistd.h>
9. #include <gmp.h>
10. #include "../../basext.h"
11.
12. static mpz_t op1;
13. static mpz_t op2;
14. static mpz_t res;
15.
16. static void gmp_clear(void){
17.   mpz_clear(op1);
18.   mpz_clear(op2);
19.   mpz_clear(res);
20.   return 0;
21. }
22.
23. static void gmp_init(void){
24.   mpz_init(op1);
25.   mpz_init(op2);
26.   mpz_init(res);
27.   return 0;
28. }
29.
30.
31. /**************************
32.  Extension Module Functions
33. **************************/
34.
35.
36. typedef struct _ModuleObject {
37.   void *HandleArray;
38. }ModuleObject,*pModuleObject;
39.
40.
41. besVERSION_NEGOTIATE
42.   return (int)INTERFACE_VERSION;
43. besEND
44.
45.
46. besSUB_START
47.   pModuleObject p;
48.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
49.   if( besMODULEPOINTER == NULL )return 0;
50.   p = (pModuleObject)besMODULEPOINTER;
51.   return 0;
52. besEND
53.
54.
55. besSUB_FINISH
56.   pModuleObject p;
57.   p = (pModuleObject)besMODULEPOINTER;
58.   if( p == NULL )return 0;
59.   return 0;
60. besEND
61.
62.
63. /*************
64.  GMP Functions
65. *************/
66.
67.
68. besFUNCTION(fibo)
69.   int fval;
70.
71.   besARGUMENTS("i")
72.     &fval
73.   besARGEND
74.
75.   char buf[1500000];
76.   memset(buf,0,1);
77.   mpz_init(res);
78.
79.   mpz_fib_ui(res, fval);
80.
81.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
82.   mpz_clear(res);
83.
84.   besRETURN_STRING(buf);
85.
86. besEND
87.
88.
90.   const char* s1;
91.   const char* s2;
92.
93.   besARGUMENTS("zz")
94.     &s1, &s2
95.   besARGEND
96.
97.   char buf[1500000];
98.   memset(buf,0,1);
99.   gmp_init();
100.   mpz_set_str(op1, s1, 10);
101.   mpz_set_str(op2, s2, 10);
102.
103.
105.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
106.   gmp_clear();
107.
108.   besRETURN_STRING(buf);
109.
110. besEND
111.
112.
113. besFUNCTION(bi_sub)
114.   const char* s1;
115.   const char* s2;
116.
117.   besARGUMENTS("zz")
118.     &s1, &s2
119.   besARGEND
120.
121.   char buf[1500000];
122.   memset(buf,0,1);
123.   gmp_init();
124.   mpz_set_str(op1, s1, 10);
125.   mpz_set_str(op2, s2, 10);
126.
127.   mpz_sub (res, op1, op2);
128.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
129.   gmp_clear();
130.
131.   besRETURN_STRING(buf);
132.
133. besEND
134.
135.
136. besFUNCTION(bi_mul)
137.   const char* s1;
138.   const char* s2;
139.
140.   besARGUMENTS("zz")
141.     &s1, &s2
142.   besARGEND
143.
144.   char buf[1500000];
145.   memset(buf,0,1);
146.   gmp_init();
147.   mpz_set_str(op1, s1, 10);
148.   mpz_set_str(op2, s2, 10);
149.
150.   mpz_mul (res, op1, op2);
151.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
152.   gmp_clear();
153.
154.   besRETURN_STRING(buf);
155.
156. besEND
157.

Code: Script BASIC
2.
3. FUNCTION sfibo (n)
4.   IF n < 2 THEN
5.     sfibo = 1
6.   ELSE
7.     m = 0
8.     p = 1
9.     q = 0
10.     FOR i = 2 TO n
12.       q = p
13.       p = m
14.     NEXT i
15.     sfibo = m
16.   END IF
17. END FUNCTION
18.
19. PRINT LEN(sfibo(78000)),"\n"
20.
Title: Re: fibonacci(4784969)
Post by: AIR on June 13, 2019, 06:34:25 PM
Code: C
1. static void gmp_clear(void){
2.   mpz_clear(op1);
3.   mpz_clear(op2);
4.   mpz_clear(res);
5.   // return 0;  // you can't return a value from a void function (think SUB)
6. }
7.
8. static void gmp_init(void){
9.   mpz_init(op1);
10.   mpz_init(op2);
11.   mpz_init(res);
12. // return 0;  // you can't return a value from a void function (think SUB)
13. }

Code: C
2.   const char* s1;
3.   const char* s2;
4.
5.   besARGUMENTS("zz")
6.     &s1, &s2
7.   besARGEND
8.
9.   // char buf[1500000];
10.   // memset(buf,0,1);
11.   gmp_init();
12.   mpz_set_str(op1, s1, 10);
13.   mpz_set_str(op2, s2, 10);
14.
15.
17.   // gmp_snprintf(buf, sizeof(buf),
18.   char* res_string = mpz_get_str (0, 10, res);
19.   besSET_RETURN_STRING(res_string);
20.   gmp_clear();
21.   free(res_string);
22.
23.   // besRETURN_STRING(buf);
24.
25. besEND

AIR.
Title: Re: fibonacci(4784969)
Post by: John on June 13, 2019, 06:49:24 PM
This is why they pay you the big bucks.

Thanks AIR!

I'll give this a try and take it as a learning experience.
Title: Re: fibonacci(4784969)
Post by: John on June 13, 2019, 08:33:31 PM
Same result. I don't think this doubling method is the way to go. I read in the Python version comments that the recursive method only takes 59 recursions. I'm going to give that a try next.

jrs@jrs-laptop:~/sb/GMP\$ time scriba sfibo.sb > sfibo.results
Killed

real   65m50.055s
user   3m49.076s
sys   0m12.994s
jrs@jrs-laptop:~/sb/GMP\$

Code: C
1. /* GMP Extension Module
2. UXLIBS: -lc -lgmp
3. */
4.
5. #include <stdio.h>
6. #include <stdlib.h>
7. #include <string.h>
8. #include <unistd.h>
9. #include <gmp.h>
10. #include "../../basext.h"
11.
12. static mpz_t op1;
13. static mpz_t op2;
14. static mpz_t res;
15.
16. static void gmp_clear(void){
17.   mpz_clear(op1);
18.   mpz_clear(op2);
19.   mpz_clear(res);
20. }
21.
22. static void gmp_init(void){
23.   mpz_init(op1);
24.   mpz_init(op2);
25.   mpz_init(res);
26. }
27.
28.
29. /**************************
30.  Extension Module Functions
31. **************************/
32.
33.
34. typedef struct _ModuleObject {
35.   void *HandleArray;
36. }ModuleObject,*pModuleObject;
37.
38.
39. besVERSION_NEGOTIATE
40.   return (int)INTERFACE_VERSION;
41. besEND
42.
43.
44. besSUB_START
45.   pModuleObject p;
46.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
47.   if( besMODULEPOINTER == NULL )return 0;
48.   p = (pModuleObject)besMODULEPOINTER;
49.   return 0;
50. besEND
51.
52.
53. besSUB_FINISH
54.   pModuleObject p;
55.   p = (pModuleObject)besMODULEPOINTER;
56.   if( p == NULL )return 0;
57.   return 0;
58. besEND
59.
60.
61. /*************
62.  GMP Functions
63. *************/
64.
65.
66. besFUNCTION(fibo)
67.   int fval;
68.
69.   besARGUMENTS("i")
70.     &fval
71.   besARGEND
72.
73.   char buf[1500000];
74.   memset(buf,0,1);
75.   mpz_init(res);
76.
77.   mpz_fib_ui(res, fval);
78.
79.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
80.   mpz_clear(res);
81.
82.   besRETURN_STRING(buf);
83.
84. besEND
85.
86.
88.   const char* s1;
89.   const char* s2;
90.
91.   besARGUMENTS("zz")
92.     &s1, &s2
93.   besARGEND
94.
95.   gmp_init();
96.   mpz_set_str(op1, s1, 10);
97.   mpz_set_str(op2, s2, 10);
98.
100.   char* res_string = mpz_get_str (0, 10, res);
101.   besSET_RETURN_STRING(res_string);
102.   gmp_clear();
103.   free(res_string);
104.
105. besEND
106.
107.
108. besFUNCTION(bi_sub)
109.   const char* s1;
110.   const char* s2;
111.
112.   besARGUMENTS("zz")
113.     &s1, &s2
114.   besARGEND
115.
116.   gmp_init();
117.   mpz_set_str(op1, s1, 10);
118.   mpz_set_str(op2, s2, 10);
119.
120.   mpz_sub (res, op1, op2);
121.   char* res_string = mpz_get_str (0, 10, res);
122.   besSET_RETURN_STRING(res_string);
123.   gmp_clear();
124.   free(res_string);
125.
126. besEND
127.
128.
129. besFUNCTION(bi_mul)
130.   const char* s1;
131.   const char* s2;
132.
133.   besARGUMENTS("zz")
134.     &s1, &s2
135.   besARGEND
136.
137.   gmp_init();
138.   mpz_set_str(op1, s1, 10);
139.   mpz_set_str(op2, s2, 10);
140.
141.   mpz_mul (res, op1, op2);
142.   char* res_string = mpz_get_str (0, 10, res);
143.   besSET_RETURN_STRING(res_string);
144.   gmp_clear();
145.   free(res_string);
146.
147. besEND
148.
Title: Re: fibonacci(4784969)
Post by: John on June 14, 2019, 12:29:42 PM
AIR,

I'm having no luck trying to convert the Python and JavaScript Fibo examples to SB I have been given. I feel the GMP extension module is solid and just needs a Fibo routine that take advantage of the design using SB strings as temp BINGINT storage.
Title: Re: fibonacci(4784969)
Post by: John on June 14, 2019, 06:36:55 PM
I tried their recursive fibo submissions and they were extremely SLOW!

I can do the Fibonacci 500 in .017 seconds. That includes printing all 500 fibos.

RPi Forum Post (https://www.raspberrypi.org/forums/viewtopic.php?f=31&t=240287&p=1480551#p1480551)
Title: Re: fibonacci(4784969)
Post by: AIR on June 14, 2019, 07:43:37 PM
Screw all that bullshit, do it in the module.  That's what they're for, to provide performance when an interpreted approach is too slow.  Even Python does this, so why limit yourself when the Module system can get you the performance you want?

Original code attribution: https://codegolf.stackexchange.com/a/9444 (https://codegolf.stackexchange.com/a/9444) by Erik Haliewicz.
Code: C
1. besFUNCTION(fib2)
2.   int fval, count;
3.   mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp;
4.
5.   besARGUMENTS("i")
6.     &fval
7.   besARGEND
8.
9.   count = fval;
10.
11.   mpz_init_set_si(a, 1);
12.   mpz_init_set_si(b, 0);
13.   mpz_init_set_si(p, 0);
14.   mpz_init_set_si(q, 1);
15.   mpz_init(psq);
16.   mpz_init(qsq);
17.   mpz_init(twopq);
18.   mpz_init(bq);
19.   mpz_init(aq);
20.   mpz_init(ap);
21.   mpz_init(bp);
22.
23.  while(count > 0) {
24.   if ((count % 2) == 0) {
25.     mpz_mul(psq, p, p);
26.     mpz_mul(qsq, q, q);
27.     mpz_mul(twopq, p, q);
28.     mpz_mul_si(twopq, twopq, 2);
29.
32.     count/=2;
33.   }else{
34.     mpz_mul(bq, b, q);
35.     mpz_mul(aq, a, q);
36.     mpz_mul(ap, a, p);
37.     mpz_mul(bp, b, p);
38.
41.
43.
44.     count--;
45.     }
46.
47. }
48.
49. char* res_string = mpz_get_str (0, 10, b);
50. besSET_RETURN_STRING(res_string);
51. free(res_string);
52.
53.
54. besEND

On my Mac Mini, the above takes about a 1.5 seconds, INCLUDING printing.  4784969.

AIR.

Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 10:58:03 AM
Thanks AIR!

I will update the fibo function in the GMP extension module.

I was able to do the 1 mil challenge with Heater recursive fib code. Completes in minute using GMP.

Thanks for all your help with this. Without you this wouldn't have been possible.
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 04:30:10 PM
I was wondering how porting the fib2 function I posted previously to a more native SB code base would look/work:
Code: Script BASIC
1. import gmp2.bas
2.
3. n = 4784969
4. count = n
5.
6. a = gmp2::init_set(1)
7. b = gmp2::init_set(0)
8. p = gmp2::init_set(0)
9. q = gmp2::init_set(1)
10.
11. psq = gmp2::init()
12. qsq = gmp2::init()
13. twopq = gmp2::init()
14. bq = gmp2::init()
15. aq = gmp2::init()
16. ap = gmp2::init()
17. bp = gmp2::init()
18.
19. while count > 0
20.     if (count % 2) = 0 then
21.         psq = gmp2::mul(p, p)
22.         qsq = gmp2::mul(q, q)
23.         twopq = gmp2::mul(p, q)
24.         twopq = gmp2::mul_si(twopq, 2)
25.
28.
29.         count = count / 2
30.     else
31.         bq = gmp2::mul(b, q)
32.         aq = gmp2::mul(a, q)
33.         ap = gmp2::mul(a, p)
34.         bp = gmp2::mul(b, p)
35.
38.
40.
41.         count = count - 1
42.
43.     end if
44.
45. wend
46. print b,"\n"

On my RasPi:

riveraa@dpi:~/sb \$ time ./AppRun newfib.sb >fib.txt

real    0m38.965s
user    0m38.733s
sys    0m0.224s

On my Mac Mini:
[riveraa@mini ~/sb] \$ time ./AppRun newfib.sb >fib.txt

real    0m3.159s
user    0m3.094s
sys    0m0.051s

Module Source:
Code: C
1. /*
2. READ THIS FILE AND CHANGE THE SOURCE WHEREVER YOU SEE COMMENTS STARTING
3. WITH THE WORD *TODO*
4.
5. WHEN YOU ARE FINISHED YOU CAN
6.
7.   FILE   : interface.c
9.   BAS    : gmp2.bas
10.   AUTHOR : *TODO*
11.
12.   DATE:
13.
14.   CONTENT:
15.   This is the interface.c file for the ScriptBasic module gmp2
16. ----------------------------------------------------------------------------
17.
18. Remove the two characters // from following line(s) if this module is supposed to
19. be compiled under specific OS's. If there is a need for some library to successfully
20. compile the module under Windows specify the names of the libraries on the line
21. as it is listed for the linker application. This is usually something like
22.
23. WINDOWS: libname1.lib libname2.lib ... libnameX.lib
24. LINUX/MACOS: -lm -ldl
25.
26. If there are no libraries, but still the module is to be compiled under Windows
27. do remove the // characters so that the program setup.pl will know that the
28. module is meant for Windows.
29.
30. //NTLIBS:
31. UXLIBS: -lgmp
32. DWLIBS: -lgmp -macosx_version_min 10.12
33.
34. */
35.
36. /*
37. *TODO*
38. INCLUDE HERE THE SYSTEM HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
39. */
40.
41. #ifdef WIN32
42. /*
43. *TODO*
44. INCLUDE HERE THE WIN32 SPECIFIC HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
45. */
46. #else
47. /*
48. *TODO*
49. INCLUDE HERE THE UNIX SPECIFIC HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
50. */
51. #endif
52.
53. /*
54. *TODO*
55. INCLUDE HERE THE LOCAL HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
56. */
57. #include <stdio.h>
58. #include <stdlib.h>
59. #include <string.h>
60. #include "../../basext.h"
61. #include <gmp.h>
62.
63. /*
64. *TODO*
65. INSERT THE BASIC CODE THAT WILL GET INTO THE FILE gmp2.BAS
66. AFTER THE LINE 'TO_BAS:' AND BEFORE THE LINE END OF THE COMMENT
67.
68. NOTE THAT SUB AND COMMAND DECLARATIONS ARE CREATED AUTOMATICALLY
69. FROM THE FUNCTION DEFINTIONS WHEN THE MODULE IS CONFIGURED BEFORE
70. COMPILATION
71.
72. TO_BAS:
73. */
74.
75. /*
76. *TODO*
77. DECLARE HERE THE MODULE OBJECT TYPE. THIS STRUCTURE SHOULD HOLD THE
78. DATA AVAILABLE FOR EACH INTERPRETER THREAD. USE THIS STRUCTURE TO
79. STORE GLOBAL VALUES INSTEAD OF USING GLOBAL VARIABLES.
80. */
81. typedef struct _ModuleObject {
82.   char a; /* You may delete this. It is here to make the initial interface.c compilable. */
83.   }ModuleObject,*pModuleObject;
84.
85. mpz_t g_Op1, g_Op2, g_Res;
86.
87. /*
88. *TODO*
89. ALTER THE VERSION NEGOTIATION CODE IF YOU NEED
90. */
91. besVERSION_NEGOTIATE
92.   return (int)INTERFACE_VERSION;
93. besEND
94.
95. /*
96. *TODO*
97. ALTER THE ERROR MESSAGE FUNCTION
98. */
99. besSUB_ERRMSG
100.
101.   switch( iError ){
102.     case 0x00080000: return "ERROR HAS HAPPENED";
103.     }
104.   return "Unknown gmp2 module error.";
105. besEND
106.
107. /*
108. *TODO*
109. ALTER THE MODULE INITIALIZATION CODE
110. */
111. besSUB_START
112.   pModuleObject p;
113.
114.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
115.   if( besMODULEPOINTER == NULL )return 0;
116.
117.   mpz_init(g_Op1);
118.   mpz_init(g_Op2);
119.   mpz_init(g_Res);
120.
121. /*
122. *TODO*
123. INSERT HERE ANY CODE THAT YOU NEED TO INITIALIZE THE MODULE FOR THE
125. */
126.
127. besEND
128.
129. /*
130. *TODO*
131. ALTER THE MODULE FINISH CODE IF NEEDED
132. */
133. besSUB_FINISH
134.   pModuleObject p;
135.
136.   /*
137.     YOU CERTAINLY NEED THIS POINTER TO FREE ALL RESOURCES THAT YOU ALLOCATED
138.     YOU NEED NOT CALL besFREE TO FREE THE MEMORY ALLOCATED USING besALLOC
139.     CLOSE ANY FILE THAT REMAINED OPEN, RELEASE DATABASE HANDLES AND ALL
140.     OTHER RESOURCES INCLUDING MEMORY *NOT* ALLOCATED CALLING besALLOC
141.   */
142.   p = (pModuleObject)besMODULEPOINTER;
143.   if( p == NULL )return 0;
144.
145.   return 0;
146. besEND
147.
148.
149. /*
150. *TODO*
151. WRITE YOUR MODULE INTERFACE FUNCTIONS FOLLOWING THIS SKELETON
152.
153. NOTE THAT THIS IS A SAMPLE FUNCTION, YOU CAN ALSO DELETE
154. LINES FROM IT IF NEEDED
155. */
156. /**
157. =section mpz
158. =H mpz
159.
160. Returns new mpz_t object
161. */
162. besFUNCTION(mpz)
163.   pModuleObject p;
164.   mpz_t r;
165.
166.   p = (pModuleObject)besMODULEPOINTER;
167.
168.   // besARGUMENTS("i[s]")
169.   //   &r
170.   // besARGEND
171.
172.   besRETURN_POINTER(r);
173. besEND
174.
175. /**
176. =section init
177. =H mpz
178.
179. Initializes mpz_t object
180. */
181. besFUNCTION(init)
182.   pModuleObject p;
183.   mpz_t r;
184.   char * res;
185.
186.   p = (pModuleObject)besMODULEPOINTER;
187.
188.   // besARGUMENTS("p")
189.   //   &r
190.   // besARGEND
191.
192.   mpz_init(r);
193.   res = mpz_get_str(NULL,10,r);
194.   besSET_RETURN_STRING(res);
195.   free(res);
196.
197.   besRETURN_POINTER(r);
198. besEND
199.
200.
201. /**
202. =section init_set
203. =H mpz
204.
205. Initializes mpz_t object
206. */
207. besFUNCTION(init_set)
208.   pModuleObject p;
209.   char *s, *res;
210.   int i;
211.
212.   p = (pModuleObject)besMODULEPOINTER;
213.
214.   besARGUMENTS("z")
215.     &s
216.   besARGEND
217.
218.   // mpz_set_str(g_Op1, s, 10);
219.   mpz_init_set_str(g_Res,s,10);
220.   res = mpz_get_str(NULL,10,g_Res);
221.   besSET_RETURN_STRING(res);
222.   free(res);
223. besEND
224.
225. /**
226. =section mul
227. =H mpz
228.
229. Multiplies mpz_t objects
230. */
231. besFUNCTION(mul)
232.   pModuleObject p;
233.   char *s, *t, *res;
234.   int i;
235.
236.   p = (pModuleObject)besMODULEPOINTER;
237.
238.   besARGUMENTS("zz")
239.     &s,&t
240.   besARGEND
241.
242.  mpz_set_str(g_Op1, s, 10);
243.  mpz_set_str(g_Op2, t, 10);
244.   mpz_mul(g_Res, g_Op1, g_Op2);
245.   res = mpz_get_str(NULL,10,g_Res);
246.   besSET_RETURN_STRING(res);
247.   free(res);
248. besEND
249.
250.
251. /**
252. =section mul_si
253. =H mpz
254.
255. Multiplies mpz_t objects
256. */
257. besFUNCTION(mul_si)
258.   pModuleObject p;
259.   char *s,*res;
260.   long i;
261.
262.   p = (pModuleObject)besMODULEPOINTER;
263.
264.   besARGUMENTS("zi")
265.     &s,&i
266.   besARGEND
267.
268.   mpz_set_str(g_Op1, s, 10);
269.   mpz_mul_si(g_Res, g_Op1, i);
270.
271.   res = mpz_get_str(NULL,10,g_Res);
272.   besSET_RETURN_STRING(res);
273.   free(res);
274. besEND
275.
276.
277. /**
280.
282. */
284.   pModuleObject p;
285.   char *s, *t, *res;
286.
287.   int i;
288.
289.   p = (pModuleObject)besMODULEPOINTER;
290.
291.   besARGUMENTS("zz")
292.     &s,&t
293.   besARGEND
294.
295.   mpz_set_str(g_Op1, s, 10);
296.   mpz_set_str(g_Op2, t, 10);
298.
299.   res = mpz_get_str(NULL,10,g_Res);
300.   besSET_RETURN_STRING(res);
301.   free(res);
302. besEND
303.
304.
305. /**
306. =section test
308.
310. */
311. besFUNCTION(test)
312.   pModuleObject p;
313.   mpz_t r, s, t;
314.   int i;
315.
316.   p = (pModuleObject)besMODULEPOINTER;
317.
318.   // besARGUMENTS("ppp")
319.   //   &r,&s,&t
320.   // besARGEND
321.
323.   i=12345;
324.
325.   besRETURN_LONG(i);
326. besEND
327.
328. /**
329. =section get_string
331.
333. */
334. besFUNCTION(get_string)
335.   pModuleObject p;
336.   mpz_t r, s, t;
337.   int i;
338.   char * retstring;
339.
340.   p = (pModuleObject)besMODULEPOINTER;
341.
342.   besARGUMENTS("p")
343.     &r
344.   besARGEND
345.
346.   retstring = mpz_get_str(0,10,r);
347.
348.   besSET_RETURN_STRING(retstring);
349.   free(retstring);
350. besEND
351.
352. /*
353. *TODO*
354. INSERT HERE THE NAME OF THE FUNCTION AND THE FUNCTION INTO THE
355. TABLE. THIS TABLE IS USED TO FIND THE FUNCTIONS WHEN THE MODULE
356. INTERFACE FILE IS COMPILED.
357. */
358.
359. SLFST GMP2_SLFST[] ={
360.
361. { "versmodu" , versmodu },
362. { "bootmodu" , bootmodu },
363. { "finimodu" , finimodu },
364. { "emsgmodu" , emsgmodu },
365. { "mpz" , mpz },
366. { "init" , init },
367. { "init_set" , init_set },
368. { "mul" , mul },
369. { "mul_si" , mul_si },
371. { "get_string" , get_string },
372. { NULL , NULL }
373.   };

AIR.

Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 05:15:11 PM
Can you include subtraction, divide standard and integer divide to your library and we can make that the ScriptBasic official GMP extension module.

Nice Job!

Your GMP2 fibo ran in 4.7 seconds on my laptop. Heater's recursive version took 1 minute 9 seconds using the GMP we worked together on.
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 07:00:59 PM
Added sub and divide functions.  Anything else, look at how I did the functions and adapt to your needs.

Pushed up to sandbox.

Code: Script BASIC
1. Import gmp2.bas
2.
3. a = gmp2::sub(1000000,500000)
4.
5. print a,"\n"
6.
7. b = gmp2::divide(a,5)
8.
9. print b,"\n"

[riveraa@mini ~/sb] \$ ./sb math.sb
500000
100000

AIR.
Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 07:05:24 PM
Outstanding!

Now Heater will push the ScriptBasic submission to the official Fibonacci 1 million digit challenge repo.

I think we are safe so you can return to being Clark Kent.  :-*

I'm surprized SB is allowing us to use the SUB keyword as a user function.
Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 08:05:28 PM
I noticed in your Sub / Divide example you didn't init any of the variables. When is it required?
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 08:14:27 PM
Really only needed if calling functions where you pass them.

Since the module functions are returning strings, SB rules apply. You only need to init the vars if they will be passed to a function at some point.

I think you can even just init them as empty strings directly, since that is what is returned from the init function.

Play with it and see.
Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 08:26:58 PM
In you example a is passed to the GMP2 function. In the previous call you pass constants. Does a returned variable from GMP2 auto init the variable?

You are setting the string in each of the operator calls like I did but made it a static function. I don't see the auto clear though.

Code: C
2.   pModuleObject p;
3.   char *s, *t, *res;
4.
5.   int i;
6.
7.   p = (pModuleObject)besMODULEPOINTER;
8.
9.   besARGUMENTS("zz")
10.     &s,&t
11.   besARGEND
12.
13.   mpz_set_str(g_Op1, s, 10);
14.   mpz_set_str(g_Op2, t, 10);
16.
17.   res = mpz_get_str(NULL,10,g_Res);
18.   besSET_RETURN_STRING(res);
19.   free(res);
20. besEND
21.
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 08:36:34 PM
The functions return strings.  Look at the code and you'll see that it's similar to what you were trying.
Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 08:44:28 PM
Here is what my ADD looks like. This way I never have to worry about initializing and clearing the GMP string objects.

Code: C
2.   const char* s1;
3.   const char* s2;
4.
5.   besARGUMENTS("zz")
6.     &s1, &s2
7.   besARGEND
8.
9.   gmp_init();
10.   mpz_set_str(op1, s1, 10);
11.   mpz_set_str(op2, s2, 10);
12.
14.   char* res_string = mpz_get_str (0, 10, res);
15.   besSET_RETURN_STRING(res_string);
16.   gmp_clear();
17.   free(res_string);
18.
19. besEND
20.
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 09:02:32 PM
Code: C
1. besSUB_START
2.   pModuleObject p;
3.
4.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
5.   if( besMODULEPOINTER == NULL )return 0;
6.
7.   mpz_init(g_Op1);
8.   mpz_init(g_Op2);
9.   mpz_init(g_Res);
10.
11. besEND

Code: C
1. besSUB_FINISH
2.   pModuleObject p;
3.
4.   p = (pModuleObject)besMODULEPOINTER;
5.   if( p == NULL )return 0;
6.   mpz_clear(g_Op1);
7.   mpz_clear(g_Op2);
8.   mpz_clear(g_Res);
9.   return 0;
10. besEND

Using SB's Module support functions, I only have to init/clear once.  Init when the module is loaded, and clear when the module exits.  3 inits/clears, vs init * number of functions and clear * number of functions.

If you look at what's happening, you are init'ing the variables, then immediately setting them.  Then you clear them, so it's like wash/rinse/repeat.  Each init/clear call you make is taking additional time that isn't necessary.

With my approach, I init once and set the variables each time I need to.  Then when the module is unloaded, the resources I init'd are released.  Once I set that in the Module, I don't have to remember to do it in each function I implement.

AIR.
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 09:08:44 PM
In response to your question about setting the variables in an SB script with the GMP2 module:
Code: Script BASIC
1. a = 1
2. b = 0
3. p = 0
4. q = 1
5.
6. psq = 0
7. qsq = 0
8. twopq = 0
9. bq = 0
10. aq = 0
11. ap = 0
12. bp = 0

This still works as expected, so the calls to GMP2::init() aren't necessary...

AIR.
Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 09:09:38 PM
I missed the code in the START / FINISH SB routines.

I will do some testing and see if anything crops up.
Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 09:12:35 PM
That's great. Is the set not need as well?
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 09:13:35 PM
Code: Script BASIC
1. import gmp2.bas
2.
3. count = 4784969
4.
5. a = 1
6. b = 0
7. p = 0
8. q = 1
9.
10.
11. while count > 0
12.     if (count % 2) = 0 then
13.         psq = gmp2::mul(p, p)
14.         qsq = gmp2::mul(q, q)
15.         twopq = gmp2::mul(p, q)
16.         twopq = gmp2::mul_si(twopq, 2)
17.
20.
21.         count = count / 2
22.     else
23.         bq = gmp2::mul(b, q)
24.         aq = gmp2::mul(a, q)
25.         ap = gmp2::mul(a, p)
26.         bp = gmp2::mul(b, p)
27.
30.
32.
33.         count = count - 1
34.
35.     end if
36.
37. wend
38. print b,"\n"

This is all you need, in this case.  The other vars are created within the WHILE loop.

AIR.
Title: Re: fibonacci(4784969)
Post by: AIR on June 15, 2019, 10:36:54 PM
Factorial(100) example:
Code: Script BASIC
1. Import gmp2.bas
2.
3. n = 100
4. fact = 1
5.
6. while n > 1
7.     fact = gmp2::mul(fact,n)
8.     n -=1
9. wend
10.
11. print fact,"\n"

[riveraa@mini ~/sb] \$ ./sb factorial.sb
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

I know it's off-topic, but wanted to show how GMP makes handling large numbers easy.

AIR.
Title: Re: fibonacci(4784969)
Post by: John on June 15, 2019, 10:53:31 PM
GMP works great with SB. Very seamless operation.

GMP User Manual (https://gmplib.org/gmp-man-6.0.0a.pdf)

What does gmp2::mul_si do differently than a standard gmp2::mul?
Title: Re: fibonacci(4784969)
Post by: AIR on June 16, 2019, 10:04:47 AM
In the case of SB, typically no difference (if using integers) because of the way I wrapped the GMP api.

In the GMP api itself, *_si indicates that you are passing a "signed integer" as a parameter. *_ui would be an "unsigned integer".

Other numeric types are represented in similar fashion (they're not implemented in the SB Module), the documentation link you posted has more details under the Integer/Rational/Floating-Point function sections.

AIR.
Title: Re: fibonacci(4784969)
Post by: John on June 16, 2019, 10:42:13 AM
Thanks!

Another mystery solved.

If you were to expand on the GMP2 extension module, what areas would SB benefit most from?
Title: Re: fibonacci(4784969)
Post by: AIR on June 16, 2019, 06:46:40 PM
Thanks!

Another mystery solved.

If you were to expand on the GMP2 extension module, what areas would SB benefit most from?

In order to answer that, I'd need an actual use case.

At the very least, support for floating point numbers should be on the todo list.

Take a look at this Bacon GMP module (https://www.basic-converter.org/gmp.bac.html), to get an idea of which functions MIGHT be needed.

AIR.
Title: Re: fibonacci(4784969)
Post by: John on June 16, 2019, 06:56:00 PM
The BaCon GMP library is almost plug & play additions to the GMP2 module.

The BaCon GMP library looks to only return a max of 100 digits. The function selection was helpful..

It would be great if we had a set of GMP operator functions that would match SB's native set.
Title: Re: fibonacci(4784969)
Post by: John on June 16, 2019, 07:35:45 PM
ScriptBasic allows creating COMMANDS as well as functions. I've only done it once with a IFF command. If we were to to do the GMP2 functions as commands there would be little difference in syntax for expressions.

-- = sub
** = mul
// = divide
....

c = GMP2::a ++ b

If no MODLE and just DECLARE COMMAND

c = a ++ b
Title: Re: fibonacci(4784969)
Post by: AIR on June 16, 2019, 08:08:47 PM
Any chance of a working example?
Title: Re: fibonacci(4784969)
Post by: John on June 16, 2019, 08:10:47 PM
The IIF example in the trial extension module.
Title: Re: fibonacci(4784969)
Post by: John on June 16, 2019, 09:35:31 PM
I added cmp to the gmp2 extension module but I'm unable to push anything anymore.

Maybe this function isn't need as SB is fully capable of comparing strings.

Code: C
1. /**
2. =section cmp
3. =H cmp
4.
5. cmp mpz_t objects
6. */
7. besFUNCTION(cmp)
8.   pModuleObject p;
9.   char *s, *t;
10.
11.   int i, rtn;
12.
13.   p = (pModuleObject)besMODULEPOINTER;
14.
15.   besARGUMENTS("zz")
16.     &s,&t
17.   besARGEND
18.
19.   mpz_set_str(g_Op1, s, 10);
20.   mpz_set_str(g_Op2, t, 10);
21.   rtn = mpz_cmp(g_Op1, g_Op2);
22.
23.   besRETURN_LONG(rtn);
24. besEND
25.

It returns a -1 if they are not equal and 0 if they are.
Title: Re: fibonacci(4784969)
Post by: John on June 19, 2019, 07:40:37 PM
Hi AIR,

Any luck with creating a command like ++ with SB?
Title: Re: fibonacci(4784969)
Post by: AIR on June 19, 2019, 08:15:18 PM
Nope.  Would need a parser to handle that.
Title: Re: fibonacci(4784969)
Post by: John on June 19, 2019, 08:27:05 PM
That sucks!

Commands have always been the final SB frontier for me.

I thought the reason ++ was reserved was for just this purpose. The ++ becomes the function (command) name which has 2 arguments. (prefix/suffix)
Title: Re: fibonacci(4784969)
Post by: AIR on June 19, 2019, 09:23:42 PM
Where is that documented?
Title: Re: fibonacci(4784969)
Post by: John on June 19, 2019, 09:27:29 PM
The keywords list shows the reserved symbol pair. You will have to dig for examples beyond IFF in trial. I'm trying to dig up what I can find.

For grins try the +! syntax in scriba. The returned message should be enlightening.
Title: Re: fibonacci(4784969)
Post by: John on June 20, 2019, 09:26:53 AM
It looks like ++ isn't one of the reserved symbol pairs. These are the options for addition.

+^    +<    +>    +?    +=    +*    +/    +%    +!    +#    +&    +\    +`    +'
+@

+! looks interesting.
Title: Re: fibonacci(4784969)
Post by: AIR on June 20, 2019, 01:27:41 PM
Taking Heater's placing the fib calculations into a function, I modified the bottom of his code like this:

Code: Script BASIC
1.
2. count = 0
3. while count < 10
4.     fibo(4784969)
5.     count = count + 1
6.     print count,"\n"
7. wend
8.

Here's what valgrind shows:

Code: Text
1.
2. \$ valgrind --leak-check=full --show-leak-kinds=all scriba heater.sb
3. ==511== Memcheck, a memory error detector
4. ==511== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
5. ==511== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
6. ==511== Command: scriba heater.sb
7. ==511==
8. 1
9. 2
10. 3
11. 4
12. 5
13. 6
14. 7
15. 8
16. 9
17. 10
18. ==511==
19. ==511== HEAP SUMMARY:
20. ==511==     in use at exit: 32 bytes in 1 blocks
21. ==511==   total heap usage: 190,305 allocs, 190,304 frees, 4,482,318,682 bytes allocated
22. ==511==
23. ==511== 32 bytes in 1 blocks are still reachable in loss record 1 of 1
24. ==511==    at 0x4C2DBC5: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
25. ==511==    by 0x54DC60E: _dlerror_run (dlerror.c:141)
26. ==511==    by 0x54DBF81: dlopen@@GLIBC_2.2.5 (dlopen.c:87)
27. ==511==    by 0x11EFEC: dynlolib_LoadLibrary (in /home/riveraa/sb/bin/scriba)
28. ==511==    by 0x180A7F: modu_LoadModule (in /home/riveraa/sb/bin/scriba)
29. ==511==    by 0x180C95: modu_GetFunctionByName (in /home/riveraa/sb/bin/scriba)
30. ==511==    by 0x12C0AA: COMMAND_EXTERNAL (in /home/riveraa/sb/bin/scriba)
31. ==511==    by 0x168DAC: execute_Execute_r (in /home/riveraa/sb/bin/scriba)
32. ==511==    by 0x169BE5: execute_Evaluate (in /home/riveraa/sb/bin/scriba)
33. ==511==    by 0x1431F7: COMMAND_LET (in /home/riveraa/sb/bin/scriba)
34. ==511==    by 0x168DAC: execute_Execute_r (in /home/riveraa/sb/bin/scriba)
35. ==511==    by 0x169BE5: execute_Evaluate (in /home/riveraa/sb/bin/scriba)
36. ==511==
37. ==511== LEAK SUMMARY:
38. ==511==    definitely lost: 0 bytes in 0 blocks
39. ==511==    indirectly lost: 0 bytes in 0 blocks
40. ==511==      possibly lost: 0 bytes in 0 blocks
41. ==511==    still reachable: 32 bytes in 1 blocks
42. ==511==         suppressed: 0 bytes in 0 blocks
43. ==511==
44. ==511== For counts of detected and suppressed errors, rerun with: -v
45. ==511== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
46.

Having an infinite loop doesn't allow SB to free up resources.  It also doesn't allow valgrind to report (I think I can have it write out to a file, but haven't tried that yet.)

This is a preliminary check, which is why I posted here instead of on the RasPi forum.

AIR.
Title: Re: fibonacci(4784969)
Post by: John on June 20, 2019, 05:01:02 PM
What resouces aren't being released until scriba exits?

I don't see this million digit fibo as real world and only a challenge to break as many languages as they can. I do care about memory leaks but not SB memory manager caching.

I'm counting on you to make the call if there is a problem with the BASIC.

With the tests I have done only Heater's recursive fibo becomes a memory hog.
Title: Re: fibonacci(4784969)
Post by: John on June 23, 2019, 11:15:36 AM
So where is the jury at with GMP2 leaking or not? I see no abnormal memory use when calling the GMP fibo function in a continuous loop.

I ran across this post that suggest that you create a buffer for the results rather than letting GMP do it. Interestingly the way you wrote the original fibo() function uses the buffer method and doesn't leak.

My old GMP module did the buffer method and didn't seem to help with the mystery memory problem.

https://gmplib.org/list-archives/gmp-discuss/2003-November/000891.html
Title: Re: fibonacci(4784969)
Post by: jack on July 07, 2019, 05:55:03 AM
I am a bit late, just out of curiosity, I converted AIR's code https://www.allbasic.info/forum/index.php?topic=588.msg6963#msg6963
to FreeBASIC using mpfr, I did not expect the execution time to be good, but surprisingly it took only .61 seconds including printing

my conversion uses include files that overload the math operators and functions, they are quite large, so I won't post them here
Code: [Select]
`#Include Once "gmp.bi"#Include Once "mpfr.bi"'we need to set mpfr_digits before including the overloded operatorsDim Shared As Long mpfr_digits_precision = 1000001 '<- set mpfr digits-precisionDim Shared As mpfr_rnd_t mpfr_rounding_mode = MPFR_RNDN '<- set the rounding mode' rounding options are'  MPFR_RNDN    round to nearest, with ties to even'  MPFR_RNDZ    round toward zero'  MPFR_RNDU    round toward +Inf'  MPFR_RNDD    round toward -Inf'  MPFR_RNDA    round away from zero'  MPFR_RNDF    faithful rounding (not implemented yet)'  MPFR_RNDNA    round to nearest, with ties away from zero (mpfr_round)#Include Once "mpfr-fb.bi" 'mpfr overloaded operators''=============================================================================sub fib2(byval n as long, byref b as mpfr) dim as long count=n dim as mpfr a = 1 dim as mpfr p = 0 dim as mpfr q = 1 dim psq as mpfr dim qsq as mpfr dim twopq as mpfr dim bq as mpfr dim aq as mpfr dim ap as mpfr dim bp as mpfr b = 0 while count > 0 if (count mod 2) = 0 then psq = p * p qsq = q * q twopq = p * q twopq = twopq * 2 p = psq + qsq q = twopq + qsq count \= 2 else bq = b * q aq = a * q ap = a * p bp = b * p a = bq + aq a = a + ap b = bp + aq count-=1 end if wendend subdim as double t=timerdim as mpfr bfib2(4784969, b)print bprint "elapsed time ";timer-t;" seconds"`
Title: Re: fibonacci(4784969)
Post by: John on July 07, 2019, 06:23:57 PM
Are you noticing any leaks with mpfr?  We are still searching for the cause of SB's abnormal memory use using GMP.
Title: Re: fibonacci(4784969)
Post by: jack on July 08, 2019, 02:41:55 AM
hello John
I must admit that I am only an amateur programmer,  I have no idea how to detect a leak, it seems especially complicated due to the multitasking OS.
but I am willing to learn, if AIR reads this, perhaps he may be willing to instruct me on how to detect leaks on macOS high Sierra.
there's the leaks command, but how do you check for memory leaks on a process that takes less than a second from start to finish?
here's a screenshot of my attempt
Title: Re: fibonacci(4784969)
Post by: jack on July 08, 2019, 06:38:41 AM
John, to the best of my ability, I don't see any memory leaks
Title: Re: fibonacci(4784969)
Post by: John on July 08, 2019, 01:23:34 PM
How others have been testing for leaks is run your fibo in a WHILE loop and watch for abnormal memory consumption.
Title: Re: fibonacci(4784969)
Post by: jack on July 09, 2019, 03:01:40 AM
I ran fibo in a loop, and as I understand, there are no leaks.
the reason for sum is so that the compiler won't optimize the loop out
Code: [Select]
`dim as double t=timerdim as mpfr b, sumfor i as integer=1 to 500 fib2(4784969, b) sum+=bnextprint sumprint "elapsed time ";timer-t;" seconds"`
Title: Re: fibonacci(4784969)
Post by: John on July 09, 2019, 12:32:57 PM
It might be worthwhile to see if your BIGINT library would work better than GMP.
Title: Re: fibonacci(4784969)
Post by: jack on July 09, 2019, 01:23:50 PM
Hi John
as I understand it, your GMP wrapper used SB strings, it seems to me, that perhaps the memory leak may be due, to perhaps inaccurate reporting of the strings memory usage.
in FB I not only overload the operators but setup constructors and destructors to allocate and deallocate the memory used by the mpfr type.
for example, DIM as mpfr x(100) would initialize all the elements of x from 0 to 100 to the set precision and after scope, clear all the elements.
Title: Re: fibonacci(4784969)
Post by: John on July 09, 2019, 01:45:19 PM
AIR wrote the GMP2 module and I don't know where he stands with the abnormal memory usage and GMP.  From my testing it doesn't look like a bug in SB.
Title: Re: fibonacci(4784969)
Post by: AIR on July 09, 2019, 06:46:06 PM
IF you properly exit an sb app, the memory is released.

With most apps, if you send a sigkill to it while monitoring for leaks, you will see that some of the memory allocated is not properly released.

So, the 'problem' is that sb never gets the chance to release allocated memory because of an artificial non-real world test.

I've tested this with a loop of 100 iterations while monitoring with valgrind.  I didn't see the memory usage jump up to the extent that others have.  And memory was released at the end.

That's as far as I'm going with this.  If y'all feel that the module is problematic, then either provide a fix or don't use it.
Title: Re: fibonacci(4784969)
Post by: John on July 09, 2019, 10:59:58 PM
That's good enough for me.
Title: Re: fibonacci(4784969)
Post by: AIR on July 12, 2019, 06:56:43 PM
John,
According to the docs, if you undef an array the memory allocated to it is freed.
Does the same apply to strings?
If so, maybe undef'ing the SB variables after printing the value of 'b' would address the leak that's occurring when you run the fibo example in an endless loop.
Title: Re: fibonacci(4784969)
Post by: John on July 12, 2019, 07:13:11 PM
undef is a variable type in SB.

The UNDEF statement will free any resources to the var(s) and set the var type to undef.

Making all the variables in the function LOCAL didn't help.