From e4ba40030f9ba4b61bb28dbf78bb41a7b14e6788 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Mon, 18 Mar 2019 16:10:07 -0700 Subject: [PATCH] math/big: accept non-decimal floats with Rat.SetString This fixes an old oversight. Rat.SetString already permitted fractions a/b where both a and b could independently specify a base prefix. With this CL, it now also accepts non-decimal floating-point numbers. Fixes #29799. Change-Id: I9cc65666a5cebb00f0202da2e4fc5654a02e3234 Reviewed-on: https://go-review.googlesource.com/c/go/+/168237 Reviewed-by: Emmanuel Odeke --- src/math/big/floatconv.go | 14 ++-- src/math/big/nat.go | 7 +- src/math/big/ratconv.go | 124 ++++++++++++++++++++++++++++------- src/math/big/ratconv_test.go | 26 +++++++- 4 files changed, 133 insertions(+), 38 deletions(-) diff --git a/src/math/big/floatconv.go b/src/math/big/floatconv.go index 88216f5600..95e32d3319 100644 --- a/src/math/big/floatconv.go +++ b/src/math/big/floatconv.go @@ -70,8 +70,8 @@ func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error) { } // len(z.mant) > 0 - // The mantissa may have a decimal point (fcount <= 0) and there - // may be a nonzero exponent exp. The decimal point amounts to a + // The mantissa may have a radix point (fcount <= 0) and there + // may be a nonzero exponent exp. The radix point amounts to a // division by b**(-fcount). An exponent means multiplication by // ebase**exp. Finally, mantissa normalization (shift left) requires // a correcting multiplication by 2**(-shiftcount). Multiplications @@ -85,11 +85,11 @@ func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error) { exp2 := int64(len(z.mant))*_W - fnorm(z.mant) exp5 := int64(0) - // determine binary or decimal exponent contribution of decimal point + // determine binary or decimal exponent contribution of radix point if fcount < 0 { - // The mantissa has a "decimal" point ddd.dddd; and - // -fcount is the number of digits to the right of '.'. - // Adjust relevant exponent accordingly. + // The mantissa has a radix point ddd.dddd; and + // -fcount is the number of digits to the right + // of '.'. Adjust relevant exponent accordingly. d := int64(fcount) switch b { case 10: @@ -111,7 +111,7 @@ func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error) { switch ebase { case 10: exp5 += exp - fallthrough + fallthrough // see fallthrough above case 2: exp2 += exp default: diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 336633a2fa..22d7a6cac0 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -35,9 +35,10 @@ import ( type nat []Word var ( - natOne = nat{1} - natTwo = nat{2} - natTen = nat{10} + natOne = nat{1} + natTwo = nat{2} + natFive = nat{5} + natTen = nat{10} ) func (z nat) clear() { diff --git a/src/math/big/ratconv.go b/src/math/big/ratconv.go index 07288ca94f..3ea03d5c61 100644 --- a/src/math/big/ratconv.go +++ b/src/math/big/ratconv.go @@ -38,10 +38,22 @@ func (z *Rat) Scan(s fmt.ScanState, ch rune) error { } // SetString sets z to the value of s and returns z and a boolean indicating -// success. s can be given as a fraction "a/b" or as a decimal floating-point -// number optionally followed by an exponent. The entire string (not just a prefix) -// must be valid for success. If the operation failed, the value of z is -// undefined but the returned value is nil. +// 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 +// 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 +// indicate octal representation in this case. +// 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 +// be distinguished from a mantissa digit). +// The entire string, not just a prefix, must be valid for success. If the +// operation failed, the value of z is undefined but the returned value is nil. func (z *Rat) SetString(s string) (*Rat, bool) { if len(s) == 0 { return nil, false @@ -78,16 +90,17 @@ func (z *Rat) SetString(s string) (*Rat, bool) { } // mantissa - // TODO(gri) allow other bases besides 10 for mantissa and exponent? (issue #29799) - var ecorr int - z.a.abs, _, ecorr, err = z.a.abs.scan(r, 10, true) + var base int + var fcount int // fractional digit count; valid if <= 0 + z.a.abs, base, fcount, err = z.a.abs.scan(r, 0, true) if err != nil { return nil, false } // exponent var exp int64 - exp, _, err = scanExponent(r, false, false) + var ebase int + exp, ebase, err = scanExponent(r, true, true) if err != nil { return nil, false } @@ -103,30 +116,91 @@ func (z *Rat) SetString(s string) (*Rat, bool) { } // len(z.a.abs) > 0 - // correct exponent - if ecorr < 0 { - exp += int64(ecorr) + // The mantissa may have a radix point (fcount <= 0) and there + // may be a nonzero exponent exp. The radix point amounts to a + // division by base**(-fcount), which equals a multiplication by + // base**fcount. An exponent means multiplication by ebase**exp. + // Multiplications are commutative, so we can apply them in any + // order. We only have powers of 2 and 10, and we split powers + // of 10 into the product of the same powers of 2 and 5. This + // may reduce the the size of shift/multiplication factors or + // divisors required to create the final fraction, depending + // on the actual floating-point value. + + // determine binary or decimal exponent contribution of radix point + var exp2, exp5 int64 + if fcount < 0 { + // The mantissa has a radix point ddd.dddd; and + // -fcount is the number of digits to the right + // of '.'. Adjust relevant exponent accordingly. + d := int64(fcount) + switch base { + case 10: + exp5 = d + fallthrough // 10**e == 5**e * 2**e + case 2: + exp2 = d + case 8: + exp2 = d * 3 // octal digits are 3 bits each + case 16: + exp2 = d * 4 // hexadecimal digits are 4 bits each + default: + panic("unexpected mantissa base") + } + // fcount consumed - not needed anymore } - // compute exponent power - expabs := exp - if expabs < 0 { - expabs = -expabs + // take actual exponent into account + switch ebase { + case 10: + exp5 += exp + fallthrough // see fallthrough above + case 2: + exp2 += exp + default: + panic("unexpected exponent base") + } + // exp consumed - not needed anymore + + // compute pow5 if needed + pow5 := z.b.abs + if exp5 != 0 { + n := exp5 + if n < 0 { + n = -n + } + pow5 = pow5.expNN(natFive, nat(nil).setWord(Word(n)), nil) } - powTen := nat(nil).expNN(natTen, nat(nil).setWord(Word(expabs)), nil) - // complete fraction - if exp < 0 { - z.b.abs = powTen - z.norm() - } else { - z.a.abs = z.a.abs.mul(z.a.abs, powTen) - z.b.abs = z.b.abs[:0] + // apply dividend contributions of exponents + // (start with exp5 so the numbers to multiply are smaller) + if exp5 > 0 { + z.a.abs = z.a.abs.mul(z.a.abs, pow5) + exp5 = 0 + } + if exp2 > 0 { + if int64(uint(exp2)) != exp2 { + panic("exponent too large") + } + z.a.abs = z.a.abs.shl(z.a.abs, uint(exp2)) + exp2 = 0 + } + + // apply divisor contributions of exponents + z.b.abs = z.b.abs.setWord(1) + if exp5 < 0 { + z.b.abs = pow5 + } + if exp2 < 0 { + if int64(uint(-exp2)) != -exp2 { + panic("exponent too large") + } + z.b.abs = z.b.abs.shl(z.b.abs, uint(-exp2)) } z.a.neg = neg && len(z.a.abs) > 0 // 0 has no sign - return z, true + return z.norm(), true } // scanExponent scans the longest possible prefix of r representing a base 10 @@ -250,7 +324,7 @@ func (x *Rat) RatString() string { } // FloatString returns a string representation of x in decimal form with prec -// digits of precision after the decimal point. The last digit is rounded to +// digits of precision after the radix point. The last digit is rounded to // nearest, with halves rounded away from zero. func (x *Rat) FloatString(prec int) string { var buf []byte diff --git a/src/math/big/ratconv_test.go b/src/math/big/ratconv_test.go index dea4d1933a..87ee9fa972 100644 --- a/src/math/big/ratconv_test.go +++ b/src/math/big/ratconv_test.go @@ -135,29 +135,49 @@ var setStringTests = []StringTest{ var setStringTests2 = []StringTest{ // invalid {in: "4/3x"}, + {in: "0/-1"}, + {in: "-1/-1"}, // invalid with separators // (smoke tests only - a comprehensive set of tests is in natconv_test.go) {in: "10_/1"}, {in: "_10/1"}, {in: "1/1__0"}, - {in: "1_000.0"}, // floats are base 10 which doesn't permit separators; see also issue #29799 // valid {"0b1000/3", "8/3", true}, {"0B1000/0x8", "1", true}, - {"-010/1", "-8", true}, - {"-010.", "-10", true}, + {"-010/1", "-8", true}, // 0-prefix indicates octal in this case + {"-010.0", "-10", true}, {"-0o10/1", "-8", true}, {"0x10/1", "16", true}, {"0x10/0x20", "1/2", true}, + {"0010", "10", true}, // 0-prefix is ignored in this case (not a fraction) + {"0x10.0", "16", true}, + {"0x1.8", "3/2", true}, + {"0X1.8p4", "24", true}, + {"0x1.1E2", "2289/2048", true}, // E is part of hex mantissa, not exponent + {"0b1.1E2", "150", true}, + {"0B1.1P3", "12", true}, + {"0o10e-2", "2/25", true}, + {"0O10p-3", "1", true}, + // valid with separators // (smoke tests only - a comprehensive set of tests is in natconv_test.go) {"0b_1000/3", "8/3", true}, {"0B_10_00/0x8", "1", true}, {"0xdead/0B1101_1110_1010_1101", "1", true}, {"0B1101_1110_1010_1101/0XD_E_A_D", "1", true}, + {"1_000.0", "1000", true}, + + {"0x_10.0", "16", true}, + {"0x1_0.0", "16", true}, + {"0x1.8_0", "3/2", true}, + {"0X1.8p0_4", "24", true}, + {"0b1.1_0E2", "150", true}, + {"0o1_0e-2", "2/25", true}, + {"0O_10p-3", "1", true}, } func TestRatSetString(t *testing.T) { -- 2.50.0