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.8th
1000000 digits:
1072739564180047722936481359622500432190 upper 40 digits
3407167474856539211500699706378405156269 lower 40 digits
279 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 1000000
say fibo(4784969)
exit


fibo:
  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 a


d2b: 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
Re-read my reply and you'll see what you're doing wrong.
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 {
  15.     return big.NewInt(0).Add(x, y)
  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 {
  28.         return d, Add(c, d)
  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 {
  13.     return big.NewInt(0).Add(x, y)
  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)
  21.         v1, v2, v3 = Add(Mul(v1, v1), calc), Mul(Add(v1, v3), v2), Add(Mul(v3, v3), calc)
  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 {
  15.     return big.NewInt(0).Add(x, y)
  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)
  23.         v1, v2, v3 = Add(Mul(v1, v1), calc), Mul(Add(v1, v3), v2), Add(Mul(v3, v3), calc)
  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
      Hyper-Threading Technology: Enabled
      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
Thread(s) per core:    1
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
  22.         mpz_add(next,res,prev)
  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) {
  85.         a = addis(fk1, fk1);
  86.         b = subis(a, fk);
  87.         res = mulis(fk, b);
  88.     } else {
  89.         a = mulis(fk, fk);
  90.         b = mulis(fk1, fk1);
  91.         res = addis(a, b);
  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.  
  113. besFUNCTION(addis)
  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);
  123.   mpz_add (res, op1, op2);
  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"
  7. DECLARE SUB ::BI_ADD            ALIAS "addis"           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
  18.     a = GMP::BI_ADD(fk1, fk1)
  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)
  24.     res = GMP::BI_ADD(a, b)
  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.  
  71. besFUNCTION(bi_add)
  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.  
  84.   mpz_add(res, s1, s2);
  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.  

biadd.sb
Code: Script BASIC
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  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.  
  9. PRINT BI_ADD(a,b),"\n"
  10.  

Output

rs@jrs-laptop:~/sb/GMP$ scriba biadd.sb
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.  
  71. besFUNCTION(bi_add)
  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.  
  86.   mpz_add(res, s1, s2);
  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
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  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.  
  8. PRINT BI_ADD(a,b),"\n"
  9.  


jrs@jrs-laptop:~/sb/GMP$ scriba biadd.sb
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
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  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
  13.       m = BI_ADD(p, q)
  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.  
  89. besFUNCTION(bi_add)
  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.  
  104.   mpz_add(res, op1, op2);
  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
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  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
  11.       m = BI_ADD(p, q)
  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
  1. besFUNCTION(bi_add)
  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.  
  16.   mpz_add(res, op1, op2);
  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.  
  87. besFUNCTION(bi_add)
  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.  
  99.   mpz_add(res, op1, op2);
  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.  
  30.     mpz_add(p, psq, qsq);
  31.     mpz_add(q, twopq, qsq);
  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.  
  39.     mpz_add(a, bq, aq);
  40.     mpz_add(a, a, ap);
  41.  
  42.     mpz_add(b, bp, aq);
  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.  
  26.         p = gmp2::add(psq, qsq)
  27.         q = gmp2::add(twopq, qsq)
  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.  
  36.         a = gmp2::add(bq, aq)
  37.         a = gmp2::add(a, ap)
  38.  
  39.         b = gmp2::add(bp, aq)
  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
  8.   HEADER : interface.h
  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
  124. ACTUAL INTERPRETER THREAD
  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. /**
  278. =section add
  279. =H add
  280.  
  281. Adds mpz_t objects
  282. */
  283. besFUNCTION(add)
  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);
  297.   mpz_add(g_Res, g_Op1, g_Op2);
  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
  307. =H add
  308.  
  309. Adds mpz_t objects
  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.  
  322.   // mpz_add(r, s, t);
  323.   i=12345;
  324.  
  325.   besRETURN_LONG(i);
  326. besEND
  327.  
  328. /**
  329. =section get_string
  330. =H add
  331.  
  332. Adds mpz_t objects
  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 },
  370. { "add" , add },
  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
  1. besFUNCTION(add)
  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);
  15.   mpz_add(g_Res, g_Op1, g_Op2);
  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
  1. besFUNCTION(bi_add)
  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.  
  13.   mpz_add(res, op1, op2);
  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

Your approach introduces additional overhead to init/clear/int/clear/etc.

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.  
  18.         p = gmp2::add(psq, qsq)
  19.         q = gmp2::add(twopq, qsq)
  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.  
  28.         a = gmp2::add(bq, aq)
  29.         a = gmp2::add(a, ap)
  30.  
  31.         b = gmp2::add(bp, aq)
  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.

++ = add
-- = 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 operators
Dim Shared As Long mpfr_digits_precision = 1000001 '<- set mpfr digits-precision
Dim 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
wend
end sub

dim as double t=timer
dim as mpfr b

fib2(4784969, b)
print b
print "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=timer
dim as mpfr b, sum
for i as integer=1 to 500
fib2(4784969, b)
sum+=b
next
print sum
print "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.