summaryrefslogtreecommitdiff
path: root/src/pkg/bignum
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/bignum')
-rw-r--r--src/pkg/bignum/arith.go26
-rwxr-xr-xsrc/pkg/bignum/bignum.go218
-rw-r--r--src/pkg/bignum/bignum_test.go177
-rw-r--r--src/pkg/bignum/integer.go26
-rw-r--r--src/pkg/bignum/nrdiv_test.go18
-rw-r--r--src/pkg/bignum/rational.go14
6 files changed, 259 insertions, 220 deletions
diff --git a/src/pkg/bignum/arith.go b/src/pkg/bignum/arith.go
index 4ae7e3e0a..f60b66828 100644
--- a/src/pkg/bignum/arith.go
+++ b/src/pkg/bignum/arith.go
@@ -18,14 +18,14 @@ func Mul128(x, y uint64) (z1, z0 uint64) {
// and return the product as 2 words.
const (
- W = uint(unsafe.Sizeof(x))*8;
- W2 = W/2;
- B2 = 1<<W2;
- M2 = B2-1;
+ W = uint(unsafe.Sizeof(x)) * 8;
+ W2 = W/2;
+ B2 = 1<<W2;
+ M2 = B2-1;
)
if x < y {
- x, y = y, x
+ x, y = y, x;
}
if x < B2 {
@@ -41,7 +41,7 @@ func Mul128(x, y uint64) (z1, z0 uint64) {
// 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;
@@ -49,7 +49,7 @@ func Mul128(x, y uint64) (z1, z0 uint64) {
// compute result digits but avoid overflow
// z = z[1]*B + z[0] = x*y
z0 = t1<<W2 + t0;
- z1 = (t1 + t0>>W2) >> W2;
+ z1 = (t1 + t0>>W2)>>W2;
return;
}
@@ -68,7 +68,7 @@ func Mul128(x, y uint64) (z1, z0 uint64) {
// compute result digits but avoid overflow
// z = z[1]*B + z[0] = x*y
z0 = t1<<W2 + t0;
- z1 = t2 + (t1 + t0>>W2) >> W2;
+ z1 = t2 + (t1 + t0>>W2)>>W2;
return;
}
@@ -80,10 +80,10 @@ func MulAdd128(x, y, c uint64) (z1, z0 uint64) {
// and return the product as 2 words.
const (
- W = uint(unsafe.Sizeof(x))*8;
- W2 = W/2;
- B2 = 1<<W2;
- M2 = B2-1;
+ W = uint(unsafe.Sizeof(x)) * 8;
+ W2 = W/2;
+ B2 = 1<<W2;
+ M2 = B2-1;
)
// TODO(gri) Should implement special cases for faster execution.
@@ -104,7 +104,7 @@ func MulAdd128(x, y, c uint64) (z1, z0 uint64) {
// compute result digits but avoid overflow
// z = z[1]*B + z[0] = x*y
z0 = t1<<W2 + t0;
- z1 = t2 + (t1 + t0>>W2) >> W2;
+ z1 = t2 + (t1 + t0>>W2)>>W2;
return;
}
diff --git a/src/pkg/bignum/bignum.go b/src/pkg/bignum/bignum.go
index 2fc138cda..55bdad0ab 100755
--- a/src/pkg/bignum/bignum.go
+++ b/src/pkg/bignum/bignum.go
@@ -56,25 +56,25 @@ import (
// in bits must be even.
type (
- digit uint64;
- digit2 uint32; // half-digits for division
+ digit uint64;
+ digit2 uint32; // half-digits for division
)
const (
- logW = 64; // word width
- logH = 4; // bits for a hex digit (= small number)
- logB = logW - logH; // largest bit-width available
+ logW = 64; // word width
+ logH = 4; // bits for a hex digit (= small number)
+ logB = logW-logH; // largest bit-width available
// half-digits
- _W2 = logB / 2; // width
- _B2 = 1 << _W2; // base
- _M2 = _B2 - 1; // mask
+ _W2 = logB/2; // width
+ _B2 = 1<<_W2; // base
+ _M2 = _B2-1; // mask
// full digits
- _W = _W2 * 2; // width
- _B = 1 << _W; // base
- _M = _B - 1; // mask
+ _W = _W2*2; // width
+ _B = 1<<_W; // base
+ _M = _B-1; // mask
)
@@ -110,14 +110,14 @@ func dump(x Natural) {
// Natural represents an unsigned integer value of arbitrary precision.
//
-type Natural []digit;
+type Natural []digit
// Nat creates a small natural number with value x.
//
func Nat(x uint64) Natural {
if x == 0 {
- return nil; // len == 0
+ return nil; // len == 0
}
// single-digit values
@@ -138,7 +138,7 @@ func Nat(x uint64) Natural {
// split x into digits
z := make(Natural, n);
for i := 0; i < n; i++ {
- z[i] = digit(x & _M);
+ z[i] = digit(x&_M);
x >>= _W;
}
@@ -152,8 +152,10 @@ func (x Natural) Value() uint64 {
// single-digit values
n := len(x);
switch n {
- case 0: return 0;
- case 1: return uint64(x[0]);
+ case 0:
+ return 0;
+ case 1:
+ return uint64(x[0]);
}
// multi-digit values
@@ -162,7 +164,7 @@ func (x Natural) Value() uint64 {
z := uint64(0);
s := uint(0);
for i := 0; i < n && s < 64; i++ {
- z += uint64(x[i]) << s;
+ z += uint64(x[i])<<s;
s += _W;
}
@@ -204,8 +206,10 @@ func (x Natural) IsZero() bool {
func normalize(x Natural) Natural {
n := len(x);
- for n > 0 && x[n-1] == 0 { n-- }
- return x[0 : n];
+ for n > 0 && x[n-1] == 0 {
+ n--;
+ }
+ return x[0:n];
}
@@ -219,7 +223,7 @@ func nalloc(z Natural, n int) Natural {
size = 4;
}
if size <= cap(z) {
- return z[0 : n];
+ return z[0:n];
}
return make(Natural, n, size);
}
@@ -240,12 +244,12 @@ func Nadd(zp *Natural, x, y Natural) {
c := digit(0);
i := 0;
for i < m {
- t := c + x[i] + y[i];
+ t := c+x[i]+y[i];
c, z[i] = t>>_W, t&_M;
i++;
}
for i < n {
- t := c + x[i];
+ t := c+x[i];
c, z[i] = t>>_W, t&_M;
i++;
}
@@ -253,7 +257,7 @@ func Nadd(zp *Natural, x, y Natural) {
z[i] = c;
i++;
}
- *zp = z[0 : i]
+ *zp = z[0:i];
}
@@ -274,20 +278,20 @@ func Nsub(zp *Natural, x, y Natural) {
n := len(x);
m := len(y);
if n < m {
- panic("underflow")
+ panic("underflow");
}
z := nalloc(*zp, n);
c := digit(0);
i := 0;
for i < m {
- t := c + x[i] - y[i];
- c, z[i] = digit(int64(t)>>_W), t&_M; // requires arithmetic shift!
+ t := c+x[i]-y[i];
+ c, z[i] = digit(int64(t)>>_W), t&_M; // requires arithmetic shift!
i++;
}
for i < n {
- t := c + x[i];
- c, z[i] = digit(int64(t)>>_W), t&_M; // requires arithmetic shift!
+ t := c+x[i];
+ c, z[i] = digit(int64(t)>>_W), t&_M; // requires arithmetic shift!
i++;
}
if int64(c) < 0 {
@@ -311,7 +315,7 @@ func (x Natural) Sub(y Natural) Natural {
//
func muladd11(x, y, c digit) (digit, digit) {
z1, z0 := MulAdd128(uint64(x), uint64(y), uint64(c));
- return digit(z1<<(64 - logB) | z0>>logB), digit(z0&_M);
+ return digit(z1<<(64-logB) | z0>>logB), digit(z0&_M);
}
@@ -329,7 +333,7 @@ func Nscale(z *Natural, d uint64) {
switch {
case d == 0:
*z = Nat(0);
- return
+ return;
case d == 1:
return;
case d >= _B:
@@ -346,7 +350,7 @@ func Nscale(z *Natural, d uint64) {
for i, d := range *z {
zz[i] = d;
}
- *z = zz
+ *z = zz;
} else {
*z = (*z)[0 : n+1];
}
@@ -360,7 +364,7 @@ func Nscale(z *Natural, d uint64) {
func muladd1(x Natural, d, c digit) Natural {
assert(isSmall(d-1) && isSmall(c));
n := len(x);
- z := make(Natural, n + 1);
+ z := make(Natural, n+1);
for i := 0; i < n; i++ {
t := c + x[i]*d;
@@ -376,13 +380,17 @@ func muladd1(x Natural, d, c digit) Natural {
//
func (x Natural) Mul1(d uint64) Natural {
switch {
- case d == 0: return Nat(0);
- case d == 1: return x;
- case isSmall(digit(d)): muladd1(x, digit(d), 0);
- case d >= _B: return x.Mul(Nat(d));
+ case d == 0:
+ return Nat(0);
+ case d == 1:
+ return x;
+ case isSmall(digit(d)):
+ muladd1(x, digit(d), 0);
+ case d >= _B:
+ return x.Mul(Nat(d));
}
- z := make(Natural, len(x) + 1);
+ z := make(Natural, len(x)+1);
c := mul1(z, x, digit(d));
z[len(x)] = c;
return normalize(z);
@@ -406,13 +414,13 @@ func (x Natural) Mul(y Natural) Natural {
return x.Mul1(uint64(y[0]));
}
- z := make(Natural, n + m);
+ z := make(Natural, n+m);
for j := 0; j < m; j++ {
d := y[j];
if d != 0 {
c := digit(0);
for i := 0; i < n; i++ {
- c, z[i+j] = muladd11(x[i], d, z[i+j] + c);
+ c, z[i+j] = muladd11(x[i], d, z[i+j]+c);
}
z[n+j] = c;
}
@@ -429,30 +437,32 @@ func (x Natural) Mul(y Natural) Natural {
func unpack(x Natural) []digit2 {
n := len(x);
- z := make([]digit2, n*2 + 1); // add space for extra digit (used by DivMod)
+ z := make([]digit2, n*2 + 1); // add space for extra digit (used by DivMod)
for i := 0; i < n; i++ {
t := x[i];
- z[i*2] = digit2(t & _M2);
- z[i*2 + 1] = digit2(t >> _W2 & _M2);
+ z[i*2] = digit2(t&_M2);
+ z[i*2 + 1] = digit2(t>>_W2&_M2);
}
// normalize result
k := 2*n;
- for k > 0 && z[k - 1] == 0 { k-- }
- return z[0 : k]; // trim leading 0's
+ for k > 0 && z[k-1] == 0 {
+ k--;
+ }
+ return z[0:k]; // trim leading 0's
}
func pack(x []digit2) Natural {
- n := (len(x) + 1) / 2;
+ n := (len(x)+1)/2;
z := make(Natural, n);
- if len(x) & 1 == 1 {
+ if len(x)&1 == 1 {
// handle odd len(x)
n--;
z[n] = digit(x[n*2]);
}
for i := 0; i < n; i++ {
- z[i] = digit(x[i*2 + 1]) << _W2 | digit(x[i*2]);
+ z[i] = digit(x[i*2 + 1])<<_W2 | digit(x[i*2]);
}
return normalize(z);
}
@@ -506,14 +516,14 @@ func divmod(x, y []digit2) ([]digit2, []digit2) {
if m == 0 {
panic("division by zero");
}
- assert(n+1 <= cap(x)); // space for one extra digit
+ assert(n+1 <= cap(x)); // space for one extra digit
x = x[0 : n+1];
assert(x[n] == 0);
if m == 1 {
// division by single digit
// result is shifted left by 1 in place!
- x[0] = div21(x[1 : n+1], x[0 : n], y[0]);
+ x[0] = div21(x[1 : n+1], x[0:n], y[0]);
} else if m > n {
// y > x => quotient = 0, remainder = x
@@ -528,12 +538,12 @@ func divmod(x, y []digit2) ([]digit2, []digit2) {
// TODO Instead of multiplying, it would be sufficient to
// shift y such that the normalization condition is
// satisfied (as done in Hacker's Delight).
- f := _B2 / (digit(y[m-1]) + 1);
+ f := _B2/(digit(y[m-1])+1);
if f != 1 {
mul21(x, x, digit2(f));
mul21(y, y, digit2(f));
}
- assert(_B2/2 <= y[m-1] && y[m-1] < _B2); // incorrect scaling
+ assert(_B2/2 <= y[m-1] && y[m-1] < _B2); // incorrect scaling
y1, y2 := digit(y[m-1]), digit(y[m-2]);
for i := n-m; i >= 0; i-- {
@@ -541,14 +551,15 @@ func divmod(x, y []digit2) ([]digit2, []digit2) {
// compute trial digit (Knuth)
var q digit;
- { x0, x1, x2 := digit(x[k]), digit(x[k-1]), digit(x[k-2]);
+ {
+ x0, x1, x2 := digit(x[k]), digit(x[k-1]), digit(x[k-2]);
if x0 != y1 {
q = (x0<<_W2 + x1)/y1;
} else {
q = _B2-1;
}
for y2*q > (x0<<_W2 + x1 - y1*q)<<_W2 + x2 {
- q--
+ q--;
}
}
@@ -556,18 +567,18 @@ func divmod(x, y []digit2) ([]digit2, []digit2) {
c := digit(0);
for j := 0; j < m; j++ {
t := c + digit(x[i+j]) - digit(y[j])*q;
- c, x[i+j] = digit(int64(t) >> _W2), digit2(t & _M2); // requires arithmetic shift!
+ c, x[i+j] = digit(int64(t)>>_W2), digit2(t&_M2); // requires arithmetic shift!
}
// correct if trial digit was too large
- if c + digit(x[k]) != 0 {
+ if c+digit(x[k]) != 0 {
// add y
c := digit(0);
for j := 0; j < m; j++ {
- t := c + digit(x[i+j]) + digit(y[j]);
- c, x[i+j] = t >> _W2, digit2(t & _M2)
+ t := c+digit(x[i+j])+digit(y[j]);
+ c, x[i+j] = t>>_W2, digit2(t&_M2);
}
- assert(c + digit(x[k]) == 0);
+ assert(c+digit(x[k]) == 0);
// correct trial digit
q--;
}
@@ -577,12 +588,12 @@ func divmod(x, y []digit2) ([]digit2, []digit2) {
// undo normalization for remainder
if f != 1 {
- c := div21(x[0 : m], x[0 : m], digit2(f));
+ c := div21(x[0:m], x[0:m], digit2(f));
assert(c == 0);
}
}
- return x[m : n+1], x[0 : m];
+ return x[m : n+1], x[0:m];
}
@@ -620,7 +631,7 @@ func shl(z, x Natural, s uint) digit {
n := len(x);
c := digit(0);
for i := 0; i < n; i++ {
- c, z[i] = x[i] >> (_W-s), x[i] << s & _M | c;
+ c, z[i] = x[i]>>(_W-s), x[i]<<s&_M | c;
}
return c;
}
@@ -643,8 +654,8 @@ func shr(z, x Natural, s uint) digit {
assert(s <= _W);
n := len(x);
c := digit(0);
- for i := n - 1; i >= 0; i-- {
- c, z[i] = x[i] << (_W-s) & _M, x[i] >> s | c;
+ for i := n-1; i >= 0; i-- {
+ c, z[i] = x[i]<<(_W-s)&_M, x[i]>>s | c;
}
return c;
}
@@ -655,7 +666,7 @@ func shr(z, x Natural, s uint) digit {
func (x Natural) Shr(s uint) Natural {
n := uint(len(x));
m := n - s/_W;
- if m > n { // check for underflow
+ if m > n { // check for underflow
m = 0;
}
z := make(Natural, m);
@@ -677,7 +688,7 @@ func (x Natural) And(y Natural) Natural {
z := make(Natural, m);
for i := 0; i < m; i++ {
- z[i] = x[i] & y[i];
+ z[i] = x[i]&y[i];
}
// upper bits are 0
@@ -687,7 +698,7 @@ func (x Natural) And(y Natural) Natural {
func copy(z, x Natural) {
for i, e := range x {
- z[i] = e
+ z[i] = e;
}
}
@@ -703,9 +714,9 @@ func (x Natural) AndNot(y Natural) Natural {
z := make(Natural, n);
for i := 0; i < m; i++ {
- z[i] = x[i] &^ y[i];
+ z[i] = x[i]&^y[i];
}
- copy(z[m : n], x[m : n]);
+ copy(z[m:n], x[m:n]);
return normalize(z);
}
@@ -722,9 +733,9 @@ func (x Natural) Or(y Natural) Natural {
z := make(Natural, n);
for i := 0; i < m; i++ {
- z[i] = x[i] | y[i];
+ z[i] = x[i]|y[i];
}
- copy(z[m : n], x[m : n]);
+ copy(z[m:n], x[m:n]);
return z;
}
@@ -741,9 +752,9 @@ func (x Natural) Xor(y Natural) Natural {
z := make(Natural, n);
for i := 0; i < m; i++ {
- z[i] = x[i] ^ y[i];
+ z[i] = x[i]^y[i];
}
- copy(z[m : n], x[m : n]);
+ copy(z[m:n], x[m:n]);
return normalize(z);
}
@@ -760,16 +771,20 @@ func (x Natural) Cmp(y Natural) int {
m := len(y);
if n != m || n == 0 {
- return n - m;
+ return n-m;
}
- i := n - 1;
- for i > 0 && x[i] == y[i] { i--; }
+ i := n-1;
+ for i > 0 && x[i] == y[i] {
+ i--;
+ }
d := 0;
switch {
- case x[i] < y[i]: d = -1;
- case x[i] > y[i]: d = 1;
+ case x[i] < y[i]:
+ d = -1;
+ case x[i] > y[i]:
+ d = 1;
}
return d;
@@ -787,7 +802,7 @@ func log2(x uint64) uint {
x >>= 1;
n++;
}
- return n - 1;
+ return n-1;
}
@@ -798,7 +813,7 @@ func log2(x uint64) uint {
func (x Natural) Log2() uint {
n := len(x);
if n > 0 {
- return (uint(n) - 1)*_W + log2(uint64(x[n - 1]));
+ return (uint(n)-1)*_W + log2(uint64(x[n-1]));
}
panic("Log2(0)");
}
@@ -808,10 +823,10 @@ func (x Natural) Log2() uint {
// Returns updated x and x mod d.
//
func divmod1(x Natural, d digit) (Natural, digit) {
- assert(0 < d && isSmall(d - 1));
+ assert(0 < d && isSmall(d-1));
c := digit(0);
- for i := len(x) - 1; i >= 0; i-- {
+ for i := len(x)-1; i >= 0; i-- {
t := c<<_W + x[i];
c, x[i] = t%d, t/d;
}
@@ -829,7 +844,7 @@ func (x Natural) ToString(base uint) string {
// allocate buffer for conversion
assert(2 <= base && base <= 16);
- n := (x.Log2() + 1) / log2(uint64(base)) + 1; // +1: round up
+ n := (x.Log2() + 1)/log2(uint64(base)) + 1; // +1: round up
s := make([]byte, n);
// don't destroy x
@@ -843,9 +858,9 @@ func (x Natural) ToString(base uint) string {
var d digit;
t, d = divmod1(t, digit(base));
s[i] = "0123456789abcdef"[d];
- };
+ }
- return string(s[i : n]);
+ return string(s[i:n]);
}
@@ -859,9 +874,12 @@ func (x Natural) String() string {
func fmtbase(c int) uint {
switch c {
- case 'b': return 2;
- case 'o': return 8;
- case 'x': return 16;
+ case 'b':
+ return 2;
+ case 'o':
+ return 8;
+ case 'x':
+ return 16;
}
return 10;
}
@@ -876,11 +894,14 @@ func (x Natural) Format(h fmt.State, c int) {
func hexvalue(ch byte) uint {
- d := uint(1 << logH);
+ d := uint(1<<logH);
switch {
- case '0' <= ch && ch <= '9': d = uint(ch - '0');
- case 'a' <= ch && ch <= 'f': d = uint(ch - 'a') + 10;
- case 'A' <= ch && ch <= 'F': d = uint(ch - 'A') + 10;
+ case '0' <= ch && ch <= '9':
+ d = uint(ch-'0');
+ case 'a' <= ch && ch <= 'f':
+ d = uint(ch-'a') + 10;
+ case 'A' <= ch && ch <= 'F':
+ d = uint(ch-'A') + 10;
}
return d;
}
@@ -942,7 +963,7 @@ func pop1(x digit) uint {
//
func (x Natural) Pop() uint {
n := uint(0);
- for i := len(x) - 1; i >= 0; i-- {
+ for i := len(x)-1; i >= 0; i-- {
n += pop1(x[i]);
}
return n;
@@ -970,13 +991,16 @@ func (xp Natural) Pow(n uint) Natural {
//
func MulRange(a, b uint) Natural {
switch {
- case a > b: return Nat(1);
- case a == b: return Nat(uint64(a));
- case a + 1 == b: return Nat(uint64(a)).Mul(Nat(uint64(b)));
+ case a > b:
+ return Nat(1);
+ case a == b:
+ return Nat(uint64(a));
+ case a+1 == b:
+ return Nat(uint64(a)).Mul(Nat(uint64(b)));
}
- m := (a + b)>>1;
+ m := (a+b)>>1;
assert(a <= m && m < b);
- return MulRange(a, m).Mul(MulRange(m + 1, b));
+ return MulRange(a, m).Mul(MulRange(m+1, b));
}
diff --git a/src/pkg/bignum/bignum_test.go b/src/pkg/bignum/bignum_test.go
index 2b2be6693..230e42f13 100644
--- a/src/pkg/bignum/bignum_test.go
+++ b/src/pkg/bignum/bignum_test.go
@@ -10,12 +10,12 @@ import (
)
const (
- sa = "991";
- sb = "2432902008176640000"; // 20!
- sc = "933262154439441526816992388562667004907159682643816214685929"
- "638952175999932299156089414639761565182862536979208272237582"
- "51185210916864000000000000000000000000"; // 100!
- sp = "170141183460469231731687303715884105727"; // prime
+ sa = "991";
+ sb = "2432902008176640000"; // 20!
+ sc = "933262154439441526816992388562667004907159682643816214685929"
+ "638952175999932299156089414639761565182862536979208272237582"
+ "51185210916864000000000000000000000000"; // 100!
+ sp = "170141183460469231731687303715884105727"; // prime
)
func natFromString(s string, base uint, slen *int) Natural {
@@ -46,30 +46,26 @@ func ratFromString(s string, base uint, slen *int) *Rational {
var (
- nat_zero = Nat(0);
- nat_one = Nat(1);
- nat_two = Nat(2);
-
- a = natFromString(sa, 10, nil);
- b = natFromString(sb, 10, nil);
- c = natFromString(sc, 10, nil);
- p = natFromString(sp, 10, nil);
-
- int_zero = Int(0);
- int_one = Int(1);
- int_two = Int(2);
-
- ip = intFromString(sp, 10, nil);
-
- rat_zero = Rat(0, 1);
- rat_half = Rat(1, 2);
- rat_one = Rat(1, 1);
- rat_two = Rat(2, 1);
+ nat_zero = Nat(0);
+ nat_one = Nat(1);
+ nat_two = Nat(2);
+ a = natFromString(sa, 10, nil);
+ b = natFromString(sb, 10, nil);
+ c = natFromString(sc, 10, nil);
+ p = natFromString(sp, 10, nil);
+ int_zero = Int(0);
+ int_one = Int(1);
+ int_two = Int(2);
+ ip = intFromString(sp, 10, nil);
+ rat_zero = Rat(0, 1);
+ rat_half = Rat(1, 2);
+ rat_one = Rat(1, 1);
+ rat_two = Rat(2, 1);
)
-var test_msg string;
-var tester *testing.T;
+var test_msg string
+var tester *testing.T
func test(n uint, b bool) {
if !b {
@@ -102,7 +98,10 @@ func rat_eq(n uint, x, y *Rational) {
func TestNatConv(t *testing.T) {
tester = t;
test_msg = "NatConvA";
- type entry1 struct { x uint64; s string };
+ type entry1 struct {
+ x uint64;
+ s string;
+ }
tab := []entry1{
entry1{0, "0"},
entry1{255, "255"},
@@ -111,8 +110,8 @@ func TestNatConv(t *testing.T) {
entry1{18446744073709551615, "18446744073709551615"},
};
for i, e := range tab {
- test(100 + uint(i), Nat(e.x).String() == e.s);
- test(200 + uint(i), natFromString(e.s, 0, nil).Value() == e.x);
+ test(100+uint(i), Nat(e.x).String() == e.s);
+ test(200+uint(i), natFromString(e.s, 0, nil).Value() == e.x);
}
test_msg = "NatConvB";
@@ -168,7 +167,10 @@ func abs(x int64) uint64 {
func TestIntConv(t *testing.T) {
tester = t;
test_msg = "IntConvA";
- type entry2 struct { x int64; s string };
+ type entry2 struct {
+ x int64;
+ s string;
+ }
tab := []entry2{
entry2{0, "0"},
entry2{-128, "-128"},
@@ -181,9 +183,9 @@ func TestIntConv(t *testing.T) {
entry2{9223372036854775807, "9223372036854775807"},
};
for i, e := range tab {
- test(100 + uint(i), Int(e.x).String() == e.s);
- test(200 + uint(i), intFromString(e.s, 0, nil).Value() == e.x);
- test(300 + uint(i), Int(e.x).Abs().Value() == abs(e.x));
+ test(100+uint(i), Int(e.x).String() == e.s);
+ test(200+uint(i), intFromString(e.s, 0, nil).Value() == e.x);
+ test(300+uint(i), Int(e.x).Abs().Value() == abs(e.x));
}
test_msg = "IntConvB";
@@ -335,26 +337,28 @@ func TestNatDiv(t *testing.T) {
func TestIntQuoRem(t *testing.T) {
tester = t;
test_msg = "IntQuoRem";
- type T struct { x, y, q, r int64 };
+ type T struct {
+ x, y, q, r int64;
+ }
a := []T{
T{+8, +3, +2, +2},
T{+8, -3, -2, +2},
T{-8, +3, -2, -2},
T{-8, -3, +2, -2},
- T{+1, +2, 0, +1},
- T{+1, -2, 0, +1},
- T{-1, +2, 0, -1},
- T{-1, -2, 0, -1},
+ T{+1, +2, 0, +1},
+ T{+1, -2, 0, +1},
+ T{-1, +2, 0, -1},
+ T{-1, -2, 0, -1},
};
for i := uint(0); i < uint(len(a)); i++ {
e := &a[i];
x, y := Int(e.x).Mul(ip), Int(e.y).Mul(ip);
q, r := Int(e.q), Int(e.r).Mul(ip);
qq, rr := x.QuoRem(y);
- int_eq(4*i+0, x.Quo(y), q);
- int_eq(4*i+1, x.Rem(y), r);
- int_eq(4*i+2, qq, q);
- int_eq(4*i+3, rr, r);
+ int_eq(4*i + 0, x.Quo(y), q);
+ int_eq(4*i + 1, x.Rem(y), r);
+ int_eq(4*i + 2, qq, q);
+ int_eq(4*i + 3, rr, r);
}
}
@@ -362,14 +366,16 @@ func TestIntQuoRem(t *testing.T) {
func TestIntDivMod(t *testing.T) {
tester = t;
test_msg = "IntDivMod";
- type T struct { x, y, q, r int64 };
+ type T struct {
+ x, y, q, r int64;
+ }
a := []T{
T{+8, +3, +2, +2},
T{+8, -3, -2, +2},
T{-8, +3, -3, +1},
T{-8, -3, +3, +1},
- T{+1, +2, 0, +1},
- T{+1, -2, 0, +1},
+ T{+1, +2, 0, +1},
+ T{+1, -2, 0, +1},
T{-1, +2, -1, +1},
T{-1, -2, +1, +1},
};
@@ -378,10 +384,10 @@ func TestIntDivMod(t *testing.T) {
x, y := Int(e.x).Mul(ip), Int(e.y).Mul(ip);
q, r := Int(e.q), Int(e.r).Mul(ip);
qq, rr := x.DivMod(y);
- int_eq(4*i+0, x.Div(y), q);
- int_eq(4*i+1, x.Mod(y), r);
- int_eq(4*i+2, qq, q);
- int_eq(4*i+3, rr, r);
+ int_eq(4*i + 0, x.Div(y), q);
+ int_eq(4*i + 1, x.Mod(y), r);
+ int_eq(4*i + 2, qq, q);
+ int_eq(4*i + 3, rr, r);
}
}
@@ -418,7 +424,8 @@ func TestNatShift(t *testing.T) {
}
test_msg = "NatShift3L";
- { const m = 3;
+ {
+ const m = 3;
p := b;
f := Nat(1<<m);
for i := uint(0); i < 100; i++ {
@@ -428,7 +435,8 @@ func TestNatShift(t *testing.T) {
}
test_msg = "NatShift3R";
- { p := c;
+ {
+ p := c;
for i := uint(0); !p.IsZero(); i++ {
nat_eq(i, c.Shr(i), p);
p = p.Shr(1);
@@ -453,7 +461,8 @@ func TestIntShift(t *testing.T) {
}
test_msg = "IntShift3L";
- { const m = 3;
+ {
+ const m = 3;
p := ip;
f := Int(1<<m);
for i := uint(0); i < 100; i++ {
@@ -463,7 +472,8 @@ func TestIntShift(t *testing.T) {
}
test_msg = "IntShift3R";
- { p := ip;
+ {
+ p := ip;
for i := uint(0); p.IsPos(); i++ {
int_eq(i, ip.Shr(i), p);
p = p.Shr(1);
@@ -487,25 +497,25 @@ func TestNatBitOps(t *testing.T) {
by := Nat(y);
test_msg = "NatAnd";
- bz := Nat(x & y);
+ bz := Nat(x&y);
for i := uint(0); i < 100; i++ {
nat_eq(i, bx.Shl(i).And(by.Shl(i)), bz.Shl(i));
}
test_msg = "NatAndNot";
- bz = Nat(x &^ y);
+ bz = Nat(x&^y);
for i := uint(0); i < 100; i++ {
nat_eq(i, bx.Shl(i).AndNot(by.Shl(i)), bz.Shl(i));
}
test_msg = "NatOr";
- bz = Nat(x | y);
+ bz = Nat(x|y);
for i := uint(0); i < 100; i++ {
nat_eq(i, bx.Shl(i).Or(by.Shl(i)), bz.Shl(i));
}
test_msg = "NatXor";
- bz = Nat(x ^ y);
+ bz = Nat(x^y);
for i := uint(0); i < 100; i++ {
nat_eq(i, bx.Shl(i).Xor(by.Shl(i)), bz.Shl(i));
}
@@ -515,19 +525,21 @@ func TestNatBitOps(t *testing.T) {
func TestIntBitOps1(t *testing.T) {
tester = t;
test_msg = "IntBitOps1";
- type T struct { x, y int64 };
- a := []T {
- T{ +7, +3 },
- T{ +7, -3 },
- T{ -7, +3 },
- T{ -7, -3 },
+ type T struct {
+ x, y int64;
+ }
+ a := []T{
+ T{+7, +3},
+ T{+7, -3},
+ T{-7, +3},
+ T{-7, -3},
};
for i := uint(0); i < uint(len(a)); i++ {
e := &a[i];
- int_eq(4*i+0, Int(e.x).And(Int(e.y)), Int(e.x & e.y));
- int_eq(4*i+1, Int(e.x).AndNot(Int(e.y)), Int(e.x &^ e.y));
- int_eq(4*i+2, Int(e.x).Or(Int(e.y)), Int(e.x | e.y));
- int_eq(4*i+3, Int(e.x).Xor(Int(e.y)), Int(e.x ^ e.y));
+ int_eq(4*i + 0, Int(e.x).And(Int(e.y)), Int(e.x & e.y));
+ int_eq(4*i + 1, Int(e.x).AndNot(Int(e.y)), Int(e.x &^ e.y));
+ int_eq(4*i + 2, Int(e.x).Or(Int(e.y)), Int(e.x | e.y));
+ int_eq(4*i + 3, Int(e.x).Xor(Int(e.y)), Int(e.x ^ e.y));
}
}
@@ -536,19 +548,19 @@ func TestIntBitOps2(t *testing.T) {
tester = t;
test_msg = "IntNot";
- int_eq(0, Int(-2).Not(), Int( 1));
- int_eq(0, Int(-1).Not(), Int( 0));
- int_eq(0, Int( 0).Not(), Int(-1));
- int_eq(0, Int( 1).Not(), Int(-2));
- int_eq(0, Int( 2).Not(), Int(-3));
+ int_eq(0, Int(-2).Not(), Int(1));
+ int_eq(0, Int(-1).Not(), Int(0));
+ int_eq(0, Int(0).Not(), Int(-1));
+ int_eq(0, Int(1).Not(), Int(-2));
+ int_eq(0, Int(2).Not(), Int(-3));
test_msg = "IntAnd";
for x := int64(-15); x < 5; x++ {
bx := Int(x);
for y := int64(-5); y < 15; y++ {
by := Int(y);
- for i := uint(50); i < 70; i++ { // shift across 64bit boundary
- int_eq(i, bx.Shl(i).And(by.Shl(i)), Int(x & y).Shl(i));
+ for i := uint(50); i < 70; i++ { // shift across 64bit boundary
+ int_eq(i, bx.Shl(i).And(by.Shl(i)), Int(x&y).Shl(i));
}
}
}
@@ -558,9 +570,9 @@ func TestIntBitOps2(t *testing.T) {
bx := Int(x);
for y := int64(-5); y < 15; y++ {
by := Int(y);
- for i := uint(50); i < 70; i++ { // shift across 64bit boundary
- int_eq(2*i+0, bx.Shl(i).AndNot(by.Shl(i)), Int(x &^ y).Shl(i));
- int_eq(2*i+1, bx.Shl(i).And(by.Shl(i).Not()), Int(x &^ y).Shl(i));
+ for i := uint(50); i < 70; i++ { // shift across 64bit boundary
+ int_eq(2*i + 0, bx.Shl(i).AndNot(by.Shl(i)), Int(x&^y).Shl(i));
+ int_eq(2*i + 1, bx.Shl(i).And(by.Shl(i).Not()), Int(x&^y).Shl(i));
}
}
}
@@ -570,8 +582,8 @@ func TestIntBitOps2(t *testing.T) {
bx := Int(x);
for y := int64(-5); y < 15; y++ {
by := Int(y);
- for i := uint(50); i < 70; i++ { // shift across 64bit boundary
- int_eq(i, bx.Shl(i).Or(by.Shl(i)), Int(x | y).Shl(i));
+ for i := uint(50); i < 70; i++ { // shift across 64bit boundary
+ int_eq(i, bx.Shl(i).Or(by.Shl(i)), Int(x|y).Shl(i));
}
}
}
@@ -581,8 +593,8 @@ func TestIntBitOps2(t *testing.T) {
bx := Int(x);
for y := int64(-5); y < 15; y++ {
by := Int(y);
- for i := uint(50); i < 70; i++ { // shift across 64bit boundary
- int_eq(i, bx.Shl(i).Xor(by.Shl(i)), Int(x ^ y).Shl(i));
+ for i := uint(50); i < 70; i++ { // shift across 64bit boundary
+ int_eq(i, bx.Shl(i).Xor(by.Shl(i)), Int(x^y).Shl(i));
}
}
}
@@ -651,4 +663,3 @@ func TestNatPop(t *testing.T) {
test(i, nat_one.Shl(i).Sub(nat_one).Pop() == i);
}
}
-
diff --git a/src/pkg/bignum/integer.go b/src/pkg/bignum/integer.go
index 35a95bb3c..0d0d0ed8e 100644
--- a/src/pkg/bignum/integer.go
+++ b/src/pkg/bignum/integer.go
@@ -18,8 +18,8 @@ import (
// Integer represents a signed integer value of arbitrary precision.
//
type Integer struct {
- sign bool;
- mant Natural;
+ sign bool;
+ mant Natural;
}
@@ -29,7 +29,7 @@ type Integer struct {
//
func MakeInt(sign bool, mant Natural) *Integer {
if mant.IsZero() {
- sign = false; // normalize
+ sign = false; // normalize
}
return &Integer{sign, mant};
}
@@ -95,14 +95,14 @@ func (x *Integer) IsZero() bool {
// IsNeg returns true iff x < 0.
//
func (x *Integer) IsNeg() bool {
- return x.sign && !x.mant.IsZero()
+ return x.sign && !x.mant.IsZero();
}
// IsPos returns true iff x >= 0.
//
func (x *Integer) IsPos() bool {
- return !x.sign && !x.mant.IsZero()
+ return !x.sign && !x.mant.IsZero();
}
@@ -383,7 +383,7 @@ func (x *Integer) And(y *Integer) *Integer {
// x.sign != y.sign
if x.sign {
- x, y = y, x; // & is symmetric
+ x, y = y, x; // & is symmetric
}
// x & (-y) == x & ^(y-1) == x &^ (y-1)
@@ -429,7 +429,7 @@ func (x *Integer) Or(y *Integer) *Integer {
// x.sign != y.sign
if x.sign {
- x, y = y, x; // | or symmetric
+ x, y = y, x; // | or symmetric
}
// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
@@ -452,7 +452,7 @@ func (x *Integer) Xor(y *Integer) *Integer {
// x.sign != y.sign
if x.sign {
- x, y = y, x; // ^ is symmetric
+ x, y = y, x; // ^ is symmetric
}
// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
@@ -478,8 +478,10 @@ func (x *Integer) Cmp(y *Integer) int {
if x.sign {
r = -r;
}
- case x.sign: r = -1;
- case y.sign: r = 1;
+ case x.sign:
+ r = -1;
+ case y.sign:
+ r = 1;
}
return r;
}
@@ -532,7 +534,7 @@ func IntFromString(s string, base uint) (*Integer, uint, int) {
i0 = 1;
}
- mant, base, slen := NatFromString(s[i0 : len(s)], base);
+ mant, base, slen := NatFromString(s[i0:len(s)], base);
- return MakeInt(i0 > 0 && s[0] == '-', mant), base, i0 + slen;
+ return MakeInt(i0 > 0 && s[0] == '-', mant), base, i0+slen;
}
diff --git a/src/pkg/bignum/nrdiv_test.go b/src/pkg/bignum/nrdiv_test.go
index 24cb4d558..6559d62bc 100644
--- a/src/pkg/bignum/nrdiv_test.go
+++ b/src/pkg/bignum/nrdiv_test.go
@@ -21,8 +21,8 @@ import "testing"
// value of an fpNat x is x.m * 2^x.e .
//
type fpNat struct {
- m Natural;
- e int;
+ m Natural;
+ e int;
}
@@ -40,7 +40,7 @@ func (x fpNat) sub(y fpNat) fpNat {
// mul2 computes x*2.
func (x fpNat) mul2() fpNat {
- return fpNat{x.m, x.e+1};
+ return fpNat{x.m, x.e + 1};
}
@@ -55,8 +55,10 @@ func (x fpNat) mul(y fpNat) fpNat {
//
func (x fpNat) mant() Natural {
switch {
- case x.e > 0: return x.m.Shl(uint(x.e));
- case x.e < 0: return x.m.Shr(uint(-x.e));
+ case x.e > 0:
+ return x.m.Shl(uint(x.e));
+ case x.e < 0:
+ return x.m.Shr(uint(-x.e));
}
return x.m;
}
@@ -131,9 +133,9 @@ func nrDivEst(x0, y0 Natural) Natural {
// reduce mantissa size
// TODO: Find smaller bound as it will reduce
// computation time massively.
- d := int(r.m.Log2()+1) - maxLen;
+ d := int(r.m.Log2() + 1) - maxLen;
if d > 0 {
- r = fpNat{r.m.Shr(uint(d)), r.e+d};
+ r = fpNat{r.m.Shr(uint(d)), r.e + d};
}
}
@@ -188,5 +190,5 @@ func TestNRDiv(t *testing.T) {
idiv(t, 7484890589595, 7484890589594);
div(t, Fact(100), Fact(91));
div(t, Fact(1000), Fact(991));
- //div(t, Fact(10000), Fact(9991)); // takes too long - disabled for now
+//div(t, Fact(10000), Fact(9991)); // takes too long - disabled for now
}
diff --git a/src/pkg/bignum/rational.go b/src/pkg/bignum/rational.go
index baa9b4110..5f7423bac 100644
--- a/src/pkg/bignum/rational.go
+++ b/src/pkg/bignum/rational.go
@@ -12,15 +12,15 @@ import "fmt"
// Rational represents a quotient a/b of arbitrary precision.
//
type Rational struct {
- a *Integer; // numerator
- b Natural; // denominator
+ a *Integer; // numerator
+ b Natural; // denominator
}
// MakeRat makes a rational number given a numerator a and a denominator b.
//
func MakeRat(a *Integer, b Natural) *Rational {
- f := a.mant.Gcd(b); // f > 0
+ f := a.mant.Gcd(b); // f > 0
if f.Cmp(Nat(1)) != 0 {
a = MakeInt(a.sign, a.mant.Div(f));
b = b.Div(f);
@@ -191,10 +191,10 @@ func RatFromString(s string, base uint) (*Rational, uint, int) {
ch := s[alen];
if ch == '/' {
alen++;
- b, base, blen = NatFromString(s[alen : len(s)], base);
+ b, base, blen = NatFromString(s[alen:len(s)], base);
} else if ch == '.' {
alen++;
- b, base, blen = NatFromString(s[alen : len(s)], abase);
+ b, base, blen = NatFromString(s[alen:len(s)], abase);
assert(base == abase);
f := Nat(uint64(base)).Pow(uint(blen));
a = MakeInt(a.sign, a.mant.Mul(f).Add(b));
@@ -203,12 +203,12 @@ func RatFromString(s string, base uint) (*Rational, uint, int) {
}
// read exponent, if any
- rlen := alen + blen;
+ rlen := alen+blen;
if rlen < len(s) {
ch := s[rlen];
if ch == 'e' || ch == 'E' {
rlen++;
- e, _, elen := IntFromString(s[rlen : len(s)], 10);
+ e, _, elen := IntFromString(s[rlen:len(s)], 10);
rlen += elen;
m := Nat(10).Pow(uint(e.mant.Value()));
if e.sign {
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-21 14:29:48 +0000