diff options
Diffstat (limited to 'src/pkg/math/big')
-rw-r--r-- | src/pkg/math/big/arith.go | 240 | ||||
-rw-r--r-- | src/pkg/math/big/arith_386.s | 278 | ||||
-rw-r--r-- | src/pkg/math/big/arith_amd64.s | 401 | ||||
-rw-r--r-- | src/pkg/math/big/arith_amd64p32.s | 41 | ||||
-rw-r--r-- | src/pkg/math/big/arith_arm.s | 300 | ||||
-rw-r--r-- | src/pkg/math/big/arith_decl.go | 19 | ||||
-rw-r--r-- | src/pkg/math/big/arith_test.go | 456 | ||||
-rw-r--r-- | src/pkg/math/big/calibrate_test.go | 88 | ||||
-rw-r--r-- | src/pkg/math/big/example_test.go | 51 | ||||
-rw-r--r-- | src/pkg/math/big/gcd_test.go | 47 | ||||
-rw-r--r-- | src/pkg/math/big/hilbert_test.go | 160 | ||||
-rw-r--r-- | src/pkg/math/big/int.go | 1011 | ||||
-rw-r--r-- | src/pkg/math/big/int_test.go | 1601 | ||||
-rw-r--r-- | src/pkg/math/big/nat.go | 1508 | ||||
-rw-r--r-- | src/pkg/math/big/nat_test.go | 771 | ||||
-rw-r--r-- | src/pkg/math/big/rat.go | 600 | ||||
-rw-r--r-- | src/pkg/math/big/rat_test.go | 994 |
17 files changed, 0 insertions, 8566 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 -} diff --git a/src/pkg/math/big/arith_386.s b/src/pkg/math/big/arith_386.s deleted file mode 100644 index 15b036c65..000000000 --- a/src/pkg/math/big/arith_386.s +++ /dev/null @@ -1,278 +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. - -#include "../../../cmd/ld/textflag.h" - -// This file provides fast assembly versions for the elementary -// arithmetic operations on vectors implemented in arith.go. - -// func mulWW(x, y Word) (z1, z0 Word) -TEXT ·mulWW(SB),NOSPLIT,$0 - MOVL x+0(FP), AX - MULL y+4(FP) - MOVL DX, z1+8(FP) - MOVL AX, z0+12(FP) - RET - - -// func divWW(x1, x0, y Word) (q, r Word) -TEXT ·divWW(SB),NOSPLIT,$0 - MOVL x1+0(FP), DX - MOVL x0+4(FP), AX - DIVL y+8(FP) - MOVL AX, q+12(FP) - MOVL DX, r+16(FP) - RET - - -// func addVV(z, x, y []Word) (c Word) -TEXT ·addVV(SB),NOSPLIT,$0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL y+24(FP), CX - MOVL z_len+4(FP), BP - MOVL $0, BX // i = 0 - MOVL $0, DX // c = 0 - JMP E1 - -L1: MOVL (SI)(BX*4), AX - RCRL $1, DX - ADCL (CX)(BX*4), AX - RCLL $1, DX - MOVL AX, (DI)(BX*4) - ADDL $1, BX // i++ - -E1: CMPL BX, BP // i < n - JL L1 - - MOVL DX, c+36(FP) - RET - - -// func subVV(z, x, y []Word) (c Word) -// (same as addVV except for SBBL instead of ADCL and label names) -TEXT ·subVV(SB),NOSPLIT,$0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL y+24(FP), CX - MOVL z_len+4(FP), BP - MOVL $0, BX // i = 0 - MOVL $0, DX // c = 0 - JMP E2 - -L2: MOVL (SI)(BX*4), AX - RCRL $1, DX - SBBL (CX)(BX*4), AX - RCLL $1, DX - MOVL AX, (DI)(BX*4) - ADDL $1, BX // i++ - -E2: CMPL BX, BP // i < n - JL L2 - - MOVL DX, c+36(FP) - RET - - -// func addVW(z, x []Word, y Word) (c Word) -TEXT ·addVW(SB),NOSPLIT,$0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL y+24(FP), AX // c = y - MOVL z_len+4(FP), BP - MOVL $0, BX // i = 0 - JMP E3 - -L3: ADDL (SI)(BX*4), AX - MOVL AX, (DI)(BX*4) - RCLL $1, AX - ANDL $1, AX - ADDL $1, BX // i++ - -E3: CMPL BX, BP // i < n - JL L3 - - MOVL AX, c+28(FP) - RET - - -// func subVW(z, x []Word, y Word) (c Word) -TEXT ·subVW(SB),NOSPLIT,$0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL y+24(FP), AX // c = y - MOVL z_len+4(FP), BP - MOVL $0, BX // i = 0 - JMP E4 - -L4: MOVL (SI)(BX*4), DX // TODO(gri) is there a reverse SUBL? - SUBL AX, DX - MOVL DX, (DI)(BX*4) - RCLL $1, AX - ANDL $1, AX - ADDL $1, BX // i++ - -E4: CMPL BX, BP // i < n - JL L4 - - MOVL AX, c+28(FP) - RET - - -// func shlVU(z, x []Word, s uint) (c Word) -TEXT ·shlVU(SB),NOSPLIT,$0 - MOVL z_len+4(FP), BX // i = z - SUBL $1, BX // i-- - JL X8b // i < 0 (n <= 0) - - // n > 0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL s+24(FP), CX - MOVL (SI)(BX*4), AX // w1 = x[n-1] - MOVL $0, DX - SHLL CX, DX:AX // w1>>ŝ - MOVL DX, c+28(FP) - - CMPL BX, $0 - JLE X8a // i <= 0 - - // i > 0 -L8: MOVL AX, DX // w = w1 - MOVL -4(SI)(BX*4), AX // w1 = x[i-1] - SHLL CX, DX:AX // w<<s | w1>>ŝ - MOVL DX, (DI)(BX*4) // z[i] = w<<s | w1>>ŝ - SUBL $1, BX // i-- - JG L8 // i > 0 - - // i <= 0 -X8a: SHLL CX, AX // w1<<s - MOVL AX, (DI) // z[0] = w1<<s - RET - -X8b: MOVL $0, c+28(FP) - RET - - -// func shrVU(z, x []Word, s uint) (c Word) -TEXT ·shrVU(SB),NOSPLIT,$0 - MOVL z_len+4(FP), BP - SUBL $1, BP // n-- - JL X9b // n < 0 (n <= 0) - - // n > 0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL s+24(FP), CX - MOVL (SI), AX // w1 = x[0] - MOVL $0, DX - SHRL CX, DX:AX // w1<<ŝ - MOVL DX, c+28(FP) - - MOVL $0, BX // i = 0 - JMP E9 - - // i < n-1 -L9: MOVL AX, DX // w = w1 - MOVL 4(SI)(BX*4), AX // w1 = x[i+1] - SHRL CX, DX:AX // w>>s | w1<<ŝ - MOVL DX, (DI)(BX*4) // z[i] = w>>s | w1<<ŝ - ADDL $1, BX // i++ - -E9: CMPL BX, BP - JL L9 // i < n-1 - - // i >= n-1 -X9a: SHRL CX, AX // w1>>s - MOVL AX, (DI)(BP*4) // z[n-1] = w1>>s - RET - -X9b: MOVL $0, c+28(FP) - RET - - -// func mulAddVWW(z, x []Word, y, r Word) (c Word) -TEXT ·mulAddVWW(SB),NOSPLIT,$0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL y+24(FP), BP - MOVL r+28(FP), CX // c = r - MOVL z_len+4(FP), BX - LEAL (DI)(BX*4), DI - LEAL (SI)(BX*4), SI - NEGL BX // i = -n - JMP E5 - -L5: MOVL (SI)(BX*4), AX - MULL BP - ADDL CX, AX - ADCL $0, DX - MOVL AX, (DI)(BX*4) - MOVL DX, CX - ADDL $1, BX // i++ - -E5: CMPL BX, $0 // i < 0 - JL L5 - - MOVL CX, c+32(FP) - RET - - -// func addMulVVW(z, x []Word, y Word) (c Word) -TEXT ·addMulVVW(SB),NOSPLIT,$0 - MOVL z+0(FP), DI - MOVL x+12(FP), SI - MOVL y+24(FP), BP - MOVL z_len+4(FP), BX - LEAL (DI)(BX*4), DI - LEAL (SI)(BX*4), SI - NEGL BX // i = -n - MOVL $0, CX // c = 0 - JMP E6 - -L6: MOVL (SI)(BX*4), AX - MULL BP - ADDL CX, AX - ADCL $0, DX - ADDL AX, (DI)(BX*4) - ADCL $0, DX - MOVL DX, CX - ADDL $1, BX // i++ - -E6: CMPL BX, $0 // i < 0 - JL L6 - - MOVL CX, c+28(FP) - RET - - -// func divWVW(z* Word, xn Word, x []Word, y Word) (r Word) -TEXT ·divWVW(SB),NOSPLIT,$0 - MOVL z+0(FP), DI - MOVL xn+12(FP), DX // r = xn - MOVL x+16(FP), SI - MOVL y+28(FP), CX - MOVL z_len+4(FP), BX // i = z - JMP E7 - -L7: MOVL (SI)(BX*4), AX - DIVL CX - MOVL AX, (DI)(BX*4) - -E7: SUBL $1, BX // i-- - JGE L7 // i >= 0 - - MOVL DX, r+32(FP) - RET - -// func bitLen(x Word) (n int) -TEXT ·bitLen(SB),NOSPLIT,$0 - BSRL x+0(FP), AX - JZ Z1 - INCL AX - MOVL AX, n+4(FP) - RET - -Z1: MOVL $0, n+4(FP) - RET diff --git a/src/pkg/math/big/arith_amd64.s b/src/pkg/math/big/arith_amd64.s deleted file mode 100644 index e2113a7e3..000000000 --- a/src/pkg/math/big/arith_amd64.s +++ /dev/null @@ -1,401 +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. - -#include "../../../cmd/ld/textflag.h" - -// This file provides fast assembly versions for the elementary -// arithmetic operations on vectors implemented in arith.go. - -// Literal instruction for MOVQ $0, CX. -// (MOVQ $0, reg is translated to XORQ reg, reg and clears CF.) -#define ZERO_CX BYTE $0x48; \ - BYTE $0xc7; \ - BYTE $0xc1; \ - BYTE $0x00; \ - BYTE $0x00; \ - BYTE $0x00; \ - BYTE $0x00 - -// func mulWW(x, y Word) (z1, z0 Word) -TEXT ·mulWW(SB),NOSPLIT,$0 - MOVQ x+0(FP), AX - MULQ y+8(FP) - MOVQ DX, z1+16(FP) - MOVQ AX, z0+24(FP) - RET - - -// func divWW(x1, x0, y Word) (q, r Word) -TEXT ·divWW(SB),NOSPLIT,$0 - MOVQ x1+0(FP), DX - MOVQ x0+8(FP), AX - DIVQ y+16(FP) - MOVQ AX, q+24(FP) - MOVQ DX, r+32(FP) - RET - - -// func addVV(z, x, y []Word) (c Word) -TEXT ·addVV(SB),NOSPLIT,$0 - MOVQ z_len+8(FP), DI - MOVQ x+24(FP), R8 - MOVQ y+48(FP), R9 - MOVQ z+0(FP), R10 - - MOVQ $0, CX // c = 0 - MOVQ $0, SI // i = 0 - - // s/JL/JMP/ below to disable the unrolled loop - SUBQ $4, DI // n -= 4 - JL V1 // if n < 0 goto V1 - -U1: // n >= 0 - // regular loop body unrolled 4x - RCRQ $1, CX // CF = c - MOVQ 0(R8)(SI*8), R11 - MOVQ 8(R8)(SI*8), R12 - MOVQ 16(R8)(SI*8), R13 - MOVQ 24(R8)(SI*8), R14 - ADCQ 0(R9)(SI*8), R11 - ADCQ 8(R9)(SI*8), R12 - ADCQ 16(R9)(SI*8), R13 - ADCQ 24(R9)(SI*8), R14 - MOVQ R11, 0(R10)(SI*8) - MOVQ R12, 8(R10)(SI*8) - MOVQ R13, 16(R10)(SI*8) - MOVQ R14, 24(R10)(SI*8) - RCLQ $1, CX // c = CF - - ADDQ $4, SI // i += 4 - SUBQ $4, DI // n -= 4 - JGE U1 // if n >= 0 goto U1 - -V1: ADDQ $4, DI // n += 4 - JLE E1 // if n <= 0 goto E1 - -L1: // n > 0 - RCRQ $1, CX // CF = c - MOVQ 0(R8)(SI*8), R11 - ADCQ 0(R9)(SI*8), R11 - MOVQ R11, 0(R10)(SI*8) - RCLQ $1, CX // c = CF - - ADDQ $1, SI // i++ - SUBQ $1, DI // n-- - JG L1 // if n > 0 goto L1 - -E1: MOVQ CX, c+72(FP) // return c - RET - - -// func subVV(z, x, y []Word) (c Word) -// (same as addVV except for SBBQ instead of ADCQ and label names) -TEXT ·subVV(SB),NOSPLIT,$0 - MOVQ z_len+8(FP), DI - MOVQ x+24(FP), R8 - MOVQ y+48(FP), R9 - MOVQ z+0(FP), R10 - - MOVQ $0, CX // c = 0 - MOVQ $0, SI // i = 0 - - // s/JL/JMP/ below to disable the unrolled loop - SUBQ $4, DI // n -= 4 - JL V2 // if n < 0 goto V2 - -U2: // n >= 0 - // regular loop body unrolled 4x - RCRQ $1, CX // CF = c - MOVQ 0(R8)(SI*8), R11 - MOVQ 8(R8)(SI*8), R12 - MOVQ 16(R8)(SI*8), R13 - MOVQ 24(R8)(SI*8), R14 - SBBQ 0(R9)(SI*8), R11 - SBBQ 8(R9)(SI*8), R12 - SBBQ 16(R9)(SI*8), R13 - SBBQ 24(R9)(SI*8), R14 - MOVQ R11, 0(R10)(SI*8) - MOVQ R12, 8(R10)(SI*8) - MOVQ R13, 16(R10)(SI*8) - MOVQ R14, 24(R10)(SI*8) - RCLQ $1, CX // c = CF - - ADDQ $4, SI // i += 4 - SUBQ $4, DI // n -= 4 - JGE U2 // if n >= 0 goto U2 - -V2: ADDQ $4, DI // n += 4 - JLE E2 // if n <= 0 goto E2 - -L2: // n > 0 - RCRQ $1, CX // CF = c - MOVQ 0(R8)(SI*8), R11 - SBBQ 0(R9)(SI*8), R11 - MOVQ R11, 0(R10)(SI*8) - RCLQ $1, CX // c = CF - - ADDQ $1, SI // i++ - SUBQ $1, DI // n-- - JG L2 // if n > 0 goto L2 - -E2: MOVQ CX, c+72(FP) // return c - RET - - -// func addVW(z, x []Word, y Word) (c Word) -TEXT ·addVW(SB),NOSPLIT,$0 - MOVQ z_len+8(FP), DI - MOVQ x+24(FP), R8 - MOVQ y+48(FP), CX // c = y - MOVQ z+0(FP), R10 - - MOVQ $0, SI // i = 0 - - // s/JL/JMP/ below to disable the unrolled loop - SUBQ $4, DI // n -= 4 - JL V3 // if n < 4 goto V3 - -U3: // n >= 0 - // regular loop body unrolled 4x - MOVQ 0(R8)(SI*8), R11 - MOVQ 8(R8)(SI*8), R12 - MOVQ 16(R8)(SI*8), R13 - MOVQ 24(R8)(SI*8), R14 - ADDQ CX, R11 - ZERO_CX - ADCQ $0, R12 - ADCQ $0, R13 - ADCQ $0, R14 - SETCS CX // c = CF - MOVQ R11, 0(R10)(SI*8) - MOVQ R12, 8(R10)(SI*8) - MOVQ R13, 16(R10)(SI*8) - MOVQ R14, 24(R10)(SI*8) - - ADDQ $4, SI // i += 4 - SUBQ $4, DI // n -= 4 - JGE U3 // if n >= 0 goto U3 - -V3: ADDQ $4, DI // n += 4 - JLE E3 // if n <= 0 goto E3 - -L3: // n > 0 - ADDQ 0(R8)(SI*8), CX - MOVQ CX, 0(R10)(SI*8) - ZERO_CX - RCLQ $1, CX // c = CF - - ADDQ $1, SI // i++ - SUBQ $1, DI // n-- - JG L3 // if n > 0 goto L3 - -E3: MOVQ CX, c+56(FP) // return c - RET - - -// func subVW(z, x []Word, y Word) (c Word) -// (same as addVW except for SUBQ/SBBQ instead of ADDQ/ADCQ and label names) -TEXT ·subVW(SB),NOSPLIT,$0 - MOVQ z_len+8(FP), DI - MOVQ x+24(FP), R8 - MOVQ y+48(FP), CX // c = y - MOVQ z+0(FP), R10 - - MOVQ $0, SI // i = 0 - - // s/JL/JMP/ below to disable the unrolled loop - SUBQ $4, DI // n -= 4 - JL V4 // if n < 4 goto V4 - -U4: // n >= 0 - // regular loop body unrolled 4x - MOVQ 0(R8)(SI*8), R11 - MOVQ 8(R8)(SI*8), R12 - MOVQ 16(R8)(SI*8), R13 - MOVQ 24(R8)(SI*8), R14 - SUBQ CX, R11 - ZERO_CX - SBBQ $0, R12 - SBBQ $0, R13 - SBBQ $0, R14 - SETCS CX // c = CF - MOVQ R11, 0(R10)(SI*8) - MOVQ R12, 8(R10)(SI*8) - MOVQ R13, 16(R10)(SI*8) - MOVQ R14, 24(R10)(SI*8) - - ADDQ $4, SI // i += 4 - SUBQ $4, DI // n -= 4 - JGE U4 // if n >= 0 goto U4 - -V4: ADDQ $4, DI // n += 4 - JLE E4 // if n <= 0 goto E4 - -L4: // n > 0 - MOVQ 0(R8)(SI*8), R11 - SUBQ CX, R11 - MOVQ R11, 0(R10)(SI*8) - ZERO_CX - RCLQ $1, CX // c = CF - - ADDQ $1, SI // i++ - SUBQ $1, DI // n-- - JG L4 // if n > 0 goto L4 - -E4: MOVQ CX, c+56(FP) // return c - RET - - -// func shlVU(z, x []Word, s uint) (c Word) -TEXT ·shlVU(SB),NOSPLIT,$0 - MOVQ z_len+8(FP), BX // i = z - SUBQ $1, BX // i-- - JL X8b // i < 0 (n <= 0) - - // n > 0 - MOVQ z+0(FP), R10 - MOVQ x+24(FP), R8 - MOVQ s+48(FP), CX - MOVQ (R8)(BX*8), AX // w1 = x[n-1] - MOVQ $0, DX - SHLQ CX, DX:AX // w1>>ŝ - MOVQ DX, c+56(FP) - - CMPQ BX, $0 - JLE X8a // i <= 0 - - // i > 0 -L8: MOVQ AX, DX // w = w1 - MOVQ -8(R8)(BX*8), AX // w1 = x[i-1] - SHLQ CX, DX:AX // w<<s | w1>>ŝ - MOVQ DX, (R10)(BX*8) // z[i] = w<<s | w1>>ŝ - SUBQ $1, BX // i-- - JG L8 // i > 0 - - // i <= 0 -X8a: SHLQ CX, AX // w1<<s - MOVQ AX, (R10) // z[0] = w1<<s - RET - -X8b: MOVQ $0, c+56(FP) - RET - - -// func shrVU(z, x []Word, s uint) (c Word) -TEXT ·shrVU(SB),NOSPLIT,$0 - MOVQ z_len+8(FP), R11 - SUBQ $1, R11 // n-- - JL X9b // n < 0 (n <= 0) - - // n > 0 - MOVQ z+0(FP), R10 - MOVQ x+24(FP), R8 - MOVQ s+48(FP), CX - MOVQ (R8), AX // w1 = x[0] - MOVQ $0, DX - SHRQ CX, DX:AX // w1<<ŝ - MOVQ DX, c+56(FP) - - MOVQ $0, BX // i = 0 - JMP E9 - - // i < n-1 -L9: MOVQ AX, DX // w = w1 - MOVQ 8(R8)(BX*8), AX // w1 = x[i+1] - SHRQ CX, DX:AX // w>>s | w1<<ŝ - MOVQ DX, (R10)(BX*8) // z[i] = w>>s | w1<<ŝ - ADDQ $1, BX // i++ - -E9: CMPQ BX, R11 - JL L9 // i < n-1 - - // i >= n-1 -X9a: SHRQ CX, AX // w1>>s - MOVQ AX, (R10)(R11*8) // z[n-1] = w1>>s - RET - -X9b: MOVQ $0, c+56(FP) - RET - - -// func mulAddVWW(z, x []Word, y, r Word) (c Word) -TEXT ·mulAddVWW(SB),NOSPLIT,$0 - MOVQ z+0(FP), R10 - MOVQ x+24(FP), R8 - MOVQ y+48(FP), R9 - MOVQ r+56(FP), CX // c = r - MOVQ z_len+8(FP), R11 - MOVQ $0, BX // i = 0 - JMP E5 - -L5: MOVQ (R8)(BX*8), AX - MULQ R9 - ADDQ CX, AX - ADCQ $0, DX - MOVQ AX, (R10)(BX*8) - MOVQ DX, CX - ADDQ $1, BX // i++ - -E5: CMPQ BX, R11 // i < n - JL L5 - - MOVQ CX, c+64(FP) - RET - - -// func addMulVVW(z, x []Word, y Word) (c Word) -TEXT ·addMulVVW(SB),NOSPLIT,$0 - MOVQ z+0(FP), R10 - MOVQ x+24(FP), R8 - MOVQ y+48(FP), R9 - MOVQ z_len+8(FP), R11 - MOVQ $0, BX // i = 0 - MOVQ $0, CX // c = 0 - JMP E6 - -L6: MOVQ (R8)(BX*8), AX - MULQ R9 - ADDQ CX, AX - ADCQ $0, DX - ADDQ AX, (R10)(BX*8) - ADCQ $0, DX - MOVQ DX, CX - ADDQ $1, BX // i++ - -E6: CMPQ BX, R11 // i < n - JL L6 - - MOVQ CX, c+56(FP) - RET - - -// func divWVW(z []Word, xn Word, x []Word, y Word) (r Word) -TEXT ·divWVW(SB),NOSPLIT,$0 - MOVQ z+0(FP), R10 - MOVQ xn+24(FP), DX // r = xn - MOVQ x+32(FP), R8 - MOVQ y+56(FP), R9 - MOVQ z_len+8(FP), BX // i = z - JMP E7 - -L7: MOVQ (R8)(BX*8), AX - DIVQ R9 - MOVQ AX, (R10)(BX*8) - -E7: SUBQ $1, BX // i-- - JGE L7 // i >= 0 - - MOVQ DX, r+64(FP) - RET - -// func bitLen(x Word) (n int) -TEXT ·bitLen(SB),NOSPLIT,$0 - BSRQ x+0(FP), AX - JZ Z1 - ADDQ $1, AX - MOVQ AX, n+8(FP) - RET - -Z1: MOVQ $0, n+8(FP) - RET diff --git a/src/pkg/math/big/arith_amd64p32.s b/src/pkg/math/big/arith_amd64p32.s deleted file mode 100644 index 227870a00..000000000 --- a/src/pkg/math/big/arith_amd64p32.s +++ /dev/null @@ -1,41 +0,0 @@ -// Copyright 2013 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. - -#include "../../../cmd/ld/textflag.h" - -TEXT ·mulWW(SB),NOSPLIT,$0 - JMP ·mulWW_g(SB) - -TEXT ·divWW(SB),NOSPLIT,$0 - JMP ·divWW_g(SB) - -TEXT ·addVV(SB),NOSPLIT,$0 - JMP ·addVV_g(SB) - -TEXT ·subVV(SB),NOSPLIT,$0 - JMP ·subVV_g(SB) - -TEXT ·addVW(SB),NOSPLIT,$0 - JMP ·addVW_g(SB) - -TEXT ·subVW(SB),NOSPLIT,$0 - JMP ·subVW_g(SB) - -TEXT ·shlVU(SB),NOSPLIT,$0 - JMP ·shlVU_g(SB) - -TEXT ·shrVU(SB),NOSPLIT,$0 - JMP ·shrVU_g(SB) - -TEXT ·mulAddVWW(SB),NOSPLIT,$0 - JMP ·mulAddVWW_g(SB) - -TEXT ·addMulVVW(SB),NOSPLIT,$0 - JMP ·addMulVVW_g(SB) - -TEXT ·divWVW(SB),NOSPLIT,$0 - JMP ·divWVW_g(SB) - -TEXT ·bitLen(SB),NOSPLIT,$0 - JMP ·bitLen_g(SB) diff --git a/src/pkg/math/big/arith_arm.s b/src/pkg/math/big/arith_arm.s deleted file mode 100644 index 8d36761c4..000000000 --- a/src/pkg/math/big/arith_arm.s +++ /dev/null @@ -1,300 +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. - -#include "../../../cmd/ld/textflag.h" - -// This file provides fast assembly versions for the elementary -// arithmetic operations on vectors implemented in arith.go. - -// func addVV(z, x, y []Word) (c Word) -TEXT ·addVV(SB),NOSPLIT,$0 - ADD.S $0, R0 // clear carry flag - MOVW z+0(FP), R1 - MOVW z_len+4(FP), R4 - MOVW x+12(FP), R2 - MOVW y+24(FP), R3 - ADD R4<<2, R1, R4 - B E1 -L1: - MOVW.P 4(R2), R5 - MOVW.P 4(R3), R6 - ADC.S R6, R5 - MOVW.P R5, 4(R1) -E1: - TEQ R1, R4 - BNE L1 - - MOVW $0, R0 - MOVW.CS $1, R0 - MOVW R0, c+36(FP) - RET - - -// func subVV(z, x, y []Word) (c Word) -// (same as addVV except for SBC instead of ADC and label names) -TEXT ·subVV(SB),NOSPLIT,$0 - SUB.S $0, R0 // clear borrow flag - MOVW z+0(FP), R1 - MOVW z_len+4(FP), R4 - MOVW x+12(FP), R2 - MOVW y+24(FP), R3 - ADD R4<<2, R1, R4 - B E2 -L2: - MOVW.P 4(R2), R5 - MOVW.P 4(R3), R6 - SBC.S R6, R5 - MOVW.P R5, 4(R1) -E2: - TEQ R1, R4 - BNE L2 - - MOVW $0, R0 - MOVW.CC $1, R0 - MOVW R0, c+36(FP) - RET - - -// func addVW(z, x []Word, y Word) (c Word) -TEXT ·addVW(SB),NOSPLIT,$0 - MOVW z+0(FP), R1 - MOVW z_len+4(FP), R4 - MOVW x+12(FP), R2 - MOVW y+24(FP), R3 - ADD R4<<2, R1, R4 - TEQ R1, R4 - BNE L3a - MOVW R3, c+28(FP) - RET -L3a: - MOVW.P 4(R2), R5 - ADD.S R3, R5 - MOVW.P R5, 4(R1) - B E3 -L3: - MOVW.P 4(R2), R5 - ADC.S $0, R5 - MOVW.P R5, 4(R1) -E3: - TEQ R1, R4 - BNE L3 - - MOVW $0, R0 - MOVW.CS $1, R0 - MOVW R0, c+28(FP) - RET - - -// func subVW(z, x []Word, y Word) (c Word) -TEXT ·subVW(SB),NOSPLIT,$0 - MOVW z+0(FP), R1 - MOVW z_len+4(FP), R4 - MOVW x+12(FP), R2 - MOVW y+24(FP), R3 - ADD R4<<2, R1, R4 - TEQ R1, R4 - BNE L4a - MOVW R3, c+28(FP) - RET -L4a: - MOVW.P 4(R2), R5 - SUB.S R3, R5 - MOVW.P R5, 4(R1) - B E4 -L4: - MOVW.P 4(R2), R5 - SBC.S $0, R5 - MOVW.P R5, 4(R1) -E4: - TEQ R1, R4 - BNE L4 - - MOVW $0, R0 - MOVW.CC $1, R0 - MOVW R0, c+28(FP) - RET - - -// func shlVU(z, x []Word, s uint) (c Word) -TEXT ·shlVU(SB),NOSPLIT,$0 - MOVW z_len+4(FP), R5 - TEQ $0, R5 - BEQ X7 - - MOVW z+0(FP), R1 - MOVW x+12(FP), R2 - ADD R5<<2, R2, R2 - ADD R5<<2, R1, R5 - MOVW s+24(FP), R3 - TEQ $0, R3 // shift 0 is special - BEQ Y7 - ADD $4, R1 // stop one word early - MOVW $32, R4 - SUB R3, R4 - MOVW $0, R7 - - MOVW.W -4(R2), R6 - MOVW R6<<R3, R7 - MOVW R6>>R4, R6 - MOVW R6, c+28(FP) - B E7 - -L7: - MOVW.W -4(R2), R6 - ORR R6>>R4, R7 - MOVW.W R7, -4(R5) - MOVW R6<<R3, R7 -E7: - TEQ R1, R5 - BNE L7 - - MOVW R7, -4(R5) - RET - -Y7: // copy loop, because shift 0 == shift 32 - MOVW.W -4(R2), R6 - MOVW.W R6, -4(R5) - TEQ R1, R5 - BNE Y7 - -X7: - MOVW $0, R1 - MOVW R1, c+28(FP) - RET - - -// func shrVU(z, x []Word, s uint) (c Word) -TEXT ·shrVU(SB),NOSPLIT,$0 - MOVW z_len+4(FP), R5 - TEQ $0, R5 - BEQ X6 - - MOVW z+0(FP), R1 - MOVW x+12(FP), R2 - ADD R5<<2, R1, R5 - MOVW s+24(FP), R3 - TEQ $0, R3 // shift 0 is special - BEQ Y6 - SUB $4, R5 // stop one word early - MOVW $32, R4 - SUB R3, R4 - MOVW $0, R7 - - // first word - MOVW.P 4(R2), R6 - MOVW R6>>R3, R7 - MOVW R6<<R4, R6 - MOVW R6, c+28(FP) - B E6 - - // word loop -L6: - MOVW.P 4(R2), R6 - ORR R6<<R4, R7 - MOVW.P R7, 4(R1) - MOVW R6>>R3, R7 -E6: - TEQ R1, R5 - BNE L6 - - MOVW R7, 0(R1) - RET - -Y6: // copy loop, because shift 0 == shift 32 - MOVW.P 4(R2), R6 - MOVW.P R6, 4(R1) - TEQ R1, R5 - BNE Y6 - -X6: - MOVW $0, R1 - MOVW R1, c+28(FP) - RET - - -// func mulAddVWW(z, x []Word, y, r Word) (c Word) -TEXT ·mulAddVWW(SB),NOSPLIT,$0 - MOVW $0, R0 - MOVW z+0(FP), R1 - MOVW z_len+4(FP), R5 - MOVW x+12(FP), R2 - MOVW y+24(FP), R3 - MOVW r+28(FP), R4 - ADD R5<<2, R1, R5 - B E8 - - // word loop -L8: - MOVW.P 4(R2), R6 - MULLU R6, R3, (R7, R6) - ADD.S R4, R6 - ADC R0, R7 - MOVW.P R6, 4(R1) - MOVW R7, R4 -E8: - TEQ R1, R5 - BNE L8 - - MOVW R4, c+32(FP) - RET - - -// func addMulVVW(z, x []Word, y Word) (c Word) -TEXT ·addMulVVW(SB),NOSPLIT,$0 - MOVW $0, R0 - MOVW z+0(FP), R1 - MOVW z_len+4(FP), R5 - MOVW x+12(FP), R2 - MOVW y+24(FP), R3 - ADD R5<<2, R1, R5 - MOVW $0, R4 - B E9 - - // word loop -L9: - MOVW.P 4(R2), R6 - MULLU R6, R3, (R7, R6) - ADD.S R4, R6 - ADC R0, R7 - MOVW 0(R1), R4 - ADD.S R4, R6 - ADC R0, R7 - MOVW.P R6, 4(R1) - MOVW R7, R4 -E9: - TEQ R1, R5 - BNE L9 - - MOVW R4, c+28(FP) - RET - - -// func divWVW(z* Word, xn Word, x []Word, y Word) (r Word) -TEXT ·divWVW(SB),NOSPLIT,$0 - // ARM has no multiword division, so use portable code. - B ·divWVW_g(SB) - - -// func divWW(x1, x0, y Word) (q, r Word) -TEXT ·divWW(SB),NOSPLIT,$0 - // ARM has no multiword division, so use portable code. - B ·divWW_g(SB) - - -// func mulWW(x, y Word) (z1, z0 Word) -TEXT ·mulWW(SB),NOSPLIT,$0 - MOVW x+0(FP), R1 - MOVW y+4(FP), R2 - MULLU R1, R2, (R4, R3) - MOVW R4, z1+8(FP) - MOVW R3, z0+12(FP) - RET - -// func bitLen(x Word) (n int) -TEXT ·bitLen(SB),NOSPLIT,$0 - MOVW x+0(FP), R0 - CLZ R0, R0 - RSB $32, R0 - MOVW R0, n+4(FP) - RET diff --git a/src/pkg/math/big/arith_decl.go b/src/pkg/math/big/arith_decl.go deleted file mode 100644 index 068cc8d93..000000000 --- a/src/pkg/math/big/arith_decl.go +++ /dev/null @@ -1,19 +0,0 @@ -// Copyright 2010 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. - -package big - -// implemented in arith_$GOARCH.s -func mulWW(x, y Word) (z1, z0 Word) -func divWW(x1, x0, y Word) (q, r Word) -func addVV(z, x, y []Word) (c Word) -func subVV(z, x, y []Word) (c Word) -func addVW(z, x []Word, y Word) (c Word) -func subVW(z, x []Word, y Word) (c Word) -func shlVU(z, x []Word, s uint) (c Word) -func shrVU(z, x []Word, s uint) (c Word) -func mulAddVWW(z, x []Word, y, r Word) (c Word) -func addMulVVW(z, x []Word, y Word) (c Word) -func divWVW(z []Word, xn Word, x []Word, y Word) (r Word) -func bitLen(x Word) (n int) diff --git a/src/pkg/math/big/arith_test.go b/src/pkg/math/big/arith_test.go deleted file mode 100644 index 3615a659c..000000000 --- a/src/pkg/math/big/arith_test.go +++ /dev/null @@ -1,456 +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. - -package big - -import ( - "math/rand" - "testing" -) - -type funWW func(x, y, c Word) (z1, z0 Word) -type argWW struct { - x, y, c, z1, z0 Word -} - -var sumWW = []argWW{ - {0, 0, 0, 0, 0}, - {0, 1, 0, 0, 1}, - {0, 0, 1, 0, 1}, - {0, 1, 1, 0, 2}, - {12345, 67890, 0, 0, 80235}, - {12345, 67890, 1, 0, 80236}, - {_M, 1, 0, 1, 0}, - {_M, 0, 1, 1, 0}, - {_M, 1, 1, 1, 1}, - {_M, _M, 0, 1, _M - 1}, - {_M, _M, 1, 1, _M}, -} - -func testFunWW(t *testing.T, msg string, f funWW, a argWW) { - z1, z0 := f(a.x, a.y, a.c) - if z1 != a.z1 || z0 != a.z0 { - t.Errorf("%s%+v\n\tgot z1:z0 = %#x:%#x; want %#x:%#x", msg, a, z1, z0, a.z1, a.z0) - } -} - -func TestFunWW(t *testing.T) { - for _, a := range sumWW { - arg := a - testFunWW(t, "addWW_g", addWW_g, arg) - - arg = argWW{a.y, a.x, a.c, a.z1, a.z0} - testFunWW(t, "addWW_g symmetric", addWW_g, arg) - - arg = argWW{a.z0, a.x, a.c, a.z1, a.y} - testFunWW(t, "subWW_g", subWW_g, arg) - - arg = argWW{a.z0, a.y, a.c, a.z1, a.x} - testFunWW(t, "subWW_g symmetric", subWW_g, arg) - } -} - -type funVV func(z, x, y []Word) (c Word) -type argVV struct { - z, x, y nat - c Word -} - -var sumVV = []argVV{ - {}, - {nat{0}, nat{0}, nat{0}, 0}, - {nat{1}, nat{1}, nat{0}, 0}, - {nat{0}, nat{_M}, nat{1}, 1}, - {nat{80235}, nat{12345}, nat{67890}, 0}, - {nat{_M - 1}, nat{_M}, nat{_M}, 1}, - {nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1}, - {nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0}, - {nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1}, -} - -func testFunVV(t *testing.T, msg string, f funVV, a argVV) { - z := make(nat, len(a.z)) - c := f(z, a.x, a.y) - for i, zi := range z { - if zi != a.z[i] { - t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i]) - break - } - } - if c != a.c { - t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c) - } -} - -func TestFunVV(t *testing.T) { - for _, a := range sumVV { - arg := a - testFunVV(t, "addVV_g", addVV_g, arg) - testFunVV(t, "addVV", addVV, arg) - - arg = argVV{a.z, a.y, a.x, a.c} - testFunVV(t, "addVV_g symmetric", addVV_g, arg) - testFunVV(t, "addVV symmetric", addVV, arg) - - arg = argVV{a.x, a.z, a.y, a.c} - testFunVV(t, "subVV_g", subVV_g, arg) - testFunVV(t, "subVV", subVV, arg) - - arg = argVV{a.y, a.z, a.x, a.c} - testFunVV(t, "subVV_g symmetric", subVV_g, arg) - testFunVV(t, "subVV symmetric", subVV, arg) - } -} - -// Always the same seed for reproducible results. -var rnd = rand.New(rand.NewSource(0)) - -func rndW() Word { - return Word(rnd.Int63()<<1 | rnd.Int63n(2)) -} - -func rndV(n int) []Word { - v := make([]Word, n) - for i := range v { - v[i] = rndW() - } - return v -} - -func benchmarkFunVV(b *testing.B, f funVV, n int) { - x := rndV(n) - y := rndV(n) - z := make([]Word, n) - b.SetBytes(int64(n * _W)) - b.ResetTimer() - for i := 0; i < b.N; i++ { - f(z, x, y) - } -} - -func BenchmarkAddVV_1(b *testing.B) { benchmarkFunVV(b, addVV, 1) } -func BenchmarkAddVV_2(b *testing.B) { benchmarkFunVV(b, addVV, 2) } -func BenchmarkAddVV_3(b *testing.B) { benchmarkFunVV(b, addVV, 3) } -func BenchmarkAddVV_4(b *testing.B) { benchmarkFunVV(b, addVV, 4) } -func BenchmarkAddVV_5(b *testing.B) { benchmarkFunVV(b, addVV, 5) } -func BenchmarkAddVV_1e1(b *testing.B) { benchmarkFunVV(b, addVV, 1e1) } -func BenchmarkAddVV_1e2(b *testing.B) { benchmarkFunVV(b, addVV, 1e2) } -func BenchmarkAddVV_1e3(b *testing.B) { benchmarkFunVV(b, addVV, 1e3) } -func BenchmarkAddVV_1e4(b *testing.B) { benchmarkFunVV(b, addVV, 1e4) } -func BenchmarkAddVV_1e5(b *testing.B) { benchmarkFunVV(b, addVV, 1e5) } - -type funVW func(z, x []Word, y Word) (c Word) -type argVW struct { - z, x nat - y Word - c Word -} - -var sumVW = []argVW{ - {}, - {nil, nil, 2, 2}, - {nat{0}, nat{0}, 0, 0}, - {nat{1}, nat{0}, 1, 0}, - {nat{1}, nat{1}, 0, 0}, - {nat{0}, nat{_M}, 1, 1}, - {nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1}, -} - -var prodVW = []argVW{ - {}, - {nat{0}, nat{0}, 0, 0}, - {nat{0}, nat{_M}, 0, 0}, - {nat{0}, nat{0}, _M, 0}, - {nat{1}, nat{1}, 1, 0}, - {nat{22793}, nat{991}, 23, 0}, - {nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0}, - {nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0}, - {nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0}, - {nat{_M << 1 & _M}, nat{_M}, 1 << 1, _M >> (_W - 1)}, - {nat{_M << 7 & _M}, nat{_M}, 1 << 7, _M >> (_W - 7)}, - {nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, _M >> (_W - 7)}, -} - -var lshVW = []argVW{ - {}, - {nat{0}, nat{0}, 0, 0}, - {nat{0}, nat{0}, 1, 0}, - {nat{0}, nat{0}, 20, 0}, - - {nat{_M}, nat{_M}, 0, 0}, - {nat{_M << 1 & _M}, nat{_M}, 1, 1}, - {nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)}, - - {nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0}, - {nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1}, - {nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)}, -} - -var rshVW = []argVW{ - {}, - {nat{0}, nat{0}, 0, 0}, - {nat{0}, nat{0}, 1, 0}, - {nat{0}, nat{0}, 20, 0}, - - {nat{_M}, nat{_M}, 0, 0}, - {nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M}, - {nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M}, - - {nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0}, - {nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M}, - {nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M}, -} - -func testFunVW(t *testing.T, msg string, f funVW, a argVW) { - z := make(nat, len(a.z)) - c := f(z, a.x, a.y) - for i, zi := range z { - if zi != a.z[i] { - t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i]) - break - } - } - if c != a.c { - t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c) - } -} - -func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW { - return func(z, x []Word, s Word) (c Word) { - return f(z, x, uint(s)) - } -} - -func TestFunVW(t *testing.T) { - for _, a := range sumVW { - arg := a - testFunVW(t, "addVW_g", addVW_g, arg) - testFunVW(t, "addVW", addVW, arg) - - arg = argVW{a.x, a.z, a.y, a.c} - testFunVW(t, "subVW_g", subVW_g, arg) - testFunVW(t, "subVW", subVW, arg) - } - - shlVW_g := makeFunVW(shlVU_g) - shlVW := makeFunVW(shlVU) - for _, a := range lshVW { - arg := a - testFunVW(t, "shlVU_g", shlVW_g, arg) - testFunVW(t, "shlVU", shlVW, arg) - } - - shrVW_g := makeFunVW(shrVU_g) - shrVW := makeFunVW(shrVU) - for _, a := range rshVW { - arg := a - testFunVW(t, "shrVU_g", shrVW_g, arg) - testFunVW(t, "shrVU", shrVW, arg) - } -} - -func benchmarkFunVW(b *testing.B, f funVW, n int) { - x := rndV(n) - y := rndW() - z := make([]Word, n) - b.SetBytes(int64(n * _W)) - b.ResetTimer() - for i := 0; i < b.N; i++ { - f(z, x, y) - } -} - -func BenchmarkAddVW_1(b *testing.B) { benchmarkFunVW(b, addVW, 1) } -func BenchmarkAddVW_2(b *testing.B) { benchmarkFunVW(b, addVW, 2) } -func BenchmarkAddVW_3(b *testing.B) { benchmarkFunVW(b, addVW, 3) } -func BenchmarkAddVW_4(b *testing.B) { benchmarkFunVW(b, addVW, 4) } -func BenchmarkAddVW_5(b *testing.B) { benchmarkFunVW(b, addVW, 5) } -func BenchmarkAddVW_1e1(b *testing.B) { benchmarkFunVW(b, addVW, 1e1) } -func BenchmarkAddVW_1e2(b *testing.B) { benchmarkFunVW(b, addVW, 1e2) } -func BenchmarkAddVW_1e3(b *testing.B) { benchmarkFunVW(b, addVW, 1e3) } -func BenchmarkAddVW_1e4(b *testing.B) { benchmarkFunVW(b, addVW, 1e4) } -func BenchmarkAddVW_1e5(b *testing.B) { benchmarkFunVW(b, addVW, 1e5) } - -type funVWW func(z, x []Word, y, r Word) (c Word) -type argVWW struct { - z, x nat - y, r Word - c Word -} - -var prodVWW = []argVWW{ - {}, - {nat{0}, nat{0}, 0, 0, 0}, - {nat{991}, nat{0}, 0, 991, 0}, - {nat{0}, nat{_M}, 0, 0, 0}, - {nat{991}, nat{_M}, 0, 991, 0}, - {nat{0}, nat{0}, _M, 0, 0}, - {nat{991}, nat{0}, _M, 991, 0}, - {nat{1}, nat{1}, 1, 0, 0}, - {nat{992}, nat{1}, 1, 991, 0}, - {nat{22793}, nat{991}, 23, 0, 0}, - {nat{22800}, nat{991}, 23, 7, 0}, - {nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0}, - {nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0}, - {nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0}, - {nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0}, - {nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0}, - {nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0}, - {nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)}, - {nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)}, - {nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)}, - {nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)}, - {nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)}, - {nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)}, -} - -func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) { - z := make(nat, len(a.z)) - c := f(z, a.x, a.y, a.r) - for i, zi := range z { - if zi != a.z[i] { - t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i]) - break - } - } - if c != a.c { - t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c) - } -} - -// TODO(gri) mulAddVWW and divWVW are symmetric operations but -// their signature is not symmetric. Try to unify. - -type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word) -type argWVW struct { - z nat - xn Word - x nat - y Word - r Word -} - -func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) { - z := make(nat, len(a.z)) - r := f(z, a.xn, a.x, a.y) - for i, zi := range z { - if zi != a.z[i] { - t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i]) - break - } - } - if r != a.r { - t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r) - } -} - -func TestFunVWW(t *testing.T) { - for _, a := range prodVWW { - arg := a - testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg) - testFunVWW(t, "mulAddVWW", mulAddVWW, arg) - - if a.y != 0 && a.r < a.y { - arg := argWVW{a.x, a.c, a.z, a.y, a.r} - testFunWVW(t, "divWVW_g", divWVW_g, arg) - testFunWVW(t, "divWVW", divWVW, arg) - } - } -} - -var mulWWTests = []struct { - x, y Word - q, r Word -}{ - {_M, _M, _M - 1, 1}, - // 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4}, -} - -func TestMulWW(t *testing.T) { - for i, test := range mulWWTests { - q, r := mulWW_g(test.x, test.y) - if q != test.q || r != test.r { - t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r) - } - } -} - -var mulAddWWWTests = []struct { - x, y, c Word - q, r Word -}{ - // TODO(agl): These will only work on 64-bit platforms. - // {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781}, - // {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382}, - {_M, _M, 0, _M - 1, 1}, - {_M, _M, _M, _M, 0}, -} - -func TestMulAddWWW(t *testing.T) { - for i, test := range mulAddWWWTests { - q, r := mulAddWWW_g(test.x, test.y, test.c) - if q != test.q || r != test.r { - t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r) - } - } -} - -func benchmarkAddMulVVW(b *testing.B, n int) { - x := rndV(n) - y := rndW() - z := make([]Word, n) - b.SetBytes(int64(n * _W)) - b.ResetTimer() - for i := 0; i < b.N; i++ { - addMulVVW(z, x, y) - } -} - -func BenchmarkAddMulVVW_1(b *testing.B) { benchmarkAddMulVVW(b, 1) } -func BenchmarkAddMulVVW_2(b *testing.B) { benchmarkAddMulVVW(b, 2) } -func BenchmarkAddMulVVW_3(b *testing.B) { benchmarkAddMulVVW(b, 3) } -func BenchmarkAddMulVVW_4(b *testing.B) { benchmarkAddMulVVW(b, 4) } -func BenchmarkAddMulVVW_5(b *testing.B) { benchmarkAddMulVVW(b, 5) } -func BenchmarkAddMulVVW_1e1(b *testing.B) { benchmarkAddMulVVW(b, 1e1) } -func BenchmarkAddMulVVW_1e2(b *testing.B) { benchmarkAddMulVVW(b, 1e2) } -func BenchmarkAddMulVVW_1e3(b *testing.B) { benchmarkAddMulVVW(b, 1e3) } -func BenchmarkAddMulVVW_1e4(b *testing.B) { benchmarkAddMulVVW(b, 1e4) } -func BenchmarkAddMulVVW_1e5(b *testing.B) { benchmarkAddMulVVW(b, 1e5) } - -func testWordBitLen(t *testing.T, fname string, f func(Word) int) { - for i := 0; i <= _W; i++ { - x := Word(1) << uint(i-1) // i == 0 => x == 0 - n := f(x) - if n != i { - t.Errorf("got %d; want %d for %s(%#x)", n, i, fname, x) - } - } -} - -func TestWordBitLen(t *testing.T) { - testWordBitLen(t, "bitLen", bitLen) - testWordBitLen(t, "bitLen_g", bitLen_g) -} - -// runs b.N iterations of bitLen called on a Word containing (1 << nbits)-1. -func benchmarkBitLenN(b *testing.B, nbits uint) { - testword := Word((uint64(1) << nbits) - 1) - for i := 0; i < b.N; i++ { - bitLen(testword) - } -} - -// Individual bitLen tests. Numbers chosen to examine both sides -// of powers-of-two boundaries. -func BenchmarkBitLen0(b *testing.B) { benchmarkBitLenN(b, 0) } -func BenchmarkBitLen1(b *testing.B) { benchmarkBitLenN(b, 1) } -func BenchmarkBitLen2(b *testing.B) { benchmarkBitLenN(b, 2) } -func BenchmarkBitLen3(b *testing.B) { benchmarkBitLenN(b, 3) } -func BenchmarkBitLen4(b *testing.B) { benchmarkBitLenN(b, 4) } -func BenchmarkBitLen5(b *testing.B) { benchmarkBitLenN(b, 5) } -func BenchmarkBitLen8(b *testing.B) { benchmarkBitLenN(b, 8) } -func BenchmarkBitLen9(b *testing.B) { benchmarkBitLenN(b, 9) } -func BenchmarkBitLen16(b *testing.B) { benchmarkBitLenN(b, 16) } -func BenchmarkBitLen17(b *testing.B) { benchmarkBitLenN(b, 17) } -func BenchmarkBitLen31(b *testing.B) { benchmarkBitLenN(b, 31) } diff --git a/src/pkg/math/big/calibrate_test.go b/src/pkg/math/big/calibrate_test.go deleted file mode 100644 index f69ffbf5c..000000000 --- a/src/pkg/math/big/calibrate_test.go +++ /dev/null @@ -1,88 +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 prints execution times for the Mul benchmark -// given different Karatsuba thresholds. The result may be -// used to manually fine-tune the threshold constant. The -// results are somewhat fragile; use repeated runs to get -// a clear picture. - -// Usage: go test -run=TestCalibrate -calibrate - -package big - -import ( - "flag" - "fmt" - "testing" - "time" -) - -var calibrate = flag.Bool("calibrate", false, "run calibration test") - -func karatsubaLoad(b *testing.B) { - BenchmarkMul(b) -} - -// measureKaratsuba returns the time to run a Karatsuba-relevant benchmark -// given Karatsuba threshold th. -func measureKaratsuba(th int) time.Duration { - th, karatsubaThreshold = karatsubaThreshold, th - res := testing.Benchmark(karatsubaLoad) - karatsubaThreshold = th - return time.Duration(res.NsPerOp()) -} - -func computeThresholds() { - fmt.Printf("Multiplication times for varying Karatsuba thresholds\n") - fmt.Printf("(run repeatedly for good results)\n") - - // determine Tk, the work load execution time using basic multiplication - Tb := measureKaratsuba(1e9) // th == 1e9 => Karatsuba multiplication disabled - fmt.Printf("Tb = %10s\n", Tb) - - // thresholds - th := 4 - th1 := -1 - th2 := -1 - - var deltaOld time.Duration - for count := -1; count != 0 && th < 128; count-- { - // determine Tk, the work load execution time using Karatsuba multiplication - Tk := measureKaratsuba(th) - - // improvement over Tb - delta := (Tb - Tk) * 100 / Tb - - fmt.Printf("th = %3d Tk = %10s %4d%%", th, Tk, delta) - - // determine break-even point - if Tk < Tb && th1 < 0 { - th1 = th - fmt.Print(" break-even point") - } - - // determine diminishing return - if 0 < delta && delta < deltaOld && th2 < 0 { - th2 = th - fmt.Print(" diminishing return") - } - deltaOld = delta - - fmt.Println() - - // trigger counter - if th1 >= 0 && th2 >= 0 && count < 0 { - count = 10 // this many extra measurements after we got both thresholds - } - - th++ - } -} - -func TestCalibrate(t *testing.T) { - if *calibrate { - computeThresholds() - } -} diff --git a/src/pkg/math/big/example_test.go b/src/pkg/math/big/example_test.go deleted file mode 100644 index 078be47f9..000000000 --- a/src/pkg/math/big/example_test.go +++ /dev/null @@ -1,51 +0,0 @@ -// Copyright 2012 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. - -package big_test - -import ( - "fmt" - "log" - "math/big" -) - -func ExampleRat_SetString() { - r := new(big.Rat) - r.SetString("355/113") - fmt.Println(r.FloatString(3)) - // Output: 3.142 -} - -func ExampleInt_SetString() { - i := new(big.Int) - i.SetString("644", 8) // octal - fmt.Println(i) - // Output: 420 -} - -func ExampleRat_Scan() { - // The Scan function is rarely used directly; - // the fmt package recognizes it as an implementation of fmt.Scanner. - r := new(big.Rat) - _, err := fmt.Sscan("1.5000", r) - if err != nil { - log.Println("error scanning value:", err) - } else { - fmt.Println(r) - } - // Output: 3/2 -} - -func ExampleInt_Scan() { - // The Scan function is rarely used directly; - // the fmt package recognizes it as an implementation of fmt.Scanner. - i := new(big.Int) - _, err := fmt.Sscan("18446744073709551617", i) - if err != nil { - log.Println("error scanning value:", err) - } else { - fmt.Println(i) - } - // Output: 18446744073709551617 -} diff --git a/src/pkg/math/big/gcd_test.go b/src/pkg/math/big/gcd_test.go deleted file mode 100644 index c0b9f5830..000000000 --- a/src/pkg/math/big/gcd_test.go +++ /dev/null @@ -1,47 +0,0 @@ -// Copyright 2012 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 a GCD benchmark. -// Usage: go test math/big -test.bench GCD - -package big - -import ( - "math/rand" - "testing" -) - -// randInt returns a pseudo-random Int in the range [1<<(size-1), (1<<size) - 1] -func randInt(r *rand.Rand, size uint) *Int { - n := new(Int).Lsh(intOne, size-1) - x := new(Int).Rand(r, n) - return x.Add(x, n) // make sure result > 1<<(size-1) -} - -func runGCD(b *testing.B, aSize, bSize uint) { - b.StopTimer() - var r = rand.New(rand.NewSource(1234)) - aa := randInt(r, aSize) - bb := randInt(r, bSize) - b.StartTimer() - for i := 0; i < b.N; i++ { - new(Int).GCD(nil, nil, aa, bb) - } -} - -func BenchmarkGCD10x10(b *testing.B) { runGCD(b, 10, 10) } -func BenchmarkGCD10x100(b *testing.B) { runGCD(b, 10, 100) } -func BenchmarkGCD10x1000(b *testing.B) { runGCD(b, 10, 1000) } -func BenchmarkGCD10x10000(b *testing.B) { runGCD(b, 10, 10000) } -func BenchmarkGCD10x100000(b *testing.B) { runGCD(b, 10, 100000) } -func BenchmarkGCD100x100(b *testing.B) { runGCD(b, 100, 100) } -func BenchmarkGCD100x1000(b *testing.B) { runGCD(b, 100, 1000) } -func BenchmarkGCD100x10000(b *testing.B) { runGCD(b, 100, 10000) } -func BenchmarkGCD100x100000(b *testing.B) { runGCD(b, 100, 100000) } -func BenchmarkGCD1000x1000(b *testing.B) { runGCD(b, 1000, 1000) } -func BenchmarkGCD1000x10000(b *testing.B) { runGCD(b, 1000, 10000) } -func BenchmarkGCD1000x100000(b *testing.B) { runGCD(b, 1000, 100000) } -func BenchmarkGCD10000x10000(b *testing.B) { runGCD(b, 10000, 10000) } -func BenchmarkGCD10000x100000(b *testing.B) { runGCD(b, 10000, 100000) } -func BenchmarkGCD100000x100000(b *testing.B) { runGCD(b, 100000, 100000) } diff --git a/src/pkg/math/big/hilbert_test.go b/src/pkg/math/big/hilbert_test.go deleted file mode 100644 index 1a84341b3..000000000 --- a/src/pkg/math/big/hilbert_test.go +++ /dev/null @@ -1,160 +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. - -// A little test program and benchmark for rational arithmetics. -// Computes a Hilbert matrix, its inverse, multiplies them -// and verifies that the product is the identity matrix. - -package big - -import ( - "fmt" - "testing" -) - -type matrix struct { - n, m int - a []*Rat -} - -func (a *matrix) at(i, j int) *Rat { - if !(0 <= i && i < a.n && 0 <= j && j < a.m) { - panic("index out of range") - } - return a.a[i*a.m+j] -} - -func (a *matrix) set(i, j int, x *Rat) { - if !(0 <= i && i < a.n && 0 <= j && j < a.m) { - panic("index out of range") - } - a.a[i*a.m+j] = x -} - -func newMatrix(n, m int) *matrix { - if !(0 <= n && 0 <= m) { - panic("illegal matrix") - } - a := new(matrix) - a.n = n - a.m = m - a.a = make([]*Rat, n*m) - return a -} - -func newUnit(n int) *matrix { - a := newMatrix(n, n) - for i := 0; i < n; i++ { - for j := 0; j < n; j++ { - x := NewRat(0, 1) - if i == j { - x.SetInt64(1) - } - a.set(i, j, x) - } - } - return a -} - -func newHilbert(n int) *matrix { - a := newMatrix(n, n) - for i := 0; i < n; i++ { - for j := 0; j < n; j++ { - a.set(i, j, NewRat(1, int64(i+j+1))) - } - } - return a -} - -func newInverseHilbert(n int) *matrix { - a := newMatrix(n, n) - for i := 0; i < n; i++ { - for j := 0; j < n; j++ { - x1 := new(Rat).SetInt64(int64(i + j + 1)) - x2 := new(Rat).SetInt(new(Int).Binomial(int64(n+i), int64(n-j-1))) - x3 := new(Rat).SetInt(new(Int).Binomial(int64(n+j), int64(n-i-1))) - x4 := new(Rat).SetInt(new(Int).Binomial(int64(i+j), int64(i))) - - x1.Mul(x1, x2) - x1.Mul(x1, x3) - x1.Mul(x1, x4) - x1.Mul(x1, x4) - - if (i+j)&1 != 0 { - x1.Neg(x1) - } - - a.set(i, j, x1) - } - } - return a -} - -func (a *matrix) mul(b *matrix) *matrix { - if a.m != b.n { - panic("illegal matrix multiply") - } - c := newMatrix(a.n, b.m) - for i := 0; i < c.n; i++ { - for j := 0; j < c.m; j++ { - x := NewRat(0, 1) - for k := 0; k < a.m; k++ { - x.Add(x, new(Rat).Mul(a.at(i, k), b.at(k, j))) - } - c.set(i, j, x) - } - } - return c -} - -func (a *matrix) eql(b *matrix) bool { - if a.n != b.n || a.m != b.m { - return false - } - for i := 0; i < a.n; i++ { - for j := 0; j < a.m; j++ { - if a.at(i, j).Cmp(b.at(i, j)) != 0 { - return false - } - } - } - return true -} - -func (a *matrix) String() string { - s := "" - for i := 0; i < a.n; i++ { - for j := 0; j < a.m; j++ { - s += fmt.Sprintf("\t%s", a.at(i, j)) - } - s += "\n" - } - return s -} - -func doHilbert(t *testing.T, n int) { - a := newHilbert(n) - b := newInverseHilbert(n) - I := newUnit(n) - ab := a.mul(b) - if !ab.eql(I) { - if t == nil { - panic("Hilbert failed") - } - t.Errorf("a = %s\n", a) - t.Errorf("b = %s\n", b) - t.Errorf("a*b = %s\n", ab) - t.Errorf("I = %s\n", I) - } -} - -func TestHilbert(t *testing.T) { - doHilbert(t, 10) -} - -func BenchmarkHilbert(b *testing.B) { - for i := 0; i < b.N; i++ { - doHilbert(nil, 10) - } -} diff --git a/src/pkg/math/big/int.go b/src/pkg/math/big/int.go deleted file mode 100644 index 269949d61..000000000 --- a/src/pkg/math/big/int.go +++ /dev/null @@ -1,1011 +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 implements signed multi-precision integers. - -package big - -import ( - "errors" - "fmt" - "io" - "math/rand" - "strings" -) - -// An Int represents a signed multi-precision integer. -// The zero value for an Int represents the value 0. -type Int struct { - neg bool // sign - abs nat // absolute value of the integer -} - -var intOne = &Int{false, natOne} - -// Sign returns: -// -// -1 if x < 0 -// 0 if x == 0 -// +1 if x > 0 -// -func (x *Int) Sign() int { - if len(x.abs) == 0 { - return 0 - } - if x.neg { - return -1 - } - return 1 -} - -// SetInt64 sets z to x and returns z. -func (z *Int) SetInt64(x int64) *Int { - neg := false - if x < 0 { - neg = true - x = -x - } - z.abs = z.abs.setUint64(uint64(x)) - z.neg = neg - return z -} - -// SetUint64 sets z to x and returns z. -func (z *Int) SetUint64(x uint64) *Int { - z.abs = z.abs.setUint64(x) - z.neg = false - return z -} - -// NewInt allocates and returns a new Int set to x. -func NewInt(x int64) *Int { - return new(Int).SetInt64(x) -} - -// Set sets z to x and returns z. -func (z *Int) Set(x *Int) *Int { - if z != x { - z.abs = z.abs.set(x.abs) - z.neg = x.neg - } - return z -} - -// Bits provides raw (unchecked but fast) access to x by returning its -// absolute value as a little-endian Word slice. The result and x share -// the same underlying array. -// Bits is intended to support implementation of missing low-level Int -// functionality outside this package; it should be avoided otherwise. -func (x *Int) Bits() []Word { - return x.abs -} - -// SetBits provides raw (unchecked but fast) access to z by setting its -// value to abs, interpreted as a little-endian Word slice, and returning -// z. The result and abs share the same underlying array. -// SetBits is intended to support implementation of missing low-level Int -// functionality outside this package; it should be avoided otherwise. -func (z *Int) SetBits(abs []Word) *Int { - z.abs = nat(abs).norm() - z.neg = false - return z -} - -// Abs sets z to |x| (the absolute value of x) and returns z. -func (z *Int) Abs(x *Int) *Int { - z.Set(x) - z.neg = false - return z -} - -// Neg sets z to -x and returns z. -func (z *Int) Neg(x *Int) *Int { - z.Set(x) - z.neg = len(z.abs) > 0 && !z.neg // 0 has no sign - return z -} - -// Add sets z to the sum x+y and returns z. -func (z *Int) Add(x, y *Int) *Int { - neg := x.neg - if x.neg == y.neg { - // x + y == x + y - // (-x) + (-y) == -(x + y) - z.abs = z.abs.add(x.abs, y.abs) - } else { - // x + (-y) == x - y == -(y - x) - // (-x) + y == y - x == -(x - y) - if x.abs.cmp(y.abs) >= 0 { - z.abs = z.abs.sub(x.abs, y.abs) - } else { - neg = !neg - z.abs = z.abs.sub(y.abs, x.abs) - } - } - z.neg = len(z.abs) > 0 && neg // 0 has no sign - return z -} - -// Sub sets z to the difference x-y and returns z. -func (z *Int) Sub(x, y *Int) *Int { - neg := x.neg - if x.neg != y.neg { - // x - (-y) == x + y - // (-x) - y == -(x + y) - z.abs = z.abs.add(x.abs, y.abs) - } else { - // x - y == x - y == -(y - x) - // (-x) - (-y) == y - x == -(x - y) - if x.abs.cmp(y.abs) >= 0 { - z.abs = z.abs.sub(x.abs, y.abs) - } else { - neg = !neg - z.abs = z.abs.sub(y.abs, x.abs) - } - } - z.neg = len(z.abs) > 0 && neg // 0 has no sign - return z -} - -// Mul sets z to the product x*y and returns z. -func (z *Int) Mul(x, y *Int) *Int { - // x * y == x * y - // x * (-y) == -(x * y) - // (-x) * y == -(x * y) - // (-x) * (-y) == x * y - z.abs = z.abs.mul(x.abs, y.abs) - z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign - return z -} - -// MulRange sets z to the product of all integers -// in the range [a, b] inclusively and returns z. -// If a > b (empty range), the result is 1. -func (z *Int) MulRange(a, b int64) *Int { - switch { - case a > b: - return z.SetInt64(1) // empty range - case a <= 0 && b >= 0: - return z.SetInt64(0) // range includes 0 - } - // a <= b && (b < 0 || a > 0) - - neg := false - if a < 0 { - neg = (b-a)&1 == 0 - a, b = -b, -a - } - - z.abs = z.abs.mulRange(uint64(a), uint64(b)) - z.neg = neg - return z -} - -// Binomial sets z to the binomial coefficient of (n, k) and returns z. -func (z *Int) Binomial(n, k int64) *Int { - var a, b Int - a.MulRange(n-k+1, n) - b.MulRange(1, k) - return z.Quo(&a, &b) -} - -// Quo sets z to the quotient x/y for y != 0 and returns z. -// If y == 0, a division-by-zero run-time panic occurs. -// Quo implements truncated division (like Go); see QuoRem for more details. -func (z *Int) Quo(x, y *Int) *Int { - z.abs, _ = z.abs.div(nil, x.abs, y.abs) - z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign - return z -} - -// Rem sets z to the remainder x%y for y != 0 and returns z. -// If y == 0, a division-by-zero run-time panic occurs. -// Rem implements truncated modulus (like Go); see QuoRem for more details. -func (z *Int) Rem(x, y *Int) *Int { - _, z.abs = nat(nil).div(z.abs, x.abs, y.abs) - z.neg = len(z.abs) > 0 && x.neg // 0 has no sign - return z -} - -// QuoRem sets z to the quotient x/y and r to the remainder x%y -// and returns the pair (z, r) for y != 0. -// If y == 0, a division-by-zero run-time panic occurs. -// -// QuoRem implements T-division and modulus (like Go): -// -// q = x/y with the result truncated to zero -// r = x - y*q -// -// (See Daan Leijen, ``Division and Modulus for Computer Scientists''.) -// See DivMod for Euclidean division and modulus (unlike Go). -// -func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) { - z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs) - z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg // 0 has no sign - return z, r -} - -// Div sets z to the quotient x/y for y != 0 and returns z. -// If y == 0, a division-by-zero run-time panic occurs. -// Div implements Euclidean division (unlike Go); see DivMod for more details. -func (z *Int) Div(x, y *Int) *Int { - y_neg := y.neg // z may be an alias for y - var r Int - z.QuoRem(x, y, &r) - if r.neg { - if y_neg { - z.Add(z, intOne) - } else { - z.Sub(z, intOne) - } - } - return z -} - -// Mod sets z to the modulus x%y for y != 0 and returns z. -// If y == 0, a division-by-zero run-time panic occurs. -// Mod implements Euclidean modulus (unlike Go); see DivMod for more details. -func (z *Int) Mod(x, y *Int) *Int { - y0 := y // save y - if z == y || alias(z.abs, y.abs) { - y0 = new(Int).Set(y) - } - var q Int - q.QuoRem(x, y, z) - if z.neg { - if y0.neg { - z.Sub(z, y0) - } else { - z.Add(z, y0) - } - } - return z -} - -// DivMod sets z to the quotient x div y and m to the modulus x mod y -// and returns the pair (z, m) for y != 0. -// If y == 0, a division-by-zero run-time panic occurs. -// -// DivMod implements Euclidean division and modulus (unlike Go): -// -// q = x div y such that -// m = x - y*q with 0 <= m < |q| -// -// (See Raymond T. Boute, ``The Euclidean definition of the functions -// div and mod''. ACM Transactions on Programming Languages and -// Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992. -// ACM press.) -// See QuoRem for T-division and modulus (like Go). -// -func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) { - y0 := y // save y - if z == y || alias(z.abs, y.abs) { - y0 = new(Int).Set(y) - } - z.QuoRem(x, y, m) - if m.neg { - if y0.neg { - z.Add(z, intOne) - m.Sub(m, y0) - } else { - z.Sub(z, intOne) - m.Add(m, y0) - } - } - return z, m -} - -// Cmp compares x and y and returns: -// -// -1 if x < y -// 0 if x == y -// +1 if x > y -// -func (x *Int) Cmp(y *Int) (r int) { - // x cmp y == x cmp y - // x cmp (-y) == x - // (-x) cmp y == y - // (-x) cmp (-y) == -(x cmp y) - switch { - case x.neg == y.neg: - r = x.abs.cmp(y.abs) - if x.neg { - r = -r - } - case x.neg: - r = -1 - default: - r = 1 - } - return -} - -func (x *Int) String() string { - switch { - case x == nil: - return "<nil>" - case x.neg: - return "-" + x.abs.decimalString() - } - return x.abs.decimalString() -} - -func charset(ch rune) string { - switch ch { - case 'b': - return lowercaseDigits[0:2] - case 'o': - return lowercaseDigits[0:8] - case 'd', 's', 'v': - return lowercaseDigits[0:10] - case 'x': - return lowercaseDigits[0:16] - case 'X': - return uppercaseDigits[0:16] - } - return "" // unknown format -} - -// write count copies of text to s -func writeMultiple(s fmt.State, text string, count int) { - if len(text) > 0 { - b := []byte(text) - for ; count > 0; count-- { - s.Write(b) - } - } -} - -// Format is a support routine for fmt.Formatter. It accepts -// the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x' -// (lowercase hexadecimal), and 'X' (uppercase hexadecimal). -// Also supported are the full suite of package fmt's format -// verbs for integral types, including '+', '-', and ' ' -// for sign control, '#' for leading zero in octal and for -// hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X" -// respectively, specification of minimum digits precision, -// output field width, space or zero padding, and left or -// right justification. -// -func (x *Int) Format(s fmt.State, ch rune) { - cs := charset(ch) - - // special cases - switch { - case cs == "": - // unknown format - fmt.Fprintf(s, "%%!%c(big.Int=%s)", ch, x.String()) - return - case x == nil: - fmt.Fprint(s, "<nil>") - return - } - - // determine sign character - sign := "" - switch { - case x.neg: - sign = "-" - case s.Flag('+'): // supersedes ' ' when both specified - sign = "+" - case s.Flag(' '): - sign = " " - } - - // determine prefix characters for indicating output base - prefix := "" - if s.Flag('#') { - switch ch { - case 'o': // octal - prefix = "0" - case 'x': // hexadecimal - prefix = "0x" - case 'X': - prefix = "0X" - } - } - - // determine digits with base set by len(cs) and digit characters from cs - digits := x.abs.string(cs) - - // number of characters for the three classes of number padding - var left int // space characters to left of digits for right justification ("%8d") - var zeroes int // zero characters (actually cs[0]) as left-most digits ("%.8d") - var right int // space characters to right of digits for left justification ("%-8d") - - // determine number padding from precision: the least number of digits to output - precision, precisionSet := s.Precision() - if precisionSet { - switch { - case len(digits) < precision: - zeroes = precision - len(digits) // count of zero padding - case digits == "0" && precision == 0: - return // print nothing if zero value (x == 0) and zero precision ("." or ".0") - } - } - - // determine field pad from width: the least number of characters to output - length := len(sign) + len(prefix) + zeroes + len(digits) - if width, widthSet := s.Width(); widthSet && length < width { // pad as specified - switch d := width - length; { - case s.Flag('-'): - // pad on the right with spaces; supersedes '0' when both specified - right = d - case s.Flag('0') && !precisionSet: - // pad with zeroes unless precision also specified - zeroes = d - default: - // pad on the left with spaces - left = d - } - } - - // print number as [left pad][sign][prefix][zero pad][digits][right pad] - writeMultiple(s, " ", left) - writeMultiple(s, sign, 1) - writeMultiple(s, prefix, 1) - writeMultiple(s, "0", zeroes) - writeMultiple(s, digits, 1) - writeMultiple(s, " ", right) -} - -// scan sets z to the integer value corresponding to the longest possible prefix -// read from r representing a signed integer number in a given conversion base. -// It returns z, the actual conversion base used, and an error, if any. In the -// error case, the value of z is undefined but the returned value is nil. The -// syntax follows the syntax of integer literals in Go. -// -// The base argument must be 0 or a value from 2 through MaxBase. If the base -// is 0, the string prefix determines the actual conversion base. A prefix of -// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a -// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10. -// -func (z *Int) scan(r io.RuneScanner, base int) (*Int, int, error) { - // determine sign - ch, _, err := r.ReadRune() - if err != nil { - return nil, 0, err - } - neg := false - switch ch { - case '-': - neg = true - case '+': // nothing to do - default: - r.UnreadRune() - } - - // determine mantissa - z.abs, base, err = z.abs.scan(r, base) - if err != nil { - return nil, base, err - } - z.neg = len(z.abs) > 0 && neg // 0 has no sign - - return z, base, nil -} - -// Scan is a support routine for fmt.Scanner; it sets z to the value of -// the scanned number. It accepts the formats 'b' (binary), 'o' (octal), -// 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal). -func (z *Int) Scan(s fmt.ScanState, ch rune) error { - s.SkipSpace() // skip leading space characters - base := 0 - switch ch { - case 'b': - base = 2 - case 'o': - base = 8 - case 'd': - base = 10 - case 'x', 'X': - base = 16 - case 's', 'v': - // let scan determine the base - default: - return errors.New("Int.Scan: invalid verb") - } - _, _, err := z.scan(s, base) - return err -} - -// Int64 returns the int64 representation of x. -// If x cannot be represented in an int64, the result is undefined. -func (x *Int) Int64() int64 { - v := int64(x.Uint64()) - if x.neg { - v = -v - } - return v -} - -// Uint64 returns the uint64 representation of x. -// If x cannot be represented in a uint64, the result is undefined. -func (x *Int) Uint64() uint64 { - if len(x.abs) == 0 { - return 0 - } - v := uint64(x.abs[0]) - if _W == 32 && len(x.abs) > 1 { - v |= uint64(x.abs[1]) << 32 - } - return v -} - -// SetString sets z to the value of s, interpreted in the given base, -// and returns z and a boolean indicating success. If SetString fails, -// the value of z is undefined but the returned value is nil. -// -// The base argument must be 0 or a value from 2 through MaxBase. If the base -// is 0, the string prefix determines the actual conversion base. A prefix of -// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a -// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10. -// -func (z *Int) SetString(s string, base int) (*Int, bool) { - r := strings.NewReader(s) - _, _, err := z.scan(r, base) - if err != nil { - return nil, false - } - _, _, err = r.ReadRune() - if err != io.EOF { - return nil, false - } - return z, true // err == io.EOF => scan consumed all of s -} - -// SetBytes interprets buf as the bytes of a big-endian unsigned -// integer, sets z to that value, and returns z. -func (z *Int) SetBytes(buf []byte) *Int { - z.abs = z.abs.setBytes(buf) - z.neg = false - return z -} - -// Bytes returns the absolute value of x as a big-endian byte slice. -func (x *Int) Bytes() []byte { - buf := make([]byte, len(x.abs)*_S) - return buf[x.abs.bytes(buf):] -} - -// BitLen returns the length of the absolute value of x in bits. -// The bit length of 0 is 0. -func (x *Int) BitLen() int { - return x.abs.bitLen() -} - -// Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. -// If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. -// See Knuth, volume 2, section 4.6.3. -func (z *Int) Exp(x, y, m *Int) *Int { - var yWords nat - if !y.neg { - yWords = y.abs - } - // y >= 0 - - var mWords nat - if m != nil { - mWords = m.abs // m.abs may be nil for m == 0 - } - - z.abs = z.abs.expNN(x.abs, yWords, mWords) - z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign - return z -} - -// GCD sets z to the greatest common divisor of a and b, which both must -// be > 0, and returns z. -// If x and y are not nil, GCD sets x and y such that z = a*x + b*y. -// If either a or b is <= 0, GCD sets z = x = y = 0. -func (z *Int) GCD(x, y, a, b *Int) *Int { - if a.Sign() <= 0 || b.Sign() <= 0 { - z.SetInt64(0) - if x != nil { - x.SetInt64(0) - } - if y != nil { - y.SetInt64(0) - } - return z - } - if x == nil && y == nil { - return z.binaryGCD(a, b) - } - - A := new(Int).Set(a) - B := new(Int).Set(b) - - X := new(Int) - Y := new(Int).SetInt64(1) - - lastX := new(Int).SetInt64(1) - lastY := new(Int) - - q := new(Int) - temp := new(Int) - - for len(B.abs) > 0 { - r := new(Int) - q, r = q.QuoRem(A, B, r) - - A, B = B, r - - temp.Set(X) - X.Mul(X, q) - X.neg = !X.neg - X.Add(X, lastX) - lastX.Set(temp) - - temp.Set(Y) - Y.Mul(Y, q) - Y.neg = !Y.neg - Y.Add(Y, lastY) - lastY.Set(temp) - } - - if x != nil { - *x = *lastX - } - - if y != nil { - *y = *lastY - } - - *z = *A - return z -} - -// binaryGCD sets z to the greatest common divisor of a and b, which both must -// be > 0, and returns z. -// See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B. -func (z *Int) binaryGCD(a, b *Int) *Int { - u := z - v := new(Int) - - // use one Euclidean iteration to ensure that u and v are approx. the same size - switch { - case len(a.abs) > len(b.abs): - u.Set(b) - v.Rem(a, b) - case len(a.abs) < len(b.abs): - u.Set(a) - v.Rem(b, a) - default: - u.Set(a) - v.Set(b) - } - - // v might be 0 now - if len(v.abs) == 0 { - return u - } - // u > 0 && v > 0 - - // determine largest k such that u = u' << k, v = v' << k - k := u.abs.trailingZeroBits() - if vk := v.abs.trailingZeroBits(); vk < k { - k = vk - } - u.Rsh(u, k) - v.Rsh(v, k) - - // determine t (we know that u > 0) - t := new(Int) - if u.abs[0]&1 != 0 { - // u is odd - t.Neg(v) - } else { - t.Set(u) - } - - for len(t.abs) > 0 { - // reduce t - t.Rsh(t, t.abs.trailingZeroBits()) - if t.neg { - v, t = t, v - v.neg = len(v.abs) > 0 && !v.neg // 0 has no sign - } else { - u, t = t, u - } - t.Sub(u, v) - } - - return z.Lsh(u, k) -} - -// ProbablyPrime performs n Miller-Rabin tests to check whether x is prime. -// If it returns true, x is prime with probability 1 - 1/4^n. -// If it returns false, x is not prime. -func (x *Int) ProbablyPrime(n int) bool { - return !x.neg && x.abs.probablyPrime(n) -} - -// Rand sets z to a pseudo-random number in [0, n) and returns z. -func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int { - z.neg = false - if n.neg == true || len(n.abs) == 0 { - z.abs = nil - return z - } - z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen()) - return z -} - -// ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where -// p is a prime) and returns z. -func (z *Int) ModInverse(g, p *Int) *Int { - var d Int - d.GCD(z, nil, g, p) - // x and y are such that g*x + p*y = d. Since p is prime, d = 1. Taking - // that modulo p results in g*x = 1, therefore x is the inverse element. - if z.neg { - z.Add(z, p) - } - return z -} - -// Lsh sets z = x << n and returns z. -func (z *Int) Lsh(x *Int, n uint) *Int { - z.abs = z.abs.shl(x.abs, n) - z.neg = x.neg - return z -} - -// Rsh sets z = x >> n and returns z. -func (z *Int) Rsh(x *Int, n uint) *Int { - if x.neg { - // (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1) - t := z.abs.sub(x.abs, natOne) // no underflow because |x| > 0 - t = t.shr(t, n) - z.abs = t.add(t, natOne) - z.neg = true // z cannot be zero if x is negative - return z - } - - z.abs = z.abs.shr(x.abs, n) - z.neg = false - return z -} - -// Bit returns the value of the i'th bit of x. That is, it -// returns (x>>i)&1. The bit index i must be >= 0. -func (x *Int) Bit(i int) uint { - if i == 0 { - // optimization for common case: odd/even test of x - if len(x.abs) > 0 { - return uint(x.abs[0] & 1) // bit 0 is same for -x - } - return 0 - } - if i < 0 { - panic("negative bit index") - } - if x.neg { - t := nat(nil).sub(x.abs, natOne) - return t.bit(uint(i)) ^ 1 - } - - return x.abs.bit(uint(i)) -} - -// SetBit sets z to x, with x's i'th bit set to b (0 or 1). -// That is, if b is 1 SetBit sets z = x | (1 << i); -// if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1, -// SetBit will panic. -func (z *Int) SetBit(x *Int, i int, b uint) *Int { - if i < 0 { - panic("negative bit index") - } - if x.neg { - t := z.abs.sub(x.abs, natOne) - t = t.setBit(t, uint(i), b^1) - z.abs = t.add(t, natOne) - z.neg = len(z.abs) > 0 - return z - } - z.abs = z.abs.setBit(x.abs, uint(i), b) - z.neg = false - return z -} - -// And sets z = x & y and returns z. -func (z *Int) And(x, y *Int) *Int { - if x.neg == y.neg { - if x.neg { - // (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1) - x1 := nat(nil).sub(x.abs, natOne) - y1 := nat(nil).sub(y.abs, natOne) - z.abs = z.abs.add(z.abs.or(x1, y1), natOne) - z.neg = true // z cannot be zero if x and y are negative - return z - } - - // x & y == x & y - z.abs = z.abs.and(x.abs, y.abs) - z.neg = false - return z - } - - // x.neg != y.neg - if x.neg { - x, y = y, x // & is symmetric - } - - // x & (-y) == x & ^(y-1) == x &^ (y-1) - y1 := nat(nil).sub(y.abs, natOne) - z.abs = z.abs.andNot(x.abs, y1) - z.neg = false - return z -} - -// AndNot sets z = x &^ y and returns z. -func (z *Int) AndNot(x, y *Int) *Int { - if x.neg == y.neg { - if x.neg { - // (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1) - x1 := nat(nil).sub(x.abs, natOne) - y1 := nat(nil).sub(y.abs, natOne) - z.abs = z.abs.andNot(y1, x1) - z.neg = false - return z - } - - // x &^ y == x &^ y - z.abs = z.abs.andNot(x.abs, y.abs) - z.neg = false - return z - } - - if x.neg { - // (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1) - x1 := nat(nil).sub(x.abs, natOne) - z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne) - z.neg = true // z cannot be zero if x is negative and y is positive - return z - } - - // x &^ (-y) == x &^ ^(y-1) == x & (y-1) - y1 := nat(nil).add(y.abs, natOne) - z.abs = z.abs.and(x.abs, y1) - z.neg = false - return z -} - -// Or sets z = x | y and returns z. -func (z *Int) Or(x, y *Int) *Int { - if x.neg == y.neg { - if x.neg { - // (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1) - x1 := nat(nil).sub(x.abs, natOne) - y1 := nat(nil).sub(y.abs, natOne) - z.abs = z.abs.add(z.abs.and(x1, y1), natOne) - z.neg = true // z cannot be zero if x and y are negative - return z - } - - // x | y == x | y - z.abs = z.abs.or(x.abs, y.abs) - z.neg = false - return z - } - - // x.neg != y.neg - if x.neg { - x, y = y, x // | is symmetric - } - - // x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1) - y1 := nat(nil).sub(y.abs, natOne) - z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne) - z.neg = true // z cannot be zero if one of x or y is negative - return z -} - -// Xor sets z = x ^ y and returns z. -func (z *Int) Xor(x, y *Int) *Int { - if x.neg == y.neg { - if x.neg { - // (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1) - x1 := nat(nil).sub(x.abs, natOne) - y1 := nat(nil).sub(y.abs, natOne) - z.abs = z.abs.xor(x1, y1) - z.neg = false - return z - } - - // x ^ y == x ^ y - z.abs = z.abs.xor(x.abs, y.abs) - z.neg = false - return z - } - - // x.neg != y.neg - if x.neg { - x, y = y, x // ^ is symmetric - } - - // x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1) - y1 := nat(nil).sub(y.abs, natOne) - z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne) - z.neg = true // z cannot be zero if only one of x or y is negative - return z -} - -// Not sets z = ^x and returns z. -func (z *Int) Not(x *Int) *Int { - if x.neg { - // ^(-x) == ^(^(x-1)) == x-1 - z.abs = z.abs.sub(x.abs, natOne) - z.neg = false - return z - } - - // ^x == -x-1 == -(x+1) - z.abs = z.abs.add(x.abs, natOne) - z.neg = true // z cannot be zero if x is positive - return z -} - -// Gob codec version. Permits backward-compatible changes to the encoding. -const intGobVersion byte = 1 - -// GobEncode implements the gob.GobEncoder interface. -func (x *Int) GobEncode() ([]byte, error) { - if x == nil { - return nil, nil - } - buf := make([]byte, 1+len(x.abs)*_S) // extra byte for version and sign bit - i := x.abs.bytes(buf) - 1 // i >= 0 - b := intGobVersion << 1 // make space for sign bit - if x.neg { - b |= 1 - } - buf[i] = b - return buf[i:], nil -} - -// GobDecode implements the gob.GobDecoder interface. -func (z *Int) GobDecode(buf []byte) error { - if len(buf) == 0 { - // Other side sent a nil or default value. - *z = Int{} - return nil - } - b := buf[0] - if b>>1 != intGobVersion { - return errors.New(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1)) - } - z.neg = b&1 != 0 - z.abs = z.abs.setBytes(buf[1:]) - return nil -} - -// MarshalJSON implements the json.Marshaler interface. -func (z *Int) MarshalJSON() ([]byte, error) { - // TODO(gri): get rid of the []byte/string conversions - return []byte(z.String()), nil -} - -// UnmarshalJSON implements the json.Unmarshaler interface. -func (z *Int) UnmarshalJSON(text []byte) error { - // TODO(gri): get rid of the []byte/string conversions - if _, ok := z.SetString(string(text), 0); !ok { - return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) - } - return nil -} - -// MarshalText implements the encoding.TextMarshaler interface -func (z *Int) MarshalText() (text []byte, err error) { - return []byte(z.String()), nil -} - -// UnmarshalText implements the encoding.TextUnmarshaler interface -func (z *Int) UnmarshalText(text []byte) error { - if _, ok := z.SetString(string(text), 0); !ok { - return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) - } - return nil -} diff --git a/src/pkg/math/big/int_test.go b/src/pkg/math/big/int_test.go deleted file mode 100644 index 299dc72fb..000000000 --- a/src/pkg/math/big/int_test.go +++ /dev/null @@ -1,1601 +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. - -package big - -import ( - "bytes" - "encoding/gob" - "encoding/hex" - "encoding/json" - "encoding/xml" - "fmt" - "math/rand" - "testing" - "testing/quick" -) - -func isNormalized(x *Int) bool { - if len(x.abs) == 0 { - return !x.neg - } - // len(x.abs) > 0 - return x.abs[len(x.abs)-1] != 0 -} - -type funZZ func(z, x, y *Int) *Int -type argZZ struct { - z, x, y *Int -} - -var sumZZ = []argZZ{ - {NewInt(0), NewInt(0), NewInt(0)}, - {NewInt(1), NewInt(1), NewInt(0)}, - {NewInt(1111111110), NewInt(123456789), NewInt(987654321)}, - {NewInt(-1), NewInt(-1), NewInt(0)}, - {NewInt(864197532), NewInt(-123456789), NewInt(987654321)}, - {NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)}, -} - -var prodZZ = []argZZ{ - {NewInt(0), NewInt(0), NewInt(0)}, - {NewInt(0), NewInt(1), NewInt(0)}, - {NewInt(1), NewInt(1), NewInt(1)}, - {NewInt(-991 * 991), NewInt(991), NewInt(-991)}, - // TODO(gri) add larger products -} - -func TestSignZ(t *testing.T) { - var zero Int - for _, a := range sumZZ { - s := a.z.Sign() - e := a.z.Cmp(&zero) - if s != e { - t.Errorf("got %d; want %d for z = %v", s, e, a.z) - } - } -} - -func TestSetZ(t *testing.T) { - for _, a := range sumZZ { - var z Int - z.Set(a.z) - if !isNormalized(&z) { - t.Errorf("%v is not normalized", z) - } - if (&z).Cmp(a.z) != 0 { - t.Errorf("got z = %v; want %v", z, a.z) - } - } -} - -func TestAbsZ(t *testing.T) { - var zero Int - for _, a := range sumZZ { - var z Int - z.Abs(a.z) - var e Int - e.Set(a.z) - if e.Cmp(&zero) < 0 { - e.Sub(&zero, &e) - } - if z.Cmp(&e) != 0 { - t.Errorf("got z = %v; want %v", z, e) - } - } -} - -func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) { - var z Int - f(&z, a.x, a.y) - if !isNormalized(&z) { - t.Errorf("%s%v is not normalized", msg, z) - } - if (&z).Cmp(a.z) != 0 { - t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z) - } -} - -func TestSumZZ(t *testing.T) { - AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) } - SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) } - for _, a := range sumZZ { - arg := a - testFunZZ(t, "AddZZ", AddZZ, arg) - - arg = argZZ{a.z, a.y, a.x} - testFunZZ(t, "AddZZ symmetric", AddZZ, arg) - - arg = argZZ{a.x, a.z, a.y} - testFunZZ(t, "SubZZ", SubZZ, arg) - - arg = argZZ{a.y, a.z, a.x} - testFunZZ(t, "SubZZ symmetric", SubZZ, arg) - } -} - -func TestProdZZ(t *testing.T) { - MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) } - for _, a := range prodZZ { - arg := a - testFunZZ(t, "MulZZ", MulZZ, arg) - - arg = argZZ{a.z, a.y, a.x} - testFunZZ(t, "MulZZ symmetric", MulZZ, arg) - } -} - -// mulBytes returns x*y via grade school multiplication. Both inputs -// and the result are assumed to be in big-endian representation (to -// match the semantics of Int.Bytes and Int.SetBytes). -func mulBytes(x, y []byte) []byte { - z := make([]byte, len(x)+len(y)) - - // multiply - k0 := len(z) - 1 - for j := len(y) - 1; j >= 0; j-- { - d := int(y[j]) - if d != 0 { - k := k0 - carry := 0 - for i := len(x) - 1; i >= 0; i-- { - t := int(z[k]) + int(x[i])*d + carry - z[k], carry = byte(t), t>>8 - k-- - } - z[k] = byte(carry) - } - k0-- - } - - // normalize (remove leading 0's) - i := 0 - for i < len(z) && z[i] == 0 { - i++ - } - - return z[i:] -} - -func checkMul(a, b []byte) bool { - var x, y, z1 Int - x.SetBytes(a) - y.SetBytes(b) - z1.Mul(&x, &y) - - var z2 Int - z2.SetBytes(mulBytes(a, b)) - - return z1.Cmp(&z2) == 0 -} - -func TestMul(t *testing.T) { - if err := quick.Check(checkMul, nil); err != nil { - t.Error(err) - } -} - -var mulRangesZ = []struct { - a, b int64 - prod string -}{ - // entirely positive ranges are covered by mulRangesN - {-1, 1, "0"}, - {-2, -1, "2"}, - {-3, -2, "6"}, - {-3, -1, "-6"}, - {1, 3, "6"}, - {-10, -10, "-10"}, - {0, -1, "1"}, // empty range - {-1, -100, "1"}, // empty range - {-1, 1, "0"}, // range includes 0 - {-1e9, 0, "0"}, // range includes 0 - {-1e9, 1e9, "0"}, // range includes 0 - {-10, -1, "3628800"}, // 10! - {-20, -2, "-2432902008176640000"}, // -20! - {-99, -1, - "-933262154439441526816992388562667004907159682643816214685929" + - "638952175999932299156089414639761565182862536979208272237582" + - "511852109168640000000000000000000000", // -99! - }, -} - -func TestMulRangeZ(t *testing.T) { - var tmp Int - // test entirely positive ranges - for i, r := range mulRangesN { - prod := tmp.MulRange(int64(r.a), int64(r.b)).String() - if prod != r.prod { - t.Errorf("#%da: got %s; want %s", i, prod, r.prod) - } - } - // test other ranges - for i, r := range mulRangesZ { - prod := tmp.MulRange(r.a, r.b).String() - if prod != r.prod { - t.Errorf("#%db: got %s; want %s", i, prod, r.prod) - } - } -} - -var stringTests = []struct { - in string - out string - base int - val int64 - ok bool -}{ - {in: "", ok: false}, - {in: "a", ok: false}, - {in: "z", ok: false}, - {in: "+", ok: false}, - {in: "-", ok: false}, - {in: "0b", ok: false}, - {in: "0x", ok: false}, - {in: "2", base: 2, ok: false}, - {in: "0b2", base: 0, ok: false}, - {in: "08", ok: false}, - {in: "8", base: 8, ok: false}, - {in: "0xg", base: 0, ok: false}, - {in: "g", base: 16, ok: false}, - {"0", "0", 0, 0, true}, - {"0", "0", 10, 0, true}, - {"0", "0", 16, 0, true}, - {"+0", "0", 0, 0, true}, - {"-0", "0", 0, 0, true}, - {"10", "10", 0, 10, true}, - {"10", "10", 10, 10, true}, - {"10", "10", 16, 16, true}, - {"-10", "-10", 16, -16, true}, - {"+10", "10", 16, 16, true}, - {"0x10", "16", 0, 16, true}, - {in: "0x10", base: 16, ok: false}, - {"-0x10", "-16", 0, -16, true}, - {"+0x10", "16", 0, 16, true}, - {"00", "0", 0, 0, true}, - {"0", "0", 8, 0, true}, - {"07", "7", 0, 7, true}, - {"7", "7", 8, 7, true}, - {"023", "19", 0, 19, true}, - {"23", "23", 8, 19, true}, - {"cafebabe", "cafebabe", 16, 0xcafebabe, true}, - {"0b0", "0", 0, 0, true}, - {"-111", "-111", 2, -7, true}, - {"-0b111", "-7", 0, -7, true}, - {"0b1001010111", "599", 0, 0x257, true}, - {"1001010111", "1001010111", 2, 0x257, true}, -} - -func format(base int) string { - switch base { - case 2: - return "%b" - case 8: - return "%o" - case 16: - return "%x" - } - return "%d" -} - -func TestGetString(t *testing.T) { - z := new(Int) - for i, test := range stringTests { - if !test.ok { - continue - } - z.SetInt64(test.val) - - if test.base == 10 { - s := z.String() - if s != test.out { - t.Errorf("#%da got %s; want %s", i, s, test.out) - } - } - - s := fmt.Sprintf(format(test.base), z) - if s != test.out { - t.Errorf("#%db got %s; want %s", i, s, test.out) - } - } -} - -func TestSetString(t *testing.T) { - tmp := new(Int) - for i, test := range stringTests { - // initialize to a non-zero value so that issues with parsing - // 0 are detected - tmp.SetInt64(1234567890) - n1, ok1 := new(Int).SetString(test.in, test.base) - n2, ok2 := tmp.SetString(test.in, test.base) - expected := NewInt(test.val) - if ok1 != test.ok || ok2 != test.ok { - t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok) - continue - } - if !ok1 { - if n1 != nil { - t.Errorf("#%d (input '%s') n1 != nil", i, test.in) - } - continue - } - if !ok2 { - if n2 != nil { - t.Errorf("#%d (input '%s') n2 != nil", i, test.in) - } - continue - } - - if ok1 && !isNormalized(n1) { - t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1) - } - if ok2 && !isNormalized(n2) { - t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2) - } - - if n1.Cmp(expected) != 0 { - t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val) - } - if n2.Cmp(expected) != 0 { - t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val) - } - } -} - -var formatTests = []struct { - input string - format string - output string -}{ - {"<nil>", "%x", "<nil>"}, - {"<nil>", "%#x", "<nil>"}, - {"<nil>", "%#y", "%!y(big.Int=<nil>)"}, - - {"10", "%b", "1010"}, - {"10", "%o", "12"}, - {"10", "%d", "10"}, - {"10", "%v", "10"}, - {"10", "%x", "a"}, - {"10", "%X", "A"}, - {"-10", "%X", "-A"}, - {"10", "%y", "%!y(big.Int=10)"}, - {"-10", "%y", "%!y(big.Int=-10)"}, - - {"10", "%#b", "1010"}, - {"10", "%#o", "012"}, - {"10", "%#d", "10"}, - {"10", "%#v", "10"}, - {"10", "%#x", "0xa"}, - {"10", "%#X", "0XA"}, - {"-10", "%#X", "-0XA"}, - {"10", "%#y", "%!y(big.Int=10)"}, - {"-10", "%#y", "%!y(big.Int=-10)"}, - - {"1234", "%d", "1234"}, - {"1234", "%3d", "1234"}, - {"1234", "%4d", "1234"}, - {"-1234", "%d", "-1234"}, - {"1234", "% 5d", " 1234"}, - {"1234", "%+5d", "+1234"}, - {"1234", "%-5d", "1234 "}, - {"1234", "%x", "4d2"}, - {"1234", "%X", "4D2"}, - {"-1234", "%3x", "-4d2"}, - {"-1234", "%4x", "-4d2"}, - {"-1234", "%5x", " -4d2"}, - {"-1234", "%-5x", "-4d2 "}, - {"1234", "%03d", "1234"}, - {"1234", "%04d", "1234"}, - {"1234", "%05d", "01234"}, - {"1234", "%06d", "001234"}, - {"-1234", "%06d", "-01234"}, - {"1234", "%+06d", "+01234"}, - {"1234", "% 06d", " 01234"}, - {"1234", "%-6d", "1234 "}, - {"1234", "%-06d", "1234 "}, - {"-1234", "%-06d", "-1234 "}, - - {"1234", "%.3d", "1234"}, - {"1234", "%.4d", "1234"}, - {"1234", "%.5d", "01234"}, - {"1234", "%.6d", "001234"}, - {"-1234", "%.3d", "-1234"}, - {"-1234", "%.4d", "-1234"}, - {"-1234", "%.5d", "-01234"}, - {"-1234", "%.6d", "-001234"}, - - {"1234", "%8.3d", " 1234"}, - {"1234", "%8.4d", " 1234"}, - {"1234", "%8.5d", " 01234"}, - {"1234", "%8.6d", " 001234"}, - {"-1234", "%8.3d", " -1234"}, - {"-1234", "%8.4d", " -1234"}, - {"-1234", "%8.5d", " -01234"}, - {"-1234", "%8.6d", " -001234"}, - - {"1234", "%+8.3d", " +1234"}, - {"1234", "%+8.4d", " +1234"}, - {"1234", "%+8.5d", " +01234"}, - {"1234", "%+8.6d", " +001234"}, - {"-1234", "%+8.3d", " -1234"}, - {"-1234", "%+8.4d", " -1234"}, - {"-1234", "%+8.5d", " -01234"}, - {"-1234", "%+8.6d", " -001234"}, - - {"1234", "% 8.3d", " 1234"}, - {"1234", "% 8.4d", " 1234"}, - {"1234", "% 8.5d", " 01234"}, - {"1234", "% 8.6d", " 001234"}, - {"-1234", "% 8.3d", " -1234"}, - {"-1234", "% 8.4d", " -1234"}, - {"-1234", "% 8.5d", " -01234"}, - {"-1234", "% 8.6d", " -001234"}, - - {"1234", "%.3x", "4d2"}, - {"1234", "%.4x", "04d2"}, - {"1234", "%.5x", "004d2"}, - {"1234", "%.6x", "0004d2"}, - {"-1234", "%.3x", "-4d2"}, - {"-1234", "%.4x", "-04d2"}, - {"-1234", "%.5x", "-004d2"}, - {"-1234", "%.6x", "-0004d2"}, - - {"1234", "%8.3x", " 4d2"}, - {"1234", "%8.4x", " 04d2"}, - {"1234", "%8.5x", " 004d2"}, - {"1234", "%8.6x", " 0004d2"}, - {"-1234", "%8.3x", " -4d2"}, - {"-1234", "%8.4x", " -04d2"}, - {"-1234", "%8.5x", " -004d2"}, - {"-1234", "%8.6x", " -0004d2"}, - - {"1234", "%+8.3x", " +4d2"}, - {"1234", "%+8.4x", " +04d2"}, - {"1234", "%+8.5x", " +004d2"}, - {"1234", "%+8.6x", " +0004d2"}, - {"-1234", "%+8.3x", " -4d2"}, - {"-1234", "%+8.4x", " -04d2"}, - {"-1234", "%+8.5x", " -004d2"}, - {"-1234", "%+8.6x", " -0004d2"}, - - {"1234", "% 8.3x", " 4d2"}, - {"1234", "% 8.4x", " 04d2"}, - {"1234", "% 8.5x", " 004d2"}, - {"1234", "% 8.6x", " 0004d2"}, - {"1234", "% 8.7x", " 00004d2"}, - {"1234", "% 8.8x", " 000004d2"}, - {"-1234", "% 8.3x", " -4d2"}, - {"-1234", "% 8.4x", " -04d2"}, - {"-1234", "% 8.5x", " -004d2"}, - {"-1234", "% 8.6x", " -0004d2"}, - {"-1234", "% 8.7x", "-00004d2"}, - {"-1234", "% 8.8x", "-000004d2"}, - - {"1234", "%-8.3d", "1234 "}, - {"1234", "%-8.4d", "1234 "}, - {"1234", "%-8.5d", "01234 "}, - {"1234", "%-8.6d", "001234 "}, - {"1234", "%-8.7d", "0001234 "}, - {"1234", "%-8.8d", "00001234"}, - {"-1234", "%-8.3d", "-1234 "}, - {"-1234", "%-8.4d", "-1234 "}, - {"-1234", "%-8.5d", "-01234 "}, - {"-1234", "%-8.6d", "-001234 "}, - {"-1234", "%-8.7d", "-0001234"}, - {"-1234", "%-8.8d", "-00001234"}, - - {"16777215", "%b", "111111111111111111111111"}, // 2**24 - 1 - - {"0", "%.d", ""}, - {"0", "%.0d", ""}, - {"0", "%3.d", ""}, -} - -func TestFormat(t *testing.T) { - for i, test := range formatTests { - var x *Int - if test.input != "<nil>" { - var ok bool - x, ok = new(Int).SetString(test.input, 0) - if !ok { - t.Errorf("#%d failed reading input %s", i, test.input) - } - } - output := fmt.Sprintf(test.format, x) - if output != test.output { - t.Errorf("#%d got %q; want %q, {%q, %q, %q}", i, output, test.output, test.input, test.format, test.output) - } - } -} - -var scanTests = []struct { - input string - format string - output string - remaining int -}{ - {"1010", "%b", "10", 0}, - {"0b1010", "%v", "10", 0}, - {"12", "%o", "10", 0}, - {"012", "%v", "10", 0}, - {"10", "%d", "10", 0}, - {"10", "%v", "10", 0}, - {"a", "%x", "10", 0}, - {"0xa", "%v", "10", 0}, - {"A", "%X", "10", 0}, - {"-A", "%X", "-10", 0}, - {"+0b1011001", "%v", "89", 0}, - {"0xA", "%v", "10", 0}, - {"0 ", "%v", "0", 1}, - {"2+3", "%v", "2", 2}, - {"0XABC 12", "%v", "2748", 3}, -} - -func TestScan(t *testing.T) { - var buf bytes.Buffer - for i, test := range scanTests { - x := new(Int) - buf.Reset() - buf.WriteString(test.input) - if _, err := fmt.Fscanf(&buf, test.format, x); err != nil { - t.Errorf("#%d error: %s", i, err) - } - if x.String() != test.output { - t.Errorf("#%d got %s; want %s", i, x.String(), test.output) - } - if buf.Len() != test.remaining { - t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining) - } - } -} - -// Examples from the Go Language Spec, section "Arithmetic operators" -var divisionSignsTests = []struct { - x, y int64 - q, r int64 // T-division - d, m int64 // Euclidian division -}{ - {5, 3, 1, 2, 1, 2}, - {-5, 3, -1, -2, -2, 1}, - {5, -3, -1, 2, -1, 2}, - {-5, -3, 1, -2, 2, 1}, - {1, 2, 0, 1, 0, 1}, - {8, 4, 2, 0, 2, 0}, -} - -func TestDivisionSigns(t *testing.T) { - for i, test := range divisionSignsTests { - x := NewInt(test.x) - y := NewInt(test.y) - q := NewInt(test.q) - r := NewInt(test.r) - d := NewInt(test.d) - m := NewInt(test.m) - - q1 := new(Int).Quo(x, y) - r1 := new(Int).Rem(x, y) - if !isNormalized(q1) { - t.Errorf("#%d Quo: %v is not normalized", i, *q1) - } - if !isNormalized(r1) { - t.Errorf("#%d Rem: %v is not normalized", i, *r1) - } - if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 { - t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r) - } - - q2, r2 := new(Int).QuoRem(x, y, new(Int)) - if !isNormalized(q2) { - t.Errorf("#%d Quo: %v is not normalized", i, *q2) - } - if !isNormalized(r2) { - t.Errorf("#%d Rem: %v is not normalized", i, *r2) - } - if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 { - t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r) - } - - d1 := new(Int).Div(x, y) - m1 := new(Int).Mod(x, y) - if !isNormalized(d1) { - t.Errorf("#%d Div: %v is not normalized", i, *d1) - } - if !isNormalized(m1) { - t.Errorf("#%d Mod: %v is not normalized", i, *m1) - } - if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 { - t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m) - } - - d2, m2 := new(Int).DivMod(x, y, new(Int)) - if !isNormalized(d2) { - t.Errorf("#%d Div: %v is not normalized", i, *d2) - } - if !isNormalized(m2) { - t.Errorf("#%d Mod: %v is not normalized", i, *m2) - } - if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 { - t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m) - } - } -} - -func checkSetBytes(b []byte) bool { - hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes()) - hex2 := hex.EncodeToString(b) - - for len(hex1) < len(hex2) { - hex1 = "0" + hex1 - } - - for len(hex1) > len(hex2) { - hex2 = "0" + hex2 - } - - return hex1 == hex2 -} - -func TestSetBytes(t *testing.T) { - if err := quick.Check(checkSetBytes, nil); err != nil { - t.Error(err) - } -} - -func checkBytes(b []byte) bool { - b2 := new(Int).SetBytes(b).Bytes() - return bytes.Equal(b, b2) -} - -func TestBytes(t *testing.T) { - if err := quick.Check(checkSetBytes, nil); err != nil { - t.Error(err) - } -} - -func checkQuo(x, y []byte) bool { - u := new(Int).SetBytes(x) - v := new(Int).SetBytes(y) - - if len(v.abs) == 0 { - return true - } - - r := new(Int) - q, r := new(Int).QuoRem(u, v, r) - - if r.Cmp(v) >= 0 { - return false - } - - uprime := new(Int).Set(q) - uprime.Mul(uprime, v) - uprime.Add(uprime, r) - - return uprime.Cmp(u) == 0 -} - -var quoTests = []struct { - x, y string - q, r string -}{ - { - "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357", - "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996", - "50911", - "1", - }, - { - "11510768301994997771168", - "1328165573307167369775", - "8", - "885443715537658812968", - }, -} - -func TestQuo(t *testing.T) { - if err := quick.Check(checkQuo, nil); err != nil { - t.Error(err) - } - - for i, test := range quoTests { - x, _ := new(Int).SetString(test.x, 10) - y, _ := new(Int).SetString(test.y, 10) - expectedQ, _ := new(Int).SetString(test.q, 10) - expectedR, _ := new(Int).SetString(test.r, 10) - - r := new(Int) - q, r := new(Int).QuoRem(x, y, r) - - if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 { - t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR) - } - } -} - -func TestQuoStepD6(t *testing.T) { - // See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises - // a code path which only triggers 1 in 10^{-19} cases. - - u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}} - v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}} - - r := new(Int) - q, r := new(Int).QuoRem(u, v, r) - const expectedQ64 = "18446744073709551613" - const expectedR64 = "3138550867693340382088035895064302439801311770021610913807" - const expectedQ32 = "4294967293" - const expectedR32 = "39614081266355540837921718287" - if q.String() != expectedQ64 && q.String() != expectedQ32 || - r.String() != expectedR64 && r.String() != expectedR32 { - t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32) - } -} - -var bitLenTests = []struct { - in string - out int -}{ - {"-1", 1}, - {"0", 0}, - {"1", 1}, - {"2", 2}, - {"4", 3}, - {"0xabc", 12}, - {"0x8000", 16}, - {"0x80000000", 32}, - {"0x800000000000", 48}, - {"0x8000000000000000", 64}, - {"0x80000000000000000000", 80}, - {"-0x4000000000000000000000", 87}, -} - -func TestBitLen(t *testing.T) { - for i, test := range bitLenTests { - x, ok := new(Int).SetString(test.in, 0) - if !ok { - t.Errorf("#%d test input invalid: %s", i, test.in) - continue - } - - if n := x.BitLen(); n != test.out { - t.Errorf("#%d got %d want %d", i, n, test.out) - } - } -} - -var expTests = []struct { - x, y, m string - out string -}{ - // y <= 0 - {"0", "0", "", "1"}, - {"1", "0", "", "1"}, - {"-10", "0", "", "1"}, - {"1234", "-1", "", "1"}, - - // m == 1 - {"0", "0", "1", "0"}, - {"1", "0", "1", "0"}, - {"-10", "0", "1", "0"}, - {"1234", "-1", "1", "0"}, - - // misc - {"5", "-7", "", "1"}, - {"-5", "-7", "", "1"}, - {"5", "0", "", "1"}, - {"-5", "0", "", "1"}, - {"5", "1", "", "5"}, - {"-5", "1", "", "-5"}, - {"-2", "3", "2", "0"}, - {"5", "2", "", "25"}, - {"1", "65537", "2", "1"}, - {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"}, - {"0x8000000000000000", "2", "6719", "4944"}, - {"0x8000000000000000", "3", "6719", "5447"}, - {"0x8000000000000000", "1000", "6719", "1603"}, - {"0x8000000000000000", "1000000", "6719", "3199"}, - {"0x8000000000000000", "-1000000", "6719", "1"}, - { - "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347", - "298472983472983471903246121093472394872319615612417471234712061", - "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464", - "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291", - }, -} - -func TestExp(t *testing.T) { - for i, test := range expTests { - x, ok1 := new(Int).SetString(test.x, 0) - y, ok2 := new(Int).SetString(test.y, 0) - out, ok3 := new(Int).SetString(test.out, 0) - - var ok4 bool - var m *Int - - if len(test.m) == 0 { - m, ok4 = nil, true - } else { - m, ok4 = new(Int).SetString(test.m, 0) - } - - if !ok1 || !ok2 || !ok3 || !ok4 { - t.Errorf("#%d: error in input", i) - continue - } - - z1 := new(Int).Exp(x, y, m) - if !isNormalized(z1) { - t.Errorf("#%d: %v is not normalized", i, *z1) - } - if z1.Cmp(out) != 0 { - t.Errorf("#%d: got %s want %s", i, z1, out) - } - - if m == nil { - // the result should be the same as for m == 0; - // specifically, there should be no div-zero panic - m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0 - z2 := new(Int).Exp(x, y, m) - if z2.Cmp(z1) != 0 { - t.Errorf("#%d: got %s want %s", i, z1, z2) - } - } - } -} - -func checkGcd(aBytes, bBytes []byte) bool { - x := new(Int) - y := new(Int) - a := new(Int).SetBytes(aBytes) - b := new(Int).SetBytes(bBytes) - - d := new(Int).GCD(x, y, a, b) - x.Mul(x, a) - y.Mul(y, b) - x.Add(x, y) - - return x.Cmp(d) == 0 -} - -var gcdTests = []struct { - d, x, y, a, b string -}{ - // a <= 0 || b <= 0 - {"0", "0", "0", "0", "0"}, - {"0", "0", "0", "0", "7"}, - {"0", "0", "0", "11", "0"}, - {"0", "0", "0", "-77", "35"}, - {"0", "0", "0", "64515", "-24310"}, - {"0", "0", "0", "-64515", "-24310"}, - - {"1", "-9", "47", "120", "23"}, - {"7", "1", "-2", "77", "35"}, - {"935", "-3", "8", "64515", "24310"}, - {"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"}, - {"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"}, - - // test early exit (after one Euclidean iteration) in binaryGCD - {"1", "", "", "1", "98920366548084643601728869055592650835572950932266967461790948584315647051443"}, -} - -func testGcd(t *testing.T, d, x, y, a, b *Int) { - var X *Int - if x != nil { - X = new(Int) - } - var Y *Int - if y != nil { - Y = new(Int) - } - - D := new(Int).GCD(X, Y, a, b) - if D.Cmp(d) != 0 { - t.Errorf("GCD(%s, %s): got d = %s, want %s", a, b, D, d) - } - if x != nil && X.Cmp(x) != 0 { - t.Errorf("GCD(%s, %s): got x = %s, want %s", a, b, X, x) - } - if y != nil && Y.Cmp(y) != 0 { - t.Errorf("GCD(%s, %s): got y = %s, want %s", a, b, Y, y) - } - - // binaryGCD requires a > 0 && b > 0 - if a.Sign() <= 0 || b.Sign() <= 0 { - return - } - - D.binaryGCD(a, b) - if D.Cmp(d) != 0 { - t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, D, d) - } -} - -func TestGcd(t *testing.T) { - for _, test := range gcdTests { - d, _ := new(Int).SetString(test.d, 0) - x, _ := new(Int).SetString(test.x, 0) - y, _ := new(Int).SetString(test.y, 0) - a, _ := new(Int).SetString(test.a, 0) - b, _ := new(Int).SetString(test.b, 0) - - testGcd(t, d, nil, nil, a, b) - testGcd(t, d, x, nil, a, b) - testGcd(t, d, nil, y, a, b) - testGcd(t, d, x, y, a, b) - } - - quick.Check(checkGcd, nil) -} - -var primes = []string{ - "2", - "3", - "5", - "7", - "11", - - "13756265695458089029", - "13496181268022124907", - "10953742525620032441", - "17908251027575790097", - - // http://code.google.com/p/go/issues/detail?id=638 - "18699199384836356663", - - "98920366548084643601728869055592650835572950932266967461790948584315647051443", - "94560208308847015747498523884063394671606671904944666360068158221458669711639", - - // http://primes.utm.edu/lists/small/small3.html - "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163", - "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593", - "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993", - "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", -} - -var composites = []string{ - "21284175091214687912771199898307297748211672914763848041968395774954376176754", - "6084766654921918907427900243509372380954290099172559290432744450051395395951", - "84594350493221918389213352992032324280367711247940675652888030554255915464401", - "82793403787388584738507275144194252681", -} - -func TestProbablyPrime(t *testing.T) { - nreps := 20 - if testing.Short() { - nreps = 1 - } - for i, s := range primes { - p, _ := new(Int).SetString(s, 10) - if !p.ProbablyPrime(nreps) { - t.Errorf("#%d prime found to be non-prime (%s)", i, s) - } - } - - for i, s := range composites { - c, _ := new(Int).SetString(s, 10) - if c.ProbablyPrime(nreps) { - t.Errorf("#%d composite found to be prime (%s)", i, s) - } - if testing.Short() { - break - } - } -} - -type intShiftTest struct { - in string - shift uint - out string -} - -var rshTests = []intShiftTest{ - {"0", 0, "0"}, - {"-0", 0, "0"}, - {"0", 1, "0"}, - {"0", 2, "0"}, - {"1", 0, "1"}, - {"1", 1, "0"}, - {"1", 2, "0"}, - {"2", 0, "2"}, - {"2", 1, "1"}, - {"-1", 0, "-1"}, - {"-1", 1, "-1"}, - {"-1", 10, "-1"}, - {"-100", 2, "-25"}, - {"-100", 3, "-13"}, - {"-100", 100, "-1"}, - {"4294967296", 0, "4294967296"}, - {"4294967296", 1, "2147483648"}, - {"4294967296", 2, "1073741824"}, - {"18446744073709551616", 0, "18446744073709551616"}, - {"18446744073709551616", 1, "9223372036854775808"}, - {"18446744073709551616", 2, "4611686018427387904"}, - {"18446744073709551616", 64, "1"}, - {"340282366920938463463374607431768211456", 64, "18446744073709551616"}, - {"340282366920938463463374607431768211456", 128, "1"}, -} - -func TestRsh(t *testing.T) { - for i, test := range rshTests { - in, _ := new(Int).SetString(test.in, 10) - expected, _ := new(Int).SetString(test.out, 10) - out := new(Int).Rsh(in, test.shift) - - if !isNormalized(out) { - t.Errorf("#%d: %v is not normalized", i, *out) - } - if out.Cmp(expected) != 0 { - t.Errorf("#%d: got %s want %s", i, out, expected) - } - } -} - -func TestRshSelf(t *testing.T) { - for i, test := range rshTests { - z, _ := new(Int).SetString(test.in, 10) - expected, _ := new(Int).SetString(test.out, 10) - z.Rsh(z, test.shift) - - if !isNormalized(z) { - t.Errorf("#%d: %v is not normalized", i, *z) - } - if z.Cmp(expected) != 0 { - t.Errorf("#%d: got %s want %s", i, z, expected) - } - } -} - -var lshTests = []intShiftTest{ - {"0", 0, "0"}, - {"0", 1, "0"}, - {"0", 2, "0"}, - {"1", 0, "1"}, - {"1", 1, "2"}, - {"1", 2, "4"}, - {"2", 0, "2"}, - {"2", 1, "4"}, - {"2", 2, "8"}, - {"-87", 1, "-174"}, - {"4294967296", 0, "4294967296"}, - {"4294967296", 1, "8589934592"}, - {"4294967296", 2, "17179869184"}, - {"18446744073709551616", 0, "18446744073709551616"}, - {"9223372036854775808", 1, "18446744073709551616"}, - {"4611686018427387904", 2, "18446744073709551616"}, - {"1", 64, "18446744073709551616"}, - {"18446744073709551616", 64, "340282366920938463463374607431768211456"}, - {"1", 128, "340282366920938463463374607431768211456"}, -} - -func TestLsh(t *testing.T) { - for i, test := range lshTests { - in, _ := new(Int).SetString(test.in, 10) - expected, _ := new(Int).SetString(test.out, 10) - out := new(Int).Lsh(in, test.shift) - - if !isNormalized(out) { - t.Errorf("#%d: %v is not normalized", i, *out) - } - if out.Cmp(expected) != 0 { - t.Errorf("#%d: got %s want %s", i, out, expected) - } - } -} - -func TestLshSelf(t *testing.T) { - for i, test := range lshTests { - z, _ := new(Int).SetString(test.in, 10) - expected, _ := new(Int).SetString(test.out, 10) - z.Lsh(z, test.shift) - - if !isNormalized(z) { - t.Errorf("#%d: %v is not normalized", i, *z) - } - if z.Cmp(expected) != 0 { - t.Errorf("#%d: got %s want %s", i, z, expected) - } - } -} - -func TestLshRsh(t *testing.T) { - for i, test := range rshTests { - in, _ := new(Int).SetString(test.in, 10) - out := new(Int).Lsh(in, test.shift) - out = out.Rsh(out, test.shift) - - if !isNormalized(out) { - t.Errorf("#%d: %v is not normalized", i, *out) - } - if in.Cmp(out) != 0 { - t.Errorf("#%d: got %s want %s", i, out, in) - } - } - for i, test := range lshTests { - in, _ := new(Int).SetString(test.in, 10) - out := new(Int).Lsh(in, test.shift) - out.Rsh(out, test.shift) - - if !isNormalized(out) { - t.Errorf("#%d: %v is not normalized", i, *out) - } - if in.Cmp(out) != 0 { - t.Errorf("#%d: got %s want %s", i, out, in) - } - } -} - -var int64Tests = []int64{ - 0, - 1, - -1, - 4294967295, - -4294967295, - 4294967296, - -4294967296, - 9223372036854775807, - -9223372036854775807, - -9223372036854775808, -} - -func TestInt64(t *testing.T) { - for i, testVal := range int64Tests { - in := NewInt(testVal) - out := in.Int64() - - if out != testVal { - t.Errorf("#%d got %d want %d", i, out, testVal) - } - } -} - -var uint64Tests = []uint64{ - 0, - 1, - 4294967295, - 4294967296, - 8589934591, - 8589934592, - 9223372036854775807, - 9223372036854775808, - 18446744073709551615, // 1<<64 - 1 -} - -func TestUint64(t *testing.T) { - in := new(Int) - for i, testVal := range uint64Tests { - in.SetUint64(testVal) - out := in.Uint64() - - if out != testVal { - t.Errorf("#%d got %d want %d", i, out, testVal) - } - - str := fmt.Sprint(testVal) - strOut := in.String() - if strOut != str { - t.Errorf("#%d.String got %s want %s", i, strOut, str) - } - } -} - -var bitwiseTests = []struct { - x, y string - and, or, xor, andNot string -}{ - {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"}, - {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"}, - {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"}, - {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"}, - {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"}, - {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"}, - {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"}, - {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"}, - {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"}, - {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"}, - {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"}, - {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"}, - {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"}, - { - "0x1000009dc6e3d9822cba04129bcbe3401", - "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd", - "0x1000001186210100001000009048c2001", - "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd", - "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc", - "0x8c40c2d8822caa04120b8321400", - }, - { - "0x1000009dc6e3d9822cba04129bcbe3401", - "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd", - "0x8c40c2d8822caa04120b8321401", - "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd", - "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe", - "0x1000001186210100001000009048c2000", - }, - { - "-0x1000009dc6e3d9822cba04129bcbe3401", - "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd", - "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd", - "-0x1000001186210100001000009048c2001", - "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc", - "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc", - }, -} - -type bitFun func(z, x, y *Int) *Int - -func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) { - expected := new(Int) - expected.SetString(exp, 0) - - out := f(new(Int), x, y) - if out.Cmp(expected) != 0 { - t.Errorf("%s: got %s want %s", msg, out, expected) - } -} - -func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) { - self := new(Int) - self.Set(x) - expected := new(Int) - expected.SetString(exp, 0) - - self = f(self, self, y) - if self.Cmp(expected) != 0 { - t.Errorf("%s: got %s want %s", msg, self, expected) - } -} - -func altBit(x *Int, i int) uint { - z := new(Int).Rsh(x, uint(i)) - z = z.And(z, NewInt(1)) - if z.Cmp(new(Int)) != 0 { - return 1 - } - return 0 -} - -func altSetBit(z *Int, x *Int, i int, b uint) *Int { - one := NewInt(1) - m := one.Lsh(one, uint(i)) - switch b { - case 1: - return z.Or(x, m) - case 0: - return z.AndNot(x, m) - } - panic("set bit is not 0 or 1") -} - -func testBitset(t *testing.T, x *Int) { - n := x.BitLen() - z := new(Int).Set(x) - z1 := new(Int).Set(x) - for i := 0; i < n+10; i++ { - old := z.Bit(i) - old1 := altBit(z1, i) - if old != old1 { - t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1) - } - z := new(Int).SetBit(z, i, 1) - z1 := altSetBit(new(Int), z1, i, 1) - if z.Bit(i) == 0 { - t.Errorf("bitset: bit %d of %s got 0 want 1", i, x) - } - if z.Cmp(z1) != 0 { - t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1) - } - z.SetBit(z, i, 0) - altSetBit(z1, z1, i, 0) - if z.Bit(i) != 0 { - t.Errorf("bitset: bit %d of %s got 1 want 0", i, x) - } - if z.Cmp(z1) != 0 { - t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1) - } - altSetBit(z1, z1, i, old) - z.SetBit(z, i, old) - if z.Cmp(z1) != 0 { - t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1) - } - } - if z.Cmp(x) != 0 { - t.Errorf("bitset: got %s want %s", z, x) - } -} - -var bitsetTests = []struct { - x string - i int - b uint -}{ - {"0", 0, 0}, - {"0", 200, 0}, - {"1", 0, 1}, - {"1", 1, 0}, - {"-1", 0, 1}, - {"-1", 200, 1}, - {"0x2000000000000000000000000000", 108, 0}, - {"0x2000000000000000000000000000", 109, 1}, - {"0x2000000000000000000000000000", 110, 0}, - {"-0x2000000000000000000000000001", 108, 1}, - {"-0x2000000000000000000000000001", 109, 0}, - {"-0x2000000000000000000000000001", 110, 1}, -} - -func TestBitSet(t *testing.T) { - for _, test := range bitwiseTests { - x := new(Int) - x.SetString(test.x, 0) - testBitset(t, x) - x = new(Int) - x.SetString(test.y, 0) - testBitset(t, x) - } - for i, test := range bitsetTests { - x := new(Int) - x.SetString(test.x, 0) - b := x.Bit(test.i) - if b != test.b { - t.Errorf("#%d got %v want %v", i, b, test.b) - } - } - z := NewInt(1) - z.SetBit(NewInt(0), 2, 1) - if z.Cmp(NewInt(4)) != 0 { - t.Errorf("destination leaked into result; got %s want 4", z) - } -} - -func BenchmarkBitset(b *testing.B) { - z := new(Int) - z.SetBit(z, 512, 1) - b.ResetTimer() - b.StartTimer() - for i := b.N - 1; i >= 0; i-- { - z.SetBit(z, i&512, 1) - } -} - -func BenchmarkBitsetNeg(b *testing.B) { - z := NewInt(-1) - z.SetBit(z, 512, 0) - b.ResetTimer() - b.StartTimer() - for i := b.N - 1; i >= 0; i-- { - z.SetBit(z, i&512, 0) - } -} - -func BenchmarkBitsetOrig(b *testing.B) { - z := new(Int) - altSetBit(z, z, 512, 1) - b.ResetTimer() - b.StartTimer() - for i := b.N - 1; i >= 0; i-- { - altSetBit(z, z, i&512, 1) - } -} - -func BenchmarkBitsetNegOrig(b *testing.B) { - z := NewInt(-1) - altSetBit(z, z, 512, 0) - b.ResetTimer() - b.StartTimer() - for i := b.N - 1; i >= 0; i-- { - altSetBit(z, z, i&512, 0) - } -} - -func TestBitwise(t *testing.T) { - x := new(Int) - y := new(Int) - for _, test := range bitwiseTests { - x.SetString(test.x, 0) - y.SetString(test.y, 0) - - testBitFun(t, "and", (*Int).And, x, y, test.and) - testBitFunSelf(t, "and", (*Int).And, x, y, test.and) - testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot) - testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot) - testBitFun(t, "or", (*Int).Or, x, y, test.or) - testBitFunSelf(t, "or", (*Int).Or, x, y, test.or) - testBitFun(t, "xor", (*Int).Xor, x, y, test.xor) - testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor) - } -} - -var notTests = []struct { - in string - out string -}{ - {"0", "-1"}, - {"1", "-2"}, - {"7", "-8"}, - {"0", "-1"}, - {"-81910", "81909"}, - { - "298472983472983471903246121093472394872319615612417471234712061", - "-298472983472983471903246121093472394872319615612417471234712062", - }, -} - -func TestNot(t *testing.T) { - in := new(Int) - out := new(Int) - expected := new(Int) - for i, test := range notTests { - in.SetString(test.in, 10) - expected.SetString(test.out, 10) - out = out.Not(in) - if out.Cmp(expected) != 0 { - t.Errorf("#%d: got %s want %s", i, out, expected) - } - out = out.Not(out) - if out.Cmp(in) != 0 { - t.Errorf("#%d: got %s want %s", i, out, in) - } - } -} - -var modInverseTests = []struct { - element string - prime string -}{ - {"1", "7"}, - {"1", "13"}, - {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"}, -} - -func TestModInverse(t *testing.T) { - var element, prime Int - one := NewInt(1) - for i, test := range modInverseTests { - (&element).SetString(test.element, 10) - (&prime).SetString(test.prime, 10) - inverse := new(Int).ModInverse(&element, &prime) - inverse.Mul(inverse, &element) - inverse.Mod(inverse, &prime) - if inverse.Cmp(one) != 0 { - t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse) - } - } -} - -var encodingTests = []string{ - "-539345864568634858364538753846587364875430589374589", - "-678645873", - "-100", - "-2", - "-1", - "0", - "1", - "2", - "10", - "42", - "1234567890", - "298472983472983471903246121093472394872319615612417471234712061", -} - -func TestIntGobEncoding(t *testing.T) { - var medium bytes.Buffer - enc := gob.NewEncoder(&medium) - dec := gob.NewDecoder(&medium) - for _, test := range encodingTests { - medium.Reset() // empty buffer for each test case (in case of failures) - var tx Int - tx.SetString(test, 10) - if err := enc.Encode(&tx); err != nil { - t.Errorf("encoding of %s failed: %s", &tx, err) - } - var rx Int - if err := dec.Decode(&rx); err != nil { - t.Errorf("decoding of %s failed: %s", &tx, err) - } - if rx.Cmp(&tx) != 0 { - t.Errorf("transmission of %s failed: got %s want %s", &tx, &rx, &tx) - } - } -} - -// Sending a nil Int pointer (inside a slice) on a round trip through gob should yield a zero. -// TODO: top-level nils. -func TestGobEncodingNilIntInSlice(t *testing.T) { - buf := new(bytes.Buffer) - enc := gob.NewEncoder(buf) - dec := gob.NewDecoder(buf) - - var in = make([]*Int, 1) - err := enc.Encode(&in) - if err != nil { - t.Errorf("gob encode failed: %q", err) - } - var out []*Int - err = dec.Decode(&out) - if err != nil { - t.Fatalf("gob decode failed: %q", err) - } - if len(out) != 1 { - t.Fatalf("wrong len; want 1 got %d", len(out)) - } - var zero Int - if out[0].Cmp(&zero) != 0 { - t.Errorf("transmission of (*Int)(nill) failed: got %s want 0", out) - } -} - -func TestIntJSONEncoding(t *testing.T) { - for _, test := range encodingTests { - var tx Int - tx.SetString(test, 10) - b, err := json.Marshal(&tx) - if err != nil { - t.Errorf("marshaling of %s failed: %s", &tx, err) - } - var rx Int - if err := json.Unmarshal(b, &rx); err != nil { - t.Errorf("unmarshaling of %s failed: %s", &tx, err) - } - if rx.Cmp(&tx) != 0 { - t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx) - } - } -} - -var intVals = []string{ - "-141592653589793238462643383279502884197169399375105820974944592307816406286", - "-1415926535897932384626433832795028841971", - "-141592653589793", - "-1", - "0", - "1", - "141592653589793", - "1415926535897932384626433832795028841971", - "141592653589793238462643383279502884197169399375105820974944592307816406286", -} - -func TestIntJSONEncodingTextMarshaller(t *testing.T) { - for _, num := range intVals { - var tx Int - tx.SetString(num, 0) - b, err := json.Marshal(&tx) - if err != nil { - t.Errorf("marshaling of %s failed: %s", &tx, err) - continue - } - var rx Int - if err := json.Unmarshal(b, &rx); err != nil { - t.Errorf("unmarshaling of %s failed: %s", &tx, err) - continue - } - if rx.Cmp(&tx) != 0 { - t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx) - } - } -} - -func TestIntXMLEncodingTextMarshaller(t *testing.T) { - for _, num := range intVals { - var tx Int - tx.SetString(num, 0) - b, err := xml.Marshal(&tx) - if err != nil { - t.Errorf("marshaling of %s failed: %s", &tx, err) - continue - } - var rx Int - if err := xml.Unmarshal(b, &rx); err != nil { - t.Errorf("unmarshaling of %s failed: %s", &tx, err) - continue - } - if rx.Cmp(&tx) != 0 { - t.Errorf("XML encoding of %s failed: got %s want %s", &tx, &rx, &tx) - } - } -} - -func TestIssue2607(t *testing.T) { - // This code sequence used to hang. - n := NewInt(10) - n.Rand(rand.New(rand.NewSource(9)), n) -} diff --git a/src/pkg/math/big/nat.go b/src/pkg/math/big/nat.go deleted file mode 100644 index 16a87f5c5..000000000 --- a/src/pkg/math/big/nat.go +++ /dev/null @@ -1,1508 +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. - -// Package big implements multi-precision arithmetic (big numbers). -// The following numeric types are supported: -// -// - Int signed integers -// - Rat rational numbers -// -// Methods are typically of the form: -// -// func (z *Int) Op(x, y *Int) *Int (similar for *Rat) -// -// and implement operations z = x Op y with the result as receiver; if it -// is one of the operands it may be overwritten (and its memory reused). -// To enable chaining of operations, the result is also returned. Methods -// returning a result other than *Int or *Rat take one of the operands as -// the receiver. -// -package big - -// This file contains operations on unsigned multi-precision integers. -// These are the building blocks for the operations on signed integers -// and rationals. - -import ( - "errors" - "io" - "math" - "math/rand" - "sync" -) - -// An unsigned integer x of the form -// -// x = x[n-1]*_B^(n-1) + x[n-2]*_B^(n-2) + ... + x[1]*_B + x[0] -// -// with 0 <= x[i] < _B and 0 <= i < n is stored in a slice of length n, -// with the digits x[i] as the slice elements. -// -// A number is normalized if the slice contains no leading 0 digits. -// During arithmetic operations, denormalized values may occur but are -// always normalized before returning the final result. The normalized -// representation of 0 is the empty or nil slice (length = 0). -// -type nat []Word - -var ( - natOne = nat{1} - natTwo = nat{2} - natTen = nat{10} -) - -func (z nat) clear() { - for i := range z { - z[i] = 0 - } -} - -func (z nat) norm() nat { - i := len(z) - for i > 0 && z[i-1] == 0 { - i-- - } - return z[0:i] -} - -func (z nat) make(n int) nat { - if n <= cap(z) { - return z[0:n] // reuse z - } - // Choosing a good value for e has significant performance impact - // because it increases the chance that a value can be reused. - const e = 4 // extra capacity - return make(nat, n, n+e) -} - -func (z nat) setWord(x Word) nat { - if x == 0 { - return z.make(0) - } - z = z.make(1) - z[0] = x - return z -} - -func (z nat) setUint64(x uint64) nat { - // single-digit values - if w := Word(x); uint64(w) == x { - return z.setWord(w) - } - - // compute number of words n required to represent x - n := 0 - for t := x; t > 0; t >>= _W { - n++ - } - - // split x into n words - z = z.make(n) - for i := range z { - z[i] = Word(x & _M) - x >>= _W - } - - return z -} - -func (z nat) set(x nat) nat { - z = z.make(len(x)) - copy(z, x) - return z -} - -func (z nat) add(x, y nat) nat { - m := len(x) - n := len(y) - - switch { - case m < n: - return z.add(y, x) - case m == 0: - // n == 0 because m >= n; result is 0 - return z.make(0) - case n == 0: - // result is x - return z.set(x) - } - // m > 0 - - z = z.make(m + 1) - c := addVV(z[0:n], x, y) - if m > n { - c = addVW(z[n:m], x[n:], c) - } - z[m] = c - - return z.norm() -} - -func (z nat) sub(x, y nat) nat { - m := len(x) - n := len(y) - - switch { - case m < n: - panic("underflow") - case m == 0: - // n == 0 because m >= n; result is 0 - return z.make(0) - case n == 0: - // result is x - return z.set(x) - } - // m > 0 - - z = z.make(m) - c := subVV(z[0:n], x, y) - if m > n { - c = subVW(z[n:], x[n:], c) - } - if c != 0 { - panic("underflow") - } - - return z.norm() -} - -func (x nat) cmp(y nat) (r int) { - m := len(x) - n := len(y) - if m != n || m == 0 { - switch { - case m < n: - r = -1 - case m > n: - r = 1 - } - return - } - - i := m - 1 - for i > 0 && x[i] == y[i] { - i-- - } - - switch { - case x[i] < y[i]: - r = -1 - case x[i] > y[i]: - r = 1 - } - return -} - -func (z nat) mulAddWW(x nat, y, r Word) nat { - m := len(x) - if m == 0 || y == 0 { - return z.setWord(r) // result is r - } - // m > 0 - - z = z.make(m + 1) - z[m] = mulAddVWW(z[0:m], x, y, r) - - return z.norm() -} - -// basicMul multiplies x and y and leaves the result in z. -// The (non-normalized) result is placed in z[0 : len(x) + len(y)]. -func basicMul(z, x, y nat) { - z[0 : len(x)+len(y)].clear() // initialize z - for i, d := range y { - if d != 0 { - z[len(x)+i] = addMulVVW(z[i:i+len(x)], x, d) - } - } -} - -// Fast version of z[0:n+n>>1].add(z[0:n+n>>1], x[0:n]) w/o bounds checks. -// Factored out for readability - do not use outside karatsuba. -func karatsubaAdd(z, x nat, n int) { - if c := addVV(z[0:n], z, x); c != 0 { - addVW(z[n:n+n>>1], z[n:], c) - } -} - -// Like karatsubaAdd, but does subtract. -func karatsubaSub(z, x nat, n int) { - if c := subVV(z[0:n], z, x); c != 0 { - subVW(z[n:n+n>>1], z[n:], c) - } -} - -// Operands that are shorter than karatsubaThreshold are multiplied using -// "grade school" multiplication; for longer operands the Karatsuba algorithm -// is used. -var karatsubaThreshold int = 40 // computed by calibrate.go - -// karatsuba multiplies x and y and leaves the result in z. -// Both x and y must have the same length n and n must be a -// power of 2. The result vector z must have len(z) >= 6*n. -// The (non-normalized) result is placed in z[0 : 2*n]. -func karatsuba(z, x, y nat) { - n := len(y) - - // Switch to basic multiplication if numbers are odd or small. - // (n is always even if karatsubaThreshold is even, but be - // conservative) - if n&1 != 0 || n < karatsubaThreshold || n < 2 { - basicMul(z, x, y) - return - } - // n&1 == 0 && n >= karatsubaThreshold && n >= 2 - - // Karatsuba multiplication is based on the observation that - // for two numbers x and y with: - // - // x = x1*b + x0 - // y = y1*b + y0 - // - // the product x*y can be obtained with 3 products z2, z1, z0 - // instead of 4: - // - // x*y = x1*y1*b*b + (x1*y0 + x0*y1)*b + x0*y0 - // = z2*b*b + z1*b + z0 - // - // with: - // - // xd = x1 - x0 - // yd = y0 - y1 - // - // z1 = xd*yd + z2 + z0 - // = (x1-x0)*(y0 - y1) + z2 + z0 - // = x1*y0 - x1*y1 - x0*y0 + x0*y1 + z2 + z0 - // = x1*y0 - z2 - z0 + x0*y1 + z2 + z0 - // = x1*y0 + x0*y1 - - // split x, y into "digits" - n2 := n >> 1 // n2 >= 1 - x1, x0 := x[n2:], x[0:n2] // x = x1*b + y0 - y1, y0 := y[n2:], y[0:n2] // y = y1*b + y0 - - // z is used for the result and temporary storage: - // - // 6*n 5*n 4*n 3*n 2*n 1*n 0*n - // z = [z2 copy|z0 copy| xd*yd | yd:xd | x1*y1 | x0*y0 ] - // - // For each recursive call of karatsuba, an unused slice of - // z is passed in that has (at least) half the length of the - // caller's z. - - // compute z0 and z2 with the result "in place" in z - karatsuba(z, x0, y0) // z0 = x0*y0 - karatsuba(z[n:], x1, y1) // z2 = x1*y1 - - // compute xd (or the negative value if underflow occurs) - s := 1 // sign of product xd*yd - xd := z[2*n : 2*n+n2] - if subVV(xd, x1, x0) != 0 { // x1-x0 - s = -s - subVV(xd, x0, x1) // x0-x1 - } - - // compute yd (or the negative value if underflow occurs) - yd := z[2*n+n2 : 3*n] - if subVV(yd, y0, y1) != 0 { // y0-y1 - s = -s - subVV(yd, y1, y0) // y1-y0 - } - - // p = (x1-x0)*(y0-y1) == x1*y0 - x1*y1 - x0*y0 + x0*y1 for s > 0 - // p = (x0-x1)*(y0-y1) == x0*y0 - x0*y1 - x1*y0 + x1*y1 for s < 0 - p := z[n*3:] - karatsuba(p, xd, yd) - - // save original z2:z0 - // (ok to use upper half of z since we're done recursing) - r := z[n*4:] - copy(r, z[:n*2]) - - // add up all partial products - // - // 2*n n 0 - // z = [ z2 | z0 ] - // + [ z0 ] - // + [ z2 ] - // + [ p ] - // - karatsubaAdd(z[n2:], r, n) - karatsubaAdd(z[n2:], r[n:], n) - if s > 0 { - karatsubaAdd(z[n2:], p, n) - } else { - karatsubaSub(z[n2:], p, n) - } -} - -// alias returns true if x and y share the same base array. -func alias(x, y nat) bool { - return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1] -} - -// addAt implements z += x<<(_W*i); z must be long enough. -// (we don't use nat.add because we need z to stay the same -// slice, and we don't need to normalize z after each addition) -func addAt(z, x nat, i int) { - if n := len(x); n > 0 { - if c := addVV(z[i:i+n], z[i:], x); c != 0 { - j := i + n - if j < len(z) { - addVW(z[j:], z[j:], c) - } - } - } -} - -func max(x, y int) int { - if x > y { - return x - } - return y -} - -// karatsubaLen computes an approximation to the maximum k <= n such that -// k = p<<i for a number p <= karatsubaThreshold and an i >= 0. Thus, the -// result is the largest number that can be divided repeatedly by 2 before -// becoming about the value of karatsubaThreshold. -func karatsubaLen(n int) int { - i := uint(0) - for n > karatsubaThreshold { - n >>= 1 - i++ - } - return n << i -} - -func (z nat) mul(x, y nat) nat { - m := len(x) - n := len(y) - - switch { - case m < n: - return z.mul(y, x) - case m == 0 || n == 0: - return z.make(0) - case n == 1: - return z.mulAddWW(x, y[0], 0) - } - // m >= n > 1 - - // determine if z can be reused - if alias(z, x) || alias(z, y) { - z = nil // z is an alias for x or y - cannot reuse - } - - // use basic multiplication if the numbers are small - if n < karatsubaThreshold { - z = z.make(m + n) - basicMul(z, x, y) - return z.norm() - } - // m >= n && n >= karatsubaThreshold && n >= 2 - - // determine Karatsuba length k such that - // - // x = xh*b + x0 (0 <= x0 < b) - // y = yh*b + y0 (0 <= y0 < b) - // b = 1<<(_W*k) ("base" of digits xi, yi) - // - k := karatsubaLen(n) - // k <= n - - // multiply x0 and y0 via Karatsuba - x0 := x[0:k] // x0 is not normalized - y0 := y[0:k] // y0 is not normalized - z = z.make(max(6*k, m+n)) // enough space for karatsuba of x0*y0 and full result of x*y - karatsuba(z, x0, y0) - z = z[0 : m+n] // z has final length but may be incomplete - z[2*k:].clear() // upper portion of z is garbage (and 2*k <= m+n since k <= n <= m) - - // If xh != 0 or yh != 0, add the missing terms to z. For - // - // xh = xi*b^i + ... + x2*b^2 + x1*b (0 <= xi < b) - // yh = y1*b (0 <= y1 < b) - // - // the missing terms are - // - // x0*y1*b and xi*y0*b^i, xi*y1*b^(i+1) for i > 0 - // - // since all the yi for i > 1 are 0 by choice of k: If any of them - // were > 0, then yh >= b^2 and thus y >= b^2. Then k' = k*2 would - // be a larger valid threshold contradicting the assumption about k. - // - if k < n || m != n { - var t nat - - // add x0*y1*b - x0 := x0.norm() - y1 := y[k:] // y1 is normalized because y is - t = t.mul(x0, y1) // update t so we don't lose t's underlying array - addAt(z, t, k) - - // add xi*y0<<i, xi*y1*b<<(i+k) - y0 := y0.norm() - for i := k; i < len(x); i += k { - xi := x[i:] - if len(xi) > k { - xi = xi[:k] - } - xi = xi.norm() - t = t.mul(xi, y0) - addAt(z, t, i) - t = t.mul(xi, y1) - addAt(z, t, i+k) - } - } - - return z.norm() -} - -// mulRange computes the product of all the unsigned integers in the -// range [a, b] inclusively. If a > b (empty range), the result is 1. -func (z nat) mulRange(a, b uint64) nat { - switch { - case a == 0: - // cut long ranges short (optimization) - return z.setUint64(0) - case a > b: - return z.setUint64(1) - case a == b: - return z.setUint64(a) - case a+1 == b: - return z.mul(nat(nil).setUint64(a), nat(nil).setUint64(b)) - } - m := (a + b) / 2 - return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b)) -} - -// q = (x-r)/y, with 0 <= r < y -func (z nat) divW(x nat, y Word) (q nat, r Word) { - m := len(x) - switch { - case y == 0: - panic("division by zero") - case y == 1: - q = z.set(x) // result is x - return - case m == 0: - q = z.make(0) // result is 0 - return - } - // m > 0 - z = z.make(m) - r = divWVW(z, 0, x, y) - q = z.norm() - return -} - -func (z nat) div(z2, u, v nat) (q, r nat) { - if len(v) == 0 { - panic("division by zero") - } - - if u.cmp(v) < 0 { - q = z.make(0) - r = z2.set(u) - return - } - - if len(v) == 1 { - var r2 Word - q, r2 = z.divW(u, v[0]) - r = z2.setWord(r2) - return - } - - q, r = z.divLarge(z2, u, v) - return -} - -// q = (uIn-r)/v, with 0 <= r < y -// Uses z as storage for q, and u as storage for r if possible. -// See Knuth, Volume 2, section 4.3.1, Algorithm D. -// Preconditions: -// len(v) >= 2 -// len(uIn) >= len(v) -func (z nat) divLarge(u, uIn, v nat) (q, r nat) { - n := len(v) - m := len(uIn) - n - - // determine if z can be reused - // TODO(gri) should find a better solution - this if statement - // is very costly (see e.g. time pidigits -s -n 10000) - if alias(z, uIn) || alias(z, v) { - z = nil // z is an alias for uIn or v - cannot reuse - } - q = z.make(m + 1) - - qhatv := make(nat, n+1) - if alias(u, uIn) || alias(u, v) { - u = nil // u is an alias for uIn or v - cannot reuse - } - u = u.make(len(uIn) + 1) - u.clear() - - // D1. - shift := leadingZeros(v[n-1]) - if shift > 0 { - // do not modify v, it may be used by another goroutine simultaneously - v1 := make(nat, n) - shlVU(v1, v, shift) - v = v1 - } - u[len(uIn)] = shlVU(u[0:len(uIn)], uIn, shift) - - // D2. - for j := m; j >= 0; j-- { - // D3. - qhat := Word(_M) - if u[j+n] != v[n-1] { - var rhat Word - qhat, rhat = divWW(u[j+n], u[j+n-1], v[n-1]) - - // x1 | x2 = q̂v_{n-2} - x1, x2 := mulWW(qhat, v[n-2]) - // test if q̂v_{n-2} > br̂ + u_{j+n-2} - for greaterThan(x1, x2, rhat, u[j+n-2]) { - qhat-- - prevRhat := rhat - rhat += v[n-1] - // v[n-1] >= 0, so this tests for overflow. - if rhat < prevRhat { - break - } - x1, x2 = mulWW(qhat, v[n-2]) - } - } - - // D4. - qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0) - - c := subVV(u[j:j+len(qhatv)], u[j:], qhatv) - if c != 0 { - c := addVV(u[j:j+n], u[j:], v) - u[j+n] += c - qhat-- - } - - q[j] = qhat - } - - q = q.norm() - shrVU(u, u, shift) - r = u.norm() - - return q, r -} - -// Length of x in bits. x must be normalized. -func (x nat) bitLen() int { - if i := len(x) - 1; i >= 0 { - return i*_W + bitLen(x[i]) - } - return 0 -} - -// MaxBase is the largest number base accepted for string conversions. -const MaxBase = 'z' - 'a' + 10 + 1 // = hexValue('z') + 1 - -func hexValue(ch rune) Word { - d := int(MaxBase + 1) // illegal base - switch { - case '0' <= ch && ch <= '9': - d = int(ch - '0') - case 'a' <= ch && ch <= 'z': - d = int(ch - 'a' + 10) - case 'A' <= ch && ch <= 'Z': - d = int(ch - 'A' + 10) - } - return Word(d) -} - -// scan sets z to the natural number corresponding to the longest possible prefix -// read from r representing an unsigned integer in a given conversion base. -// It returns z, the actual conversion base used, and an error, if any. In the -// error case, the value of z is undefined. The syntax follows the syntax of -// unsigned integer literals in Go. -// -// The base argument must be 0 or a value from 2 through MaxBase. If the base -// is 0, the string prefix determines the actual conversion base. A prefix of -// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a -// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10. -// -func (z nat) scan(r io.RuneScanner, base int) (nat, int, error) { - // reject illegal bases - if base < 0 || base == 1 || MaxBase < base { - return z, 0, errors.New("illegal number base") - } - - // one char look-ahead - ch, _, err := r.ReadRune() - if err != nil { - return z, 0, err - } - - // determine base if necessary - b := Word(base) - if base == 0 { - b = 10 - if ch == '0' { - switch ch, _, err = r.ReadRune(); err { - case nil: - b = 8 - switch ch { - case 'x', 'X': - b = 16 - case 'b', 'B': - b = 2 - } - if b == 2 || b == 16 { - if ch, _, err = r.ReadRune(); err != nil { - return z, 0, err - } - } - case io.EOF: - return z.make(0), 10, nil - default: - return z, 10, err - } - } - } - - // convert string - // - group as many digits d as possible together into a "super-digit" dd with "super-base" bb - // - only when bb does not fit into a word anymore, do a full number mulAddWW using bb and dd - z = z.make(0) - bb := Word(1) - dd := Word(0) - for max := _M / b; ; { - d := hexValue(ch) - if d >= b { - r.UnreadRune() // ch does not belong to number anymore - break - } - - if bb <= max { - bb *= b - dd = dd*b + d - } else { - // bb * b would overflow - z = z.mulAddWW(z, bb, dd) - bb = b - dd = d - } - - if ch, _, err = r.ReadRune(); err != nil { - if err != io.EOF { - return z, int(b), err - } - break - } - } - - switch { - case bb > 1: - // there was at least one mantissa digit - z = z.mulAddWW(z, bb, dd) - case base == 0 && b == 8: - // there was only the octal prefix 0 (possibly followed by digits > 7); - // return base 10, not 8 - return z, 10, nil - case base != 0 || b != 8: - // there was neither a mantissa digit nor the octal prefix 0 - return z, int(b), errors.New("syntax error scanning number") - } - - return z.norm(), int(b), nil -} - -// Character sets for string conversion. -const ( - lowercaseDigits = "0123456789abcdefghijklmnopqrstuvwxyz" - uppercaseDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" -) - -// decimalString returns a decimal representation of x. -// It calls x.string with the charset "0123456789". -func (x nat) decimalString() string { - return x.string(lowercaseDigits[0:10]) -} - -// string converts x to a string using digits from a charset; a digit with -// value d is represented by charset[d]. The conversion base is determined -// by len(charset), which must be >= 2 and <= 256. -func (x nat) string(charset string) string { - b := Word(len(charset)) - - // special cases - switch { - case b < 2 || MaxBase > 256: - panic("illegal base") - case len(x) == 0: - return string(charset[0]) - } - - // allocate buffer for conversion - i := int(float64(x.bitLen())/math.Log2(float64(b))) + 1 // off by one at most - s := make([]byte, i) - - // convert power of two and non power of two bases separately - if b == b&-b { - // shift is base-b digit size in bits - shift := trailingZeroBits(b) // shift > 0 because b >= 2 - mask := Word(1)<<shift - 1 - w := x[0] - nbits := uint(_W) // number of unprocessed bits in w - - // convert less-significant words - for k := 1; k < len(x); k++ { - // convert full digits - for nbits >= shift { - i-- - s[i] = charset[w&mask] - w >>= shift - nbits -= shift - } - - // convert any partial leading digit and advance to next word - if nbits == 0 { - // no partial digit remaining, just advance - w = x[k] - nbits = _W - } else { - // partial digit in current (k-1) and next (k) word - w |= x[k] << nbits - i-- - s[i] = charset[w&mask] - - // advance - w = x[k] >> (shift - nbits) - nbits = _W - (shift - nbits) - } - } - - // convert digits of most-significant word (omit leading zeros) - for nbits >= 0 && w != 0 { - i-- - s[i] = charset[w&mask] - w >>= shift - nbits -= shift - } - - } else { - // determine "big base"; i.e., the largest possible value bb - // that is a power of base b and still fits into a Word - // (as in 10^19 for 19 decimal digits in a 64bit Word) - bb := b // big base is b**ndigits - ndigits := 1 // number of base b digits - for max := Word(_M / b); bb <= max; bb *= b { - ndigits++ // maximize ndigits where bb = b**ndigits, bb <= _M - } - - // construct table of successive squares of bb*leafSize to use in subdivisions - // result (table != nil) <=> (len(x) > leafSize > 0) - table := divisors(len(x), b, ndigits, bb) - - // preserve x, create local copy for use by convertWords - q := nat(nil).set(x) - - // convert q to string s in base b - q.convertWords(s, charset, b, ndigits, bb, table) - - // strip leading zeros - // (x != 0; thus s must contain at least one non-zero digit - // and the loop will terminate) - i = 0 - for zero := charset[0]; s[i] == zero; { - i++ - } - } - - return string(s[i:]) -} - -// Convert words of q to base b digits in s. If q is large, it is recursively "split in half" -// by nat/nat division using tabulated divisors. Otherwise, it is converted iteratively using -// repeated nat/Word division. -// -// The iterative method processes n Words by n divW() calls, each of which visits every Word in the -// incrementally shortened q for a total of n + (n-1) + (n-2) ... + 2 + 1, or n(n+1)/2 divW()'s. -// Recursive conversion divides q by its approximate square root, yielding two parts, each half -// the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s -// plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and -// is made better by splitting the subblocks recursively. Best is to split blocks until one more -// split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the -// iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the -// range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and -// ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for -// specific hardware. -// -func (q nat) convertWords(s []byte, charset string, b Word, ndigits int, bb Word, table []divisor) { - // split larger blocks recursively - if table != nil { - // len(q) > leafSize > 0 - var r nat - index := len(table) - 1 - for len(q) > leafSize { - // find divisor close to sqrt(q) if possible, but in any case < q - maxLength := q.bitLen() // ~= log2 q, or at of least largest possible q of this bit length - minLength := maxLength >> 1 // ~= log2 sqrt(q) - for index > 0 && table[index-1].nbits > minLength { - index-- // desired - } - if table[index].nbits >= maxLength && table[index].bbb.cmp(q) >= 0 { - index-- - if index < 0 { - panic("internal inconsistency") - } - } - - // split q into the two digit number (q'*bbb + r) to form independent subblocks - q, r = q.div(r, q, table[index].bbb) - - // convert subblocks and collect results in s[:h] and s[h:] - h := len(s) - table[index].ndigits - r.convertWords(s[h:], charset, b, ndigits, bb, table[0:index]) - s = s[:h] // == q.convertWords(s, charset, b, ndigits, bb, table[0:index+1]) - } - } - - // having split any large blocks now process the remaining (small) block iteratively - i := len(s) - var r Word - if b == 10 { - // hard-coding for 10 here speeds this up by 1.25x (allows for / and % by constants) - for len(q) > 0 { - // extract least significant, base bb "digit" - q, r = q.divW(q, bb) - for j := 0; j < ndigits && i > 0; j++ { - i-- - // avoid % computation since r%10 == r - int(r/10)*10; - // this appears to be faster for BenchmarkString10000Base10 - // and smaller strings (but a bit slower for larger ones) - t := r / 10 - s[i] = charset[r-t<<3-t-t] // TODO(gri) replace w/ t*10 once compiler produces better code - r = t - } - } - } else { - for len(q) > 0 { - // extract least significant, base bb "digit" - q, r = q.divW(q, bb) - for j := 0; j < ndigits && i > 0; j++ { - i-- - s[i] = charset[r%b] - r /= b - } - } - } - - // prepend high-order zeroes - zero := charset[0] - for i > 0 { // while need more leading zeroes - i-- - s[i] = zero - } -} - -// Split blocks greater than leafSize Words (or set to 0 to disable recursive conversion) -// Benchmark and configure leafSize using: go test -bench="Leaf" -// 8 and 16 effective on 3.0 GHz Xeon "Clovertown" CPU (128 byte cache lines) -// 8 and 16 effective on 2.66 GHz Core 2 Duo "Penryn" CPU -var leafSize int = 8 // number of Word-size binary values treat as a monolithic block - -type divisor struct { - bbb nat // divisor - nbits int // bit length of divisor (discounting leading zeroes) ~= log2(bbb) - ndigits int // digit length of divisor in terms of output base digits -} - -var cacheBase10 struct { - sync.Mutex - table [64]divisor // cached divisors for base 10 -} - -// expWW computes x**y -func (z nat) expWW(x, y Word) nat { - return z.expNN(nat(nil).setWord(x), nat(nil).setWord(y), nil) -} - -// construct table of powers of bb*leafSize to use in subdivisions -func divisors(m int, b Word, ndigits int, bb Word) []divisor { - // only compute table when recursive conversion is enabled and x is large - if leafSize == 0 || m <= leafSize { - return nil - } - - // determine k where (bb**leafSize)**(2**k) >= sqrt(x) - k := 1 - for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 { - k++ - } - - // reuse and extend existing table of divisors or create new table as appropriate - var table []divisor // for b == 10, table overlaps with cacheBase10.table - if b == 10 { - cacheBase10.Lock() - table = cacheBase10.table[0:k] // reuse old table for this conversion - } else { - table = make([]divisor, k) // create new table for this conversion - } - - // extend table - if table[k-1].ndigits == 0 { - // add new entries as needed - var larger nat - for i := 0; i < k; i++ { - if table[i].ndigits == 0 { - if i == 0 { - table[0].bbb = nat(nil).expWW(bb, Word(leafSize)) - table[0].ndigits = ndigits * leafSize - } else { - table[i].bbb = nat(nil).mul(table[i-1].bbb, table[i-1].bbb) - table[i].ndigits = 2 * table[i-1].ndigits - } - - // optimization: exploit aggregated extra bits in macro blocks - larger = nat(nil).set(table[i].bbb) - for mulAddVWW(larger, larger, b, 0) == 0 { - table[i].bbb = table[i].bbb.set(larger) - table[i].ndigits++ - } - - table[i].nbits = table[i].bbb.bitLen() - } - } - } - - if b == 10 { - cacheBase10.Unlock() - } - - return table -} - -const deBruijn32 = 0x077CB531 - -var deBruijn32Lookup = []byte{ - 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, - 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9, -} - -const deBruijn64 = 0x03f79d71b4ca8b09 - -var deBruijn64Lookup = []byte{ - 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, - 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, - 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, - 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6, -} - -// trailingZeroBits returns the number of consecutive least significant zero -// bits of x. -func trailingZeroBits(x Word) uint { - // x & -x leaves only the right-most bit set in the word. Let k be the - // index of that bit. Since only a single bit is set, the value is two - // to the power of k. Multiplying by a power of two is equivalent to - // left shifting, in this case by k bits. The de Bruijn constant is - // such that all six bit, consecutive substrings are distinct. - // Therefore, if we have a left shifted version of this constant we can - // find by how many bits it was shifted by looking at which six bit - // substring ended up at the top of the word. - // (Knuth, volume 4, section 7.3.1) - switch _W { - case 32: - return uint(deBruijn32Lookup[((x&-x)*deBruijn32)>>27]) - case 64: - return uint(deBruijn64Lookup[((x&-x)*(deBruijn64&_M))>>58]) - default: - panic("unknown word size") - } -} - -// trailingZeroBits returns the number of consecutive least significant zero -// bits of x. -func (x nat) trailingZeroBits() uint { - if len(x) == 0 { - return 0 - } - var i uint - for x[i] == 0 { - i++ - } - // x[i] != 0 - return i*_W + trailingZeroBits(x[i]) -} - -// z = x << s -func (z nat) shl(x nat, s uint) nat { - m := len(x) - if m == 0 { - return z.make(0) - } - // m > 0 - - n := m + int(s/_W) - z = z.make(n + 1) - z[n] = shlVU(z[n-m:n], x, s%_W) - z[0 : n-m].clear() - - return z.norm() -} - -// z = x >> s -func (z nat) shr(x nat, s uint) nat { - m := len(x) - n := m - int(s/_W) - if n <= 0 { - return z.make(0) - } - // n > 0 - - z = z.make(n) - shrVU(z, x[m-n:], s%_W) - - return z.norm() -} - -func (z nat) setBit(x nat, i uint, b uint) nat { - j := int(i / _W) - m := Word(1) << (i % _W) - n := len(x) - switch b { - case 0: - z = z.make(n) - copy(z, x) - if j >= n { - // no need to grow - return z - } - z[j] &^= m - return z.norm() - case 1: - if j >= n { - z = z.make(j + 1) - z[n:].clear() - } else { - z = z.make(n) - } - copy(z, x) - z[j] |= m - // no need to normalize - return z - } - panic("set bit is not 0 or 1") -} - -func (z nat) bit(i uint) uint { - j := int(i / _W) - if j >= len(z) { - return 0 - } - return uint(z[j] >> (i % _W) & 1) -} - -func (z nat) and(x, y nat) nat { - m := len(x) - n := len(y) - if m > n { - m = n - } - // m <= n - - z = z.make(m) - for i := 0; i < m; i++ { - z[i] = x[i] & y[i] - } - - return z.norm() -} - -func (z nat) andNot(x, y nat) nat { - m := len(x) - n := len(y) - if n > m { - n = m - } - // m >= n - - z = z.make(m) - for i := 0; i < n; i++ { - z[i] = x[i] &^ y[i] - } - copy(z[n:m], x[n:m]) - - return z.norm() -} - -func (z nat) or(x, y nat) nat { - m := len(x) - n := len(y) - s := x - if m < n { - n, m = m, n - s = y - } - // m >= n - - z = z.make(m) - for i := 0; i < n; i++ { - z[i] = x[i] | y[i] - } - copy(z[n:m], s[n:m]) - - return z.norm() -} - -func (z nat) xor(x, y nat) nat { - m := len(x) - n := len(y) - s := x - if m < n { - n, m = m, n - s = y - } - // m >= n - - z = z.make(m) - for i := 0; i < n; i++ { - z[i] = x[i] ^ y[i] - } - copy(z[n:m], s[n:m]) - - return z.norm() -} - -// greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2) -func greaterThan(x1, x2, y1, y2 Word) bool { - return x1 > y1 || x1 == y1 && x2 > y2 -} - -// modW returns x % d. -func (x nat) modW(d Word) (r Word) { - // TODO(agl): we don't actually need to store the q value. - var q nat - q = q.make(len(x)) - return divWVW(q, 0, x, d) -} - -// random creates a random integer in [0..limit), using the space in z if -// possible. n is the bit length of limit. -func (z nat) random(rand *rand.Rand, limit nat, n int) nat { - if alias(z, limit) { - z = nil // z is an alias for limit - cannot reuse - } - z = z.make(len(limit)) - - bitLengthOfMSW := uint(n % _W) - if bitLengthOfMSW == 0 { - bitLengthOfMSW = _W - } - mask := Word((1 << bitLengthOfMSW) - 1) - - for { - switch _W { - case 32: - for i := range z { - z[i] = Word(rand.Uint32()) - } - case 64: - for i := range z { - z[i] = Word(rand.Uint32()) | Word(rand.Uint32())<<32 - } - default: - panic("unknown word size") - } - z[len(limit)-1] &= mask - if z.cmp(limit) < 0 { - break - } - } - - return z.norm() -} - -// If m != 0 (i.e., len(m) != 0), expNN sets z to x**y mod m; -// otherwise it sets z to x**y. The result is the value of z. -func (z nat) expNN(x, y, m nat) nat { - if alias(z, x) || alias(z, y) { - // We cannot allow in-place modification of x or y. - z = nil - } - - // x**y mod 1 == 0 - if len(m) == 1 && m[0] == 1 { - return z.setWord(0) - } - // m == 0 || m > 1 - - // x**0 == 1 - if len(y) == 0 { - return z.setWord(1) - } - // y > 0 - - if len(m) != 0 { - // We likely end up being as long as the modulus. - z = z.make(len(m)) - } - z = z.set(x) - - // If the base is non-trivial and the exponent is large, we use - // 4-bit, windowed exponentiation. This involves precomputing 14 values - // (x^2...x^15) but then reduces the number of multiply-reduces by a - // third. Even for a 32-bit exponent, this reduces the number of - // operations. - if len(x) > 1 && len(y) > 1 && len(m) > 0 { - return z.expNNWindowed(x, y, m) - } - - v := y[len(y)-1] // v > 0 because y is normalized and y > 0 - shift := leadingZeros(v) + 1 - v <<= shift - var q nat - - const mask = 1 << (_W - 1) - - // We walk through the bits of the exponent one by one. Each time we - // see a bit, we square, thus doubling the power. If the bit is a one, - // we also multiply by x, thus adding one to the power. - - w := _W - int(shift) - // zz and r are used to avoid allocating in mul and div as - // otherwise the arguments would alias. - var zz, r nat - for j := 0; j < w; j++ { - zz = zz.mul(z, z) - zz, z = z, zz - - if v&mask != 0 { - zz = zz.mul(z, x) - zz, z = z, zz - } - - if len(m) != 0 { - zz, r = zz.div(r, z, m) - zz, r, q, z = q, z, zz, r - } - - v <<= 1 - } - - for i := len(y) - 2; i >= 0; i-- { - v = y[i] - - for j := 0; j < _W; j++ { - zz = zz.mul(z, z) - zz, z = z, zz - - if v&mask != 0 { - zz = zz.mul(z, x) - zz, z = z, zz - } - - if len(m) != 0 { - zz, r = zz.div(r, z, m) - zz, r, q, z = q, z, zz, r - } - - v <<= 1 - } - } - - return z.norm() -} - -// expNNWindowed calculates x**y mod m using a fixed, 4-bit window. -func (z nat) expNNWindowed(x, y, m nat) nat { - // zz and r are used to avoid allocating in mul and div as otherwise - // the arguments would alias. - var zz, r nat - - const n = 4 - // powers[i] contains x^i. - var powers [1 << n]nat - powers[0] = natOne - powers[1] = x - for i := 2; i < 1<<n; i += 2 { - p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1] - *p = p.mul(*p2, *p2) - zz, r = zz.div(r, *p, m) - *p, r = r, *p - *p1 = p1.mul(*p, x) - zz, r = zz.div(r, *p1, m) - *p1, r = r, *p1 - } - - z = z.setWord(1) - - for i := len(y) - 1; i >= 0; i-- { - yi := y[i] - for j := 0; j < _W; j += n { - if i != len(y)-1 || j != 0 { - // Unrolled loop for significant performance - // gain. Use go test -bench=".*" in crypto/rsa - // to check performance before making changes. - zz = zz.mul(z, z) - zz, z = z, zz - zz, r = zz.div(r, z, m) - z, r = r, z - - zz = zz.mul(z, z) - zz, z = z, zz - zz, r = zz.div(r, z, m) - z, r = r, z - - zz = zz.mul(z, z) - zz, z = z, zz - zz, r = zz.div(r, z, m) - z, r = r, z - - zz = zz.mul(z, z) - zz, z = z, zz - zz, r = zz.div(r, z, m) - z, r = r, z - } - - zz = zz.mul(z, powers[yi>>(_W-n)]) - zz, z = z, zz - zz, r = zz.div(r, z, m) - z, r = r, z - - yi <<= n - } - } - - return z.norm() -} - -// probablyPrime performs reps Miller-Rabin tests to check whether n is prime. -// If it returns true, n is prime with probability 1 - 1/4^reps. -// If it returns false, n is not prime. -func (n nat) probablyPrime(reps int) bool { - if len(n) == 0 { - return false - } - - if len(n) == 1 { - if n[0] < 2 { - return false - } - - if n[0]%2 == 0 { - return n[0] == 2 - } - - // We have to exclude these cases because we reject all - // multiples of these numbers below. - switch n[0] { - case 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53: - return true - } - } - - const primesProduct32 = 0xC0CFD797 // Π {p ∈ primes, 2 < p <= 29} - const primesProduct64 = 0xE221F97C30E94E1D // Π {p ∈ primes, 2 < p <= 53} - - var r Word - switch _W { - case 32: - r = n.modW(primesProduct32) - case 64: - r = n.modW(primesProduct64 & _M) - default: - panic("Unknown word size") - } - - if r%3 == 0 || r%5 == 0 || r%7 == 0 || r%11 == 0 || - r%13 == 0 || r%17 == 0 || r%19 == 0 || r%23 == 0 || r%29 == 0 { - return false - } - - if _W == 64 && (r%31 == 0 || r%37 == 0 || r%41 == 0 || - r%43 == 0 || r%47 == 0 || r%53 == 0) { - return false - } - - nm1 := nat(nil).sub(n, natOne) - // determine q, k such that nm1 = q << k - k := nm1.trailingZeroBits() - q := nat(nil).shr(nm1, k) - - nm3 := nat(nil).sub(nm1, natTwo) - rand := rand.New(rand.NewSource(int64(n[0]))) - - var x, y, quotient nat - nm3Len := nm3.bitLen() - -NextRandom: - for i := 0; i < reps; i++ { - x = x.random(rand, nm3, nm3Len) - x = x.add(x, natTwo) - y = y.expNN(x, q, n) - if y.cmp(natOne) == 0 || y.cmp(nm1) == 0 { - continue - } - for j := uint(1); j < k; j++ { - y = y.mul(y, y) - quotient, y = quotient.div(y, y, n) - if y.cmp(nm1) == 0 { - continue NextRandom - } - if y.cmp(natOne) == 0 { - return false - } - } - return false - } - - return true -} - -// bytes writes the value of z into buf using big-endian encoding. -// len(buf) must be >= len(z)*_S. The value of z is encoded in the -// slice buf[i:]. The number i of unused bytes at the beginning of -// buf is returned as result. -func (z nat) bytes(buf []byte) (i int) { - i = len(buf) - for _, d := range z { - for j := 0; j < _S; j++ { - i-- - buf[i] = byte(d) - d >>= 8 - } - } - - for i < len(buf) && buf[i] == 0 { - i++ - } - - return -} - -// setBytes interprets buf as the bytes of a big-endian unsigned -// integer, sets z to that value, and returns z. -func (z nat) setBytes(buf []byte) nat { - z = z.make((len(buf) + _S - 1) / _S) - - k := 0 - s := uint(0) - var d Word - for i := len(buf); i > 0; i-- { - d |= Word(buf[i-1]) << s - if s += 8; s == _S*8 { - z[k] = d - k++ - s = 0 - d = 0 - } - } - if k < len(z) { - z[k] = d - } - - return z.norm() -} diff --git a/src/pkg/math/big/nat_test.go b/src/pkg/math/big/nat_test.go deleted file mode 100644 index a2ae53385..000000000 --- a/src/pkg/math/big/nat_test.go +++ /dev/null @@ -1,771 +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. - -package big - -import ( - "io" - "runtime" - "strings" - "testing" -) - -var cmpTests = []struct { - x, y nat - r int -}{ - {nil, nil, 0}, - {nil, nat(nil), 0}, - {nat(nil), nil, 0}, - {nat(nil), nat(nil), 0}, - {nat{0}, nat{0}, 0}, - {nat{0}, nat{1}, -1}, - {nat{1}, nat{0}, 1}, - {nat{1}, nat{1}, 0}, - {nat{0, _M}, nat{1}, 1}, - {nat{1}, nat{0, _M}, -1}, - {nat{1, _M}, nat{0, _M}, 1}, - {nat{0, _M}, nat{1, _M}, -1}, - {nat{16, 571956, 8794, 68}, nat{837, 9146, 1, 754489}, -1}, - {nat{34986, 41, 105, 1957}, nat{56, 7458, 104, 1957}, 1}, -} - -func TestCmp(t *testing.T) { - for i, a := range cmpTests { - r := a.x.cmp(a.y) - if r != a.r { - t.Errorf("#%d got r = %v; want %v", i, r, a.r) - } - } -} - -type funNN func(z, x, y nat) nat -type argNN struct { - z, x, y nat -} - -var sumNN = []argNN{ - {}, - {nat{1}, nil, nat{1}}, - {nat{1111111110}, nat{123456789}, nat{987654321}}, - {nat{0, 0, 0, 1}, nil, nat{0, 0, 0, 1}}, - {nat{0, 0, 0, 1111111110}, nat{0, 0, 0, 123456789}, nat{0, 0, 0, 987654321}}, - {nat{0, 0, 0, 1}, nat{0, 0, _M}, nat{0, 0, 1}}, -} - -var prodNN = []argNN{ - {}, - {nil, nil, nil}, - {nil, nat{991}, nil}, - {nat{991}, nat{991}, nat{1}}, - {nat{991 * 991}, nat{991}, nat{991}}, - {nat{0, 0, 991 * 991}, nat{0, 991}, nat{0, 991}}, - {nat{1 * 991, 2 * 991, 3 * 991, 4 * 991}, nat{1, 2, 3, 4}, nat{991}}, - {nat{4, 11, 20, 30, 20, 11, 4}, nat{1, 2, 3, 4}, nat{4, 3, 2, 1}}, - // 3^100 * 3^28 = 3^128 - { - natFromString("11790184577738583171520872861412518665678211592275841109096961"), - natFromString("515377520732011331036461129765621272702107522001"), - natFromString("22876792454961"), - }, - // z = 111....1 (70000 digits) - // x = 10^(99*700) + ... + 10^1400 + 10^700 + 1 - // y = 111....1 (700 digits, larger than Karatsuba threshold on 32-bit and 64-bit) - { - natFromString(strings.Repeat("1", 70000)), - natFromString("1" + strings.Repeat(strings.Repeat("0", 699)+"1", 99)), - natFromString(strings.Repeat("1", 700)), - }, - // z = 111....1 (20000 digits) - // x = 10^10000 + 1 - // y = 111....1 (10000 digits) - { - natFromString(strings.Repeat("1", 20000)), - natFromString("1" + strings.Repeat("0", 9999) + "1"), - natFromString(strings.Repeat("1", 10000)), - }, -} - -func natFromString(s string) nat { - x, _, err := nat(nil).scan(strings.NewReader(s), 0) - if err != nil { - panic(err) - } - return x -} - -func TestSet(t *testing.T) { - for _, a := range sumNN { - z := nat(nil).set(a.z) - if z.cmp(a.z) != 0 { - t.Errorf("got z = %v; want %v", z, a.z) - } - } -} - -func testFunNN(t *testing.T, msg string, f funNN, a argNN) { - z := f(nil, a.x, a.y) - if z.cmp(a.z) != 0 { - t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, z, a.z) - } -} - -func TestFunNN(t *testing.T) { - for _, a := range sumNN { - arg := a - testFunNN(t, "add", nat.add, arg) - - arg = argNN{a.z, a.y, a.x} - testFunNN(t, "add symmetric", nat.add, arg) - - arg = argNN{a.x, a.z, a.y} - testFunNN(t, "sub", nat.sub, arg) - - arg = argNN{a.y, a.z, a.x} - testFunNN(t, "sub symmetric", nat.sub, arg) - } - - for _, a := range prodNN { - arg := a - testFunNN(t, "mul", nat.mul, arg) - - arg = argNN{a.z, a.y, a.x} - testFunNN(t, "mul symmetric", nat.mul, arg) - } -} - -var mulRangesN = []struct { - a, b uint64 - prod string -}{ - {0, 0, "0"}, - {1, 1, "1"}, - {1, 2, "2"}, - {1, 3, "6"}, - {10, 10, "10"}, - {0, 100, "0"}, - {0, 1e9, "0"}, - {1, 0, "1"}, // empty range - {100, 1, "1"}, // empty range - {1, 10, "3628800"}, // 10! - {1, 20, "2432902008176640000"}, // 20! - {1, 100, - "933262154439441526816992388562667004907159682643816214685929" + - "638952175999932299156089414639761565182862536979208272237582" + - "51185210916864000000000000000000000000", // 100! - }, -} - -func TestMulRangeN(t *testing.T) { - for i, r := range mulRangesN { - prod := nat(nil).mulRange(r.a, r.b).decimalString() - if prod != r.prod { - t.Errorf("#%d: got %s; want %s", i, prod, r.prod) - } - } -} - -// allocBytes returns the number of bytes allocated by invoking f. -func allocBytes(f func()) uint64 { - var stats runtime.MemStats - runtime.ReadMemStats(&stats) - t := stats.TotalAlloc - f() - runtime.ReadMemStats(&stats) - return stats.TotalAlloc - t -} - -// TestMulUnbalanced tests that multiplying numbers of different lengths -// does not cause deep recursion and in turn allocate too much memory. -// Test case for issue 3807. -func TestMulUnbalanced(t *testing.T) { - defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(1)) - x := rndNat(50000) - y := rndNat(40) - allocSize := allocBytes(func() { - nat(nil).mul(x, y) - }) - inputSize := uint64(len(x)+len(y)) * _S - if ratio := allocSize / uint64(inputSize); ratio > 10 { - t.Errorf("multiplication uses too much memory (%d > %d times the size of inputs)", allocSize, ratio) - } -} - -func rndNat(n int) nat { - return nat(rndV(n)).norm() -} - -func BenchmarkMul(b *testing.B) { - mulx := rndNat(1e4) - muly := rndNat(1e4) - b.ResetTimer() - for i := 0; i < b.N; i++ { - var z nat - z.mul(mulx, muly) - } -} - -func toString(x nat, charset string) string { - base := len(charset) - - // special cases - switch { - case base < 2: - panic("illegal base") - case len(x) == 0: - return string(charset[0]) - } - - // allocate buffer for conversion - i := x.bitLen()/log2(Word(base)) + 1 // +1: round up - s := make([]byte, i) - - // don't destroy x - q := nat(nil).set(x) - - // convert - for len(q) > 0 { - i-- - var r Word - q, r = q.divW(q, Word(base)) - s[i] = charset[r] - } - - return string(s[i:]) -} - -var strTests = []struct { - x nat // nat value to be converted - c string // conversion charset - s string // expected result -}{ - {nil, "01", "0"}, - {nat{1}, "01", "1"}, - {nat{0xc5}, "01", "11000101"}, - {nat{03271}, lowercaseDigits[0:8], "3271"}, - {nat{10}, lowercaseDigits[0:10], "10"}, - {nat{1234567890}, uppercaseDigits[0:10], "1234567890"}, - {nat{0xdeadbeef}, lowercaseDigits[0:16], "deadbeef"}, - {nat{0xdeadbeef}, uppercaseDigits[0:16], "DEADBEEF"}, - {nat{0x229be7}, lowercaseDigits[0:17], "1a2b3c"}, - {nat{0x309663e6}, uppercaseDigits[0:32], "O9COV6"}, -} - -func TestString(t *testing.T) { - for _, a := range strTests { - s := a.x.string(a.c) - if s != a.s { - t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s) - } - - x, b, err := nat(nil).scan(strings.NewReader(a.s), len(a.c)) - if x.cmp(a.x) != 0 { - t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x) - } - if b != len(a.c) { - t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, len(a.c)) - } - if err != nil { - t.Errorf("scan%+v\n\tgot error = %s", a, err) - } - } -} - -var natScanTests = []struct { - s string // string to be scanned - base int // input base - x nat // expected nat - b int // expected base - ok bool // expected success - next rune // next character (or 0, if at EOF) -}{ - // error: illegal base - {base: -1}, - {base: 1}, - {base: 37}, - - // error: no mantissa - {}, - {s: "?"}, - {base: 10}, - {base: 36}, - {s: "?", base: 10}, - {s: "0x"}, - {s: "345", base: 2}, - - // no errors - {"0", 0, nil, 10, true, 0}, - {"0", 10, nil, 10, true, 0}, - {"0", 36, nil, 36, true, 0}, - {"1", 0, nat{1}, 10, true, 0}, - {"1", 10, nat{1}, 10, true, 0}, - {"0 ", 0, nil, 10, true, ' '}, - {"08", 0, nil, 10, true, '8'}, - {"018", 0, nat{1}, 8, true, '8'}, - {"0b1", 0, nat{1}, 2, true, 0}, - {"0b11000101", 0, nat{0xc5}, 2, true, 0}, - {"03271", 0, nat{03271}, 8, true, 0}, - {"10ab", 0, nat{10}, 10, true, 'a'}, - {"1234567890", 0, nat{1234567890}, 10, true, 0}, - {"xyz", 36, nat{(33*36+34)*36 + 35}, 36, true, 0}, - {"xyz?", 36, nat{(33*36+34)*36 + 35}, 36, true, '?'}, - {"0x", 16, nil, 16, true, 'x'}, - {"0xdeadbeef", 0, nat{0xdeadbeef}, 16, true, 0}, - {"0XDEADBEEF", 0, nat{0xdeadbeef}, 16, true, 0}, -} - -func TestScanBase(t *testing.T) { - for _, a := range natScanTests { - r := strings.NewReader(a.s) - x, b, err := nat(nil).scan(r, a.base) - if err == nil && !a.ok { - t.Errorf("scan%+v\n\texpected error", a) - } - if err != nil { - if a.ok { - t.Errorf("scan%+v\n\tgot error = %s", a, err) - } - continue - } - if x.cmp(a.x) != 0 { - t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x) - } - if b != a.b { - t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.base) - } - next, _, err := r.ReadRune() - if err == io.EOF { - next = 0 - err = nil - } - if err == nil && next != a.next { - t.Errorf("scan%+v\n\tgot next = %q; want %q", a, next, a.next) - } - } -} - -var pi = "3" + - "14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651" + - "32823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461" + - "28475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920" + - "96282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179" + - "31051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798" + - "60943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901" + - "22495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837" + - "29780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083" + - "81420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909" + - "21642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151" + - "55748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035" + - "63707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104" + - "75216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992" + - "45863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818" + - "34797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548" + - "16136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179" + - "04946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886" + - "26945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645" + - "99581339047802759009946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745" + - "53050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382" + - "68683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244" + - "13654976278079771569143599770012961608944169486855584840635342207222582848864815845602850601684273945226746767" + - "88952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288" + - "79710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821" + - "68299894872265880485756401427047755513237964145152374623436454285844479526586782105114135473573952311342716610" + - "21359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435" + - "06430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675" + - "14269123974894090718649423196156794520809514655022523160388193014209376213785595663893778708303906979207734672" + - "21825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539" + - "05796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007" + - "23055876317635942187312514712053292819182618612586732157919841484882916447060957527069572209175671167229109816" + - "90915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398" + - "31501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064" + - "20467525907091548141654985946163718027098199430992448895757128289059232332609729971208443357326548938239119325" + - "97463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100" + - "44929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915" + - "44110104468232527162010526522721116603966655730925471105578537634668206531098965269186205647693125705863566201" + - "85581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318" + - "58676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797" + - "27082668306343285878569830523580893306575740679545716377525420211495576158140025012622859413021647155097925923" + - "09907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111" + - "79042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043" + - "06332175182979866223717215916077166925474873898665494945011465406284336639379003976926567214638530673609657120" + - "91807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862" + - "94726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939" + - "78054193414473774418426312986080998886874132604721569516239658645730216315981931951673538129741677294786724229" + - "24654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001" + - "59377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541" + - "34189948544473456738316249934191318148092777710386387734317720754565453220777092120190516609628049092636019759" + - "88281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267" + - "94561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337" - -// Test case for BenchmarkScanPi. -func TestScanPi(t *testing.T) { - var x nat - z, _, err := x.scan(strings.NewReader(pi), 10) - if err != nil { - t.Errorf("scanning pi: %s", err) - } - if s := z.decimalString(); s != pi { - t.Errorf("scanning pi: got %s", s) - } -} - -func TestScanPiParallel(t *testing.T) { - const n = 2 - c := make(chan int) - for i := 0; i < n; i++ { - go func() { - TestScanPi(t) - c <- 0 - }() - } - for i := 0; i < n; i++ { - <-c - } -} - -func BenchmarkScanPi(b *testing.B) { - for i := 0; i < b.N; i++ { - var x nat - x.scan(strings.NewReader(pi), 10) - } -} - -func BenchmarkStringPiParallel(b *testing.B) { - var x nat - x, _, _ = x.scan(strings.NewReader(pi), 0) - if x.decimalString() != pi { - panic("benchmark incorrect: conversion failed") - } - b.RunParallel(func(pb *testing.PB) { - for pb.Next() { - x.decimalString() - } - }) -} - -func BenchmarkScan10Base2(b *testing.B) { ScanHelper(b, 2, 10, 10) } -func BenchmarkScan100Base2(b *testing.B) { ScanHelper(b, 2, 10, 100) } -func BenchmarkScan1000Base2(b *testing.B) { ScanHelper(b, 2, 10, 1000) } -func BenchmarkScan10000Base2(b *testing.B) { ScanHelper(b, 2, 10, 10000) } -func BenchmarkScan100000Base2(b *testing.B) { ScanHelper(b, 2, 10, 100000) } - -func BenchmarkScan10Base8(b *testing.B) { ScanHelper(b, 8, 10, 10) } -func BenchmarkScan100Base8(b *testing.B) { ScanHelper(b, 8, 10, 100) } -func BenchmarkScan1000Base8(b *testing.B) { ScanHelper(b, 8, 10, 1000) } -func BenchmarkScan10000Base8(b *testing.B) { ScanHelper(b, 8, 10, 10000) } -func BenchmarkScan100000Base8(b *testing.B) { ScanHelper(b, 8, 10, 100000) } - -func BenchmarkScan10Base10(b *testing.B) { ScanHelper(b, 10, 10, 10) } -func BenchmarkScan100Base10(b *testing.B) { ScanHelper(b, 10, 10, 100) } -func BenchmarkScan1000Base10(b *testing.B) { ScanHelper(b, 10, 10, 1000) } -func BenchmarkScan10000Base10(b *testing.B) { ScanHelper(b, 10, 10, 10000) } -func BenchmarkScan100000Base10(b *testing.B) { ScanHelper(b, 10, 10, 100000) } - -func BenchmarkScan10Base16(b *testing.B) { ScanHelper(b, 16, 10, 10) } -func BenchmarkScan100Base16(b *testing.B) { ScanHelper(b, 16, 10, 100) } -func BenchmarkScan1000Base16(b *testing.B) { ScanHelper(b, 16, 10, 1000) } -func BenchmarkScan10000Base16(b *testing.B) { ScanHelper(b, 16, 10, 10000) } -func BenchmarkScan100000Base16(b *testing.B) { ScanHelper(b, 16, 10, 100000) } - -func ScanHelper(b *testing.B, base int, x, y Word) { - b.StopTimer() - var z nat - z = z.expWW(x, y) - - var s string - s = z.string(lowercaseDigits[0:base]) - if t := toString(z, lowercaseDigits[0:base]); t != s { - b.Fatalf("scanning: got %s; want %s", s, t) - } - b.StartTimer() - - for i := 0; i < b.N; i++ { - z.scan(strings.NewReader(s), base) - } -} - -func BenchmarkString10Base2(b *testing.B) { StringHelper(b, 2, 10, 10) } -func BenchmarkString100Base2(b *testing.B) { StringHelper(b, 2, 10, 100) } -func BenchmarkString1000Base2(b *testing.B) { StringHelper(b, 2, 10, 1000) } -func BenchmarkString10000Base2(b *testing.B) { StringHelper(b, 2, 10, 10000) } -func BenchmarkString100000Base2(b *testing.B) { StringHelper(b, 2, 10, 100000) } - -func BenchmarkString10Base8(b *testing.B) { StringHelper(b, 8, 10, 10) } -func BenchmarkString100Base8(b *testing.B) { StringHelper(b, 8, 10, 100) } -func BenchmarkString1000Base8(b *testing.B) { StringHelper(b, 8, 10, 1000) } -func BenchmarkString10000Base8(b *testing.B) { StringHelper(b, 8, 10, 10000) } -func BenchmarkString100000Base8(b *testing.B) { StringHelper(b, 8, 10, 100000) } - -func BenchmarkString10Base10(b *testing.B) { StringHelper(b, 10, 10, 10) } -func BenchmarkString100Base10(b *testing.B) { StringHelper(b, 10, 10, 100) } -func BenchmarkString1000Base10(b *testing.B) { StringHelper(b, 10, 10, 1000) } -func BenchmarkString10000Base10(b *testing.B) { StringHelper(b, 10, 10, 10000) } -func BenchmarkString100000Base10(b *testing.B) { StringHelper(b, 10, 10, 100000) } - -func BenchmarkString10Base16(b *testing.B) { StringHelper(b, 16, 10, 10) } -func BenchmarkString100Base16(b *testing.B) { StringHelper(b, 16, 10, 100) } -func BenchmarkString1000Base16(b *testing.B) { StringHelper(b, 16, 10, 1000) } -func BenchmarkString10000Base16(b *testing.B) { StringHelper(b, 16, 10, 10000) } -func BenchmarkString100000Base16(b *testing.B) { StringHelper(b, 16, 10, 100000) } - -func StringHelper(b *testing.B, base int, x, y Word) { - b.StopTimer() - var z nat - z = z.expWW(x, y) - z.string(lowercaseDigits[0:base]) // warm divisor cache - b.StartTimer() - - for i := 0; i < b.N; i++ { - _ = z.string(lowercaseDigits[0:base]) - } -} - -func BenchmarkLeafSize0(b *testing.B) { LeafSizeHelper(b, 10, 0) } // test without splitting -func BenchmarkLeafSize1(b *testing.B) { LeafSizeHelper(b, 10, 1) } -func BenchmarkLeafSize2(b *testing.B) { LeafSizeHelper(b, 10, 2) } -func BenchmarkLeafSize3(b *testing.B) { LeafSizeHelper(b, 10, 3) } -func BenchmarkLeafSize4(b *testing.B) { LeafSizeHelper(b, 10, 4) } -func BenchmarkLeafSize5(b *testing.B) { LeafSizeHelper(b, 10, 5) } -func BenchmarkLeafSize6(b *testing.B) { LeafSizeHelper(b, 10, 6) } -func BenchmarkLeafSize7(b *testing.B) { LeafSizeHelper(b, 10, 7) } -func BenchmarkLeafSize8(b *testing.B) { LeafSizeHelper(b, 10, 8) } -func BenchmarkLeafSize9(b *testing.B) { LeafSizeHelper(b, 10, 9) } -func BenchmarkLeafSize10(b *testing.B) { LeafSizeHelper(b, 10, 10) } -func BenchmarkLeafSize11(b *testing.B) { LeafSizeHelper(b, 10, 11) } -func BenchmarkLeafSize12(b *testing.B) { LeafSizeHelper(b, 10, 12) } -func BenchmarkLeafSize13(b *testing.B) { LeafSizeHelper(b, 10, 13) } -func BenchmarkLeafSize14(b *testing.B) { LeafSizeHelper(b, 10, 14) } -func BenchmarkLeafSize15(b *testing.B) { LeafSizeHelper(b, 10, 15) } -func BenchmarkLeafSize16(b *testing.B) { LeafSizeHelper(b, 10, 16) } -func BenchmarkLeafSize32(b *testing.B) { LeafSizeHelper(b, 10, 32) } // try some large lengths -func BenchmarkLeafSize64(b *testing.B) { LeafSizeHelper(b, 10, 64) } - -func LeafSizeHelper(b *testing.B, base Word, size int) { - b.StopTimer() - originalLeafSize := leafSize - resetTable(cacheBase10.table[:]) - leafSize = size - b.StartTimer() - - for d := 1; d <= 10000; d *= 10 { - b.StopTimer() - var z nat - z = z.expWW(base, Word(d)) // build target number - _ = z.string(lowercaseDigits[0:base]) // warm divisor cache - b.StartTimer() - - for i := 0; i < b.N; i++ { - _ = z.string(lowercaseDigits[0:base]) - } - } - - b.StopTimer() - resetTable(cacheBase10.table[:]) - leafSize = originalLeafSize - b.StartTimer() -} - -func resetTable(table []divisor) { - if table != nil && table[0].bbb != nil { - for i := 0; i < len(table); i++ { - table[i].bbb = nil - table[i].nbits = 0 - table[i].ndigits = 0 - } - } -} - -func TestStringPowers(t *testing.T) { - var b, p Word - for b = 2; b <= 16; b++ { - for p = 0; p <= 512; p++ { - x := nat(nil).expWW(b, p) - xs := x.string(lowercaseDigits[0:b]) - xs2 := toString(x, lowercaseDigits[0:b]) - if xs != xs2 { - t.Errorf("failed at %d ** %d in base %d: %s != %s", b, p, b, xs, xs2) - } - } - if b >= 3 && testing.Short() { - break - } - } -} - -func TestLeadingZeros(t *testing.T) { - var x Word = _B >> 1 - for i := 0; i <= _W; i++ { - if int(leadingZeros(x)) != i { - t.Errorf("failed at %x: got %d want %d", x, leadingZeros(x), i) - } - x >>= 1 - } -} - -type shiftTest struct { - in nat - shift uint - out nat -} - -var leftShiftTests = []shiftTest{ - {nil, 0, nil}, - {nil, 1, nil}, - {natOne, 0, natOne}, - {natOne, 1, natTwo}, - {nat{1 << (_W - 1)}, 1, nat{0}}, - {nat{1 << (_W - 1), 0}, 1, nat{0, 1}}, -} - -func TestShiftLeft(t *testing.T) { - for i, test := range leftShiftTests { - var z nat - z = z.shl(test.in, test.shift) - for j, d := range test.out { - if j >= len(z) || z[j] != d { - t.Errorf("#%d: got: %v want: %v", i, z, test.out) - break - } - } - } -} - -var rightShiftTests = []shiftTest{ - {nil, 0, nil}, - {nil, 1, nil}, - {natOne, 0, natOne}, - {natOne, 1, nil}, - {natTwo, 1, natOne}, - {nat{0, 1}, 1, nat{1 << (_W - 1)}}, - {nat{2, 1, 1}, 1, nat{1<<(_W-1) + 1, 1 << (_W - 1)}}, -} - -func TestShiftRight(t *testing.T) { - for i, test := range rightShiftTests { - var z nat - z = z.shr(test.in, test.shift) - for j, d := range test.out { - if j >= len(z) || z[j] != d { - t.Errorf("#%d: got: %v want: %v", i, z, test.out) - break - } - } - } -} - -type modWTest struct { - in string - dividend string - out string -} - -var modWTests32 = []modWTest{ - {"23492635982634928349238759823742", "252341", "220170"}, -} - -var modWTests64 = []modWTest{ - {"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"}, -} - -func runModWTests(t *testing.T, tests []modWTest) { - for i, test := range tests { - in, _ := new(Int).SetString(test.in, 10) - d, _ := new(Int).SetString(test.dividend, 10) - out, _ := new(Int).SetString(test.out, 10) - - r := in.abs.modW(d.abs[0]) - if r != out.abs[0] { - t.Errorf("#%d failed: got %d want %s", i, r, out) - } - } -} - -func TestModW(t *testing.T) { - if _W >= 32 { - runModWTests(t, modWTests32) - } - if _W >= 64 { - runModWTests(t, modWTests64) - } -} - -func TestTrailingZeroBits(t *testing.T) { - x := Word(1) - for i := uint(0); i <= _W; i++ { - n := trailingZeroBits(x) - if n != i%_W { - t.Errorf("got trailingZeroBits(%#x) = %d; want %d", x, n, i%_W) - } - x <<= 1 - } - - y := nat(nil).set(natOne) - for i := uint(0); i <= 3*_W; i++ { - n := y.trailingZeroBits() - if n != i { - t.Errorf("got 0x%s.trailingZeroBits() = %d; want %d", y.string(lowercaseDigits[0:16]), n, i) - } - y = y.shl(y, 1) - } -} - -var expNNTests = []struct { - x, y, m string - out string -}{ - {"0", "0", "0", "1"}, - {"0", "0", "1", "0"}, - {"1", "1", "1", "0"}, - {"2", "1", "1", "0"}, - {"2", "2", "1", "0"}, - {"10", "100000000000", "1", "0"}, - {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"}, - {"0x8000000000000000", "2", "6719", "4944"}, - {"0x8000000000000000", "3", "6719", "5447"}, - {"0x8000000000000000", "1000", "6719", "1603"}, - {"0x8000000000000000", "1000000", "6719", "3199"}, - { - "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347", - "298472983472983471903246121093472394872319615612417471234712061", - "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464", - "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291", - }, -} - -func TestExpNN(t *testing.T) { - for i, test := range expNNTests { - x, _, _ := nat(nil).scan(strings.NewReader(test.x), 0) - y, _, _ := nat(nil).scan(strings.NewReader(test.y), 0) - out, _, _ := nat(nil).scan(strings.NewReader(test.out), 0) - - var m nat - - if len(test.m) > 0 { - m, _, _ = nat(nil).scan(strings.NewReader(test.m), 0) - } - - z := nat(nil).expNN(x, y, m) - if z.cmp(out) != 0 { - t.Errorf("#%d got %s want %s", i, z.decimalString(), out.decimalString()) - } - } -} - -func ExpHelper(b *testing.B, x, y Word) { - var z nat - for i := 0; i < b.N; i++ { - z.expWW(x, y) - } -} - -func BenchmarkExp3Power0x10(b *testing.B) { ExpHelper(b, 3, 0x10) } -func BenchmarkExp3Power0x40(b *testing.B) { ExpHelper(b, 3, 0x40) } -func BenchmarkExp3Power0x100(b *testing.B) { ExpHelper(b, 3, 0x100) } -func BenchmarkExp3Power0x400(b *testing.B) { ExpHelper(b, 3, 0x400) } -func BenchmarkExp3Power0x1000(b *testing.B) { ExpHelper(b, 3, 0x1000) } -func BenchmarkExp3Power0x4000(b *testing.B) { ExpHelper(b, 3, 0x4000) } -func BenchmarkExp3Power0x10000(b *testing.B) { ExpHelper(b, 3, 0x10000) } -func BenchmarkExp3Power0x40000(b *testing.B) { ExpHelper(b, 3, 0x40000) } -func BenchmarkExp3Power0x100000(b *testing.B) { ExpHelper(b, 3, 0x100000) } -func BenchmarkExp3Power0x400000(b *testing.B) { ExpHelper(b, 3, 0x400000) } diff --git a/src/pkg/math/big/rat.go b/src/pkg/math/big/rat.go deleted file mode 100644 index f0973b390..000000000 --- a/src/pkg/math/big/rat.go +++ /dev/null @@ -1,600 +0,0 @@ -// Copyright 2010 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 multi-precision rational numbers. - -package big - -import ( - "encoding/binary" - "errors" - "fmt" - "math" - "strings" -) - -// A Rat represents a quotient a/b of arbitrary precision. -// The zero value for a Rat represents the value 0. -type Rat struct { - // To make zero values for Rat work w/o initialization, - // a zero value of b (len(b) == 0) acts like b == 1. - // a.neg determines the sign of the Rat, b.neg is ignored. - a, b Int -} - -// NewRat creates a new Rat with numerator a and denominator b. -func NewRat(a, b int64) *Rat { - return new(Rat).SetFrac64(a, b) -} - -// SetFloat64 sets z to exactly f and returns z. -// If f is not finite, SetFloat returns nil. -func (z *Rat) SetFloat64(f float64) *Rat { - const expMask = 1<<11 - 1 - bits := math.Float64bits(f) - mantissa := bits & (1<<52 - 1) - exp := int((bits >> 52) & expMask) - switch exp { - case expMask: // non-finite - return nil - case 0: // denormal - exp -= 1022 - default: // normal - mantissa |= 1 << 52 - exp -= 1023 - } - - shift := 52 - exp - - // Optimization (?): partially pre-normalise. - for mantissa&1 == 0 && shift > 0 { - mantissa >>= 1 - shift-- - } - - z.a.SetUint64(mantissa) - z.a.neg = f < 0 - z.b.Set(intOne) - if shift > 0 { - z.b.Lsh(&z.b, uint(shift)) - } else { - z.a.Lsh(&z.a, uint(-shift)) - } - return z.norm() -} - -// isFinite reports whether f represents a finite rational value. -// It is equivalent to !math.IsNan(f) && !math.IsInf(f, 0). -func isFinite(f float64) bool { - return math.Abs(f) <= math.MaxFloat64 -} - -// low64 returns the least significant 64 bits of natural number z. -func low64(z nat) uint64 { - if len(z) == 0 { - return 0 - } - if _W == 32 && len(z) > 1 { - return uint64(z[1])<<32 | uint64(z[0]) - } - return uint64(z[0]) -} - -// quotToFloat returns the non-negative IEEE 754 double-precision -// value nearest to the quotient a/b, using round-to-even in halfway -// cases. It does not mutate its arguments. -// Preconditions: b is non-zero; a and b have no common factors. -func quotToFloat(a, b nat) (f float64, exact bool) { - // TODO(adonovan): specialize common degenerate cases: 1.0, integers. - alen := a.bitLen() - if alen == 0 { - return 0, true - } - blen := b.bitLen() - if blen == 0 { - panic("division by zero") - } - - // 1. Left-shift A or B such that quotient A/B is in [1<<53, 1<<55). - // (54 bits if A<B when they are left-aligned, 55 bits if A>=B.) - // This is 2 or 3 more than the float64 mantissa field width of 52: - // - the optional extra bit is shifted away in step 3 below. - // - the high-order 1 is omitted in float64 "normal" representation; - // - the low-order 1 will be used during rounding then discarded. - exp := alen - blen - var a2, b2 nat - a2 = a2.set(a) - b2 = b2.set(b) - if shift := 54 - exp; shift > 0 { - a2 = a2.shl(a2, uint(shift)) - } else if shift < 0 { - b2 = b2.shl(b2, uint(-shift)) - } - - // 2. Compute quotient and remainder (q, r). NB: due to the - // extra shift, the low-order bit of q is logically the - // high-order bit of r. - var q nat - q, r := q.div(a2, a2, b2) // (recycle a2) - mantissa := low64(q) - haveRem := len(r) > 0 // mantissa&1 && !haveRem => remainder is exactly half - - // 3. If quotient didn't fit in 54 bits, re-do division by b2<<1 - // (in effect---we accomplish this incrementally). - if mantissa>>54 == 1 { - if mantissa&1 == 1 { - haveRem = true - } - mantissa >>= 1 - exp++ - } - if mantissa>>53 != 1 { - panic("expected exactly 54 bits of result") - } - - // 4. Rounding. - if -1022-52 <= exp && exp <= -1022 { - // Denormal case; lose 'shift' bits of precision. - shift := uint64(-1022 - (exp - 1)) // [1..53) - lostbits := mantissa & (1<<shift - 1) - haveRem = haveRem || lostbits != 0 - mantissa >>= shift - exp = -1023 + 2 - } - // Round q using round-half-to-even. - exact = !haveRem - if mantissa&1 != 0 { - exact = false - if haveRem || mantissa&2 != 0 { - if mantissa++; mantissa >= 1<<54 { - // Complete rollover 11...1 => 100...0, so shift is safe - mantissa >>= 1 - exp++ - } - } - } - mantissa >>= 1 // discard rounding bit. Mantissa now scaled by 2^53. - - f = math.Ldexp(float64(mantissa), exp-53) - if math.IsInf(f, 0) { - exact = false - } - return -} - -// Float64 returns the nearest float64 value for x and a bool indicating -// whether f represents x exactly. If the magnitude of x is too large to -// be represented by a float64, f is an infinity and exact is false. -// The sign of f always matches the sign of x, even if f == 0. -func (x *Rat) Float64() (f float64, exact bool) { - b := x.b.abs - if len(b) == 0 { - b = b.set(natOne) // materialize denominator - } - f, exact = quotToFloat(x.a.abs, b) - if x.a.neg { - f = -f - } - return -} - -// SetFrac sets z to a/b and returns z. -func (z *Rat) SetFrac(a, b *Int) *Rat { - z.a.neg = a.neg != b.neg - babs := b.abs - if len(babs) == 0 { - panic("division by zero") - } - if &z.a == b || alias(z.a.abs, babs) { - babs = nat(nil).set(babs) // make a copy - } - z.a.abs = z.a.abs.set(a.abs) - z.b.abs = z.b.abs.set(babs) - return z.norm() -} - -// SetFrac64 sets z to a/b and returns z. -func (z *Rat) SetFrac64(a, b int64) *Rat { - z.a.SetInt64(a) - if b == 0 { - panic("division by zero") - } - if b < 0 { - b = -b - z.a.neg = !z.a.neg - } - z.b.abs = z.b.abs.setUint64(uint64(b)) - return z.norm() -} - -// SetInt sets z to x (by making a copy of x) and returns z. -func (z *Rat) SetInt(x *Int) *Rat { - z.a.Set(x) - z.b.abs = z.b.abs.make(0) - return z -} - -// SetInt64 sets z to x and returns z. -func (z *Rat) SetInt64(x int64) *Rat { - z.a.SetInt64(x) - z.b.abs = z.b.abs.make(0) - return z -} - -// Set sets z to x (by making a copy of x) and returns z. -func (z *Rat) Set(x *Rat) *Rat { - if z != x { - z.a.Set(&x.a) - z.b.Set(&x.b) - } - return z -} - -// Abs sets z to |x| (the absolute value of x) and returns z. -func (z *Rat) Abs(x *Rat) *Rat { - z.Set(x) - z.a.neg = false - return z -} - -// Neg sets z to -x and returns z. -func (z *Rat) Neg(x *Rat) *Rat { - z.Set(x) - z.a.neg = len(z.a.abs) > 0 && !z.a.neg // 0 has no sign - return z -} - -// Inv sets z to 1/x and returns z. -func (z *Rat) Inv(x *Rat) *Rat { - if len(x.a.abs) == 0 { - panic("division by zero") - } - z.Set(x) - a := z.b.abs - if len(a) == 0 { - a = a.set(natOne) // materialize numerator - } - b := z.a.abs - if b.cmp(natOne) == 0 { - b = b.make(0) // normalize denominator - } - z.a.abs, z.b.abs = a, b // sign doesn't change - return z -} - -// Sign returns: -// -// -1 if x < 0 -// 0 if x == 0 -// +1 if x > 0 -// -func (x *Rat) Sign() int { - return x.a.Sign() -} - -// IsInt returns true if the denominator of x is 1. -func (x *Rat) IsInt() bool { - return len(x.b.abs) == 0 || x.b.abs.cmp(natOne) == 0 -} - -// Num returns the numerator of x; it may be <= 0. -// The result is a reference to x's numerator; it -// may change if a new value is assigned to x, and vice versa. -// The sign of the numerator corresponds to the sign of x. -func (x *Rat) Num() *Int { - return &x.a -} - -// Denom returns the denominator of x; it is always > 0. -// The result is a reference to x's denominator; it -// may change if a new value is assigned to x, and vice versa. -func (x *Rat) Denom() *Int { - x.b.neg = false // the result is always >= 0 - if len(x.b.abs) == 0 { - x.b.abs = x.b.abs.set(natOne) // materialize denominator - } - return &x.b -} - -func (z *Rat) norm() *Rat { - switch { - case len(z.a.abs) == 0: - // z == 0 - normalize sign and denominator - z.a.neg = false - z.b.abs = z.b.abs.make(0) - case len(z.b.abs) == 0: - // z is normalized int - nothing to do - case z.b.abs.cmp(natOne) == 0: - // z is int - normalize denominator - z.b.abs = z.b.abs.make(0) - default: - neg := z.a.neg - z.a.neg = false - z.b.neg = false - if f := NewInt(0).binaryGCD(&z.a, &z.b); f.Cmp(intOne) != 0 { - z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f.abs) - z.b.abs, _ = z.b.abs.div(nil, z.b.abs, f.abs) - if z.b.abs.cmp(natOne) == 0 { - // z is int - normalize denominator - z.b.abs = z.b.abs.make(0) - } - } - z.a.neg = neg - } - return z -} - -// mulDenom sets z to the denominator product x*y (by taking into -// account that 0 values for x or y must be interpreted as 1) and -// returns z. -func mulDenom(z, x, y nat) nat { - switch { - case len(x) == 0: - return z.set(y) - case len(y) == 0: - return z.set(x) - } - return z.mul(x, y) -} - -// scaleDenom computes x*f. -// If f == 0 (zero value of denominator), the result is (a copy of) x. -func scaleDenom(x *Int, f nat) *Int { - var z Int - if len(f) == 0 { - return z.Set(x) - } - z.abs = z.abs.mul(x.abs, f) - z.neg = x.neg - return &z -} - -// Cmp compares x and y and returns: -// -// -1 if x < y -// 0 if x == y -// +1 if x > y -// -func (x *Rat) Cmp(y *Rat) int { - return scaleDenom(&x.a, y.b.abs).Cmp(scaleDenom(&y.a, x.b.abs)) -} - -// Add sets z to the sum x+y and returns z. -func (z *Rat) Add(x, y *Rat) *Rat { - a1 := scaleDenom(&x.a, y.b.abs) - a2 := scaleDenom(&y.a, x.b.abs) - z.a.Add(a1, a2) - z.b.abs = mulDenom(z.b.abs, x.b.abs, y.b.abs) - return z.norm() -} - -// Sub sets z to the difference x-y and returns z. -func (z *Rat) Sub(x, y *Rat) *Rat { - a1 := scaleDenom(&x.a, y.b.abs) - a2 := scaleDenom(&y.a, x.b.abs) - z.a.Sub(a1, a2) - z.b.abs = mulDenom(z.b.abs, x.b.abs, y.b.abs) - return z.norm() -} - -// Mul sets z to the product x*y and returns z. -func (z *Rat) Mul(x, y *Rat) *Rat { - z.a.Mul(&x.a, &y.a) - z.b.abs = mulDenom(z.b.abs, x.b.abs, y.b.abs) - return z.norm() -} - -// Quo sets z to the quotient x/y and returns z. -// If y == 0, a division-by-zero run-time panic occurs. -func (z *Rat) Quo(x, y *Rat) *Rat { - if len(y.a.abs) == 0 { - panic("division by zero") - } - a := scaleDenom(&x.a, y.b.abs) - b := scaleDenom(&y.a, x.b.abs) - z.a.abs = a.abs - z.b.abs = b.abs - z.a.neg = a.neg != b.neg - return z.norm() -} - -func ratTok(ch rune) bool { - return strings.IndexRune("+-/0123456789.eE", ch) >= 0 -} - -// Scan is a support routine for fmt.Scanner. It accepts the formats -// 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent. -func (z *Rat) Scan(s fmt.ScanState, ch rune) error { - tok, err := s.Token(true, ratTok) - if err != nil { - return err - } - if strings.IndexRune("efgEFGv", ch) < 0 { - return errors.New("Rat.Scan: invalid verb") - } - if _, ok := z.SetString(string(tok)); !ok { - return errors.New("Rat.Scan: invalid syntax") - } - return nil -} - -// SetString sets z to the value of s and returns z and a boolean indicating -// success. s can be given as a fraction "a/b" or as a floating-point number -// optionally followed by an exponent. If the operation failed, the value of -// z is undefined but the returned value is nil. -func (z *Rat) SetString(s string) (*Rat, bool) { - if len(s) == 0 { - return nil, false - } - - // check for a quotient - sep := strings.Index(s, "/") - if sep >= 0 { - if _, ok := z.a.SetString(s[0:sep], 10); !ok { - return nil, false - } - s = s[sep+1:] - var err error - if z.b.abs, _, err = z.b.abs.scan(strings.NewReader(s), 10); err != nil { - return nil, false - } - return z.norm(), true - } - - // check for a decimal point - sep = strings.Index(s, ".") - // check for an exponent - e := strings.IndexAny(s, "eE") - var exp Int - if e >= 0 { - if e < sep { - // The E must come after the decimal point. - return nil, false - } - if _, ok := exp.SetString(s[e+1:], 10); !ok { - return nil, false - } - s = s[0:e] - } - if sep >= 0 { - s = s[0:sep] + s[sep+1:] - exp.Sub(&exp, NewInt(int64(len(s)-sep))) - } - - if _, ok := z.a.SetString(s, 10); !ok { - return nil, false - } - powTen := nat(nil).expNN(natTen, exp.abs, nil) - if exp.neg { - z.b.abs = powTen - z.norm() - } else { - z.a.abs = z.a.abs.mul(z.a.abs, powTen) - z.b.abs = z.b.abs.make(0) - } - - return z, true -} - -// String returns a string representation of x in the form "a/b" (even if b == 1). -func (x *Rat) String() string { - s := "/1" - if len(x.b.abs) != 0 { - s = "/" + x.b.abs.decimalString() - } - return x.a.String() + s -} - -// RatString returns a string representation of x in the form "a/b" if b != 1, -// and in the form "a" if b == 1. -func (x *Rat) RatString() string { - if x.IsInt() { - return x.a.String() - } - return x.String() -} - -// FloatString returns a string representation of x in decimal form with prec -// digits of precision after the decimal point and the last digit rounded. -func (x *Rat) FloatString(prec int) string { - if x.IsInt() { - s := x.a.String() - if prec > 0 { - s += "." + strings.Repeat("0", prec) - } - return s - } - // x.b.abs != 0 - - q, r := nat(nil).div(nat(nil), x.a.abs, x.b.abs) - - p := natOne - if prec > 0 { - p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil) - } - - r = r.mul(r, p) - r, r2 := r.div(nat(nil), r, x.b.abs) - - // see if we need to round up - r2 = r2.add(r2, r2) - if x.b.abs.cmp(r2) <= 0 { - r = r.add(r, natOne) - if r.cmp(p) >= 0 { - q = nat(nil).add(q, natOne) - r = nat(nil).sub(r, p) - } - } - - s := q.decimalString() - if x.a.neg { - s = "-" + s - } - - if prec > 0 { - rs := r.decimalString() - leadingZeros := prec - len(rs) - s += "." + strings.Repeat("0", leadingZeros) + rs - } - - return s -} - -// Gob codec version. Permits backward-compatible changes to the encoding. -const ratGobVersion byte = 1 - -// GobEncode implements the gob.GobEncoder interface. -func (x *Rat) GobEncode() ([]byte, error) { - if x == nil { - return nil, nil - } - buf := make([]byte, 1+4+(len(x.a.abs)+len(x.b.abs))*_S) // extra bytes for version and sign bit (1), and numerator length (4) - i := x.b.abs.bytes(buf) - j := x.a.abs.bytes(buf[0:i]) - n := i - j - if int(uint32(n)) != n { - // this should never happen - return nil, errors.New("Rat.GobEncode: numerator too large") - } - binary.BigEndian.PutUint32(buf[j-4:j], uint32(n)) - j -= 1 + 4 - b := ratGobVersion << 1 // make space for sign bit - if x.a.neg { - b |= 1 - } - buf[j] = b - return buf[j:], nil -} - -// GobDecode implements the gob.GobDecoder interface. -func (z *Rat) GobDecode(buf []byte) error { - if len(buf) == 0 { - // Other side sent a nil or default value. - *z = Rat{} - return nil - } - b := buf[0] - if b>>1 != ratGobVersion { - return errors.New(fmt.Sprintf("Rat.GobDecode: encoding version %d not supported", b>>1)) - } - const j = 1 + 4 - i := j + binary.BigEndian.Uint32(buf[j-4:j]) - z.a.neg = b&1 != 0 - z.a.abs = z.a.abs.setBytes(buf[j:i]) - z.b.abs = z.b.abs.setBytes(buf[i:]) - return nil -} - -// MarshalText implements the encoding.TextMarshaler interface -func (r *Rat) MarshalText() (text []byte, err error) { - return []byte(r.RatString()), nil -} - -// UnmarshalText implements the encoding.TextUnmarshaler interface -func (r *Rat) UnmarshalText(text []byte) error { - if _, ok := r.SetString(string(text)); !ok { - return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Rat", text) - } - return nil -} diff --git a/src/pkg/math/big/rat_test.go b/src/pkg/math/big/rat_test.go deleted file mode 100644 index 414a67d41..000000000 --- a/src/pkg/math/big/rat_test.go +++ /dev/null @@ -1,994 +0,0 @@ -// Copyright 2010 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. - -package big - -import ( - "bytes" - "encoding/gob" - "encoding/json" - "encoding/xml" - "fmt" - "math" - "strconv" - "strings" - "testing" -) - -func TestZeroRat(t *testing.T) { - var x, y, z Rat - y.SetFrac64(0, 42) - - if x.Cmp(&y) != 0 { - t.Errorf("x and y should be both equal and zero") - } - - if s := x.String(); s != "0/1" { - t.Errorf("got x = %s, want 0/1", s) - } - - if s := x.RatString(); s != "0" { - t.Errorf("got x = %s, want 0", s) - } - - z.Add(&x, &y) - if s := z.RatString(); s != "0" { - t.Errorf("got x+y = %s, want 0", s) - } - - z.Sub(&x, &y) - if s := z.RatString(); s != "0" { - t.Errorf("got x-y = %s, want 0", s) - } - - z.Mul(&x, &y) - if s := z.RatString(); s != "0" { - t.Errorf("got x*y = %s, want 0", s) - } - - // check for division by zero - defer func() { - if s := recover(); s == nil || s.(string) != "division by zero" { - panic(s) - } - }() - z.Quo(&x, &y) -} - -var setStringTests = []struct { - in, out string - ok bool -}{ - {"0", "0", true}, - {"-0", "0", true}, - {"1", "1", true}, - {"-1", "-1", true}, - {"1.", "1", true}, - {"1e0", "1", true}, - {"1.e1", "10", true}, - {in: "1e", ok: false}, - {in: "1.e", ok: false}, - {in: "1e+14e-5", ok: false}, - {in: "1e4.5", ok: false}, - {in: "r", ok: false}, - {in: "a/b", ok: false}, - {in: "a.b", ok: false}, - {"-0.1", "-1/10", true}, - {"-.1", "-1/10", true}, - {"2/4", "1/2", true}, - {".25", "1/4", true}, - {"-1/5", "-1/5", true}, - {"8129567.7690E14", "812956776900000000000", true}, - {"78189e+4", "781890000", true}, - {"553019.8935e+8", "55301989350000", true}, - {"98765432109876543210987654321e-10", "98765432109876543210987654321/10000000000", true}, - {"9877861857500000E-7", "3951144743/4", true}, - {"2169378.417e-3", "2169378417/1000000", true}, - {"884243222337379604041632732738665534", "884243222337379604041632732738665534", true}, - {"53/70893980658822810696", "53/70893980658822810696", true}, - {"106/141787961317645621392", "53/70893980658822810696", true}, - {"204211327800791583.81095", "4084226556015831676219/20000", true}, -} - -func TestRatSetString(t *testing.T) { - for i, test := range setStringTests { - x, ok := new(Rat).SetString(test.in) - - if ok { - if !test.ok { - t.Errorf("#%d SetString(%q) expected failure", i, test.in) - } else if x.RatString() != test.out { - t.Errorf("#%d SetString(%q) got %s want %s", i, test.in, x.RatString(), test.out) - } - } else if x != nil { - t.Errorf("#%d SetString(%q) got %p want nil", i, test.in, x) - } - } -} - -func TestRatScan(t *testing.T) { - var buf bytes.Buffer - for i, test := range setStringTests { - x := new(Rat) - buf.Reset() - buf.WriteString(test.in) - - _, err := fmt.Fscanf(&buf, "%v", x) - if err == nil != test.ok { - if test.ok { - t.Errorf("#%d error: %s", i, err) - } else { - t.Errorf("#%d expected error", i) - } - continue - } - if err == nil && x.RatString() != test.out { - t.Errorf("#%d got %s want %s", i, x.RatString(), test.out) - } - } -} - -var floatStringTests = []struct { - in string - prec int - out string -}{ - {"0", 0, "0"}, - {"0", 4, "0.0000"}, - {"1", 0, "1"}, - {"1", 2, "1.00"}, - {"-1", 0, "-1"}, - {".25", 2, "0.25"}, - {".25", 1, "0.3"}, - {".25", 3, "0.250"}, - {"-1/3", 3, "-0.333"}, - {"-2/3", 4, "-0.6667"}, - {"0.96", 1, "1.0"}, - {"0.999", 2, "1.00"}, - {"0.9", 0, "1"}, - {".25", -1, "0"}, - {".55", -1, "1"}, -} - -func TestFloatString(t *testing.T) { - for i, test := range floatStringTests { - x, _ := new(Rat).SetString(test.in) - - if x.FloatString(test.prec) != test.out { - t.Errorf("#%d got %s want %s", i, x.FloatString(test.prec), test.out) - } - } -} - -func TestRatSign(t *testing.T) { - zero := NewRat(0, 1) - for _, a := range setStringTests { - x, ok := new(Rat).SetString(a.in) - if !ok { - continue - } - s := x.Sign() - e := x.Cmp(zero) - if s != e { - t.Errorf("got %d; want %d for z = %v", s, e, &x) - } - } -} - -var ratCmpTests = []struct { - rat1, rat2 string - out int -}{ - {"0", "0/1", 0}, - {"1/1", "1", 0}, - {"-1", "-2/2", 0}, - {"1", "0", 1}, - {"0/1", "1/1", -1}, - {"-5/1434770811533343057144", "-5/1434770811533343057145", -1}, - {"49832350382626108453/8964749413", "49832350382626108454/8964749413", -1}, - {"-37414950961700930/7204075375675961", "37414950961700930/7204075375675961", -1}, - {"37414950961700930/7204075375675961", "74829901923401860/14408150751351922", 0}, -} - -func TestRatCmp(t *testing.T) { - for i, test := range ratCmpTests { - x, _ := new(Rat).SetString(test.rat1) - y, _ := new(Rat).SetString(test.rat2) - - out := x.Cmp(y) - if out != test.out { - t.Errorf("#%d got out = %v; want %v", i, out, test.out) - } - } -} - -func TestIsInt(t *testing.T) { - one := NewInt(1) - for _, a := range setStringTests { - x, ok := new(Rat).SetString(a.in) - if !ok { - continue - } - i := x.IsInt() - e := x.Denom().Cmp(one) == 0 - if i != e { - t.Errorf("got IsInt(%v) == %v; want %v", x, i, e) - } - } -} - -func TestRatAbs(t *testing.T) { - zero := new(Rat) - for _, a := range setStringTests { - x, ok := new(Rat).SetString(a.in) - if !ok { - continue - } - e := new(Rat).Set(x) - if e.Cmp(zero) < 0 { - e.Sub(zero, e) - } - z := new(Rat).Abs(x) - if z.Cmp(e) != 0 { - t.Errorf("got Abs(%v) = %v; want %v", x, z, e) - } - } -} - -func TestRatNeg(t *testing.T) { - zero := new(Rat) - for _, a := range setStringTests { - x, ok := new(Rat).SetString(a.in) - if !ok { - continue - } - e := new(Rat).Sub(zero, x) - z := new(Rat).Neg(x) - if z.Cmp(e) != 0 { - t.Errorf("got Neg(%v) = %v; want %v", x, z, e) - } - } -} - -func TestRatInv(t *testing.T) { - zero := new(Rat) - for _, a := range setStringTests { - x, ok := new(Rat).SetString(a.in) - if !ok { - continue - } - if x.Cmp(zero) == 0 { - continue // avoid division by zero - } - e := new(Rat).SetFrac(x.Denom(), x.Num()) - z := new(Rat).Inv(x) - if z.Cmp(e) != 0 { - t.Errorf("got Inv(%v) = %v; want %v", x, z, e) - } - } -} - -type ratBinFun func(z, x, y *Rat) *Rat -type ratBinArg struct { - x, y, z string -} - -func testRatBin(t *testing.T, i int, name string, f ratBinFun, a ratBinArg) { - x, _ := new(Rat).SetString(a.x) - y, _ := new(Rat).SetString(a.y) - z, _ := new(Rat).SetString(a.z) - out := f(new(Rat), x, y) - - if out.Cmp(z) != 0 { - t.Errorf("%s #%d got %s want %s", name, i, out, z) - } -} - -var ratBinTests = []struct { - x, y string - sum, prod string -}{ - {"0", "0", "0", "0"}, - {"0", "1", "1", "0"}, - {"-1", "0", "-1", "0"}, - {"-1", "1", "0", "-1"}, - {"1", "1", "2", "1"}, - {"1/2", "1/2", "1", "1/4"}, - {"1/4", "1/3", "7/12", "1/12"}, - {"2/5", "-14/3", "-64/15", "-28/15"}, - {"4707/49292519774798173060", "-3367/70976135186689855734", "84058377121001851123459/1749296273614329067191168098769082663020", "-1760941/388732505247628681598037355282018369560"}, - {"-61204110018146728334/3", "-31052192278051565633/2", "-215564796870448153567/6", "950260896245257153059642991192710872711/3"}, - {"-854857841473707320655/4237645934602118692642972629634714039", "-18/31750379913563777419", "-27/133467566250814981", "15387441146526731771790/134546868362786310073779084329032722548987800600710485341"}, - {"618575745270541348005638912139/19198433543745179392300736", "-19948846211000086/637313996471", "27674141753240653/30123979153216", "-6169936206128396568797607742807090270137721977/6117715203873571641674006593837351328"}, - {"-3/26206484091896184128", "5/2848423294177090248", "15310893822118706237/9330894968229805033368778458685147968", "-5/24882386581946146755650075889827061248"}, - {"26946729/330400702820", "41563965/225583428284", "1238218672302860271/4658307703098666660055", "224002580204097/14906584649915733312176"}, - {"-8259900599013409474/7", "-84829337473700364773/56707961321161574960", "-468402123685491748914621885145127724451/396955729248131024720", "350340947706464153265156004876107029701/198477864624065512360"}, - {"575775209696864/1320203974639986246357", "29/712593081308", "410331716733912717985762465/940768218243776489278275419794956", "808/45524274987585732633"}, - {"1786597389946320496771/2066653520653241", "6269770/1992362624741777", "3559549865190272133656109052308126637/4117523232840525481453983149257", "8967230/3296219033"}, - {"-36459180403360509753/32150500941194292113930", "9381566963714/9633539", "301622077145533298008420642898530153/309723104686531919656937098270", "-3784609207827/3426986245"}, -} - -func TestRatBin(t *testing.T) { - for i, test := range ratBinTests { - arg := ratBinArg{test.x, test.y, test.sum} - testRatBin(t, i, "Add", (*Rat).Add, arg) - - arg = ratBinArg{test.y, test.x, test.sum} - testRatBin(t, i, "Add symmetric", (*Rat).Add, arg) - - arg = ratBinArg{test.sum, test.x, test.y} - testRatBin(t, i, "Sub", (*Rat).Sub, arg) - - arg = ratBinArg{test.sum, test.y, test.x} - testRatBin(t, i, "Sub symmetric", (*Rat).Sub, arg) - - arg = ratBinArg{test.x, test.y, test.prod} - testRatBin(t, i, "Mul", (*Rat).Mul, arg) - - arg = ratBinArg{test.y, test.x, test.prod} - testRatBin(t, i, "Mul symmetric", (*Rat).Mul, arg) - - if test.x != "0" { - arg = ratBinArg{test.prod, test.x, test.y} - testRatBin(t, i, "Quo", (*Rat).Quo, arg) - } - - if test.y != "0" { - arg = ratBinArg{test.prod, test.y, test.x} - testRatBin(t, i, "Quo symmetric", (*Rat).Quo, arg) - } - } -} - -func TestIssue820(t *testing.T) { - x := NewRat(3, 1) - y := NewRat(2, 1) - z := y.Quo(x, y) - q := NewRat(3, 2) - if z.Cmp(q) != 0 { - t.Errorf("got %s want %s", z, q) - } - - y = NewRat(3, 1) - x = NewRat(2, 1) - z = y.Quo(x, y) - q = NewRat(2, 3) - if z.Cmp(q) != 0 { - t.Errorf("got %s want %s", z, q) - } - - x = NewRat(3, 1) - z = x.Quo(x, x) - q = NewRat(3, 3) - if z.Cmp(q) != 0 { - t.Errorf("got %s want %s", z, q) - } -} - -var setFrac64Tests = []struct { - a, b int64 - out string -}{ - {0, 1, "0"}, - {0, -1, "0"}, - {1, 1, "1"}, - {-1, 1, "-1"}, - {1, -1, "-1"}, - {-1, -1, "1"}, - {-9223372036854775808, -9223372036854775808, "1"}, -} - -func TestRatSetFrac64Rat(t *testing.T) { - for i, test := range setFrac64Tests { - x := new(Rat).SetFrac64(test.a, test.b) - if x.RatString() != test.out { - t.Errorf("#%d got %s want %s", i, x.RatString(), test.out) - } - } -} - -func TestRatGobEncoding(t *testing.T) { - var medium bytes.Buffer - enc := gob.NewEncoder(&medium) - dec := gob.NewDecoder(&medium) - for _, test := range encodingTests { - medium.Reset() // empty buffer for each test case (in case of failures) - var tx Rat - tx.SetString(test + ".14159265") - if err := enc.Encode(&tx); err != nil { - t.Errorf("encoding of %s failed: %s", &tx, err) - } - var rx Rat - if err := dec.Decode(&rx); err != nil { - t.Errorf("decoding of %s failed: %s", &tx, err) - } - if rx.Cmp(&tx) != 0 { - t.Errorf("transmission of %s failed: got %s want %s", &tx, &rx, &tx) - } - } -} - -// Sending a nil Rat pointer (inside a slice) on a round trip through gob should yield a zero. -// TODO: top-level nils. -func TestGobEncodingNilRatInSlice(t *testing.T) { - buf := new(bytes.Buffer) - enc := gob.NewEncoder(buf) - dec := gob.NewDecoder(buf) - - var in = make([]*Rat, 1) - err := enc.Encode(&in) - if err != nil { - t.Errorf("gob encode failed: %q", err) - } - var out []*Rat - err = dec.Decode(&out) - if err != nil { - t.Fatalf("gob decode failed: %q", err) - } - if len(out) != 1 { - t.Fatalf("wrong len; want 1 got %d", len(out)) - } - var zero Rat - if out[0].Cmp(&zero) != 0 { - t.Errorf("transmission of (*Int)(nill) failed: got %s want 0", out) - } -} - -var ratNums = []string{ - "-141592653589793238462643383279502884197169399375105820974944592307816406286", - "-1415926535897932384626433832795028841971", - "-141592653589793", - "-1", - "0", - "1", - "141592653589793", - "1415926535897932384626433832795028841971", - "141592653589793238462643383279502884197169399375105820974944592307816406286", -} - -var ratDenoms = []string{ - "1", - "718281828459045", - "7182818284590452353602874713526624977572", - "718281828459045235360287471352662497757247093699959574966967627724076630353", -} - -func TestRatJSONEncoding(t *testing.T) { - for _, num := range ratNums { - for _, denom := range ratDenoms { - var tx Rat - tx.SetString(num + "/" + denom) - b, err := json.Marshal(&tx) - if err != nil { - t.Errorf("marshaling of %s failed: %s", &tx, err) - continue - } - var rx Rat - if err := json.Unmarshal(b, &rx); err != nil { - t.Errorf("unmarshaling of %s failed: %s", &tx, err) - continue - } - if rx.Cmp(&tx) != 0 { - t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx) - } - } - } -} - -func TestRatXMLEncoding(t *testing.T) { - for _, num := range ratNums { - for _, denom := range ratDenoms { - var tx Rat - tx.SetString(num + "/" + denom) - b, err := xml.Marshal(&tx) - if err != nil { - t.Errorf("marshaling of %s failed: %s", &tx, err) - continue - } - var rx Rat - if err := xml.Unmarshal(b, &rx); err != nil { - t.Errorf("unmarshaling of %s failed: %s", &tx, err) - continue - } - if rx.Cmp(&tx) != 0 { - t.Errorf("XML encoding of %s failed: got %s want %s", &tx, &rx, &tx) - } - } - } -} - -func TestIssue2379(t *testing.T) { - // 1) no aliasing - q := NewRat(3, 2) - x := new(Rat) - x.SetFrac(NewInt(3), NewInt(2)) - if x.Cmp(q) != 0 { - t.Errorf("1) got %s want %s", x, q) - } - - // 2) aliasing of numerator - x = NewRat(2, 3) - x.SetFrac(NewInt(3), x.Num()) - if x.Cmp(q) != 0 { - t.Errorf("2) got %s want %s", x, q) - } - - // 3) aliasing of denominator - x = NewRat(2, 3) - x.SetFrac(x.Denom(), NewInt(2)) - if x.Cmp(q) != 0 { - t.Errorf("3) got %s want %s", x, q) - } - - // 4) aliasing of numerator and denominator - x = NewRat(2, 3) - x.SetFrac(x.Denom(), x.Num()) - if x.Cmp(q) != 0 { - t.Errorf("4) got %s want %s", x, q) - } - - // 5) numerator and denominator are the same - q = NewRat(1, 1) - x = new(Rat) - n := NewInt(7) - x.SetFrac(n, n) - if x.Cmp(q) != 0 { - t.Errorf("5) got %s want %s", x, q) - } -} - -func TestIssue3521(t *testing.T) { - a := new(Int) - b := new(Int) - a.SetString("64375784358435883458348587", 0) - b.SetString("4789759874531", 0) - - // 0) a raw zero value has 1 as denominator - zero := new(Rat) - one := NewInt(1) - if zero.Denom().Cmp(one) != 0 { - t.Errorf("0) got %s want %s", zero.Denom(), one) - } - - // 1a) a zero value remains zero independent of denominator - x := new(Rat) - x.Denom().Set(new(Int).Neg(b)) - if x.Cmp(zero) != 0 { - t.Errorf("1a) got %s want %s", x, zero) - } - - // 1b) a zero value may have a denominator != 0 and != 1 - x.Num().Set(a) - qab := new(Rat).SetFrac(a, b) - if x.Cmp(qab) != 0 { - t.Errorf("1b) got %s want %s", x, qab) - } - - // 2a) an integral value becomes a fraction depending on denominator - x.SetFrac64(10, 2) - x.Denom().SetInt64(3) - q53 := NewRat(5, 3) - if x.Cmp(q53) != 0 { - t.Errorf("2a) got %s want %s", x, q53) - } - - // 2b) an integral value becomes a fraction depending on denominator - x = NewRat(10, 2) - x.Denom().SetInt64(3) - if x.Cmp(q53) != 0 { - t.Errorf("2b) got %s want %s", x, q53) - } - - // 3) changing the numerator/denominator of a Rat changes the Rat - x.SetFrac(a, b) - a = x.Num() - b = x.Denom() - a.SetInt64(5) - b.SetInt64(3) - if x.Cmp(q53) != 0 { - t.Errorf("3) got %s want %s", x, q53) - } -} - -// Test inputs to Rat.SetString. The prefix "long:" causes the test -// to be skipped in --test.short mode. (The threshold is about 500us.) -var float64inputs = []string{ - // Constants plundered from strconv/testfp.txt. - - // Table 1: Stress Inputs for Conversion to 53-bit Binary, < 1/2 ULP - "5e+125", - "69e+267", - "999e-026", - "7861e-034", - "75569e-254", - "928609e-261", - "9210917e+080", - "84863171e+114", - "653777767e+273", - "5232604057e-298", - "27235667517e-109", - "653532977297e-123", - "3142213164987e-294", - "46202199371337e-072", - "231010996856685e-073", - "9324754620109615e+212", - "78459735791271921e+049", - "272104041512242479e+200", - "6802601037806061975e+198", - "20505426358836677347e-221", - "836168422905420598437e-234", - "4891559871276714924261e+222", - - // Table 2: Stress Inputs for Conversion to 53-bit Binary, > 1/2 ULP - "9e-265", - "85e-037", - "623e+100", - "3571e+263", - "81661e+153", - "920657e-023", - "4603285e-024", - "87575437e-309", - "245540327e+122", - "6138508175e+120", - "83356057653e+193", - "619534293513e+124", - "2335141086879e+218", - "36167929443327e-159", - "609610927149051e-255", - "3743626360493413e-165", - "94080055902682397e-242", - "899810892172646163e+283", - "7120190517612959703e+120", - "25188282901709339043e-252", - "308984926168550152811e-052", - "6372891218502368041059e+064", - - // Table 14: Stress Inputs for Conversion to 24-bit Binary, <1/2 ULP - "5e-20", - "67e+14", - "985e+15", - "7693e-42", - "55895e-16", - "996622e-44", - "7038531e-32", - "60419369e-46", - "702990899e-20", - "6930161142e-48", - "25933168707e+13", - "596428896559e+20", - - // Table 15: Stress Inputs for Conversion to 24-bit Binary, >1/2 ULP - "3e-23", - "57e+18", - "789e-35", - "2539e-18", - "76173e+28", - "887745e-11", - "5382571e-37", - "82381273e-35", - "750486563e-38", - "3752432815e-39", - "75224575729e-45", - "459926601011e+15", - - // Constants plundered from strconv/atof_test.go. - - "0", - "1", - "+1", - "1e23", - "1E23", - "100000000000000000000000", - "1e-100", - "123456700", - "99999999999999974834176", - "100000000000000000000001", - "100000000000000008388608", - "100000000000000016777215", - "100000000000000016777216", - "-1", - "-0.1", - "-0", // NB: exception made for this input - "1e-20", - "625e-3", - - // largest float64 - "1.7976931348623157e308", - "-1.7976931348623157e308", - // next float64 - too large - "1.7976931348623159e308", - "-1.7976931348623159e308", - // the border is ...158079 - // borderline - okay - "1.7976931348623158e308", - "-1.7976931348623158e308", - // borderline - too large - "1.797693134862315808e308", - "-1.797693134862315808e308", - - // a little too large - "1e308", - "2e308", - "1e309", - - // way too large - "1e310", - "-1e310", - "1e400", - "-1e400", - "long:1e400000", - "long:-1e400000", - - // denormalized - "1e-305", - "1e-306", - "1e-307", - "1e-308", - "1e-309", - "1e-310", - "1e-322", - // smallest denormal - "5e-324", - "4e-324", - "3e-324", - // too small - "2e-324", - // way too small - "1e-350", - "long:1e-400000", - // way too small, negative - "-1e-350", - "long:-1e-400000", - - // try to overflow exponent - // [Disabled: too slow and memory-hungry with rationals.] - // "1e-4294967296", - // "1e+4294967296", - // "1e-18446744073709551616", - // "1e+18446744073709551616", - - // http://www.exploringbinary.com/java-hangs-when-converting-2-2250738585072012e-308/ - "2.2250738585072012e-308", - // http://www.exploringbinary.com/php-hangs-on-numeric-value-2-2250738585072011e-308/ - - "2.2250738585072011e-308", - - // A very large number (initially wrongly parsed by the fast algorithm). - "4.630813248087435e+307", - - // A different kind of very large number. - "22.222222222222222", - "long:2." + strings.Repeat("2", 4000) + "e+1", - - // Exactly halfway between 1 and math.Nextafter(1, 2). - // Round to even (down). - "1.00000000000000011102230246251565404236316680908203125", - // Slightly lower; still round down. - "1.00000000000000011102230246251565404236316680908203124", - // Slightly higher; round up. - "1.00000000000000011102230246251565404236316680908203126", - // Slightly higher, but you have to read all the way to the end. - "long:1.00000000000000011102230246251565404236316680908203125" + strings.Repeat("0", 10000) + "1", - - // Smallest denormal, 2^(-1022-52) - "4.940656458412465441765687928682213723651e-324", - // Half of smallest denormal, 2^(-1022-53) - "2.470328229206232720882843964341106861825e-324", - // A little more than the exact half of smallest denormal - // 2^-1075 + 2^-1100. (Rounds to 1p-1074.) - "2.470328302827751011111470718709768633275e-324", - // The exact halfway between smallest normal and largest denormal: - // 2^-1022 - 2^-1075. (Rounds to 2^-1022.) - "2.225073858507201136057409796709131975935e-308", - - "1152921504606846975", // 1<<60 - 1 - "-1152921504606846975", // -(1<<60 - 1) - "1152921504606846977", // 1<<60 + 1 - "-1152921504606846977", // -(1<<60 + 1) - - "1/3", -} - -func TestFloat64SpecialCases(t *testing.T) { - for _, input := range float64inputs { - if strings.HasPrefix(input, "long:") { - if testing.Short() { - continue - } - input = input[len("long:"):] - } - - r, ok := new(Rat).SetString(input) - if !ok { - t.Errorf("Rat.SetString(%q) failed", input) - continue - } - f, exact := r.Float64() - - // 1. Check string -> Rat -> float64 conversions are - // consistent with strconv.ParseFloat. - // Skip this check if the input uses "a/b" rational syntax. - if !strings.Contains(input, "/") { - e, _ := strconv.ParseFloat(input, 64) - - // Careful: negative Rats too small for - // float64 become -0, but Rat obviously cannot - // preserve the sign from SetString("-0"). - switch { - case math.Float64bits(e) == math.Float64bits(f): - // Ok: bitwise equal. - case f == 0 && r.Num().BitLen() == 0: - // Ok: Rat(0) is equivalent to both +/- float64(0). - default: - t.Errorf("strconv.ParseFloat(%q) = %g (%b), want %g (%b); delta = %g", input, e, e, f, f, f-e) - } - } - - if !isFinite(f) { - continue - } - - // 2. Check f is best approximation to r. - if !checkIsBestApprox(t, f, r) { - // Append context information. - t.Errorf("(input was %q)", input) - } - - // 3. Check f->R->f roundtrip is non-lossy. - checkNonLossyRoundtrip(t, f) - - // 4. Check exactness using slow algorithm. - if wasExact := new(Rat).SetFloat64(f).Cmp(r) == 0; wasExact != exact { - t.Errorf("Rat.SetString(%q).Float64().exact = %t, want %t", input, exact, wasExact) - } - } -} - -func TestFloat64Distribution(t *testing.T) { - // Generate a distribution of (sign, mantissa, exp) values - // broader than the float64 range, and check Rat.Float64() - // always picks the closest float64 approximation. - var add = []int64{ - 0, - 1, - 3, - 5, - 7, - 9, - 11, - } - var winc, einc = uint64(1), int(1) // soak test (~75s on x86-64) - if testing.Short() { - winc, einc = 10, 500 // quick test (~12ms on x86-64) - } - - for _, sign := range "+-" { - for _, a := range add { - for wid := uint64(0); wid < 60; wid += winc { - b := int64(1<<wid + a) - if sign == '-' { - b = -b - } - for exp := -1100; exp < 1100; exp += einc { - num, den := NewInt(b), NewInt(1) - if exp > 0 { - num.Lsh(num, uint(exp)) - } else { - den.Lsh(den, uint(-exp)) - } - r := new(Rat).SetFrac(num, den) - f, _ := r.Float64() - - if !checkIsBestApprox(t, f, r) { - // Append context information. - t.Errorf("(input was mantissa %#x, exp %d; f = %g (%b); f ~ %g; r = %v)", - b, exp, f, f, math.Ldexp(float64(b), exp), r) - } - - checkNonLossyRoundtrip(t, f) - } - } - } - } -} - -// TestFloat64NonFinite checks that SetFloat64 of a non-finite value -// returns nil. -func TestSetFloat64NonFinite(t *testing.T) { - for _, f := range []float64{math.NaN(), math.Inf(+1), math.Inf(-1)} { - var r Rat - if r2 := r.SetFloat64(f); r2 != nil { - t.Errorf("SetFloat64(%g) was %v, want nil", f, r2) - } - } -} - -// checkNonLossyRoundtrip checks that a float->Rat->float roundtrip is -// non-lossy for finite f. -func checkNonLossyRoundtrip(t *testing.T, f float64) { - if !isFinite(f) { - return - } - r := new(Rat).SetFloat64(f) - if r == nil { - t.Errorf("Rat.SetFloat64(%g (%b)) == nil", f, f) - return - } - f2, exact := r.Float64() - if f != f2 || !exact { - t.Errorf("Rat.SetFloat64(%g).Float64() = %g (%b), %v, want %g (%b), %v; delta = %b", - f, f2, f2, exact, f, f, true, f2-f) - } -} - -// delta returns the absolute difference between r and f. -func delta(r *Rat, f float64) *Rat { - d := new(Rat).Sub(r, new(Rat).SetFloat64(f)) - return d.Abs(d) -} - -// checkIsBestApprox checks that f is the best possible float64 -// approximation of r. -// Returns true on success. -func checkIsBestApprox(t *testing.T, f float64, r *Rat) bool { - if math.Abs(f) >= math.MaxFloat64 { - // Cannot check +Inf, -Inf, nor the float next to them (MaxFloat64). - // But we have tests for these special cases. - return true - } - - // r must be strictly between f0 and f1, the floats bracketing f. - f0 := math.Nextafter(f, math.Inf(-1)) - f1 := math.Nextafter(f, math.Inf(+1)) - - // For f to be correct, r must be closer to f than to f0 or f1. - df := delta(r, f) - df0 := delta(r, f0) - df1 := delta(r, f1) - if df.Cmp(df0) > 0 { - t.Errorf("Rat(%v).Float64() = %g (%b), but previous float64 %g (%b) is closer", r, f, f, f0, f0) - return false - } - if df.Cmp(df1) > 0 { - t.Errorf("Rat(%v).Float64() = %g (%b), but next float64 %g (%b) is closer", r, f, f, f1, f1) - return false - } - if df.Cmp(df0) == 0 && !isEven(f) { - t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f0, f0) - return false - } - if df.Cmp(df1) == 0 && !isEven(f) { - t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f1, f1) - return false - } - return true -} - -func isEven(f float64) bool { return math.Float64bits(f)&1 == 0 } - -func TestIsFinite(t *testing.T) { - finites := []float64{ - 1.0 / 3, - 4891559871276714924261e+222, - math.MaxFloat64, - math.SmallestNonzeroFloat64, - -math.MaxFloat64, - -math.SmallestNonzeroFloat64, - } - for _, f := range finites { - if !isFinite(f) { - t.Errorf("!IsFinite(%g (%b))", f, f) - } - } - nonfinites := []float64{ - math.NaN(), - math.Inf(-1), - math.Inf(+1), - } - for _, f := range nonfinites { - if isFinite(f) { - t.Errorf("IsFinite(%g, (%b))", f, f) - } - } -} |