fibonacci(4784969)

[John]

Works! 

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: ScriptBasic

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$

[AIR]

Re-read my reply and you'll see what you're doing wrong.

[John]

It's working so I guess you posted before reading my last post.

[John]

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?

[AIR]

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.

[jalih]

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.

[AIR]

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

[John]

How does execution time look?

[jalih]

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;


[AIR]

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

[AIR]

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.

[John]

ScriptBasic 1 mil fibo challenge.

Code: ScriptBasic

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

[jalih]

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.

[AIR]

ScriptBasic 1 mil fibo challenge.

Code: ScriptBasic

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.

[jalih]

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