-
Notifications
You must be signed in to change notification settings - Fork 1
/
fibonacci.go
54 lines (49 loc) · 1.06 KB
/
fibonacci.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package fibonacci
import (
"log"
"math/big"
)
var debug = false
// Calc returns n-th Fibonacci number. It computes Fibonacci numbers in time O(log(n))
// and uses 'Rising a matrix to the power' method: (F0, F1) * P^n = (Fn, Fn+1).
// Calc panics if n is negative.
func Calc(n int64) *big.Int {
if n < 0 {
panic("Calc: index should be not negative")
}
var a, b, c, d big.Int
var ta, tb, tc big.Int
var rc, rd big.Int
a.SetInt64(1)
b.SetInt64(1)
c.SetInt64(1)
rd.SetInt64(1)
for n != 0 {
var tmp big.Int
if (n & 1) != 0 {
tc.Set(&rc)
rc.Mul(&rc, &a)
tmp.Mul(&rd, &c)
rc.Add(&rc, &tmp)
tmp.Mul(&rd, &d)
rd.Mul(&tc, &b)
rd.Add(&rd, &tmp)
if debug {
log.Printf("rc: %s, rd: %s", rc.String(), rd.String())
}
}
ta.Set(&a)
tb.Set(&b)
tc.Set(&c)
a.Add(a.Mul(&a, &a), tmp.Mul(&b, &c))
b.Add(tmp.Mul(&ta, &b), b.Mul(&b, &d))
c.Add(tmp.Mul(&ta, &c), c.Mul(&c, &d))
d.Add(d.Mul(&d, &d), tmp.Mul(&tc, &tb))
if debug {
log.Printf("a: %s, b: %s", &a, &b)
log.Printf("c: %s, d: %s", &c, &d)
}
n >>= 1
}
return &rc
}