summaryrefslogtreecommitdiff
path: root/src/pkg/big
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/big')
-rw-r--r--src/pkg/big/Makefile2
-rw-r--r--src/pkg/big/arith.go228
-rw-r--r--src/pkg/big/arith_arm.s289
-rw-r--r--src/pkg/big/arith_test.go197
-rwxr-xr-xsrc/pkg/big/int.go69
-rwxr-xr-xsrc/pkg/big/int_test.go453
-rwxr-xr-xsrc/pkg/big/nat.go24
-rwxr-xr-xsrc/pkg/big/nat_test.go162
-rw-r--r--src/pkg/big/rat.go136
-rw-r--r--src/pkg/big/rat_test.go219
10 files changed, 1041 insertions, 738 deletions
diff --git a/src/pkg/big/Makefile b/src/pkg/big/Makefile
index 7a4311dca..3d4b56d78 100644
--- a/src/pkg/big/Makefile
+++ b/src/pkg/big/Makefile
@@ -2,7 +2,7 @@
# Use of this source code is governed by a BSD-style
# license that can be found in the LICENSE file.
-include ../../Make.$(GOARCH)
+include ../../Make.inc
TARG=big
GOFILES=\
diff --git a/src/pkg/big/arith.go b/src/pkg/big/arith.go
index 29966c7bc..df3808f5e 100644
--- a/src/pkg/big/arith.go
+++ b/src/pkg/big/arith.go
@@ -56,161 +56,29 @@ func subWW_g(x, y, c Word) (z1, z0 Word) {
// z1<<_W + z0 = x*y
+// Adapted from Warren, Hacker's Delight, p. 132.
func mulWW_g(x, y Word) (z1, z0 Word) {
- // Split x and y into 2 halfWords each, multiply
- // the halfWords separately while avoiding overflow,
- // and return the product as 2 Words.
-
- if x < y {
- x, y = y, x
- }
-
- if x < _B2 {
- // y < _B2 because y <= x
- // sub-digits of x and y are (0, x) and (0, y)
- // z = z[0] = x*y
- z0 = x * y
- return
- }
-
- if y < _B2 {
- // sub-digits of x and y are (x1, x0) and (0, y)
- // x = (x1*_B2 + x0)
- // y = (y1*_B2 + y0)
- x1, x0 := x>>_W2, x&_M2
-
- // x*y = t2*_B2*_B2 + t1*_B2 + t0
- t0 := x0 * y
- t1 := x1 * y
-
- // compute result digits but avoid overflow
- // z = z[1]*_B + z[0] = x*y
- z0 = t1<<_W2 + t0
- z1 = (t1 + t0>>_W2) >> _W2
- return
- }
-
- // general case
- // sub-digits of x and y are (x1, x0) and (y1, y0)
- // x = (x1*_B2 + x0)
- // y = (y1*_B2 + y0)
- x1, x0 := x>>_W2, x&_M2
- y1, y0 := y>>_W2, y&_M2
-
- // x*y = t2*_B2*_B2 + t1*_B2 + t0
- t0 := x0 * y0
- // t1 := x1*y0 + x0*y1;
- var c Word
- t1 := x1 * y0
- t1a := t1
- t1 += x0 * y1
- if t1 < t1a {
- c++
- }
- t2 := x1*y1 + c*_B2
-
- // compute result digits but avoid overflow
- // z = z[1]*_B + z[0] = x*y
- // This may overflow, but that's ok because we also sum t1 and t0 above
- // and we take care of the overflow there.
- z0 = t1<<_W2 + t0
-
- // z1 = t2 + (t1 + t0>>_W2)>>_W2;
- var c3 Word
- z1 = t1 + t0>>_W2
- if z1 < t1 {
- c3++
- }
- z1 >>= _W2
- z1 += c3 * _B2
- z1 += t2
+ 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) {
- // Split x and y into 2 halfWords each, multiply
- // the halfWords separately while avoiding overflow,
- // and return the product as 2 Words.
-
- // TODO(gri) Should implement special cases for faster execution.
-
- // general case
- // sub-digits of x, y, and c are (x1, x0), (y1, y0), (c1, c0)
- // x = (x1*_B2 + x0)
- // y = (y1*_B2 + y0)
- x1, x0 := x>>_W2, x&_M2
- y1, y0 := y>>_W2, y&_M2
- c1, c0 := c>>_W2, c&_M2
-
- // x*y + c = t2*_B2*_B2 + t1*_B2 + t0
- // (1<<32-1)^2 == 1<<64 - 1<<33 + 1, so there's space to add c0 in here.
- t0 := x0*y0 + c0
-
- // t1 := x1*y0 + x0*y1 + c1;
- var c2 Word // extra carry
- t1 := x1*y0 + c1
- t1a := t1
- t1 += x0 * y1
- if t1 < t1a { // If the number got smaller then we overflowed.
- c2++
+ z1, zz0 := mulWW(x, y)
+ if z0 = zz0 + c; z0 < zz0 {
+ z1++
}
-
- t2 := x1*y1 + c2*_B2
-
- // compute result digits but avoid overflow
- // z = z[1]*_B + z[0] = x*y
- // z0 = t1<<_W2 + t0;
- // This may overflow, but that's ok because we also sum t1 and t0 below
- // and we take care of the overflow there.
- z0 = t1<<_W2 + t0
-
- var c3 Word
- z1 = t1 + t0>>_W2
- if z1 < t1 {
- c3++
- }
- z1 >>= _W2
- z1 += t2 + c3*_B2
-
- return
-}
-
-
-// q = (x1<<_W + x0 - r)/y
-// The most significant bit of y must be 1.
-func divStep(x1, x0, y Word) (q, r Word) {
- d1, d0 := y>>_W2, y&_M2
- q1, r1 := x1/d1, x1%d1
- m := q1 * d0
- r1 = r1*_B2 | x0>>_W2
- if r1 < m {
- q1--
- r1 += y
- if r1 >= y && r1 < m {
- q1--
- r1 += y
- }
- }
- r1 -= m
-
- r0 := r1 % d1
- q0 := r1 / d1
- m = q0 * d0
- r0 = r0*_B2 | x0&_M2
- if r0 < m {
- q0--
- r0 += y
- if r0 >= y && r0 < m {
- q0--
- r0 += y
- }
- }
- r0 -= m
-
- q = q1*_B2 | q0
- r = r0
return
}
@@ -241,46 +109,48 @@ func leadingZeros(x Word) uint {
}
-// q = (x1<<_W + x0 - r)/y
-func divWW_g(x1, x0, y Word) (q, r Word) {
- if x1 == 0 {
- q, r = x0/y, x0%y
- return
+// 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
}
- var q0, q1 Word
- z := leadingZeros(y)
- if y > x1 {
- if z != 0 {
- y <<= z
- x1 = (x1 << z) | (x0 >> (_W - z))
- x0 <<= z
- }
- q0, x0 = divStep(x1, x0, y)
- q1 = 0
- } else {
- if z == 0 {
- x1 -= y
- q1 = 1
- } else {
- z1 := _W - z
- y <<= z
- x2 := x1 >> z1
- x1 = (x1 << z) | (x0 >> z1)
- x0 <<= z
- q1, x1 = divStep(x2, x1, y)
- }
+ 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
- q0, x0 = divStep(x1, x0, y)
+again1:
+ if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
+ q1--
+ rhat += vn1
+ if rhat < _B2 {
+ goto again1
+ }
}
- r = x0 >> z
+ un21 := un32*_B2 + un1 - q1*v
+ q0 := un21 / vn1
+ rhat = un21 - q0*vn1
- if q1 != 0 {
- panic("div out of range")
+again2:
+ if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
+ q0--
+ rhat += vn1
+ if rhat < _B2 {
+ goto again2
+ }
}
- return q0, r
+ return q1*_B2 + q0, (un21*_B2 + un0 - q0*v) >> s
}
diff --git a/src/pkg/big/arith_arm.s b/src/pkg/big/arith_arm.s
index c8a45efc4..e4a9a962c 100644
--- a/src/pkg/big/arith_arm.s
+++ b/src/pkg/big/arith_arm.s
@@ -5,31 +5,302 @@
// This file provides fast assembly versions for the elementary
// arithmetic operations on vectors implemented in arith.go.
-// TODO(gri) Implement these routines.
+#define CFLAG 29 // bit position of carry flag
+
+// func addVV(z, x, y []Word) (c Word)
TEXT ·addVV(SB),7,$0
- B ·addVV_g(SB)
+ MOVW $0, R0
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW y+24(FP), R3
+ MOVW n+4(FP), R4
+ MOVW R4<<2, R4
+ ADD R1, R4
+ B E1
+L1:
+ MOVW.P 4(R2), R5
+ MOVW.P 4(R3), R6
+ MOVW R0, CPSR
+ ADC.S R6, R5
+ MOVW.P R5, 4(R1)
+ MOVW CPSR, R0
+E1:
+ CMP R1, R4
+ BNE L1
+
+ MOVW R0>>CFLAG, R0
+ AND $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),7,$0
- B ·subVV_g(SB)
+ MOVW $(1<<CFLAG), R0
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW y+24(FP), R3
+ MOVW n+4(FP), R4
+ MOVW R4<<2, R4
+ ADD R1, R4
+ B E2
+L2:
+ MOVW.P 4(R2), R5
+ MOVW.P 4(R3), R6
+ MOVW R0, CPSR
+ SBC.S R6, R5
+ MOVW.P R5, 4(R1)
+ MOVW CPSR, R0
+E2:
+ CMP R1, R4
+ BNE L2
+
+ MOVW R0>>CFLAG, R0
+ AND $1, R0
+ EOR $1, R0
+ MOVW R0, c+36(FP)
+ RET
+
+// func addVW(z, x []Word, y Word) (c Word)
TEXT ·addVW(SB),7,$0
- B ·addVW_g(SB)
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW y+24(FP), R3
+ MOVW n+4(FP), R4
+ MOVW R4<<2, R4
+ ADD R1, R4
+ CMP 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)
+ MOVW CPSR, R0
+ B E3
+L3:
+ MOVW.P 4(R2), R5
+ MOVW R0, CPSR
+ ADC.S $0, R5
+ MOVW.P R5, 4(R1)
+ MOVW CPSR, R0
+E3:
+ CMP R1, R4
+ BNE L3
+
+ MOVW R0>>CFLAG, R0
+ AND $1, R0
+ MOVW R0, c+28(FP)
+ RET
+
TEXT ·subVW(SB),7,$0
- B ·subVW_g(SB)
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW y+24(FP), R3
+ MOVW n+4(FP), R4
+ MOVW R4<<2, R4
+ ADD R1, R4
+ CMP 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)
+ MOVW CPSR, R0
+ B E4
+L4:
+ MOVW.P 4(R2), R5
+ MOVW R0, CPSR
+ SBC.S $0, R5
+ MOVW.P R5, 4(R1)
+ MOVW CPSR, R0
+E4:
+ CMP R1, R4
+ BNE L4
+
+ MOVW R0>>CFLAG, R0
+ AND $1, R0
+ EOR $1, R0
+ MOVW R0, c+28(FP)
+ RET
+
+// func shlVW(z, x []Word, s Word) (c Word)
TEXT ·shlVW(SB),7,$0
- B ·shlVW_g(SB)
+ MOVW n+4(FP), R5
+ CMP $0, R5
+ BEQ X7
+
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW R5<<2, R5
+ ADD R5, R2
+ ADD R1, R5
+ MOVW s+24(FP), R3
+ CMP $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:
+ CMP 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)
+ CMP R1, R5
+ BNE Y7
+
+X7:
+ MOVW $0, R1
+ MOVW R1, c+28(FP)
+ RET
+
TEXT ·shrVW(SB),7,$0
- B ·shrVW_g(SB)
+ MOVW n+4(FP), R5
+ CMP $0, R5
+ BEQ X6
+
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW R5<<2, R5
+ ADD R1, R5
+ MOVW s+24(FP), R3
+ CMP $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:
+ CMP 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)
+ CMP R1, R5
+ BNE Y6
+
+X6:
+ MOVW $0, R1
+ MOVW R1, c+28(FP)
+ RET
+
TEXT ·mulAddVWW(SB),7,$0
- B ·mulAddVWW_g(SB)
+ MOVW $0, R0
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW y+24(FP), R3
+ MOVW r+28(FP), R4
+ MOVW n+4(FP), R5
+ MOVW R5<<2, R5
+ ADD 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:
+ CMP R1, R5
+ BNE L8
+
+ MOVW R4, c+32(FP)
+ RET
+
TEXT ·addMulVVW(SB),7,$0
- B ·addMulVVW_g(SB)
+ MOVW $0, R0
+ MOVW z+0(FP), R1
+ MOVW x+12(FP), R2
+ MOVW y+24(FP), R3
+ MOVW n+4(FP), R5
+ MOVW R5<<2, R5
+ ADD 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:
+ CMP R1, R5
+ BNE L9
+
+ MOVW R4, c+28(FP)
+ RET
+
TEXT ·divWVW(SB),7,$0
+ // ARM has no multiword division, so use portable code.
B ·divWVW_g(SB)
+
+TEXT ·divWW(SB),7,$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),7,$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
diff --git a/src/pkg/big/arith_test.go b/src/pkg/big/arith_test.go
index efdb65123..934b302df 100644
--- a/src/pkg/big/arith_test.go
+++ b/src/pkg/big/arith_test.go
@@ -13,17 +13,17 @@ type argWW struct {
}
var sumWW = []argWW{
- argWW{0, 0, 0, 0, 0},
- argWW{0, 1, 0, 0, 1},
- argWW{0, 0, 1, 0, 1},
- argWW{0, 1, 1, 0, 2},
- argWW{12345, 67890, 0, 0, 80235},
- argWW{12345, 67890, 1, 0, 80236},
- argWW{_M, 1, 0, 1, 0},
- argWW{_M, 0, 1, 1, 0},
- argWW{_M, 1, 1, 1, 1},
- argWW{_M, _M, 0, 1, _M - 1},
- argWW{_M, _M, 1, 1, _M},
+ {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},
}
@@ -59,15 +59,15 @@ type argVV struct {
}
var sumVV = []argVV{
- argVV{},
- argVV{nat{0}, nat{0}, nat{0}, 0},
- argVV{nat{1}, nat{1}, nat{0}, 0},
- argVV{nat{0}, nat{_M}, nat{1}, 1},
- argVV{nat{80235}, nat{12345}, nat{67890}, 0},
- argVV{nat{_M - 1}, nat{_M}, nat{_M}, 1},
- argVV{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
- argVV{nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
- argVV{nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
+ {},
+ {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},
}
@@ -115,57 +115,58 @@ type argVW struct {
}
var sumVW = []argVW{
- argVW{},
- argVW{nat{0}, nat{0}, 0, 0},
- argVW{nat{1}, nat{0}, 1, 0},
- argVW{nat{1}, nat{1}, 0, 0},
- argVW{nat{0}, nat{_M}, 1, 1},
- argVW{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
+ {},
+ {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{
- argVW{},
- argVW{nat{0}, nat{0}, 0, 0},
- argVW{nat{0}, nat{_M}, 0, 0},
- argVW{nat{0}, nat{0}, _M, 0},
- argVW{nat{1}, nat{1}, 1, 0},
- argVW{nat{22793}, nat{991}, 23, 0},
- argVW{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0},
- argVW{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0},
- argVW{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0},
- argVW{nat{_M << 1 & _M}, nat{_M}, 1 << 1, _M >> (_W - 1)},
- argVW{nat{_M << 7 & _M}, nat{_M}, 1 << 7, _M >> (_W - 7)},
- argVW{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, _M >> (_W - 7)},
+ {},
+ {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{
- argVW{},
- argVW{nat{0}, nat{0}, 0, 0},
- argVW{nat{0}, nat{0}, 1, 0},
- argVW{nat{0}, nat{0}, 20, 0},
-
- argVW{nat{_M}, nat{_M}, 0, 0},
- argVW{nat{_M << 1 & _M}, nat{_M}, 1, 1},
- argVW{nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
-
- argVW{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
- argVW{nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
- argVW{nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
+ {},
+ {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{
- argVW{},
- argVW{nat{0}, nat{0}, 0, 0},
- argVW{nat{0}, nat{0}, 1, 0},
- argVW{nat{0}, nat{0}, 20, 0},
-
- argVW{nat{_M}, nat{_M}, 0, 0},
- argVW{nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
- argVW{nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
-
- argVW{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
- argVW{nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
- argVW{nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
+ {},
+ {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},
}
@@ -217,29 +218,29 @@ type argVWW struct {
}
var prodVWW = []argVWW{
- argVWW{},
- argVWW{nat{0}, nat{0}, 0, 0, 0},
- argVWW{nat{991}, nat{0}, 0, 991, 0},
- argVWW{nat{0}, nat{_M}, 0, 0, 0},
- argVWW{nat{991}, nat{_M}, 0, 991, 0},
- argVWW{nat{0}, nat{0}, _M, 0, 0},
- argVWW{nat{991}, nat{0}, _M, 991, 0},
- argVWW{nat{1}, nat{1}, 1, 0, 0},
- argVWW{nat{992}, nat{1}, 1, 991, 0},
- argVWW{nat{22793}, nat{991}, 23, 0, 0},
- argVWW{nat{22800}, nat{991}, 23, 7, 0},
- argVWW{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
- argVWW{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
- argVWW{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
- argVWW{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
- argVWW{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
- argVWW{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
- argVWW{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
- argVWW{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
- argVWW{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
- argVWW{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
- argVWW{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
- argVWW{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
+ {},
+ {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)},
}
@@ -300,15 +301,12 @@ func TestFunVWW(t *testing.T) {
}
-type mulWWTest struct {
+var mulWWTests = []struct {
x, y Word
q, r Word
-}
-
-
-var mulWWTests = []mulWWTest{
- mulWWTest{_M, _M, _M - 1, 1},
- // 32 bit only: mulWWTest{0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
+}{
+ {_M, _M, _M - 1, 1},
+ // 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
}
@@ -322,18 +320,15 @@ func TestMulWW(t *testing.T) {
}
-type mulAddWWWTest struct {
+var mulAddWWWTests = []struct {
x, y, c Word
q, r Word
-}
-
-
-var mulAddWWWTests = []mulAddWWWTest{
+}{
// TODO(agl): These will only work on 64-bit platforms.
- // mulAddWWWTest{15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
- // mulAddWWWTest{15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
- mulAddWWWTest{_M, _M, 0, _M - 1, 1},
- mulAddWWWTest{_M, _M, _M, _M, 0},
+ // {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
+ // {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
+ {_M, _M, 0, _M - 1, 1},
+ {_M, _M, _M, _M, 0},
}
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go
index 873d5b50c..46e008734 100755
--- a/src/pkg/big/int.go
+++ b/src/pkg/big/int.go
@@ -6,8 +6,10 @@
package big
-import "fmt"
-
+import (
+ "fmt"
+ "rand"
+)
// An Int represents a signed multi-precision integer.
// The zero value for an Int represents the value 0.
@@ -20,6 +22,23 @@ type Int struct {
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
@@ -47,6 +66,14 @@ func (z *Int) Set(x *Int) *Int {
}
+// Abs sets z to |x| (the absolute value of x) and returns z.
+func (z *Int) Abs(x *Int) *Int {
+ z.abs = z.abs.set(x.abs)
+ z.neg = false
+ return z
+}
+
+
// Neg sets z to -x and returns z.
func (z *Int) Neg(x *Int) *Int {
z.abs = z.abs.set(x.abs)
@@ -347,10 +374,12 @@ func (z *Int) SetString(s string, base int) (*Int, bool) {
return z, false
}
- neg := false
- if s[0] == '-' {
- neg = true
+ neg := s[0] == '-'
+ if neg || s[0] == '+' {
s = s[1:]
+ if len(s) == 0 {
+ return z, false
+ }
}
var scanned int
@@ -518,6 +547,18 @@ func ProbablyPrime(z *Int, n int) bool {
}
+// 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 {
@@ -563,7 +604,7 @@ func (z *Int) And(x, y *Int) *Int {
if x.neg {
// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
x1 := nat{}.sub(x.abs, natOne)
- y1 := z.abs.sub(y.abs, natOne)
+ y1 := nat{}.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
@@ -581,7 +622,7 @@ func (z *Int) And(x, y *Int) *Int {
}
// x & (-y) == x & ^(y-1) == x &^ (y-1)
- y1 := z.abs.sub(y.abs, natOne)
+ y1 := nat{}.sub(y.abs, natOne)
z.abs = z.abs.andNot(x.abs, y1)
z.neg = false
return z
@@ -594,7 +635,7 @@ func (z *Int) AndNot(x, y *Int) *Int {
if x.neg {
// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
x1 := nat{}.sub(x.abs, natOne)
- y1 := z.abs.sub(y.abs, natOne)
+ y1 := nat{}.sub(y.abs, natOne)
z.abs = z.abs.andNot(y1, x1)
z.neg = false
return z
@@ -608,14 +649,14 @@ func (z *Int) AndNot(x, y *Int) *Int {
if x.neg {
// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
- x1 := z.abs.sub(x.abs, natOne)
+ x1 := nat{}.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 := z.abs.add(y.abs, natOne)
+ y1 := nat{}.add(y.abs, natOne)
z.abs = z.abs.and(x.abs, y1)
z.neg = false
return z
@@ -628,7 +669,7 @@ func (z *Int) Or(x, y *Int) *Int {
if x.neg {
// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
x1 := nat{}.sub(x.abs, natOne)
- y1 := z.abs.sub(y.abs, natOne)
+ y1 := nat{}.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
@@ -646,7 +687,7 @@ func (z *Int) Or(x, y *Int) *Int {
}
// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
- y1 := z.abs.sub(y.abs, natOne)
+ y1 := nat{}.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
@@ -659,7 +700,7 @@ func (z *Int) Xor(x, y *Int) *Int {
if x.neg {
// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
x1 := nat{}.sub(x.abs, natOne)
- y1 := z.abs.sub(y.abs, natOne)
+ y1 := nat{}.sub(y.abs, natOne)
z.abs = z.abs.xor(x1, y1)
z.neg = false
return z
@@ -677,7 +718,7 @@ func (z *Int) Xor(x, y *Int) *Int {
}
// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
- y1 := z.abs.sub(y.abs, natOne)
+ y1 := nat{}.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
diff --git a/src/pkg/big/int_test.go b/src/pkg/big/int_test.go
index 269c814d4..fc981e1da 100755
--- a/src/pkg/big/int_test.go
+++ b/src/pkg/big/int_test.go
@@ -29,24 +29,36 @@ type argZZ struct {
var sumZZ = []argZZ{
- argZZ{NewInt(0), NewInt(0), NewInt(0)},
- argZZ{NewInt(1), NewInt(1), NewInt(0)},
- argZZ{NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
- argZZ{NewInt(-1), NewInt(-1), NewInt(0)},
- argZZ{NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
- argZZ{NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
+ {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{
- argZZ{NewInt(0), NewInt(0), NewInt(0)},
- argZZ{NewInt(0), NewInt(1), NewInt(0)},
- argZZ{NewInt(1), NewInt(1), NewInt(1)},
- argZZ{NewInt(-991 * 991), NewInt(991), NewInt(-991)},
+ {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
@@ -61,11 +73,28 @@ func TestSetZ(t *testing.T) {
}
+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("msg: %v is not normalized", z, msg)
+ t.Errorf("%s%v is not normalized", z, msg)
}
if (&z).Cmp(a.z) != 0 {
t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
@@ -157,28 +186,25 @@ func TestMul(t *testing.T) {
}
-type mulRangeZ struct {
+var mulRangesZ = []struct {
a, b int64
prod string
-}
-
-
-var mulRangesZ = []mulRangeZ{
+}{
// entirely positive ranges are covered by mulRangesN
- mulRangeZ{-1, 1, "0"},
- mulRangeZ{-2, -1, "2"},
- mulRangeZ{-3, -2, "6"},
- mulRangeZ{-3, -1, "-6"},
- mulRangeZ{1, 3, "6"},
- mulRangeZ{-10, -10, "-10"},
- mulRangeZ{0, -1, "1"}, // empty range
- mulRangeZ{-1, -100, "1"}, // empty range
- mulRangeZ{-1, 1, "0"}, // range includes 0
- mulRangeZ{-1e9, 0, "0"}, // range includes 0
- mulRangeZ{-1e9, 1e9, "0"}, // range includes 0
- mulRangeZ{-10, -1, "3628800"}, // 10!
- mulRangeZ{-20, -2, "-2432902008176640000"}, // -20!
- mulRangeZ{-99, -1,
+ {-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!
@@ -205,50 +231,52 @@ func TestMulRangeZ(t *testing.T) {
}
-type stringTest struct {
+var stringTests = []struct {
in string
out string
base int
val int64
ok bool
-}
-
-
-var stringTests = []stringTest{
- stringTest{in: "", ok: false},
- stringTest{in: "a", ok: false},
- stringTest{in: "z", ok: false},
- stringTest{in: "+", ok: false},
- stringTest{in: "0b", ok: false},
- stringTest{in: "0x", ok: false},
- stringTest{in: "2", base: 2, ok: false},
- stringTest{in: "0b2", base: 0, ok: false},
- stringTest{in: "08", ok: false},
- stringTest{in: "8", base: 8, ok: false},
- stringTest{in: "0xg", base: 0, ok: false},
- stringTest{in: "g", base: 16, ok: false},
- stringTest{"0", "0", 0, 0, true},
- stringTest{"0", "0", 10, 0, true},
- stringTest{"0", "0", 16, 0, true},
- stringTest{"10", "10", 0, 10, true},
- stringTest{"10", "10", 10, 10, true},
- stringTest{"10", "10", 16, 16, true},
- stringTest{"-10", "-10", 16, -16, true},
- stringTest{"0x10", "16", 0, 16, true},
- stringTest{in: "0x10", base: 16, ok: false},
- stringTest{"-0x10", "-16", 0, -16, true},
- stringTest{"00", "0", 0, 0, true},
- stringTest{"0", "0", 8, 0, true},
- stringTest{"07", "7", 0, 7, true},
- stringTest{"7", "7", 8, 7, true},
- stringTest{"023", "19", 0, 19, true},
- stringTest{"23", "23", 8, 19, true},
- stringTest{"cafebabe", "cafebabe", 16, 0xcafebabe, true},
- stringTest{"0b0", "0", 0, 0, true},
- stringTest{"-111", "-111", 2, -7, true},
- stringTest{"-0b111", "-7", 0, -7, true},
- stringTest{"0b1001010111", "599", 0, 0x257, true},
- stringTest{"1001010111", "1001010111", 2, 0x257, true},
+}{
+ {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},
}
@@ -276,13 +304,13 @@ func TestGetString(t *testing.T) {
if test.base == 10 {
s := z.String()
if s != test.out {
- t.Errorf("#%da got %s; want %s\n", i, 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\n", i, s, test.out)
+ t.Errorf("#%db got %s; want %s", i, s, test.out)
}
}
}
@@ -310,30 +338,27 @@ func TestSetString(t *testing.T) {
}
if n1.Cmp(expected) != 0 {
- t.Errorf("#%d (input '%s') got: %s want: %d\n", i, test.in, n1, test.val)
+ 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\n", i, test.in, n2, test.val)
+ t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
}
}
}
-type divisionSignsTest struct {
+// 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
-}
-
-
-// Examples from the Go Language Spec, section "Arithmetic operators"
-var divisionSignsTests = []divisionSignsTest{
- divisionSignsTest{5, 3, 1, 2, 1, 2},
- divisionSignsTest{-5, 3, -1, -2, -2, 1},
- divisionSignsTest{5, -3, -1, 2, -1, 2},
- divisionSignsTest{-5, -3, 1, -2, 2, 1},
- divisionSignsTest{1, 2, 0, 1, 0, 1},
- divisionSignsTest{8, 4, 2, 0, 2, 0},
+}{
+ {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},
}
@@ -454,20 +479,17 @@ func checkQuo(x, y []byte) bool {
}
-type quoTest struct {
+var quoTests = []struct {
x, y string
q, r string
-}
-
-
-var quoTests = []quoTest{
- quoTest{
+}{
+ {
"476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
"9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
"50911",
"1",
},
- quoTest{
+ {
"11510768301994997771168",
"1328165573307167369775",
"8",
@@ -517,25 +539,22 @@ func TestQuoStepD6(t *testing.T) {
}
-type bitLenTest struct {
+var bitLenTests = []struct {
in string
out int
-}
-
-
-var bitLenTests = []bitLenTest{
- bitLenTest{"-1", 1},
- bitLenTest{"0", 0},
- bitLenTest{"1", 1},
- bitLenTest{"2", 2},
- bitLenTest{"4", 3},
- bitLenTest{"0xabc", 12},
- bitLenTest{"0x8000", 16},
- bitLenTest{"0x80000000", 32},
- bitLenTest{"0x800000000000", 48},
- bitLenTest{"0x8000000000000000", 64},
- bitLenTest{"0x80000000000000000000", 80},
- bitLenTest{"-0x4000000000000000000000", 87},
+}{
+ {"-1", 1},
+ {"0", 0},
+ {"1", 1},
+ {"2", 2},
+ {"4", 3},
+ {"0xabc", 12},
+ {"0x8000", 16},
+ {"0x80000000", 32},
+ {"0x800000000000", 48},
+ {"0x8000000000000000", 64},
+ {"0x80000000000000000000", 80},
+ {"-0x4000000000000000000000", 87},
}
@@ -548,32 +567,29 @@ func TestBitLen(t *testing.T) {
}
if n := x.BitLen(); n != test.out {
- t.Errorf("#%d got %d want %d\n", i, n, test.out)
+ t.Errorf("#%d got %d want %d", i, n, test.out)
}
}
}
-type expTest struct {
+var expTests = []struct {
x, y, m string
out string
-}
-
-
-var expTests = []expTest{
- expTest{"5", "0", "", "1"},
- expTest{"-5", "0", "", "-1"},
- expTest{"5", "1", "", "5"},
- expTest{"-5", "1", "", "-5"},
- expTest{"-2", "3", "2", "0"},
- expTest{"5", "2", "", "25"},
- expTest{"1", "65537", "2", "1"},
- expTest{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
- expTest{"0x8000000000000000", "2", "6719", "4944"},
- expTest{"0x8000000000000000", "3", "6719", "5447"},
- expTest{"0x8000000000000000", "1000", "6719", "1603"},
- expTest{"0x8000000000000000", "1000000", "6719", "3199"},
- expTest{
+}{
+ {"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"},
+ {
"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
"298472983472983471903246121093472394872319615612417471234712061",
"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
@@ -630,14 +646,11 @@ func checkGcd(aBytes, bBytes []byte) bool {
}
-type gcdTest struct {
+var gcdTests = []struct {
a, b int64
d, x, y int64
-}
-
-
-var gcdTests = []gcdTest{
- gcdTest{120, 23, 1, -9, 47},
+}{
+ {120, 23, 1, -9, 47},
}
@@ -726,30 +739,30 @@ type intShiftTest struct {
var rshTests = []intShiftTest{
- intShiftTest{"0", 0, "0"},
- intShiftTest{"-0", 0, "0"},
- intShiftTest{"0", 1, "0"},
- intShiftTest{"0", 2, "0"},
- intShiftTest{"1", 0, "1"},
- intShiftTest{"1", 1, "0"},
- intShiftTest{"1", 2, "0"},
- intShiftTest{"2", 0, "2"},
- intShiftTest{"2", 1, "1"},
- intShiftTest{"-1", 0, "-1"},
- intShiftTest{"-1", 1, "-1"},
- intShiftTest{"-1", 10, "-1"},
- intShiftTest{"-100", 2, "-25"},
- intShiftTest{"-100", 3, "-13"},
- intShiftTest{"-100", 100, "-1"},
- intShiftTest{"4294967296", 0, "4294967296"},
- intShiftTest{"4294967296", 1, "2147483648"},
- intShiftTest{"4294967296", 2, "1073741824"},
- intShiftTest{"18446744073709551616", 0, "18446744073709551616"},
- intShiftTest{"18446744073709551616", 1, "9223372036854775808"},
- intShiftTest{"18446744073709551616", 2, "4611686018427387904"},
- intShiftTest{"18446744073709551616", 64, "1"},
- intShiftTest{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
- intShiftTest{"340282366920938463463374607431768211456", 128, "1"},
+ {"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"},
}
@@ -786,25 +799,25 @@ func TestRshSelf(t *testing.T) {
var lshTests = []intShiftTest{
- intShiftTest{"0", 0, "0"},
- intShiftTest{"0", 1, "0"},
- intShiftTest{"0", 2, "0"},
- intShiftTest{"1", 0, "1"},
- intShiftTest{"1", 1, "2"},
- intShiftTest{"1", 2, "4"},
- intShiftTest{"2", 0, "2"},
- intShiftTest{"2", 1, "4"},
- intShiftTest{"2", 2, "8"},
- intShiftTest{"-87", 1, "-174"},
- intShiftTest{"4294967296", 0, "4294967296"},
- intShiftTest{"4294967296", 1, "8589934592"},
- intShiftTest{"4294967296", 2, "17179869184"},
- intShiftTest{"18446744073709551616", 0, "18446744073709551616"},
- intShiftTest{"9223372036854775808", 1, "18446744073709551616"},
- intShiftTest{"4611686018427387904", 2, "18446744073709551616"},
- intShiftTest{"1", 64, "18446744073709551616"},
- intShiftTest{"18446744073709551616", 64, "340282366920938463463374607431768211456"},
- intShiftTest{"1", 128, "340282366920938463463374607431768211456"},
+ {"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"},
}
@@ -894,26 +907,24 @@ func TestInt64(t *testing.T) {
}
-type bitwiseTest struct {
+var bitwiseTests = []struct {
x, y string
and, or, xor, andNot string
-}
-
-var bitwiseTests = []bitwiseTest{
- bitwiseTest{"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
- bitwiseTest{"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
- bitwiseTest{"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
- bitwiseTest{"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
- bitwiseTest{"-0xAF", "-0x50", "0x00", "-0xFF", "-0x01", "-0x01"},
- bitwiseTest{"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
- bitwiseTest{"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
- bitwiseTest{"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
- bitwiseTest{"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
- bitwiseTest{"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
- bitwiseTest{"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
- bitwiseTest{"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
- bitwiseTest{"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
- bitwiseTest{
+}{
+ {"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",
@@ -921,7 +932,7 @@ var bitwiseTests = []bitwiseTest{
"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
"0x8c40c2d8822caa04120b8321400",
},
- bitwiseTest{
+ {
"0x1000009dc6e3d9822cba04129bcbe3401",
"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
"0x8c40c2d8822caa04120b8321401",
@@ -929,7 +940,7 @@ var bitwiseTests = []bitwiseTest{
"-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
"0x1000001186210100001000009048c2000",
},
- bitwiseTest{
+ {
"-0x1000009dc6e3d9822cba04129bcbe3401",
"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
"-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
@@ -944,24 +955,24 @@ 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, 16)
+ expected.SetString(exp, 0)
out := f(new(Int), x, y)
if out.Cmp(expected) != 0 {
- println("Test failed")
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, 16)
+ expected.SetString(exp, 0)
- x = f(x, x, y)
- if x.Cmp(expected) != 0 {
- println("Test failed")
- t.Errorf("%s: got %s want %s", msg, x, expected)
+ self = f(self, self, y)
+ if self.Cmp(expected) != 0 {
+ t.Errorf("%s: got %s want %s", msg, self, expected)
}
}
@@ -970,8 +981,8 @@ func TestBitwise(t *testing.T) {
x := new(Int)
y := new(Int)
for _, test := range bitwiseTests {
- x.SetString(test.x, 16)
- y.SetString(test.y, 16)
+ 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)
@@ -985,18 +996,16 @@ func TestBitwise(t *testing.T) {
}
-type notTest struct {
+var notTests = []struct {
in string
out string
-}
-
-var notTests = []notTest{
- notTest{"0", "-1"},
- notTest{"1", "-2"},
- notTest{"7", "-8"},
- notTest{"0", "-1"},
- notTest{"-81910", "81909"},
- notTest{
+}{
+ {"0", "-1"},
+ {"1", "-2"},
+ {"7", "-8"},
+ {"0", "-1"},
+ {"-81910", "81909"},
+ {
"298472983472983471903246121093472394872319615612417471234712061",
"-298472983472983471903246121093472394872319615612417471234712062",
},
@@ -1021,15 +1030,13 @@ func TestNot(t *testing.T) {
}
-type modInverseTest struct {
+var modInverseTests = []struct {
element string
prime string
-}
-
-var modInverseTests = []modInverseTest{
- modInverseTest{"1", "7"},
- modInverseTest{"1", "13"},
- modInverseTest{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
+}{
+ {"1", "7"},
+ {"1", "13"},
+ {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
}
func TestModInverse(t *testing.T) {
diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go
index dc2e6be28..a308f69e8 100755
--- a/src/pkg/big/nat.go
+++ b/src/pkg/big/nat.go
@@ -103,9 +103,7 @@ func (z nat) setUint64(x uint64) nat {
func (z nat) set(x nat) nat {
z = z.make(len(x))
- for i, d := range x {
- z[i] = d
- }
+ copy(z, x)
return z
}
@@ -666,7 +664,7 @@ func (z nat) scan(s string, base int) (nat, int, int) {
}
}
- return z, base, i
+ return z.norm(), base, i
}
@@ -818,13 +816,13 @@ func (z nat) or(x, y nat) nat {
n, m = m, n
s = y
}
- // n >= m
+ // m >= n
- z = z.make(n)
- for i := 0; i < m; i++ {
+ z = z.make(m)
+ for i := 0; i < n; i++ {
z[i] = x[i] | y[i]
}
- copy(z[m:n], s[m:n])
+ copy(z[n:m], s[n:m])
return z.norm()
}
@@ -834,17 +832,17 @@ func (z nat) xor(x, y nat) nat {
m := len(x)
n := len(y)
s := x
- if n < m {
+ if m < n {
n, m = m, n
s = y
}
- // n >= m
+ // m >= n
- z = z.make(n)
- for i := 0; i < m; i++ {
+ z = z.make(m)
+ for i := 0; i < n; i++ {
z[i] = x[i] ^ y[i]
}
- copy(z[m:n], s[m:n])
+ copy(z[n:m], s[n:m])
return z.norm()
}
diff --git a/src/pkg/big/nat_test.go b/src/pkg/big/nat_test.go
index 8545981c0..0bcb94554 100755
--- a/src/pkg/big/nat_test.go
+++ b/src/pkg/big/nat_test.go
@@ -6,27 +6,24 @@ package big
import "testing"
-type cmpTest struct {
+var cmpTests = []struct {
x, y nat
r int
-}
-
-
-var cmpTests = []cmpTest{
- cmpTest{nil, nil, 0},
- cmpTest{nil, nat{}, 0},
- cmpTest{nat{}, nil, 0},
- cmpTest{nat{}, nat{}, 0},
- cmpTest{nat{0}, nat{0}, 0},
- cmpTest{nat{0}, nat{1}, -1},
- cmpTest{nat{1}, nat{0}, 1},
- cmpTest{nat{1}, nat{1}, 0},
- cmpTest{nat{0, _M}, nat{1}, 1},
- cmpTest{nat{1}, nat{0, _M}, -1},
- cmpTest{nat{1, _M}, nat{0, _M}, 1},
- cmpTest{nat{0, _M}, nat{1, _M}, -1},
- cmpTest{nat{16, 571956, 8794, 68}, nat{837, 9146, 1, 754489}, -1},
- cmpTest{nat{34986, 41, 105, 1957}, nat{56, 7458, 104, 1957}, 1},
+}{
+ {nil, nil, 0},
+ {nil, nat{}, 0},
+ {nat{}, nil, 0},
+ {nat{}, nat{}, 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},
}
@@ -47,24 +44,24 @@ type argNN struct {
var sumNN = []argNN{
- argNN{},
- argNN{nat{1}, nil, nat{1}},
- argNN{nat{1111111110}, nat{123456789}, nat{987654321}},
- argNN{nat{0, 0, 0, 1}, nil, nat{0, 0, 0, 1}},
- argNN{nat{0, 0, 0, 1111111110}, nat{0, 0, 0, 123456789}, nat{0, 0, 0, 987654321}},
- argNN{nat{0, 0, 0, 1}, nat{0, 0, _M}, nat{0, 0, 1}},
+ {},
+ {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{
- argNN{},
- argNN{nil, nil, nil},
- argNN{nil, nat{991}, nil},
- argNN{nat{991}, nat{991}, nat{1}},
- argNN{nat{991 * 991}, nat{991}, nat{991}},
- argNN{nat{0, 0, 991 * 991}, nat{0, 991}, nat{0, 991}},
- argNN{nat{1 * 991, 2 * 991, 3 * 991, 4 * 991}, nat{1, 2, 3, 4}, nat{991}},
- argNN{nat{4, 11, 20, 30, 20, 11, 4}, nat{1, 2, 3, 4}, nat{4, 3, 2, 1}},
+ {},
+ {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}},
}
@@ -111,25 +108,22 @@ func TestFunNN(t *testing.T) {
}
-type mulRangeN struct {
+var mulRangesN = []struct {
a, b uint64
prod string
-}
-
-
-var mulRangesN = []mulRangeN{
- mulRangeN{0, 0, "0"},
- mulRangeN{1, 1, "1"},
- mulRangeN{1, 2, "2"},
- mulRangeN{1, 3, "6"},
- mulRangeN{10, 10, "10"},
- mulRangeN{0, 100, "0"},
- mulRangeN{0, 1e9, "0"},
- mulRangeN{1, 0, "1"}, // empty range
- mulRangeN{100, 1, "1"}, // empty range
- mulRangeN{1, 10, "3628800"}, // 10!
- mulRangeN{1, 20, "2432902008176640000"}, // 20!
- mulRangeN{1, 100,
+}{
+ {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!
@@ -173,18 +167,15 @@ func BenchmarkMul(b *testing.B) {
}
-type str struct {
+var tab = []struct {
x nat
b int
s string
-}
-
-
-var tab = []str{
- str{nil, 10, "0"},
- str{nat{1}, 10, "1"},
- str{nat{10}, 10, "10"},
- str{nat{1234567890}, 10, "1234567890"},
+}{
+ {nil, 10, "0"},
+ {nat{1}, 10, "1"},
+ {nat{10}, 10, "10"},
+ {nat{1234567890}, 10, "1234567890"},
}
@@ -228,12 +219,12 @@ type shiftTest struct {
var leftShiftTests = []shiftTest{
- shiftTest{nil, 0, nil},
- shiftTest{nil, 1, nil},
- shiftTest{natOne, 0, natOne},
- shiftTest{natOne, 1, natTwo},
- shiftTest{nat{1 << (_W - 1)}, 1, nat{0}},
- shiftTest{nat{1 << (_W - 1), 0}, 1, nat{0, 1}},
+ {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}},
}
@@ -252,13 +243,13 @@ func TestShiftLeft(t *testing.T) {
var rightShiftTests = []shiftTest{
- shiftTest{nil, 0, nil},
- shiftTest{nil, 1, nil},
- shiftTest{natOne, 0, natOne},
- shiftTest{natOne, 1, nil},
- shiftTest{natTwo, 1, natOne},
- shiftTest{nat{0, 1}, 1, nat{1 << (_W - 1)}},
- shiftTest{nat{2, 1, 1}, 1, nat{1<<(_W-1) + 1, 1 << (_W - 1)}},
+ {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)}},
}
@@ -284,12 +275,12 @@ type modWTest struct {
var modWTests32 = []modWTest{
- modWTest{"23492635982634928349238759823742", "252341", "220170"},
+ {"23492635982634928349238759823742", "252341", "220170"},
}
var modWTests64 = []modWTest{
- modWTest{"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
+ {"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
}
@@ -301,7 +292,7 @@ func runModWTests(t *testing.T, tests []modWTest) {
r := in.abs.modW(d.abs[0])
if r != out.abs[0] {
- t.Errorf("#%d failed: got %s want %s\n", i, r, out)
+ t.Errorf("#%d failed: got %s want %s", i, r, out)
}
}
}
@@ -322,26 +313,23 @@ func TestTrailingZeroBits(t *testing.T) {
x--
for i := 0; i < _W; i++ {
if trailingZeroBits(x) != i {
- t.Errorf("Failed at step %d: x: %x got: %d\n", i, x, trailingZeroBits(x))
+ t.Errorf("Failed at step %d: x: %x got: %d", i, x, trailingZeroBits(x))
}
x <<= 1
}
}
-type expNNTest struct {
+var expNNTests = []struct {
x, y, m string
out string
-}
-
-
-var expNNTests = []expNNTest{
- expNNTest{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
- expNNTest{"0x8000000000000000", "2", "6719", "4944"},
- expNNTest{"0x8000000000000000", "3", "6719", "5447"},
- expNNTest{"0x8000000000000000", "1000", "6719", "1603"},
- expNNTest{"0x8000000000000000", "1000000", "6719", "3199"},
- expNNTest{
+}{
+ {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
+ {"0x8000000000000000", "2", "6719", "4944"},
+ {"0x8000000000000000", "3", "6719", "5447"},
+ {"0x8000000000000000", "1000", "6719", "1603"},
+ {"0x8000000000000000", "1000000", "6719", "3199"},
+ {
"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
"298472983472983471903246121093472394872319615612417471234712061",
"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
diff --git a/src/pkg/big/rat.go b/src/pkg/big/rat.go
index ddd858d5c..e70673a1c 100644
--- a/src/pkg/big/rat.go
+++ b/src/pkg/big/rat.go
@@ -35,9 +35,8 @@ func (z *Rat) SetFrac(a, b *Int) *Rat {
func (z *Rat) SetFrac64(a, b int64) *Rat {
z.a.SetInt64(a)
if b < 0 {
- z.b.setUint64(uint64(-b))
+ b = -b
z.a.neg = !z.a.neg
- return z.norm()
}
z.b = z.b.setUint64(uint64(b))
return z.norm()
@@ -60,6 +59,23 @@ func (z *Rat) SetInt64(x int64) *Rat {
}
+// 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) == 1 && x.b[0] == 1
+}
+
+
// Num returns the numerator of z; it may be <= 0.
// The result is a reference to z's numerator; it
// may change if a new value is assigned to z.
@@ -126,6 +142,14 @@ func (x *Rat) Cmp(y *Rat) (r int) {
}
+// Abs sets z to |x| (the absolute value of x) and returns z.
+func (z *Rat) Abs(x *Rat) *Rat {
+ z.a.Abs(&x.a)
+ z.b = z.b.set(x.b)
+ return z
+}
+
+
// Add sets z to the sum x+y and returns z.
func (z *Rat) Add(x, y *Rat) *Rat {
a1 := mulNat(&x.a, y.b)
@@ -186,26 +210,17 @@ func (z *Rat) Set(x *Rat) *Rat {
// 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 decimal number "a.b".
-// If the operation failed, the value of z is undefined.
+// 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.
func (z *Rat) SetString(s string) (*Rat, bool) {
if len(s) == 0 {
return z, false
}
- // Check for a decimal point
- sep := strings.Index(s, ".")
- if sep < 0 {
- // Check for a quotient
- sep = strings.Index(s, "/")
- if sep < 0 {
- // Just read in the string as an integer
- if _, ok := z.a.SetString(s, 10); !ok {
- return z, false
- }
- z.b = z.b.setWord(1)
- return z, true
- }
+ // check for a quotient
+ sep := strings.Index(s, "/")
+ if sep >= 0 {
if _, ok := z.a.SetString(s[0:sep], 10); !ok {
return z, false
}
@@ -214,59 +229,98 @@ func (z *Rat) SetString(s string) (*Rat, bool) {
if z.b, _, n = z.b.scan(s, 10); n != len(s) {
return z, false
}
-
return z.norm(), true
}
- s = s[0:sep] + s[sep+1:]
+ // 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 z, false
+ }
+ if _, ok := exp.SetString(s[e+1:], 10); !ok {
+ return z, 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 z, false
}
- z.b = z.b.expNN(natTen, nat{Word(len(s) - sep)}, nil)
+ powTen := nat{}.expNN(natTen, exp.abs, nil)
+ if exp.neg {
+ z.b = powTen
+ z.norm()
+ } else {
+ z.a.abs = z.a.abs.mul(z.a.abs, powTen)
+ z.b = z.b.setWord(1)
+ }
- return z.norm(), true
+ return z, true
}
-// String returns a string representation of z in the form "a/b".
+// String returns a string representation of z in the form "a/b" (even if b == 1).
func (z *Rat) String() string {
- s := z.a.String()
- if len(z.b) == 1 && z.b[0] == 1 {
- return s
+ return z.a.String() + "/" + z.b.string(10)
+}
+
+
+// RatString returns a string representation of z in the form "a/b" if b != 1,
+// and in the form "a" if b == 1.
+func (z *Rat) RatString() string {
+ if z.IsInt() {
+ return z.a.String()
}
- return s + "/" + z.b.string(10)
+ return z.String()
}
// FloatString returns a string representation of z in decimal form with prec
// digits of precision after the decimal point and the last digit rounded.
func (z *Rat) FloatString(prec int) string {
- q, r := nat{}.div(nat{}, z.a.abs, z.b)
-
- s := ""
- if z.a.neg {
- s = "-"
+ if z.IsInt() {
+ return z.a.String()
}
- s += q.string(10)
- if len(z.b) == 1 && z.b[0] == 1 {
- return s
+ q, r := nat{}.div(nat{}, z.a.abs, z.b)
+
+ p := natOne
+ if prec > 0 {
+ p = nat{}.expNN(natTen, nat{}.setUint64(uint64(prec)), nil)
}
- p := nat{}.expNN(natTen, nat{Word(prec)}, nil)
r = r.mul(r, p)
r, r2 := r.div(nat{}, r, z.b)
- // See if we need to round up
- r2 = r2.mul(r2, natTwo)
+ // see if we need to round up
+ r2 = r2.add(r2, r2)
if z.b.cmp(r2) <= 0 {
r = r.add(r, natOne)
+ if r.cmp(p) >= 0 {
+ q = nat{}.add(q, natOne)
+ r = nat{}.sub(r, p)
+ }
}
- rs := r.string(10)
- leadingZeros := prec - len(rs)
- s += "." + strings.Repeat("0", leadingZeros) + rs
- s = strings.TrimRight(s, "0")
+ s := q.string(10)
+ if z.a.neg {
+ s = "-" + s
+ }
+
+ if prec > 0 {
+ rs := r.string(10)
+ leadingZeros := prec - len(rs)
+ s += "." + strings.Repeat("0", leadingZeros) + rs
+ }
return s
}
diff --git a/src/pkg/big/rat_test.go b/src/pkg/big/rat_test.go
index 2379cc0d5..8f42949b0 100644
--- a/src/pkg/big/rat_test.go
+++ b/src/pkg/big/rat_test.go
@@ -7,57 +7,71 @@ package big
import "testing"
-type setStringTest struct {
+var setStringTests = []struct {
in, out string
ok bool
-}
-
-var setStringTests = []setStringTest{
- setStringTest{"0", "0", true},
- setStringTest{"-0", "0", true},
- setStringTest{"1", "1", true},
- setStringTest{"-1", "-1", true},
- setStringTest{in: "r", ok: false},
- setStringTest{in: "a/b", ok: false},
- setStringTest{in: "a.b", ok: false},
- setStringTest{"-0.1", "-1/10", true},
- setStringTest{"-.1", "-1/10", true},
- setStringTest{"2/4", "1/2", true},
- setStringTest{".25", "1/4", true},
- setStringTest{"-1/5", "-1/5", true},
- setStringTest{"884243222337379604041632732738665534", "884243222337379604041632732738665534", true},
- setStringTest{"53/70893980658822810696", "53/70893980658822810696", true},
- setStringTest{"106/141787961317645621392", "53/70893980658822810696", true},
- setStringTest{"204211327800791583.81095", "4084226556015831676219/20000", true},
+}{
+ {"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 != test.ok || ok && x.String() != test.out {
- t.Errorf("#%d got %s want %s", i, x.String(), test.out)
+ if ok != test.ok || ok && x.RatString() != test.out {
+ t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
}
}
}
-type floatStringTest struct {
+var floatStringTests = []struct {
in string
prec int
out string
-}
-
-var floatStringTests = []floatStringTest{
- floatStringTest{"0", 0, "0"},
- floatStringTest{"0", 4, "0"},
- floatStringTest{"1", 0, "1"},
- floatStringTest{"1", 2, "1"},
- floatStringTest{"-1", 0, "-1"},
- floatStringTest{".25", 2, "0.25"},
- floatStringTest{".25", 1, "0.3"},
- floatStringTest{"-1/3", 3, "-0.333"},
- floatStringTest{"-2/3", 4, "-0.6667"},
+}{
+ {"0", 0, "0"},
+ {"0", 4, "0"},
+ {"1", 0, "1"},
+ {"1", 2, "1"},
+ {"-1", 0, "-1"},
+ {".25", 2, "0.25"},
+ {".25", 1, "0.3"},
+ {"-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) {
@@ -71,21 +85,33 @@ func TestFloatString(t *testing.T) {
}
-type ratCmpTest struct {
- rat1, rat2 string
- out int
+func TestRatSign(t *testing.T) {
+ zero := NewRat(0, 1)
+ for _, a := range setStringTests {
+ var x Rat
+ x.SetString(a.in)
+ s := x.Sign()
+ e := x.Cmp(zero)
+ if s != e {
+ t.Errorf("got %d; want %d for z = %v", s, e, &x)
+ }
+ }
}
-var ratCmpTests = []ratCmpTest{
- ratCmpTest{"0", "0/1", 0},
- ratCmpTest{"1/1", "1", 0},
- ratCmpTest{"-1", "-2/2", 0},
- ratCmpTest{"1", "0", 1},
- ratCmpTest{"0/1", "1/1", -1},
- ratCmpTest{"-5/1434770811533343057144", "-5/1434770811533343057145", -1},
- ratCmpTest{"49832350382626108453/8964749413", "49832350382626108454/8964749413", -1},
- ratCmpTest{"-37414950961700930/7204075375675961", "37414950961700930/7204075375675961", -1},
- ratCmpTest{"37414950961700930/7204075375675961", "74829901923401860/14408150751351922", 0},
+
+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) {
@@ -101,6 +127,38 @@ func TestRatCmp(t *testing.T) {
}
+func TestIsInt(t *testing.T) {
+ one := NewInt(1)
+ for _, a := range setStringTests {
+ var x Rat
+ x.SetString(a.in)
+ i := x.IsInt()
+ e := x.Denom().Cmp(one) == 0
+ if i != e {
+ t.Errorf("got %v; want %v for z = %v", i, e, &x)
+ }
+ }
+}
+
+
+func TestRatAbs(t *testing.T) {
+ zero := NewRat(0, 1)
+ for _, a := range setStringTests {
+ var z Rat
+ z.SetString(a.in)
+ var e Rat
+ e.Set(&z)
+ if e.Cmp(zero) < 0 {
+ e.Sub(zero, &e)
+ }
+ z.Abs(&z)
+ if z.Cmp(&e) != 0 {
+ t.Errorf("got z = %v; want %v", &z, &e)
+ }
+ }
+}
+
+
type ratBinFun func(z, x, y *Rat) *Rat
type ratBinArg struct {
x, y, z string
@@ -118,30 +176,28 @@ func testRatBin(t *testing.T, i int, name string, f ratBinFun, a ratBinArg) {
}
-type ratBinTest struct {
+var ratBinTests = []struct {
x, y string
sum, prod string
-}
-
-var ratBinTests = []ratBinTest{
- ratBinTest{"0", "0", "0", "0"},
- ratBinTest{"0", "1", "1", "0"},
- ratBinTest{"-1", "0", "-1", "0"},
- ratBinTest{"-1", "1", "0", "-1"},
- ratBinTest{"1", "1", "2", "1"},
- ratBinTest{"1/2", "1/2", "1", "1/4"},
- ratBinTest{"1/4", "1/3", "7/12", "1/12"},
- ratBinTest{"2/5", "-14/3", "-64/15", "-28/15"},
- ratBinTest{"4707/49292519774798173060", "-3367/70976135186689855734", "84058377121001851123459/1749296273614329067191168098769082663020", "-1760941/388732505247628681598037355282018369560"},
- ratBinTest{"-61204110018146728334/3", "-31052192278051565633/2", "-215564796870448153567/6", "950260896245257153059642991192710872711/3"},
- ratBinTest{"-854857841473707320655/4237645934602118692642972629634714039", "-18/31750379913563777419", "-27/133467566250814981", "15387441146526731771790/134546868362786310073779084329032722548987800600710485341"},
- ratBinTest{"618575745270541348005638912139/19198433543745179392300736", "-19948846211000086/637313996471", "27674141753240653/30123979153216", "-6169936206128396568797607742807090270137721977/6117715203873571641674006593837351328"},
- ratBinTest{"-3/26206484091896184128", "5/2848423294177090248", "15310893822118706237/9330894968229805033368778458685147968", "-5/24882386581946146755650075889827061248"},
- ratBinTest{"26946729/330400702820", "41563965/225583428284", "1238218672302860271/4658307703098666660055", "224002580204097/14906584649915733312176"},
- ratBinTest{"-8259900599013409474/7", "-84829337473700364773/56707961321161574960", "-468402123685491748914621885145127724451/396955729248131024720", "350340947706464153265156004876107029701/198477864624065512360"},
- ratBinTest{"575775209696864/1320203974639986246357", "29/712593081308", "410331716733912717985762465/940768218243776489278275419794956", "808/45524274987585732633"},
- ratBinTest{"1786597389946320496771/2066653520653241", "6269770/1992362624741777", "3559549865190272133656109052308126637/4117523232840525481453983149257", "8967230/3296219033"},
- ratBinTest{"-36459180403360509753/32150500941194292113930", "9381566963714/9633539", "301622077145533298008420642898530153/309723104686531919656937098270", "-3784609207827/3426986245"},
+}{
+ {"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) {
@@ -201,3 +257,26 @@ func TestIssue820(t *testing.T) {
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)
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-01 10:43:33 +0000