Float Accuracy in Go

Question

This question is a follow on from a previous question I asked. The answers I received suggested that I make use of the Go math.Big library. In this question I use the library but unfortunately to little effect.

I am trying to using the Binet formula to calculate fib(100). I am using Go's Big.Float but without success. I get accuracy to about 10 decimal places. Please advise.

I am trying to avoid loops/recursion as I think these approaches will not scale well. Hence my attempt to leverage Binet's formula

// currently produces inaccurate results as the input increases.

package main

import (
    "fmt"
    "math/big"
    "math"
    "strconv"
)

func fib(n int) float64  {
    var sroot5 = new(big.Float).SetPrec(200).SetFloat64(2.236067977499789696409173668731276235440618359611525724270897)
    var phi = new(big.Float).SetPrec(200).SetFloat64(1.61803398874989484820458683436563811772030917980576286213544862)
    var minusPhi = new(big.Float).SetPrec(200).SetFloat64(-0.61803398874989484820458683436563811772030917980576)

    var fltP float64;
    fltP, _ = phi.Float64()

    var fltN float64;
    fltN, _ = minusPhi.Float64()

    var denom float64
    denom, _ = sroot5.Float64()

    // Magic fib formula (Binet) is:
    // (Phi ^ n - (-phi ^ n)) / sqrt(5)

    z := (math.Pow(fltP, float64(n)) - math.Pow(fltN, float64(n))) / denom 

    return math.Ceil(z) 

}

func main() {

    fib(100)

    fmt.Println(strconv.FormatFloat(fib(100), 'f', 0, 64))
    fmt.Println("true answer of fib(100) should be -> 354224848179261915075")

}

Read http://floating-point-gui.de/ and consider using some [bignum](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic) library — Basile Starynkevitch, Aug 22 '15 at 15:37
You asked basically the same thing yesterday: [Accuracy in Go Programs](http://stackoverflow.com/questions/32143511/accuracy-in-go-programs) — Dave C, Aug 22 '15 at 16:49
Notice that the argument of `SetFloat64()` has type `float64`, thus your high precision is being truncated to the precision of a `float64` before being converted to a big float. — fuz, Aug 22 '15 at 17:02
If I read this right, you're creating a bunch of high-accuracy variables, and then immediately converting them back to standard floats *before* doing anything with them. So you might as well skip the use of big.Float entirely. — IMSoP, Aug 22 '15 at 17:04
Yes the Go math.Pow function only accepts float64 types not big.Float. I need to find an alternative way of raising powers that will work with larger datatypes — Kevin, Aug 22 '15 at 17:09
OK, so that's the question you should be asking then - you know why this code doesn't work (it's using float64 values, which have limited accuracy), because it's effectively the same as you posted in your previous question. — IMSoP, Aug 22 '15 at 17:12

peterSO · Answer 1 · 2015-08-22T22:50:03.933

6

You are using IEEE 754 64-bit floating point.

In Go, to calculate fib(100) accurately you could simply say:

package main

import (
    "fmt"
    "math/big"
)

func fib(n int) *big.Int {
    f := big.NewInt(0)
    a, b := big.NewInt(0), big.NewInt(1)
    for i := 0; i <= n; i++ {
        f.Set(a)
        a.Set(b)
        b.Add(f, b)
    }
    return f
}

func main() {
    fmt.Println(fib(100))
}

Output:

354224848179261915075

edited Aug 22 '15 at 22:50

answered Aug 22 '15 at 16:00

peterSO

158,998
31
281
276

Thank you for your answer. I guess I am trying to avoid loops which will not perform so well when the input to fib is high. Your solution is great when you pass 100 but performs more slowly as the numbers increase. Which is why I am trying out Binet's method. – Kevin Aug 22 '15 at 16:18
3

@Kevin The fastest way to compute Fibonacci numbers is via repeated matrix squaring as described [here](https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form). You don't really want to mess with floating point numbers as the results get imprecise. – fuz Aug 22 '15 at 17:00
@Kevin, adding 100 `big.Int`s could be faster than calling calculating Binet's formula using `big.Float`. – kostya Aug 24 '15 at 07:24
Agreed, but will adding 4 millions ints be faster? – Kevin Aug 25 '15 at 12:41

Float Accuracy in Go

1 Answers1