blob: 985b60bd4b742708775ac39c532e91ccefdcd8bd [file] [log] [blame]
// 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)
}
}
}