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
