diff options
Diffstat (limited to 'src/pkg/math/big/arith.go')
| -rw-r--r-- | src/pkg/math/big/arith.go | 240 |
1 files changed, 0 insertions, 240 deletions
diff --git a/src/pkg/math/big/arith.go b/src/pkg/math/big/arith.go deleted file mode 100644 index 3d5a8682d..000000000 --- a/src/pkg/math/big/arith.go +++ /dev/null @@ -1,240 +0,0 @@ -// 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. Needed for platforms without -// assembly implementations of these routines. - -package big - -// A Word represents a single digit of a multi-precision unsigned integer. -type Word uintptr - -const ( - // Compute the size _S of a Word in bytes. - _m = ^Word(0) - _logS = _m>>8&1 + _m>>16&1 + _m>>32&1 - _S = 1 << _logS - - _W = _S << 3 // word size in bits - _B = 1 << _W // digit base - _M = _B - 1 // digit mask - - _W2 = _W / 2 // half word size in bits - _B2 = 1 << _W2 // half digit base - _M2 = _B2 - 1 // half digit mask -) - -// ---------------------------------------------------------------------------- -// Elementary operations on words -// -// These operations are used by the vector operations below. - -// z1<<_W + z0 = x+y+c, with c == 0 or 1 -func addWW_g(x, y, c Word) (z1, z0 Word) { - yc := y + c - z0 = x + yc - if z0 < x || yc < y { - z1 = 1 - } - return -} - -// z1<<_W + z0 = x-y-c, with c == 0 or 1 -func subWW_g(x, y, c Word) (z1, z0 Word) { - yc := y + c - z0 = x - yc - if z0 > x || yc < y { - z1 = 1 - } - return -} - -// z1<<_W + z0 = x*y -// Adapted from Warren, Hacker's Delight, p. 132. -func mulWW_g(x, y Word) (z1, z0 Word) { - x0 := x & _M2 - x1 := x >> _W2 - y0 := y & _M2 - y1 := y >> _W2 - w0 := x0 * y0 - t := x1*y0 + w0>>_W2 - w1 := t & _M2 - w2 := t >> _W2 - w1 += x0 * y1 - z1 = x1*y1 + w2 + w1>>_W2 - z0 = x * y - return -} - -// z1<<_W + z0 = x*y + c -func mulAddWWW_g(x, y, c Word) (z1, z0 Word) { - z1, zz0 := mulWW(x, y) - if z0 = zz0 + c; z0 < zz0 { - z1++ - } - return -} - -// Length of x in bits. -func bitLen_g(x Word) (n int) { - for ; x >= 0x8000; x >>= 16 { - n += 16 - } - if x >= 0x80 { - x >>= 8 - n += 8 - } - if x >= 0x8 { - x >>= 4 - n += 4 - } - if x >= 0x2 { - x >>= 2 - n += 2 - } - if x >= 0x1 { - n++ - } - return -} - -// log2 computes the integer binary logarithm of x. -// The result is the integer n for which 2^n <= x < 2^(n+1). -// If x == 0, the result is -1. -func log2(x Word) int { - return bitLen(x) - 1 -} - -// Number of leading zeros in x. -func leadingZeros(x Word) uint { - return uint(_W - bitLen(x)) -} - -// q = (u1<<_W + u0 - r)/y -// Adapted from Warren, Hacker's Delight, p. 152. -func divWW_g(u1, u0, v Word) (q, r Word) { - if u1 >= v { - return 1<<_W - 1, 1<<_W - 1 - } - - s := leadingZeros(v) - v <<= s - - vn1 := v >> _W2 - vn0 := v & _M2 - un32 := u1<<s | u0>>(_W-s) - un10 := u0 << s - un1 := un10 >> _W2 - un0 := un10 & _M2 - q1 := un32 / vn1 - rhat := un32 - q1*vn1 - - for q1 >= _B2 || q1*vn0 > _B2*rhat+un1 { - q1-- - rhat += vn1 - if rhat >= _B2 { - break - } - } - - un21 := un32*_B2 + un1 - q1*v - q0 := un21 / vn1 - rhat = un21 - q0*vn1 - - for q0 >= _B2 || q0*vn0 > _B2*rhat+un0 { - q0-- - rhat += vn1 - if rhat >= _B2 { - break - } - } - - return q1*_B2 + q0, (un21*_B2 + un0 - q0*v) >> s -} - -func addVV_g(z, x, y []Word) (c Word) { - for i := range z { - c, z[i] = addWW_g(x[i], y[i], c) - } - return -} - -func subVV_g(z, x, y []Word) (c Word) { - for i := range z { - c, z[i] = subWW_g(x[i], y[i], c) - } - return -} - -func addVW_g(z, x []Word, y Word) (c Word) { - c = y - for i := range z { - c, z[i] = addWW_g(x[i], c, 0) - } - return -} - -func subVW_g(z, x []Word, y Word) (c Word) { - c = y - for i := range z { - c, z[i] = subWW_g(x[i], c, 0) - } - return -} - -func shlVU_g(z, x []Word, s uint) (c Word) { - if n := len(z); n > 0 { - ŝ := _W - s - w1 := x[n-1] - c = w1 >> ŝ - for i := n - 1; i > 0; i-- { - w := w1 - w1 = x[i-1] - z[i] = w<<s | w1>>ŝ - } - z[0] = w1 << s - } - return -} - -func shrVU_g(z, x []Word, s uint) (c Word) { - if n := len(z); n > 0 { - ŝ := _W - s - w1 := x[0] - c = w1 << ŝ - for i := 0; i < n-1; i++ { - w := w1 - w1 = x[i+1] - z[i] = w>>s | w1<<ŝ - } - z[n-1] = w1 >> s - } - return -} - -func mulAddVWW_g(z, x []Word, y, r Word) (c Word) { - c = r - for i := range z { - c, z[i] = mulAddWWW_g(x[i], y, c) - } - return -} - -func addMulVVW_g(z, x []Word, y Word) (c Word) { - for i := range z { - z1, z0 := mulAddWWW_g(x[i], y, z[i]) - c, z[i] = addWW_g(z0, c, 0) - 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 -} |