Source file src/pkg/big/arith.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// This file provides Go implementations of elementary multi-precision
     6	// arithmetic operations on word vectors. Needed for platforms without
     7	// assembly implementations of these routines.
     8	
     9	package big
    10	
    11	// TODO(gri) Decide if Word needs to remain exported.
    12	
    13	type Word uintptr
    14	
    15	const (
    16		// Compute the size _S of a Word in bytes.
    17		_m    = ^Word(0)
    18		_logS = _m>>8&1 + _m>>16&1 + _m>>32&1
    19		_S    = 1 << _logS
    20	
    21		_W = _S << 3 // word size in bits
    22		_B = 1 << _W // digit base
    23		_M = _B - 1  // digit mask
    24	
    25		_W2 = _W / 2   // half word size in bits
    26		_B2 = 1 << _W2 // half digit base
    27		_M2 = _B2 - 1  // half digit mask
    28	)
    29	
    30	// ----------------------------------------------------------------------------
    31	// Elementary operations on words
    32	//
    33	// These operations are used by the vector operations below.
    34	
    35	// z1<<_W + z0 = x+y+c, with c == 0 or 1
    36	func addWW_g(x, y, c Word) (z1, z0 Word) {
    37		yc := y + c
    38		z0 = x + yc
    39		if z0 < x || yc < y {
    40			z1 = 1
    41		}
    42		return
    43	}
    44	
    45	// z1<<_W + z0 = x-y-c, with c == 0 or 1
    46	func subWW_g(x, y, c Word) (z1, z0 Word) {
    47		yc := y + c
    48		z0 = x - yc
    49		if z0 > x || yc < y {
    50			z1 = 1
    51		}
    52		return
    53	}
    54	
    55	// z1<<_W + z0 = x*y
    56	// Adapted from Warren, Hacker's Delight, p. 132.
    57	func mulWW_g(x, y Word) (z1, z0 Word) {
    58		x0 := x & _M2
    59		x1 := x >> _W2
    60		y0 := y & _M2
    61		y1 := y >> _W2
    62		w0 := x0 * y0
    63		t := x1*y0 + w0>>_W2
    64		w1 := t & _M2
    65		w2 := t >> _W2
    66		w1 += x0 * y1
    67		z1 = x1*y1 + w2 + w1>>_W2
    68		z0 = x * y
    69		return
    70	}
    71	
    72	// z1<<_W + z0 = x*y + c
    73	func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
    74		z1, zz0 := mulWW(x, y)
    75		if z0 = zz0 + c; z0 < zz0 {
    76			z1++
    77		}
    78		return
    79	}
    80	
    81	// Length of x in bits.
    82	func bitLen(x Word) (n int) {
    83		for ; x >= 0x100; x >>= 8 {
    84			n += 8
    85		}
    86		for ; x > 0; x >>= 1 {
    87			n++
    88		}
    89		return
    90	}
    91	
    92	// log2 computes the integer binary logarithm of x.
    93	// The result is the integer n for which 2^n <= x < 2^(n+1).
    94	// If x == 0, the result is -1.
    95	func log2(x Word) int {
    96		return bitLen(x) - 1
    97	}
    98	
    99	// Number of leading zeros in x.
   100	func leadingZeros(x Word) uint {
   101		return uint(_W - bitLen(x))
   102	}
   103	
   104	// q = (u1<<_W + u0 - r)/y
   105	// Adapted from Warren, Hacker's Delight, p. 152.
   106	func divWW_g(u1, u0, v Word) (q, r Word) {
   107		if u1 >= v {
   108			return 1<<_W - 1, 1<<_W - 1
   109		}
   110	
   111		s := leadingZeros(v)
   112		v <<= s
   113	
   114		vn1 := v >> _W2
   115		vn0 := v & _M2
   116		un32 := u1<<s | u0>>(_W-s)
   117		un10 := u0 << s
   118		un1 := un10 >> _W2
   119		un0 := un10 & _M2
   120		q1 := un32 / vn1
   121		rhat := un32 - q1*vn1
   122	
   123	again1:
   124		if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
   125			q1--
   126			rhat += vn1
   127			if rhat < _B2 {
   128				goto again1
   129			}
   130		}
   131	
   132		un21 := un32*_B2 + un1 - q1*v
   133		q0 := un21 / vn1
   134		rhat = un21 - q0*vn1
   135	
   136	again2:
   137		if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
   138			q0--
   139			rhat += vn1
   140			if rhat < _B2 {
   141				goto again2
   142			}
   143		}
   144	
   145		return q1*_B2 + q0, (un21*_B2 + un0 - q0*v) >> s
   146	}
   147	
   148	func addVV_g(z, x, y []Word) (c Word) {
   149		for i := range z {
   150			c, z[i] = addWW_g(x[i], y[i], c)
   151		}
   152		return
   153	}
   154	
   155	func subVV_g(z, x, y []Word) (c Word) {
   156		for i := range z {
   157			c, z[i] = subWW_g(x[i], y[i], c)
   158		}
   159		return
   160	}
   161	
   162	func addVW_g(z, x []Word, y Word) (c Word) {
   163		c = y
   164		for i := range z {
   165			c, z[i] = addWW_g(x[i], c, 0)
   166		}
   167		return
   168	}
   169	
   170	func subVW_g(z, x []Word, y Word) (c Word) {
   171		c = y
   172		for i := range z {
   173			c, z[i] = subWW_g(x[i], c, 0)
   174		}
   175		return
   176	}
   177	
   178	func shlVU_g(z, x []Word, s uint) (c Word) {
   179		if n := len(z); n > 0 {
   180			ŝ := _W - s
   181			w1 := x[n-1]
   182			c = w1 >> ŝ
   183			for i := n - 1; i > 0; i-- {
   184				w := w1
   185				w1 = x[i-1]
   186				z[i] = w<<s | w1>>ŝ
   187			}
   188			z[0] = w1 << s
   189		}
   190		return
   191	}
   192	
   193	func shrVU_g(z, x []Word, s uint) (c Word) {
   194		if n := len(z); n > 0 {
   195			ŝ := _W - s
   196			w1 := x[0]
   197			c = w1 << ŝ
   198			for i := 0; i < n-1; i++ {
   199				w := w1
   200				w1 = x[i+1]
   201				z[i] = w>>s | w1<<ŝ
   202			}
   203			z[n-1] = w1 >> s
   204		}
   205		return
   206	}
   207	
   208	func mulAddVWW_g(z, x []Word, y, r Word) (c Word) {
   209		c = r
   210		for i := range z {
   211			c, z[i] = mulAddWWW_g(x[i], y, c)
   212		}
   213		return
   214	}
   215	
   216	func addMulVVW_g(z, x []Word, y Word) (c Word) {
   217		for i := range z {
   218			z1, z0 := mulAddWWW_g(x[i], y, z[i])
   219			c, z[i] = addWW_g(z0, c, 0)
   220			c += z1
   221		}
   222		return
   223	}
   224	
   225	func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word) {
   226		r = xn
   227		for i := len(z) - 1; i >= 0; i-- {
   228			z[i], r = divWW_g(r, x[i], y)
   229		}
   230		return
   231	}
The Go Programming Language

Source file src/pkg/big/arith.go
