0xkohe

package main

import (
	"fmt"
	"math/big"
	"math/rand"
	"time"
)

func main() {

0xkohe

package main

import (
	"fmt"
	"math/big"
)

type fibNum struct {
	num               *big.Rat
	numMultipliedBySR *big.Rat

0xkohe

func fibMin(t1, t2 fibNum) (r fibNum) {
	r1 := new(big.Rat).Add(
		t1.num,
		new(big.Rat).Mul(t2.num, big.NewRat(-1, 1)),
	)

	r2 := new(big.Rat).Add(
		t1.numMultipliedBySR,
		new(big.Rat).Mul(t2.numMultipliedBySR, big.NewRat(-1, 1)),
	)

0xkohe

func fibExp(t fibNum, n int) fibNum {

	r := t

	// 1
	a := fibNum{num: big.NewRat(1, 1), numMultipliedBySR: big.NewRat(0, 999)}

	for n > 1 {
		if n%2 == 1 {
			a = fibMul(a, r)

0xkohe

func fibExp(t fibNum, n int) (r fibNum) {
	r := t
	for i := 1; i < n; i++ {
		r = fibMul(t, r)
	}
	return
}

0xkohe

//(a+b√5)(c+d√5) = (ac+5bd)+(ad+bc)√5
func fibMul(t1, t2 fibNum) (r fibNum) {
	//(ac+5bd)
	var r1, r2 *big.Rat
	tmp1 := new(big.Rat).Mul(t1.num, t2.num)
	tmp2 := new(big.Rat).Mul(
		new(big.Rat).Mul(t1.numMultipliedBySR, t2.numMultipliedBySR),
		big.NewRat(5, 1),
	)
	r1 = new(big.Rat).Add(tmp1, tmp2)

0xkohe

func calcFib(n int) *big.Int {
	// (1+√5)/2
	a := big.NewRat(1, 2)
	b := big.NewRat(1, 2)
	x := fibNum{a, b}

	// (1-√5)/2
	c := big.NewRat(1, 2)
	d := big.NewRat(-1, 2)
	y := fibNum{c, d}

0xkohe

a := big.NewRat(1, 2)
b := big.NewRat(1, 2)
fibNum{a, b}

0xkohe

type fibNum struct {
	num               *big.Rat
	numMultipliedBySR *big.Rat
}

0xkohe

func fib(num int) int {
	if num <= 1 {
		return num
	}
	return fib(num-2) + fib(num-1)
}