...
Run Format

Source file src/math/big/bits_test.go

Documentation: math/big

  // 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)
  		}
  	}
  }
  

View as plain text