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 is NOT permitted.
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.