go/src/math/big/arith.go

type Word …

const _S …

const _W …

const _B …

const _M …

// z1<<_W + z0 = x*y
func mulWW(x, y Word) (z1, z0 Word) { … }

// z1<<_W + z0 = x*y + c
func mulAddWWW_g(x, y, c Word) (z1, z0 Word) { … }

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

// The resulting carry c is either 0 or 1.
func addVV_g(z, x, y []Word) (c Word) { … }

// The resulting carry c is either 0 or 1.
func subVV_g(z, x, y []Word) (c Word) { … }

// The resulting carry c is either 0 or 1.
func addVW_g(z, x []Word, y Word) (c Word) { … }

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

func subVW_g(z, x []Word, y Word) (c Word) { … }

// subVWlarge is to subVW as addVWlarge is to addVW.
func subVWlarge(z, x []Word, y Word) (c Word) { … }

func shlVU_g(z, x []Word, s uint) (c Word) { … }

func shrVU_g(z, x []Word, s uint) (c Word) { … }

func mulAddVWW_g(z, x []Word, y, r Word) (c Word) { … }

func addMulVVW_g(z, x []Word, y Word) (c Word) { … }

// q = ( x1 << _W + x0 - r)/y. m = floor(( _B^2 - 1 ) / d - _B). Requiring x1<y.
// An approximate reciprocal with a reference to "Improved Division by Invariant Integers
// (IEEE Transactions on Computers, 11 Jun. 2010)"
func divWW(x1, x0, y, m Word) (q, r Word) { … }

// reciprocalWord return the reciprocal of the divisor. rec = floor(( _B^2 - 1 ) / u - _B). u = d1 << nlz(d1).
func reciprocalWord(d1 Word) Word { … }