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

Offline AIR

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



Offline jalih

  • Advocate
  • Posts: 49
Re: fibonacci(4784969)
« Reply #31 on: April 22, 2019, 08:47:31 AM »
RPI 3B+

Very good time! How long does it take to output the whole result?

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #32 on: April 22, 2019, 08:58:29 AM »
Printing is always expensive....



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

« Last Edit: April 22, 2019, 09:26:46 AM by AIR »

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #33 on: April 22, 2019, 09:52:04 AM »
GMP is the only way to fly. (with unreal numbers)
« Last Edit: April 22, 2019, 06:37:38 PM by John »

Offline jalih

  • Advocate
  • Posts: 49
Re: fibonacci(4784969)
« Reply #34 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.
« Last Edit: April 23, 2019, 07:24:02 AM by jalih »

Offline AIR

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



Offline jalih

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

Offline AIR

  • BASIC Developer
  • Posts: 628
Re: fibonacci(4784969)
« Reply #37 on: April 23, 2019, 01:41:57 PM »
Jali, you say you "format" the number into a string rather than say "convert".  Interesting.

Offline John

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

Offline AIR

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

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #40 on: April 23, 2019, 07:13:52 PM »
Nice finish!

Offline AIR

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

Offline petelomax

  • BASIC Developer
  • Posts: 8
  • Author of Phix
    • The Phix Programming Language
Re: fibonacci(4784969)
« Reply #42 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.  

Offline John

  • Forum Support / SB Dev
  • Posts: 2622
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #43 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?
« Last Edit: May 18, 2019, 08:23:14 PM by John »