Gecko [ 167.86.127.34 ]

Name	Size	Permission
accuracy_string.go	414 B	-rw-r--r--
arith.go	5.68 KB	-rw-r--r--
arith_386.s	4.67 KB	-rw-r--r--
arith_amd64.go	277 B	-rw-r--r--
arith_amd64.s	9.71 KB	-rw-r--r--
arith_arm.s	4.47 KB	-rw-r--r--
arith_arm64.s	9.94 KB	-rw-r--r--
arith_decl.go	707 B	-rw-r--r--
arith_decl_pure.go	1.24 KB	-rw-r--r--
arith_decl_s390x.go	791 B	-rw-r--r--
arith_mips64x.s	917 B	-rw-r--r--
arith_mipsx.s	913 B	-rw-r--r--
arith_ppc64x.s	12.62 KB	-rw-r--r--
arith_s390x.s	29.12 KB	-rw-r--r--
arith_s390x_test.go	1014 B	-rw-r--r--
arith_test.go	12.29 KB	-rw-r--r--
arith_wasm.s	757 B	-rw-r--r--
bits_test.go	5.07 KB	-rw-r--r--
calibrate_test.go	4.63 KB	-rw-r--r--
decimal.go	6.52 KB	-rw-r--r--
decimal_test.go	3.33 KB	-rw-r--r--
doc.go	3.79 KB	-rw-r--r--
example_rat_test.go	1.68 KB	-rw-r--r--
example_test.go	3.94 KB	-rw-r--r--
float.go	44.14 KB	-rw-r--r--
float_test.go	51.94 KB	-rw-r--r--
floatconv.go	8.36 KB	-rw-r--r--
floatconv_test.go	24.28 KB	-rw-r--r--
floatexample_test.go	3.63 KB	-rw-r--r--
floatmarsh.go	3.34 KB	-rw-r--r--
floatmarsh_test.go	3.64 KB	-rw-r--r--
ftoa.go	13.55 KB	-rw-r--r--
gcd_test.go	2.16 KB	-rw-r--r--
hilbert_test.go	2.88 KB	-rw-r--r--
int.go	29.56 KB	-rw-r--r--
int_test.go	51.93 KB	-rw-r--r--
intconv.go	6.68 KB	-rw-r--r--
intconv_test.go	10.01 KB	-rw-r--r--
intmarsh.go	2.09 KB	-rw-r--r--
intmarsh_test.go	2.8 KB	-rw-r--r--
nat.go	33.76 KB	-rw-r--r--
nat_test.go	18.87 KB	-rw-r--r--
natconv.go	14.57 KB	-rw-r--r--
natconv_test.go	16.85 KB	-rw-r--r--
prime.go	10.34 KB	-rw-r--r--
prime_test.go	7.1 KB	-rw-r--r--
rat.go	13.49 KB	-rw-r--r--
rat_test.go	18.54 KB	-rw-r--r--
ratconv.go	9.49 KB	-rw-r--r--
ratconv_test.go	14.96 KB	-rw-r--r--
ratmarsh.go	1.95 KB	-rw-r--r--
ratmarsh_test.go	3.04 KB	-rw-r--r--
roundingmode_string.go	501 B	-rw-r--r--
sqrt.go	3.59 KB	-rw-r--r--
sqrt_test.go	4.81 KB	-rw-r--r--

Code Editor : arith.go

// Copyright 2009 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 provides Go implementations of elementary multi-precision
// arithmetic operations on word vectors. These have the suffix _g.
// These are needed for platforms without assembly implementations of these routines.
// This file also contains elementary operations that can be implemented
// sufficiently efficiently in Go.

package big

import "math/bits"

// A Word represents a single digit of a multi-precision unsigned integer.
type Word uint

const (
	_S = _W / 8 // word size in bytes

_W = bits.UintSize // word size in bits
	_B = 1 << _W       // digit base
	_M = _B - 1        // digit mask
)

// Many of the loops in this file are of the form
//   for i := 0; i < len(z) && i < len(x) && i < len(y); i++
// i < len(z) is the real condition.
// However, checking i < len(x) && i < len(y) as well is faster than
// having the compiler do a bounds check in the body of the loop;
// remarkably it is even faster than hoisting the bounds check
// out of the loop, by doing something like
//   _, _ = x[len(z)-1], y[len(z)-1]
// There are other ways to hoist the bounds check out of the loop,
// but the compiler's BCE isn't powerful enough for them (yet?).
// See the discussion in CL 164966.

