From dd88f23a2006307f835f42063b5168ec56c2c428 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Thu, 2 Nov 2023 21:48:03 -0700 Subject: [PATCH] math/big: implement Rat.FloatPrec goos: darwin goarch: amd64 pkg: math/big cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz BenchmarkFloatPrecExact/1-12 9380685 125.0 ns/op BenchmarkFloatPrecExact/10-12 3780493 321.2 ns/op BenchmarkFloatPrecExact/100-12 698272 1679 ns/op BenchmarkFloatPrecExact/1000-12 117975 9113 ns/op BenchmarkFloatPrecExact/10000-12 5913 192768 ns/op BenchmarkFloatPrecExact/100000-12 164 7401817 ns/op BenchmarkFloatPrecExact/1000000-12 4 293568523 ns/op BenchmarkFloatPrecInexact/1-12 12836612 91.26 ns/op BenchmarkFloatPrecInexact/10-12 10144908 114.9 ns/op BenchmarkFloatPrecInexact/100-12 4121931 297.3 ns/op BenchmarkFloatPrecInexact/1000-12 1275886 927.7 ns/op BenchmarkFloatPrecInexact/10000-12 170392 6546 ns/op BenchmarkFloatPrecInexact/100000-12 18307 65232 ns/op BenchmarkFloatPrecInexact/1000000-12 1701 621412 ns/op Fixes #50489. Change-Id: Ic952f00e35d42f2470ecab53df712721997eac94 Reviewed-on: https://go-review.googlesource.com/c/go/+/539299 TryBot-Result: Gopher Robot Reviewed-by: Cherry Mui Auto-Submit: Robert Griesemer Run-TryBot: Robert Griesemer Reviewed-by: Robert Griesemer --- api/next/50489.txt | 1 + src/math/big/ratconv.go | 96 ++++++++++++++++++++++++++++ src/math/big/ratconv_test.go | 117 +++++++++++++++++++++++++++++++++++ 3 files changed, 214 insertions(+) create mode 100644 api/next/50489.txt diff --git a/api/next/50489.txt b/api/next/50489.txt new file mode 100644 index 0000000000..5fc8723c9e --- /dev/null +++ b/api/next/50489.txt @@ -0,0 +1 @@ +pkg math/big, method (*Rat) FloatPrec() (int, bool) #50489 diff --git a/src/math/big/ratconv.go b/src/math/big/ratconv.go index 8537a6795f..9fb5711ff9 100644 --- a/src/math/big/ratconv.go +++ b/src/math/big/ratconv.go @@ -378,3 +378,99 @@ func (x *Rat) FloatString(prec int) string { 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) + } +} diff --git a/src/math/big/ratconv_test.go b/src/math/big/ratconv_test.go index 45a35608f4..1f5b47eab4 100644 --- a/src/math/big/ratconv_test.go +++ b/src/math/big/ratconv_test.go @@ -624,3 +624,120 @@ func TestIssue45910(t *testing.T) { } } } +func TestFloatPrec(t *testing.T) { + var tests = []struct { + f string + prec int + ok bool + fdec string + }{ + // examples from the issue #50489 + {"10/100", 1, true, "0.1"}, + {"3/100", 2, true, "0.03"}, + {"10", 0, true, "10"}, + + // more examples + {"zero", 0, true, "0"}, // test uninitialized zero value for Rat + {"0", 0, true, "0"}, // 0 + {"1", 0, true, "1"}, // 1 + {"1/2", 1, true, "0.5"}, // 0.5 + {"1/3", 0, false, "0"}, // 0.(3) + {"1/4", 2, true, "0.25"}, // 0.25 + {"1/5", 1, true, "0.2"}, // 0.2 + {"1/6", 1, false, "0.2"}, // 0.1(6) + {"1/7", 0, false, "0"}, // 0.(142857) + {"1/8", 3, true, "0.125"}, // 0.125 + {"1/9", 0, false, "0"}, // 0.(1) + {"1/10", 1, true, "0.1"}, // 0.1 + {"1/11", 0, false, "0"}, // 0.(09) + {"1/12", 2, false, "0.08"}, // 0.08(3) + {"1/13", 0, false, "0"}, // 0.(076923) + {"1/14", 1, false, "0.1"}, // 0.0(714285) + {"1/15", 1, false, "0.1"}, // 0.0(6) + {"1/16", 4, true, "0.0625"}, // 0.0625 + + {"10/2", 0, true, "5"}, // 5 + {"10/3", 0, false, "3"}, // 3.(3) + {"10/6", 0, false, "2"}, // 1.(6) + {"1/10000000", 7, true, "0.0000001"}, // 0.0000001 + {"1/3125", 5, true, "0.00032"}, // "0.00032" + {"1/1024", 10, true, "0.0009765625"}, // 0.0009765625 + {"1/304000", 7, false, "0.0000033"}, // 0.0000032(894736842105263157) + {"1/48828125", 11, true, "0.00000002048"}, // 0.00000002048 + } + + for _, test := range tests { + var f Rat + + // check uninitialized zero value + if test.f != "zero" { + _, ok := f.SetString(test.f) + if !ok { + t.Fatalf("invalid test case: f = %s", test.f) + } + } + + // results for f and -f must be the same + fdec := test.fdec + for i := 0; i < 2; i++ { + prec, ok := f.FloatPrec() + if prec != test.prec || ok != test.ok { + t.Errorf("%s: FloatPrec(%s): got prec, ok = %d, %v; want %d, %v", test.f, &f, prec, ok, test.prec, test.ok) + } + s := f.FloatString(test.prec) + if s != fdec { + t.Errorf("%s: FloatString(%s, %d): got %s; want %s", test.f, &f, prec, s, fdec) + } + // proceed with -f but don't add a "-" before a "0" + if f.Sign() > 0 { + f.Neg(&f) + fdec = "-" + fdec + } + } + } +} + +func BenchmarkFloatPrecExact(b *testing.B) { + for _, n := range []int{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6} { + // d := 5^n + d := NewInt(5) + p := NewInt(int64(n)) + d.Exp(d, p, nil) + + // r := 1/d + var r Rat + r.SetFrac(NewInt(1), d) + + b.Run(fmt.Sprint(n), func(b *testing.B) { + for i := 0; i < b.N; i++ { + prec, ok := r.FloatPrec() + if prec != n || !ok { + b.Fatalf("got exact, ok = %d, %v; want %d, %v", prec, ok, uint64(n), true) + } + } + }) + } +} + +func BenchmarkFloatPrecInexact(b *testing.B) { + for _, n := range []int{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6} { + // d := 5^n + 1 + d := NewInt(5) + p := NewInt(int64(n)) + d.Exp(d, p, nil) + d.Add(d, NewInt(1)) + + // r := 1/d + var r Rat + r.SetFrac(NewInt(1), d) + + b.Run(fmt.Sprint(n), func(b *testing.B) { + for i := 0; i < b.N; i++ { + _, ok := r.FloatPrec() + if ok { + b.Fatalf("got unexpected ok") + } + } + }) + } +} -- 2.44.0