From f3d3328988a547cd21bcd398b7155ec390b642d3 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Wed, 4 Mar 2015 14:19:08 -0800 Subject: [PATCH] math/big: move "bits" operations used for Float tests into separate file This is a pure code move without any semantic change. Change-Id: I2c18efc858955d07949b1241e793232f2cf1deb9 Reviewed-on: https://go-review.googlesource.com/6821 Reviewed-by: Alan Donovan --- src/math/big/bits_test.go | 207 +++++++++++++++++++++++++++++++++++++ src/math/big/float_test.go | 197 ----------------------------------- 2 files changed, 207 insertions(+), 197 deletions(-) create mode 100644 src/math/big/bits_test.go diff --git a/src/math/big/bits_test.go b/src/math/big/bits_test.go new file mode 100644 index 0000000000..ef6ade0115 --- /dev/null +++ b/src/math/big/bits_test.go @@ -0,0 +1,207 @@ +// Copyright 2015 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package big + +import ( + "fmt" + "sort" + "testing" +) + +func addBits(x, y []int) []int { + return append(x, y...) +} + +func mulBits(x, y []int) []int { + var p []int + for _, x := range x { + for _, y := range y { + p = append(p, x+y) + } + } + return p +} + +func TestMulBits(t *testing.T) { + for _, test := range []struct { + x, y, want []int + }{ + {nil, nil, nil}, + {[]int{}, []int{}, nil}, + {[]int{0}, []int{0}, []int{0}}, + {[]int{0}, []int{1}, []int{1}}, + {[]int{1}, []int{1, 2, 3}, []int{2, 3, 4}}, + {[]int{-1}, []int{1}, []int{0}}, + {[]int{-10, -1, 0, 1, 10}, []int{1, 2, 3}, []int{-9, -8, -7, 0, 1, 2, 1, 2, 3, 2, 3, 4, 11, 12, 13}}, + } { + got := fmt.Sprintf("%v", mulBits(test.x, test.y)) + want := fmt.Sprintf("%v", test.want) + if got != want { + t.Errorf("%v * %v = %s; want %s", test.x, test.y, got, want) + } + + } +} + +// normBits returns the normalized bits for x: It +// removes multiple equal entries by treating them +// as an addition (e.g., []int{5, 5} => []int{6}), +// and it sorts the result list for reproducible +// results. +func normBits(x []int) []int { + m := make(map[int]bool) + for _, b := range x { + for m[b] { + m[b] = false + b++ + } + m[b] = true + } + var z []int + for b, set := range m { + if set { + z = append(z, b) + } + } + sort.Ints(z) + return z +} + +func TestNormBits(t *testing.T) { + for _, test := range []struct { + x, want []int + }{ + {nil, nil}, + {[]int{}, []int{}}, + {[]int{0}, []int{0}}, + {[]int{0, 0}, []int{1}}, + {[]int{3, 1, 1}, []int{2, 3}}, + {[]int{10, 9, 8, 7, 6, 6}, []int{11}}, + } { + got := fmt.Sprintf("%v", normBits(test.x)) + want := fmt.Sprintf("%v", test.want) + if got != want { + t.Errorf("normBits(%v) = %s; want %s", test.x, got, want) + } + + } +} + +// roundBits returns the Float value rounded to prec bits +// according to mode from the bit set x. +func roundBits(x []int, prec uint, mode RoundingMode) *Float { + x = normBits(x) + + // determine range + var min, max int + for i, b := range x { + if i == 0 || b < min { + min = b + } + if i == 0 || b > max { + max = b + } + } + prec0 := uint(max + 1 - min) + if prec >= prec0 { + return fromBits(x) + } + // prec < prec0 + + // determine bit 0, rounding, and sticky bit, and result bits z + var bit0, rbit, sbit uint + var z []int + r := max - int(prec) + for _, b := range x { + switch { + case b == r: + rbit = 1 + case b < r: + sbit = 1 + default: + // b > r + if b == r+1 { + bit0 = 1 + } + z = append(z, b) + } + } + + // round + f := fromBits(z) // rounded to zero + if mode == ToNearestAway { + panic("not yet implemented") + } + if mode == ToNearestEven && rbit == 1 && (sbit == 1 || sbit == 0 && bit0 != 0) || mode == AwayFromZero { + // round away from zero + f.SetMode(ToZero).SetPrec(prec) + f.Add(f, fromBits([]int{int(r) + 1})) + } + return f +} + +// fromBits returns the *Float z of the smallest possible precision +// such that z = sum(2**bits[i]), with i = range bits. +// If multiple bits[i] are equal, they are added: fromBits(0, 1, 0) +// == 2**1 + 2**0 + 2**0 = 4. +func fromBits(bits []int) *Float { + // handle 0 + if len(bits) == 0 { + return new(Float) + } + // len(bits) > 0 + + // determine lsb exponent + var min int + for i, b := range bits { + if i == 0 || b < min { + min = b + } + } + + // create bit pattern + x := NewInt(0) + for _, b := range bits { + badj := b - min + // propagate carry if necessary + for x.Bit(badj) != 0 { + x.SetBit(x, badj, 0) + badj++ + } + x.SetBit(x, badj, 1) + } + + // create corresponding float + z := new(Float).SetInt(x) // normalized + z.setExp(int64(z.exp) + int64(min)) + return z +} + +func TestFromBits(t *testing.T) { + for _, test := range []struct { + bits []int + want string + }{ + // all different bit numbers + {nil, "0"}, + {[]int{0}, "0x.8p1"}, + {[]int{1}, "0x.8p2"}, + {[]int{-1}, "0x.8p0"}, + {[]int{63}, "0x.8p64"}, + {[]int{33, -30}, "0x.8000000000000001p34"}, + {[]int{255, 0}, "0x.8000000000000000000000000000000000000000000000000000000000000001p256"}, + + // multiple equal bit numbers + {[]int{0, 0}, "0x.8p2"}, + {[]int{0, 0, 0, 0}, "0x.8p3"}, + {[]int{0, 1, 0}, "0x.8p3"}, + {append([]int{2, 1, 0} /* 7 */, []int{3, 1} /* 10 */ ...), "0x.88p5" /* 17 */}, + } { + f := fromBits(test.bits) + if got := f.Format('p', 0); got != test.want { + t.Errorf("setBits(%v) = %s; want %s", test.bits, got, test.want) + } + } +} diff --git a/src/math/big/float_test.go b/src/math/big/float_test.go index 8c07709fe8..97a54f62b3 100644 --- a/src/math/big/float_test.go +++ b/src/math/big/float_test.go @@ -7,7 +7,6 @@ package big import ( "fmt" "math" - "sort" "strconv" "strings" "testing" @@ -1448,199 +1447,3 @@ func TestFloatArithmeticRounding(t *testing.T) { func TestFloatCmp(t *testing.T) { // TODO(gri) implement this } - -func addBits(x, y []int) []int { - return append(x, y...) -} - -func mulBits(x, y []int) []int { - var p []int - for _, x := range x { - for _, y := range y { - p = append(p, x+y) - } - } - return p -} - -func TestMulBits(t *testing.T) { - for _, test := range []struct { - x, y, want []int - }{ - {nil, nil, nil}, - {[]int{}, []int{}, nil}, - {[]int{0}, []int{0}, []int{0}}, - {[]int{0}, []int{1}, []int{1}}, - {[]int{1}, []int{1, 2, 3}, []int{2, 3, 4}}, - {[]int{-1}, []int{1}, []int{0}}, - {[]int{-10, -1, 0, 1, 10}, []int{1, 2, 3}, []int{-9, -8, -7, 0, 1, 2, 1, 2, 3, 2, 3, 4, 11, 12, 13}}, - } { - got := fmt.Sprintf("%v", mulBits(test.x, test.y)) - want := fmt.Sprintf("%v", test.want) - if got != want { - t.Errorf("%v * %v = %s; want %s", test.x, test.y, got, want) - } - - } -} - -// normBits returns the normalized bits for x: It -// removes multiple equal entries by treating them -// as an addition (e.g., []int{5, 5} => []int{6}), -// and it sorts the result list for reproducible -// results. -func normBits(x []int) []int { - m := make(map[int]bool) - for _, b := range x { - for m[b] { - m[b] = false - b++ - } - m[b] = true - } - var z []int - for b, set := range m { - if set { - z = append(z, b) - } - } - sort.Ints(z) - return z -} - -func TestNormBits(t *testing.T) { - for _, test := range []struct { - x, want []int - }{ - {nil, nil}, - {[]int{}, []int{}}, - {[]int{0}, []int{0}}, - {[]int{0, 0}, []int{1}}, - {[]int{3, 1, 1}, []int{2, 3}}, - {[]int{10, 9, 8, 7, 6, 6}, []int{11}}, - } { - got := fmt.Sprintf("%v", normBits(test.x)) - want := fmt.Sprintf("%v", test.want) - if got != want { - t.Errorf("normBits(%v) = %s; want %s", test.x, got, want) - } - - } -} - -// roundBits returns the Float value rounded to prec bits -// according to mode from the bit set x. -func roundBits(x []int, prec uint, mode RoundingMode) *Float { - x = normBits(x) - - // determine range - var min, max int - for i, b := range x { - if i == 0 || b < min { - min = b - } - if i == 0 || b > max { - max = b - } - } - prec0 := uint(max + 1 - min) - if prec >= prec0 { - return fromBits(x) - } - // prec < prec0 - - // determine bit 0, rounding, and sticky bit, and result bits z - var bit0, rbit, sbit uint - var z []int - r := max - int(prec) - for _, b := range x { - switch { - case b == r: - rbit = 1 - case b < r: - sbit = 1 - default: - // b > r - if b == r+1 { - bit0 = 1 - } - z = append(z, b) - } - } - - // round - f := fromBits(z) // rounded to zero - if mode == ToNearestAway { - panic("not yet implemented") - } - if mode == ToNearestEven && rbit == 1 && (sbit == 1 || sbit == 0 && bit0 != 0) || mode == AwayFromZero { - // round away from zero - f.SetMode(ToZero).SetPrec(prec) - f.Add(f, fromBits([]int{int(r) + 1})) - } - return f -} - -// fromBits returns the *Float z of the smallest possible precision -// such that z = sum(2**bits[i]), with i = range bits. -// If multiple bits[i] are equal, they are added: fromBits(0, 1, 0) -// == 2**1 + 2**0 + 2**0 = 4. -func fromBits(bits []int) *Float { - // handle 0 - if len(bits) == 0 { - return new(Float) - } - // len(bits) > 0 - - // determine lsb exponent - var min int - for i, b := range bits { - if i == 0 || b < min { - min = b - } - } - - // create bit pattern - x := NewInt(0) - for _, b := range bits { - badj := b - min - // propagate carry if necessary - for x.Bit(badj) != 0 { - x.SetBit(x, badj, 0) - badj++ - } - x.SetBit(x, badj, 1) - } - - // create corresponding float - z := new(Float).SetInt(x) // normalized - z.setExp(int64(z.exp) + int64(min)) - return z -} - -func TestFromBits(t *testing.T) { - for _, test := range []struct { - bits []int - want string - }{ - // all different bit numbers - {nil, "0"}, - {[]int{0}, "0x.8p1"}, - {[]int{1}, "0x.8p2"}, - {[]int{-1}, "0x.8p0"}, - {[]int{63}, "0x.8p64"}, - {[]int{33, -30}, "0x.8000000000000001p34"}, - {[]int{255, 0}, "0x.8000000000000000000000000000000000000000000000000000000000000001p256"}, - - // multiple equal bit numbers - {[]int{0, 0}, "0x.8p2"}, - {[]int{0, 0, 0, 0}, "0x.8p3"}, - {[]int{0, 1, 0}, "0x.8p3"}, - {append([]int{2, 1, 0} /* 7 */, []int{3, 1} /* 10 */ ...), "0x.88p5" /* 17 */}, - } { - f := fromBits(test.bits) - if got := f.Format('p', 0); got != test.want { - t.Errorf("setBits(%v) = %s; want %s", test.bits, got, test.want) - } - } -} -- 2.48.1