package kata

import (
	"math"
)

var sqrt5 = math.Sqrt(5)
var Phi1 = (1.0 + sqrt5) / 2
var Phi2 = (1.0 - sqrt5) / 2

/*
Binet returns the n-th element of the Fibonacci suite using Binet's formula.
*/
func Binet(n uint64) uint64 {
	fn := float64(n)
	fl := (math.Pow(Phi1, fn) - math.Pow(Phi2, fn)) / sqrt5
	res := uint64(math.Round(fl))
	return res
}

/*
Prod return Fibonacci(n)*Fibonacci(n+1).
 */
func Prod(n uint64) uint64 {
	return Binet(n) * Binet(n+1)
}

/*
Near returns an integer n such as Fib(n)*Fib(n+1) be close to be the argument received.

The approximation used is based on Binet's formula for Fibonacci.
*/
func Near(prod uint64) (n uint64, ok bool) {
	// fn is within 1 of the actual value if it exists.
	fn := math.Log(math.Sqrt(5*float64(prod)/Phi1)) / math.Log(Phi1)
	b, c := uint64(math.Floor(fn)), uint64(math.Ceil(fn))
	a, d := b-1, c+1
	for _, x := range [...]uint64{a, b, c, d} {
		if Prod(x) == prod {
			return x, true
		}
	}
	for _, x := range [...]uint64{a, b, c, d} {
		if Prod(x) > prod {
			return x, false
		}
	}
	return d+1, false
}

func ProductFib(prod uint64) [3]uint64 {
	// n is within 1 of the actual potential solution.
	n, ok := Near(prod)
	return [3]uint64{Binet(n), Binet(n + 1), map[bool]uint64{false: 0, true: 1}[ok]}
}