bits_test.go

Documentation: math/big

		 1  // Copyright 2015 The Go Authors. All rights reserved.
		 2  // Use of this source code is governed by a BSD-style
		 3  // license that can be found in the LICENSE file.
		 4  
		 5  // This file implements the Bits type used for testing Float operations
		 6  // via an independent (albeit slower) representations for floating-point
		 7  // numbers.
		 8  
		 9  package big
		10  
		11  import (
		12  	"fmt"
		13  	"sort"
		14  	"testing"
		15  )
		16  
		17  // A Bits value b represents a finite floating-point number x of the form
		18  //
		19  //	x = 2**b[0] + 2**b[1] + ... 2**b[len(b)-1]
		20  //
		21  // The order of slice elements is not significant. Negative elements may be
		22  // used to form fractions. A Bits value is normalized if each b[i] occurs at
		23  // most once. For instance Bits{0, 0, 1} is not normalized but represents the
		24  // same floating-point number as Bits{2}, which is normalized. The zero (nil)
		25  // value of Bits is a ready to use Bits value and represents the value 0.
		26  type Bits []int
		27  
		28  func (x Bits) add(y Bits) Bits {
		29  	return append(x, y...)
		30  }
		31  
		32  func (x Bits) mul(y Bits) Bits {
		33  	var p Bits
		34  	for _, x := range x {
		35  		for _, y := range y {
		36  			p = append(p, x+y)
		37  		}
		38  	}
		39  	return p
		40  }
		41  
		42  func TestMulBits(t *testing.T) {
		43  	for _, test := range []struct {
		44  		x, y, want Bits
		45  	}{
		46  		{nil, nil, nil},
		47  		{Bits{}, Bits{}, nil},
		48  		{Bits{0}, Bits{0}, Bits{0}},
		49  		{Bits{0}, Bits{1}, Bits{1}},
		50  		{Bits{1}, Bits{1, 2, 3}, Bits{2, 3, 4}},
		51  		{Bits{-1}, Bits{1}, Bits{0}},
		52  		{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}},
		53  	} {
		54  		got := fmt.Sprintf("%v", test.x.mul(test.y))
		55  		want := fmt.Sprintf("%v", test.want)
		56  		if got != want {
		57  			t.Errorf("%v * %v = %s; want %s", test.x, test.y, got, want)
		58  		}
		59  
		60  	}
		61  }
		62  
		63  // norm returns the normalized bits for x: It removes multiple equal entries
		64  // by treating them as an addition (e.g., Bits{5, 5} => Bits{6}), and it sorts
		65  // the result list for reproducible results.
		66  func (x Bits) norm() Bits {
		67  	m := make(map[int]bool)
		68  	for _, b := range x {
		69  		for m[b] {
		70  			m[b] = false
		71  			b++
		72  		}
		73  		m[b] = true
		74  	}
		75  	var z Bits
		76  	for b, set := range m {
		77  		if set {
		78  			z = append(z, b)
		79  		}
		80  	}
		81  	sort.Ints([]int(z))
		82  	return z
		83  }
		84  
		85  func TestNormBits(t *testing.T) {
		86  	for _, test := range []struct {
		87  		x, want Bits
		88  	}{
		89  		{nil, nil},
		90  		{Bits{}, Bits{}},
		91  		{Bits{0}, Bits{0}},
		92  		{Bits{0, 0}, Bits{1}},
		93  		{Bits{3, 1, 1}, Bits{2, 3}},
		94  		{Bits{10, 9, 8, 7, 6, 6}, Bits{11}},
		95  	} {
		96  		got := fmt.Sprintf("%v", test.x.norm())
		97  		want := fmt.Sprintf("%v", test.want)
		98  		if got != want {
		99  			t.Errorf("normBits(%v) = %s; want %s", test.x, got, want)
	 100  		}
	 101  
	 102  	}
	 103  }
	 104  
	 105  // round returns the Float value corresponding to x after rounding x
	 106  // to prec bits according to mode.
	 107  func (x Bits) round(prec uint, mode RoundingMode) *Float {
	 108  	x = x.norm()
	 109  
	 110  	// determine range
	 111  	var min, max int
	 112  	for i, b := range x {
	 113  		if i == 0 || b < min {
	 114  			min = b
	 115  		}
	 116  		if i == 0 || b > max {
	 117  			max = b
	 118  		}
	 119  	}
	 120  	prec0 := uint(max + 1 - min)
	 121  	if prec >= prec0 {
	 122  		return x.Float()
	 123  	}
	 124  	// prec < prec0
	 125  
	 126  	// determine bit 0, rounding, and sticky bit, and result bits z
	 127  	var bit0, rbit, sbit uint
	 128  	var z Bits
	 129  	r := max - int(prec)
	 130  	for _, b := range x {
	 131  		switch {
	 132  		case b == r:
	 133  			rbit = 1
	 134  		case b < r:
	 135  			sbit = 1
	 136  		default:
	 137  			// b > r
	 138  			if b == r+1 {
	 139  				bit0 = 1
	 140  			}
	 141  			z = append(z, b)
	 142  		}
	 143  	}
	 144  
	 145  	// round
	 146  	f := z.Float() // rounded to zero
	 147  	if mode == ToNearestAway {
	 148  		panic("not yet implemented")
	 149  	}
	 150  	if mode == ToNearestEven && rbit == 1 && (sbit == 1 || sbit == 0 && bit0 != 0) || mode == AwayFromZero {
	 151  		// round away from zero
	 152  		f.SetMode(ToZero).SetPrec(prec)
	 153  		f.Add(f, Bits{int(r) + 1}.Float())
	 154  	}
	 155  	return f
	 156  }
	 157  
	 158  // Float returns the *Float z of the smallest possible precision such that
	 159  // z = sum(2**bits[i]), with i = range bits. If multiple bits[i] are equal,
	 160  // they are added: Bits{0, 1, 0}.Float() == 2**0 + 2**1 + 2**0 = 4.
	 161  func (bits Bits) Float() *Float {
	 162  	// handle 0
	 163  	if len(bits) == 0 {
	 164  		return new(Float)
	 165  	}
	 166  	// len(bits) > 0
	 167  
	 168  	// determine lsb exponent
	 169  	var min int
	 170  	for i, b := range bits {
	 171  		if i == 0 || b < min {
	 172  			min = b
	 173  		}
	 174  	}
	 175  
	 176  	// create bit pattern
	 177  	x := NewInt(0)
	 178  	for _, b := range bits {
	 179  		badj := b - min
	 180  		// propagate carry if necessary
	 181  		for x.Bit(badj) != 0 {
	 182  			x.SetBit(x, badj, 0)
	 183  			badj++
	 184  		}
	 185  		x.SetBit(x, badj, 1)
	 186  	}
	 187  
	 188  	// create corresponding float
	 189  	z := new(Float).SetInt(x) // normalized
	 190  	if e := int64(z.exp) + int64(min); MinExp <= e && e <= MaxExp {
	 191  		z.exp = int32(e)
	 192  	} else {
	 193  		// this should never happen for our test cases
	 194  		panic("exponent out of range")
	 195  	}
	 196  	return z
	 197  }
	 198  
	 199  func TestFromBits(t *testing.T) {
	 200  	for _, test := range []struct {
	 201  		bits Bits
	 202  		want string
	 203  	}{
	 204  		// all different bit numbers
	 205  		{nil, "0"},
	 206  		{Bits{0}, "0x.8p+1"},
	 207  		{Bits{1}, "0x.8p+2"},
	 208  		{Bits{-1}, "0x.8p+0"},
	 209  		{Bits{63}, "0x.8p+64"},
	 210  		{Bits{33, -30}, "0x.8000000000000001p+34"},
	 211  		{Bits{255, 0}, "0x.8000000000000000000000000000000000000000000000000000000000000001p+256"},
	 212  
	 213  		// multiple equal bit numbers
	 214  		{Bits{0, 0}, "0x.8p+2"},
	 215  		{Bits{0, 0, 0, 0}, "0x.8p+3"},
	 216  		{Bits{0, 1, 0}, "0x.8p+3"},
	 217  		{append(Bits{2, 1, 0} /* 7 */, Bits{3, 1} /* 10 */ ...), "0x.88p+5" /* 17 */},
	 218  	} {
	 219  		f := test.bits.Float()
	 220  		if got := f.Text('p', 0); got != test.want {
	 221  			t.Errorf("setBits(%v) = %s; want %s", test.bits, got, test.want)
	 222  		}
	 223  	}
	 224  }
	 225
View as plain text