From 73df946d56c74384511a194dd01dbe099584fd1a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 15:14:23 +0200 Subject: Adding upstream version 1.16.10. Signed-off-by: Daniel Baumann --- src/math/big/bits_test.go | 224 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 224 insertions(+) create mode 100644 src/math/big/bits_test.go (limited to '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 0000000..985b60b --- /dev/null +++ b/src/math/big/bits_test.go @@ -0,0 +1,224 @@ +// 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. + +// This file implements the Bits type used for testing Float operations +// via an independent (albeit slower) representations for floating-point +// numbers. + +package big + +import ( + "fmt" + "sort" + "testing" +) + +// A Bits value b represents a finite floating-point number x of the form +// +// x = 2**b[0] + 2**b[1] + ... 2**b[len(b)-1] +// +// The order of slice elements is not significant. Negative elements may be +// used to form fractions. A Bits value is normalized if each b[i] occurs at +// most once. For instance Bits{0, 0, 1} is not normalized but represents the +// same floating-point number as Bits{2}, which is normalized. The zero (nil) +// value of Bits is a ready to use Bits value and represents the value 0. +type Bits []int + +func (x Bits) add(y Bits) Bits { + return append(x, y...) +} + +func (x Bits) mul(y Bits) Bits { + var p Bits + 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 Bits + }{ + {nil, nil, nil}, + {Bits{}, Bits{}, nil}, + {Bits{0}, Bits{0}, Bits{0}}, + {Bits{0}, Bits{1}, Bits{1}}, + {Bits{1}, Bits{1, 2, 3}, Bits{2, 3, 4}}, + {Bits{-1}, Bits{1}, Bits{0}}, + {Bits{-10, -1, 0, 1, 10}, Bits{1, 2, 3}, Bits{-9, -8, -7, 0, 1, 2, 1, 2, 3, 2, 3, 4, 11, 12, 13}}, + } { + got := fmt.Sprintf("%v", test.x.mul(test.y)) + want := fmt.Sprintf("%v", test.want) + if got != want { + t.Errorf("%v * %v = %s; want %s", test.x, test.y, got, want) + } + + } +} + +// norm returns the normalized bits for x: It removes multiple equal entries +// by treating them as an addition (e.g., Bits{5, 5} => Bits{6}), and it sorts +// the result list for reproducible results. +func (x Bits) norm() Bits { + m := make(map[int]bool) + for _, b := range x { + for m[b] { + m[b] = false + b++ + } + m[b] = true + } + var z Bits + for b, set := range m { + if set { + z = append(z, b) + } + } + sort.Ints([]int(z)) + return z +} + +func TestNormBits(t *testing.T) { + for _, test := range []struct { + x, want Bits + }{ + {nil, nil}, + {Bits{}, Bits{}}, + {Bits{0}, Bits{0}}, + {Bits{0, 0}, Bits{1}}, + {Bits{3, 1, 1}, Bits{2, 3}}, + {Bits{10, 9, 8, 7, 6, 6}, Bits{11}}, + } { + got := fmt.Sprintf("%v", test.x.norm()) + want := fmt.Sprintf("%v", test.want) + if got != want { + t.Errorf("normBits(%v) = %s; want %s", test.x, got, want) + } + + } +} + +// round returns the Float value corresponding to x after rounding x +// to prec bits according to mode. +func (x Bits) round(prec uint, mode RoundingMode) *Float { + x = x.norm() + + // 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 x.Float() + } + // prec < prec0 + + // determine bit 0, rounding, and sticky bit, and result bits z + var bit0, rbit, sbit uint + var z Bits + 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 := z.Float() // 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, Bits{int(r) + 1}.Float()) + } + return f +} + +// Float 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: Bits{0, 1, 0}.Float() == 2**0 + 2**1 + 2**0 = 4. +func (bits Bits) Float() *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 + if e := int64(z.exp) + int64(min); MinExp <= e && e <= MaxExp { + z.exp = int32(e) + } else { + // this should never happen for our test cases + panic("exponent out of range") + } + return z +} + +func TestFromBits(t *testing.T) { + for _, test := range []struct { + bits Bits + want string + }{ + // all different bit numbers + {nil, "0"}, + {Bits{0}, "0x.8p+1"}, + {Bits{1}, "0x.8p+2"}, + {Bits{-1}, "0x.8p+0"}, + {Bits{63}, "0x.8p+64"}, + {Bits{33, -30}, "0x.8000000000000001p+34"}, + {Bits{255, 0}, "0x.8000000000000000000000000000000000000000000000000000000000000001p+256"}, + + // multiple equal bit numbers + {Bits{0, 0}, "0x.8p+2"}, + {Bits{0, 0, 0, 0}, "0x.8p+3"}, + {Bits{0, 1, 0}, "0x.8p+3"}, + {append(Bits{2, 1, 0} /* 7 */, Bits{3, 1} /* 10 */ ...), "0x.88p+5" /* 17 */}, + } { + f := test.bits.Float() + if got := f.Text('p', 0); got != test.want { + t.Errorf("setBits(%v) = %s; want %s", test.bits, got, test.want) + } + } +} -- cgit v1.2.3