Floating-point numbers, as we know, are notorious for losing precision when their values become too large or too small. They are also bad at representing decimals accurately, yielding confusions like `0.1 + 0.2 != 0.3`

for every beginner in their programming 101.

Albeit being imprecise, floats are good enough for most daily scenarios. For those not, however, Golang provides `*big.Rat`

to the rescue. Rats are designed to represent rational numbers with arbitary precision, addressing most flaws of floats, yet at a cost of much slower computation speed and bigger memory footprint. For example, we are confident to compare `0.1 + 0.2`

to `0.3`

using Rats without caring about tolerance:

`package main`

import (

"fmt"

"math/big"

)

func main() {

x, y := 0.1, 0.2

f := x + y

fmt.Printf("%.20f %v\n", f, f == 0.3)

// 0.30000000000000004441 false

a, b := new(big.Rat).SetFrac64(1, 10), new(big.Rat).SetFrac64(2, 10)

c := new(big.Rat).Add(a, b)

c2 := new(big.Rat).SetFrac64(3, 10)

fmt.Printf("%s %v\n", c.FloatString(20), c.Cmp(c2) == 0)

// 0.30000000000000000000 true

}

You may have noticed that the Rats are initialized by the `z.SetFrac64(a, b)`

method, which sets `z`

to the fractional number `a/b`

. In fact there’s even a `z.SetString()`

to parse a Rat from either its fractional or decimal representation, which is a convenient utility:

`r1, ok1 := new(big.Rat).SetString("3/5")`

r2, ok2 := new(big.Rat).SetString("0.6")

In the above listing, both `r1`

and `r2`

equal to the same number of 0.6. `.SetString()`

smartly infers the input format and performs parsing.

Now let’s think about the reversed problem – how to display a `*big.Rat`

as string smartly and loselessly?

To clarify, we would like to obtain a string `s`

from the given Rat `z`

. `s`

is formatted as decimal when `z`

could be written as finite decimal, and otherwise formatted as fractional. If we give name `SmartRatString()`

to such a function, some samples may be:

`SmartRatString(new(big.Rat).SetFrac64(3, 5)) == "0.6"`

SmartRatString(new(big.Rat).SetFrac64(1, 3)) == "1/3" // instead of 0.33333...

This is a legitimate use case. You may want to print out some numbers to the user, and expect they would be parsed *exactly* as they were if being typed back, for the motive of reproducibility or whatever. Simultaneously, the numbers should be in decimal form whenever they could, to conform the preference of human.

Unfortunately, `*big.Rat`

does not come with such conversion method. The most relevant ones we could find are RatString() and FloatString(prec). `RatString()`

always converts the Rat into fractional form `a/b`

, while `FloatString(prec)`

displays it as decimal form with exactly `prec`

digits after the decimal point.

A straightforward thought is to combine the two utility methods in an adaptive way. If the Rat couldn’t be written as finite decimal, we call the `RatString()`

. Otherwise, we compute the appropriate `prec`

for `FloatString()`

such that the Rat is converted into decimal form without any truncation. In such a way, we reduce the problem into two simpler ones:

- How to determine a Rat has a finite decimal representation?
- How to compute the number of digits after the decimal point?

Answers to both problems concealed in the factorization of the denominator. Say we have a rational number $z=a/b$ where $b \in \mathbb{Z}^+$ and $gcd(a, b)=1$. $z$ has a finite decimal form if and only if $b=2^n5^m$ for some natural numbers $n$ and $m$, while $\max(n, m)$ being the number of digits after the decimal point. These conclusions can be derived from some easy math so we won’t discuss in this post.

The following section will focus on the implementation. We can sketch out the framework of `SmartRatString()`

:

`func SmartRatString(r *big.Rat) string {`

denom := new(big.Int).Set(r.Denom())

n := ... // compute 2's power in the factorization of denom

// denom = denom / 2^n

m, isFiveExp := ... // check power of 5

if !isFiveExp {

return r.RatString()

}

return r.FloatString(int(max(n, m)))

}

Estimating `n`

is the easiest part. We can compute `n`

by counting zero bits at the rear of `denom`

‘s binary form, with the help of `TrailingZeroBits()`

method. Dividing `denom`

by `2^n`

can also be achieved efficiently with bitwise right shifting. We complete the first blank as follows:

`func SmartRatString(r *big.Rat) string {`

denom := new(big.Int).Set(r.Denom())

n := denom.TrailingZeroBits()

denom.Rsh(&denom, n)

m, isFiveExp := ... // check power of 5

if !isFiveExp {

return r.RatString()

}

return r.FloatString(int(max(n, m)))

}

For the second part, however, there’s no shortcut, at least I don’t have an idea. We have to iteratively divide `denom`

by 5 until the process cannot proceed. For readability I write a small function `log5`

:

`var intOne = new(big.Int).SetUint64(1)`

var intFive = new(big.Int).SetUint64(5)

// log5 checks x in the form of $5^m$ or not. If so, isExp is true

// and cnt stores the power $m$.

func log5(x *big.Int) (cnt uint, isExp bool) {

tmp2 := new(big.Int)

m := new(big.Int) // m stores the modulo

for x.CmpAbs(intOne) > 0 {

tmp2.DivMod(x, intFive, m)

if m.Sign() != 0 { // m != 0

return cnt, false

}

cnt++

x, tmp2 = tmp2, x

}

return cnt, true

}

This function is not efficient but it serves the purpose. We modify the second part of `SmartRatString()`

accordingly:

`var intOne = new(big.Int).SetUint64(1)`

var intFive = new(big.Int).SetUint64(5)

// log5 checks x in the form of $5^m$ or not. If so, isExp is true

// and cnt stores the power $m$.

func log5(x *big.Int) (cnt uint, isExp bool) {

tmp2 := new(big.Int)

m := new(big.Int) // m stores the modulo

for x.CmpAbs(intOne) > 0 {

tmp2.DivMod(x, intFive, m)

if m.Sign() != 0 { // m != 0

return cnt, false

}

cnt++

x, tmp2 = tmp2, x

}

return cnt, true

}

func SmartRatString(r *big.Rat) string {

denom := new(big.Int).Set(r.Denom())

n := denom.TrailingZeroBits()

denom.Rsh(&denom, n)

m, isFiveExp := log5(&denom)

if !isFiveExp {

return r.RatString()

}

return r.FloatString(int(max(n, m)))

}

With all these in hand, we have finished the complete function of `SmartRatString()`

.

Author:hsfzxjy.Link:.License:CC BY-NC-ND 4.0.

All rights reserved by the author.

Commercial use of this post in any form isNOTpermitted.

Non-commercial use of this post should be attributed with this block of text.

## OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.