76 lines
1.5 KiB
Go
76 lines
1.5 KiB
Go
package fibonacci
|
|
|
|
import (
|
|
"errors"
|
|
"fmt"
|
|
"math/big"
|
|
)
|
|
|
|
// Fibonacci calculates Fibonacci number.
|
|
// This function generated correct values from 0 to 93 sequence number.
|
|
// For bigger values use FibonacciBig function.
|
|
func Fibonacci(n uint) uint64 {
|
|
if n <= 1 {
|
|
return uint64(n)
|
|
}
|
|
|
|
var n2, n1 uint64 = 0, 1
|
|
|
|
for i := uint(2); i < n; i++ {
|
|
n2, n1 = n1, n1+n2
|
|
}
|
|
|
|
return n2 + n1
|
|
}
|
|
|
|
// FibonacciBig calculates Fibonacci number using bit.Int.
|
|
// For the sequence numbers below 94, it is recommended to use Fibonacci function as it is more efficient.
|
|
func FibonacciBig(n uint) *big.Int {
|
|
if n <= 1 {
|
|
return big.NewInt(int64(n))
|
|
}
|
|
|
|
var n2, n1 = big.NewInt(0), big.NewInt(1)
|
|
|
|
for i := uint(1); i < n; i++ {
|
|
n2.Add(n2, n1)
|
|
n1, n2 = n2, n1
|
|
}
|
|
|
|
return n1
|
|
}
|
|
|
|
func FibonacciFromString(str string) (*big.Int, error) {
|
|
|
|
n := new(big.Int)
|
|
n, ok := n.SetString(str, 10)
|
|
|
|
if !ok {
|
|
return nil, errors.New("ConvertError")
|
|
}
|
|
|
|
if n.Sign() != 1 {
|
|
return big.NewInt(int64(n.Int64())), nil
|
|
}
|
|
|
|
// Initialize two big ints with the first two numbers in the sequence.
|
|
a := big.NewInt(0)
|
|
b := big.NewInt(1)
|
|
|
|
// Loop while a is smaller than 1e100.
|
|
for i := int64(1); i <= n.Int64(); i++ {
|
|
// Compute the next Fibonacci number, storing it in a.
|
|
a.Add(a, b)
|
|
// Swap a and b so that b is the next number in the sequence.
|
|
a, b = b, a
|
|
}
|
|
|
|
fmt.Println(a) // 100-digit Fibonacci number
|
|
|
|
// Test a for primality.
|
|
// (ProbablyPrimes' argument sets the number of Miller-Rabin
|
|
// rounds to be performed. 20 is a good value.)
|
|
fmt.Println(a.ProbablyPrime(20))
|
|
|
|
return a, nil
|
|
}
|