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
9package big
10
11import (
12	"fmt"
13	"slices"
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.
26type Bits []int
27
28func (x Bits) add(y Bits) Bits {
29	return append(x, y...)
30}
31
32func (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
42func 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.
66func (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	slices.Sort([]int(z))
82	return z
83}
84
85func 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.
107func (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.
161func (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
199func 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