code review 1258042: big: potential bug fix, cleanups

src/pkg/big/nat.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 contains operations on unsigned multi-precision integers.
 // These are the building blocks for the operations on signed integers
 // and rationals.
 
 // This package implements multi-precision arithmetic (big numbers).
 // The following numeric types are supported:
@@ skipping 51 matching lines @@
         if n <= cap(z) {
                 return z[0:n] // reuse z
         }
         // Choosing a good value for e has significant performance impact
         // because it increases the chance that a value can be reused.
         const e = 4 // extra capacity
         return make(nat, n, n+e)
 }
 
 
+func (z nat) setWord(x Word) nat {
+        if x == 0 {
+                return z.make(0)
+        }
+        z = z.make(1)
+        z[0] = x
+        return z
+}
+
+
 func (z nat) setUint64(x uint64) nat {
-        if x == 0 {
-                return z.make(0)
-        }
-
         // single-digit values
-        if x == uint64(Word(x)) {
-                z = z.make(1)
-                z[0] = Word(x)
-                return z
+        if w := Word(x); uint64(w) == x {
+                return z.setWord(w)
         }
 
         // compute number of words n required to represent x
         n := 0
         for t := x; t > 0; t >>= _W {
                 n++
         }
 
         // split x into n words
         z = z.make(n)
@@ skipping 95 matching lines @@
         case x[i] > y[i]:
                 r = 1
         }
         return
 }
 
 
 func (z nat) mulAddWW(x nat, y, r Word) nat {
         m := len(x)
         if m == 0 || y == 0 {
-                return z.setUint64(uint64(r)) // result is r
+                return z.setWord(r) // result is r
         }
         // m > 0
 
         z = z.make(m + 1)
         z[m] = mulAddVWW(z[0:m], x, y, r)
 
         return z.norm()
 }
 
 
@@ skipping 314 matching lines @@
 // Uses z as storage for q, and u as storage for r if possible.
 // See Knuth, Volume 2, section 4.3.1, Algorithm D.
 // Preconditions:
 //    len(v) >= 2
 //    len(uIn) >= len(v)
 func (z nat) divLarge(u, uIn, v nat) (q, r nat) {
         n := len(v)
         m := len(uIn) - n
 
         // determine if z can be reused
+        // TODO(gri) should find a better solution - this if statement
+        //           is very costly (see e.g. time pidigits -s -n 10000)
         if alias(z, uIn) || alias(z, v) {
                 z = nil // z is an alias for uIn or v - cannot reuse
         }
         q = z.make(m + 1)
 
         qhatv := make(nat, n+1)
         if alias(u, uIn) || alias(u, v) {
                 u = nil // u is an alias for uIn or v - cannot reuse
         }
         u = u.make(len(uIn) + 1)
         u.clear()
 
         // D1.
         shift := Word(leadingZeros(v[n-1]))
         shlVW(v, v, shift)
         u[len(uIn)] = shlVW(u[0:len(uIn)], uIn, shift)
 
         // D2.
         for j := m; j >= 0; j-- {
                 // D3.
-                var qhat Word
-                if u[j+n] == v[n-1] {
-                        qhat = _B - 1
-                } else {
+                qhat := Word(_M)
+                if u[j+n] != v[n-1] {
                         var rhat Word
-                        qhat, rhat = divWW_g(u[j+n], u[j+n-1], v[n-1])
+                        qhat, rhat = divWW(u[j+n], u[j+n-1], v[n-1])
 
                         // x1 | x2 = q̂v_{n-2}
-                        x1, x2 := mulWW_g(qhat, v[n-2])
+                        x1, x2 := mulWW(qhat, v[n-2])
                         // test if q̂v_{n-2} > br̂ + u_{j+n-2}
                         for greaterThan(x1, x2, rhat, u[j+n-2]) {
                                 qhat--
                                 prevRhat := rhat
                                 rhat += v[n-1]
                                 // v[n-1] >= 0, so this tests for overflow.
                                 if rhat < prevRhat {
                                         break
                                 }
-                                x1, x2 = mulWW_g(qhat, v[n-2])
+                                x1, x2 = mulWW(qhat, v[n-2])
                         }
                 }
 
                 // D4.
                 qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0)
 
                 c := subVV(u[j:j+len(qhatv)], u[j:], qhatv)
                 if c != 0 {
                         c := addVV(u[j:j+n], u[j:], v)
                         u[j+n] += c
@@ skipping 471 matching lines @@
                         }
                         if y.cmp(natOne) == 0 {
                                 return false
                         }
                 }
                 return false
         }
 
         return true
 }