Author Topic: fibonacci(4784969)  (Read 717 times)

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #15 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$
« Last Edit: April 20, 2019, 03:22:06 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #16 on: April 20, 2019, 03:33:51 PM »
Re-read my reply and you'll see what you're doing wrong.

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #17 on: April 20, 2019, 03:42:33 PM »
It's working so I guess you posted before reading my last post.

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #18 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?

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #19 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.

Offline jalih

  • Advocate
  • Posts: 49
Re: fibonacci(4784969)
« Reply #20 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.

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #21 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. }

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #22 on: April 21, 2019, 10:41:00 AM »
How does execution time look?

Offline jalih

  • Advocate
  • Posts: 49
Re: fibonacci(4784969)
« Reply #23 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;
« Last Edit: April 21, 2019, 11:19:26 AM by jalih »

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #24 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

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #25 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.

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #26 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+?

Offline jalih

  • Advocate
  • Posts: 49
Re: fibonacci(4784969)
« Reply #27 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.

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #28 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.

Offline jalih

  • Advocate
  • Posts: 49
Re: fibonacci(4784969)
« Reply #29 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+ ?