bits_test.go

     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