src/pkg/bignum/nrdiv_test.go

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file implements Newton-Raphson division and uses
// it as an additional test case for bignum.
//
// Division of x/y is achieved by computing r = 1/y to
// obtain the quotient q = x*r = x*(1/y) = x/y. The
// reciprocal r is the solution for f(x) = 1/x - y and
// the solution is approximated through iteration. The
// iteration does not require division.

package bignum

import "testing"


// An fpNat is a Natural scaled by a power of two
// (an unsigned floating point representation). The
// value of an fpNat x is x.m * 2^x.e .
//
type fpNat struct {
	m Natural;
	e int;
}


// sub computes x - y.
func (x fpNat) sub(y fpNat) fpNat {
	switch d := x.e - y.e; {
	case d < 0:
		return fpNat{x.m.Sub(y.m.Shl(uint(-d))), x.e};
	case d > 0:
		return fpNat{x.m.Shl(uint(d)).Sub(y.m), y.e};
	}
	return fpNat{x.m.Sub(y.m), x.e};
}


// mul2 computes x*2.
func (x fpNat) mul2() fpNat {
	return fpNat{x.m, x.e+1};
}


// mul computes x*y.
func (x fpNat) mul(y fpNat) fpNat {
	return fpNat{x.m.Mul(y.m), x.e + y.e};
}


// mant computes the (possibly truncated) Natural representation
// of an fpNat x.
//
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));
	}
	return x.m;
}


// nrDivEst computes an estimate of the quotient q = x0/y0 and returns q.
// q may be too small (usually by 1).
//
func nrDivEst(x0, y0 Natural) Natural {
	if y0.IsZero() {
		panic("division by zero");
		return nil;
	}
	// y0 > 0

	if y0.Cmp(Nat(1)) == 0 {
		return x0;
	}
	// y0 > 1

	switch d := x0.Cmp(y0); {
	case d < 0:
		return Nat(0);
	case d == 0:
		return Nat(1);
	}
	// x0 > y0 > 1

	// Determine maximum result length.
	maxLen := int(x0.Log2() - y0.Log2() + 1);

	// In the following, each number x is represented
	// as a mantissa x.m and an exponent x.e such that
	// x = xm * 2^x.e.
	x := fpNat{x0, 0};
	y := fpNat{y0, 0};

	// Determine a scale factor f = 2^e such that
	// 0.5 <= y/f == y*(2^-e) < 1.0
	// and scale y accordingly.
	e := int(y.m.Log2()) + 1;
	y.e -= e;

	// t1
	var c = 2.9142;
	const n = 14;
	t1 := fpNat{Nat(uint64(c*(1<<n))), -n};

	// Compute initial value r0 for the reciprocal of y/f.
	// r0 = t1 - 2*y
	r := t1.sub(y.mul2());
	two := fpNat{Nat(2), 0};

	// Newton-Raphson iteration
	p := Nat(0);
	for i := 0; ; i++ {
		// check if we are done
		// TODO: Need to come up with a better test here
		//       as it will reduce computation time significantly.
		// q = x*r/f
		q := x.mul(r);
		q.e -= e;
		res := q.mant();
		if res.Cmp(p) == 0 {
			return res;
		}
		p = res;

		// r' = r*(2 - y*r)
		r = r.mul(two.sub(y.mul(r)));

		// reduce mantissa size
		// TODO: Find smaller bound as it will reduce
		//       computation time massively.
		d := int(r.m.Log2()+1) - maxLen;
		if d > 0 {
			r = fpNat{r.m.Shr(uint(d)), r.e+d};
		}
	}

	panic("unreachable");
	return nil;
}


func nrdiv(x, y Natural) (q, r Natural) {
	q = nrDivEst(x, y);
	r = x.Sub(y.Mul(q));
	// if r is too large, correct q and r
	// (usually one iteration)
	for r.Cmp(y) >= 0 {
		q = q.Add(Nat(1));
		r = r.Sub(y);
	}
	return;
}


func div(t *testing.T, x, y Natural) {
	q, r := nrdiv(x, y);
	qx, rx := x.DivMod(y);
	if q.Cmp(qx) != 0 {
		t.Errorf("x = %s, y = %s, got q = %s, want q = %s", x, y, q, qx);
	}
	if r.Cmp(rx) != 0 {
		t.Errorf("x = %s, y = %s, got r = %s, want r = %s", x, y, r, rx);
	}
}


func idiv(t *testing.T, x0, y0 uint64) {
	div(t, Nat(x0), Nat(y0));
}


func TestNRDiv(t *testing.T) {
	idiv(t, 17, 18);
	idiv(t, 17, 17);
	idiv(t, 17, 1);
	idiv(t, 17, 16);
	idiv(t, 17, 10);
	idiv(t, 17, 9);
	idiv(t, 17, 8);
	idiv(t, 17, 5);
	idiv(t, 17, 3);
	idiv(t, 1025, 512);
	idiv(t, 7489595, 2);
	idiv(t, 5404679459, 78495);
	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
}