// ----------------------------------------------------------------------------
// Elementary operations on words
//
// These operations are used by the vector operations below.

// z1<<_W + z0 = x*y
func mulWW_g(x, y Word) (z1, z0 Word) {
	hi, lo := bits.Mul(uint(x), uint(y))
	return Word(hi), Word(lo)
}

// z1<<_W + z0 = x*y + c
func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
	hi, lo := bits.Mul(uint(x), uint(y))
	var cc uint
	lo, cc = bits.Add(lo, uint(c), 0)
	return Word(hi + cc), Word(lo)
}

// nlz returns the number of leading zeros in x.
// Wraps bits.LeadingZeros call for convenience.
func nlz(x Word) uint {
	return uint(bits.LeadingZeros(uint(x)))
}

// q = (u1<<_W + u0 - r)/v
func divWW_g(u1, u0, v Word) (q, r Word) {
	qq, rr := bits.Div(uint(u1), uint(u0), uint(v))
	return Word(qq), Word(rr)
}

// The resulting carry c is either 0 or 1.
func addVV_g(z, x, y []Word) (c Word) {
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x) && i < len(y); i++ {
		zi, cc := bits.Add(uint(x[i]), uint(y[i]), uint(c))
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// The resulting carry c is either 0 or 1.
func subVV_g(z, x, y []Word) (c Word) {
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x) && i < len(y); i++ {
		zi, cc := bits.Sub(uint(x[i]), uint(y[i]), uint(c))
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// The resulting carry c is either 0 or 1.
func addVW_g(z, x []Word, y Word) (c Word) {
	c = y
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x); i++ {
		zi, cc := bits.Add(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// addVWlarge is addVW, but intended for large z.
// The only difference is that we check on every iteration
// whether we are done with carries,
// and if so, switch to a much faster copy instead.
// This is only a good idea for large z,
// because the overhead of the check and the function call
// outweigh the benefits when z is small.
func addVWlarge(z, x []Word, y Word) (c Word) {
	c = y
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x); i++ {
		if c == 0 {
			copy(z[i:], x[i:])
			return
		}
		zi, cc := bits.Add(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

func subVW_g(z, x []Word, y Word) (c Word) {
	c = y
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x); i++ {
		zi, cc := bits.Sub(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

// subVWlarge is to subVW as addVWlarge is to addVW.
func subVWlarge(z, x []Word, y Word) (c Word) {
	c = y
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x); i++ {
		if c == 0 {
			copy(z[i:], x[i:])
			return
		}
		zi, cc := bits.Sub(uint(x[i]), uint(c), 0)
		z[i] = Word(zi)
		c = Word(cc)
	}
	return
}

func shlVU_g(z, x []Word, s uint) (c Word) {
	if s == 0 {
		copy(z, x)
		return
	}
	if len(z) == 0 {
		return
	}
	s &= _W - 1 // hint to the compiler that shifts by s don't need guard code
	ŝ := _W - s
	ŝ &= _W - 1 // ditto
	c = x[len(z)-1] >> ŝ
	for i := len(z) - 1; i > 0; i-- {
		z[i] = x[i]<<s | x[i-1]>>ŝ
	}
	z[0] = x[0] << s
	return
}

func shrVU_g(z, x []Word, s uint) (c Word) {
	if s == 0 {
		copy(z, x)
		return
	}
	if len(z) == 0 {
		return
	}
	s &= _W - 1 // hint to the compiler that shifts by s don't need guard code
	ŝ := _W - s
	ŝ &= _W - 1 // ditto
	c = x[0] << ŝ
	for i := 0; i < len(z)-1; i++ {
		z[i] = x[i]>>s | x[i+1]<<ŝ
	}
	z[len(z)-1] = x[len(z)-1] >> s
	return
}

func mulAddVWW_g(z, x []Word, y, r Word) (c Word) {
	c = r
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x); i++ {
		c, z[i] = mulAddWWW_g(x[i], y, c)
	}
	return
}

func addMulVVW_g(z, x []Word, y Word) (c Word) {
	// The comment near the top of this file discusses this for loop condition.
	for i := 0; i < len(z) && i < len(x); i++ {
		z1, z0 := mulAddWWW_g(x[i], y, z[i])
		lo, cc := bits.Add(uint(z0), uint(c), 0)
		c, z[i] = Word(cc), Word(lo)
		c += z1
	}
	return
}

func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word) {
	r = xn
	for i := len(z) - 1; i >= 0; i-- {
		z[i], r = divWW_g(r, x[i], y)
	}
	return
}

${this.title}

Code Editor : arith.go