// success. s can be given as a (possibly signed) fraction "a/b", or as a
// floating-point number optionally followed by an exponent.
// If a fraction is provided, both the dividend and the divisor may be a
-// decimal integer or independently use a prefix of ``0b'', ``0'' or ``0o'',
-// or ``0x'' (or their upper-case variants) to denote a binary, octal, or
+// decimal integer or independently use a prefix of “0b”, “0” or “0o”,
+// or “0x” (or their upper-case variants) to denote a binary, octal, or
// hexadecimal integer, respectively. The divisor may not be signed.
// If a floating-point number is provided, it may be in decimal form or
-// use any of the same prefixes as above but for ``0'' to denote a non-decimal
-// mantissa. A leading ``0'' is considered a decimal leading 0; it does not
+// use any of the same prefixes as above but for “0” to denote a non-decimal
+// mantissa. A leading “0” is considered a decimal leading 0; it does not
// indicate octal representation in this case.
-// An optional base-10 ``e'' or base-2 ``p'' (or their upper-case variants)
+// An optional base-10 “e” or base-2 “p” (or their upper-case variants)
// exponent may be provided as well, except for hexadecimal floats which
-// only accept an (optional) ``p'' exponent (because an ``e'' or ``E'' cannot
+// only accept an (optional) “p” exponent (because an “e” or “E” cannot
// be distinguished from a mantissa digit). If the exponent's absolute value
// is too large, the operation may fail.
// The entire string, not just a prefix, must be valid for success. If the
if n > 1e6 {
return nil, false // avoid excessively large exponents
}
- pow5 := z.b.abs.expNN(natFive, nat(nil).setWord(Word(n)), nil) // use underlying array of z.b.abs
+ pow5 := z.b.abs.expNN(natFive, nat(nil).setWord(Word(n)), nil, false) // use underlying array of z.b.abs
if exp5 > 0 {
z.a.abs = z.a.abs.mul(z.a.abs, pow5)
z.b.abs = z.b.abs.setWord(1)
}
// scanExponent scans the longest possible prefix of r representing a base 10
-// (``e'', ``E'') or a base 2 (``p'', ``P'') exponent, if any. It returns the
+// (“e”, “E”) or a base 2 (“p”, “P”) exponent, if any. It returns the
// exponent, the exponent base (10 or 2), or a read or syntax error, if any.
//
-// If sepOk is set, an underscore character ``_'' may appear between successive
+// If sepOk is set, an underscore character “_” may appear between successive
// exponent digits; such underscores do not change the value of the exponent.
// Incorrect placement of underscores is reported as an error if there are no
// other errors. If sepOk is not set, underscores are not recognized and thus
p := natOne
if prec > 0 {
- p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil)
+ p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil, false)
}
r = r.mul(r, p)
return string(buf)
}
+
+// Note: FloatPrec (below) is in this file rather than rat.go because
+// its results are relevant for decimal representation/printing.
+
+// FloatPrec returns the number n of non-repeating digits immediately
+// following the decimal point of the decimal representation of x.
+// The boolean result indicates whether a decimal representation of x
+// with that many fractional digits is exact or rounded.
+//
+// Examples:
+//
+// x n exact decimal representation n fractional digits
+// 0 0 true 0
+// 1 0 true 1
+// 1/2 1 true 0.5
+// 1/3 0 false 0 (0.333... rounded)
+// 1/4 2 true 0.25
+// 1/6 1 false 0.2 (0.166... rounded)
+func (x *Rat) FloatPrec() (n int, exact bool) {
+ // Determine q and largest p2, p5 such that d = q·2^p2·5^p5.
+ // The results n, exact are:
+ //
+ // n = max(p2, p5)
+ // exact = q == 1
+ //
+ // See https://en.wikipedia.org/wiki/Repeating_decimal for
+ // details.
+ d := x.Denom().abs // d >= 1
+
+ // Determine p2 by counting factors of 2.
+ // p2 corresponds to the trailing zero bits in d.
+ // Do this first to reduce q as much as possible.
+ var q nat
+ p2 := d.trailingZeroBits()
+ q = q.shr(d, p2)
+
+ // Determine p5 by counting factors of 5.
+
+ // Build a table starting with an initial power of 5,
+ // and using repeated squaring until the factor doesn't
+ // divide q anymore. Then use the table to determine
+ // the power of 5 in q.
+ //
+ // Setting the table limit to 0 turns this off;
+ // a limit of 1 uses just one factor 5^fp.
+ // Larger values build up a more comprehensive table.
+ const fp = 13 // f == 5^fp
+ const limit = 100 // table size limit
+ var tab []nat // tab[i] == 5^(fp·2^i)
+ f := nat{1220703125} // == 5^fp (must fit into a uint32 Word)
+ var t, r nat // temporaries
+ for len(tab) < limit {
+ if _, r = t.div(r, q, f); len(r) != 0 {
+ break // f doesn't divide q evenly
+ }
+ tab = append(tab, f)
+ f = f.sqr(f)
+ }
+
+ // TODO(gri) Optimization: don't waste the successful
+ // division q/f above; instead reduce q and
+ // count the multiples.
+
+ // Factor q using the table entries, if any.
+ var p5, p uint
+ for i := len(tab) - 1; i >= 0; i-- {
+ q, p = multiples(q, tab[i])
+ p5 += p << i * fp
+ }
+
+ q, p = multiples(q, natFive)
+ p5 += p
+
+ return int(max(p2, p5)), q.cmp(natOne) == 0
+}
+
+// multiples returns d and largest p such that x = d·f^p.
+// x and f must not be 0.
+func multiples(x, f nat) (d nat, p uint) {
+ // Determine p through repeated division.
+ d = d.set(x)
+ // p == 0
+ var q, r nat
+ for {
+ // invariant x == d·f^p
+ q, r = q.div(r, d, f)
+ if len(r) != 0 {
+ return
+ }
+ // q == d/f
+ // x == q·f·f^p
+ p++
+ // x == q·f^p
+ d = d.set(q)
+ }
+}