Source File
arith.go
Belonging Package
math/big
// 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 provides Go implementations of elementary multi-precision
// arithmetic operations on word vectors. These have the suffix _g.
// These are needed for platforms without assembly implementations of these routines.
// This file also contains elementary operations that can be implemented
// sufficiently efficiently in Go.
package big
import (
_ // for go:linkname
)
// A Word represents a single digit of a multi-precision unsigned integer.
type Word uint
const (
_S = _W / 8 // word size in bytes
_W = bits.UintSize // word size in bits
_B = 1 << _W // digit base
_M = _B - 1 // digit mask
)
// In these routines, it is the caller's responsibility to arrange for
// x, y, and z to all have the same length. We check this and panic.
// The assembly versions of these routines do not include that check.
//
// The check+panic also has the effect of teaching the compiler that
// “i in range for z” implies “i in range for x and y”, eliminating all
// bounds checks in loops from 0 to len(z) and vice versa.
// ----------------------------------------------------------------------------
// Elementary operations on words
//
// These operations are used by the vector operations below.
// z1<<_W + z0 = x*y
func mulWW(, Word) (, Word) {
, := bits.Mul(uint(), uint())
return Word(), Word()
}
// z1<<_W + z0 = x*y + c
func mulAddWWW_g(, , Word) (, Word) {
, := bits.Mul(uint(), uint())
var uint
, = bits.Add(, uint(), 0)
return Word( + ), Word()
}
// nlz returns the number of leading zeros in x.
// Wraps bits.LeadingZeros call for convenience.
func nlz( Word) uint {
return uint(bits.LeadingZeros(uint()))
}
// The resulting carry c is either 0 or 1.
func addVV_g(, , []Word) ( Word) {
if len() != len() || len() != len() {
panic("addVV len")
}
for := range {
, := bits.Add(uint([]), uint([]), uint())
[] = Word()
= Word()
}
return
}
// The resulting carry c is either 0 or 1.
func subVV_g(, , []Word) ( Word) {
if len() != len() || len() != len() {
panic("subVV len")
}
for := range {
, := bits.Sub(uint([]), uint([]), uint())
[] = Word()
= Word()
}
return
}
// addVW sets z = x + y, returning the final carry c.
// The behavior is undefined if len(x) != len(z).
// If len(z) == 0, c = y; otherwise, c is 0 or 1.
//
// addVW should be an internal detail,
// but widely used packages access it using linkname.
// Notable members of the hall of shame include:
// - github.com/remyoudompheng/bigfft
//
// Do not remove or change the type signature.
// See go.dev/issue/67401.
//
//go:linkname addVW
func addVW(, []Word, Word) ( Word) {
if len() != len() {
panic("addVW len")
}
if len() == 0 {
return
}
, := bits.Add(uint([0]), uint(), 0)
[0] = Word()
if == 0 {
if &[0] != &[0] {
copy([1:], [1:])
}
return 0
}
for := 1; < len(); ++ {
:= []
if != ^Word(0) {
[] = + 1
if &[0] != &[0] {
copy([+1:], [+1:])
}
return 0
}
[] = 0
}
return 1
}
// addVW_ref is the reference implementation for addVW, used only for testing.
func addVW_ref(, []Word, Word) ( Word) {
=
for := range {
, := bits.Add(uint([]), uint(), 0)
[] = Word()
= Word()
}
return
}
// subVW sets z = x - y, returning the final carry c.
// The behavior is undefined if len(x) != len(z).
// If len(z) == 0, c = y; otherwise, c is 0 or 1.
//
// subVW should be an internal detail,
// but widely used packages access it using linkname.
// Notable members of the hall of shame include:
// - github.com/remyoudompheng/bigfft
//
// Do not remove or change the type signature.
// See go.dev/issue/67401.
//
//go:linkname subVW
func subVW(, []Word, Word) ( Word) {
if len() != len() {
panic("subVW len")
}
if len() == 0 {
return
}
, := bits.Sub(uint([0]), uint(), 0)
[0] = Word()
if == 0 {
if &[0] != &[0] {
copy([1:], [1:])
}
return 0
}
for := 1; < len(); ++ {
:= []
if != 0 {
[] = - 1
if &[0] != &[0] {
copy([+1:], [+1:])
}
return 0
}
[] = ^Word(0)
}
return 1
}
// subVW_ref is the reference implementation for subVW, used only for testing.
func subVW_ref(, []Word, Word) ( Word) {
=
for := range {
, := bits.Sub(uint([]), uint(), 0)
[] = Word()
= Word()
}
return
}
func lshVU_g(, []Word, uint) ( Word) {
if len() != len() {
panic("lshVU len")
}
if == 0 {
copy(, )
return
}
if len() == 0 {
return
}
&= _W - 1 // hint to the compiler that shifts by s don't need guard code
:= _W -
&= _W - 1 // ditto
= [len()-1] >>
for := len() - 1; > 0; -- {
[] = []<< | [-1]>>
}
[0] = [0] <<
return
}
func rshVU_g(, []Word, uint) ( Word) {
if len() != len() {
panic("rshVU len")
}
if == 0 {
copy(, )
return
}
if len() == 0 {
return
}
&= _W - 1 // hint to the compiler that shifts by s don't need guard code
:= _W -
&= _W - 1 // ditto
= [0] <<
for := 1; < len(); ++ {
[-1] = [-1]>> | []<<
}
[len()-1] = [len()-1] >>
return
}
func mulAddVWW_g(, []Word, , Word) ( Word) {
if len() != len() {
panic("mulAddVWW len")
}
=
for := range {
, [] = mulAddWWW_g([], , )
}
return
}
func addMulVVWW_g(, , []Word, , Word) ( Word) {
if len() != len() || len() != len() {
panic("rshVU len")
}
=
for := range {
, := mulAddWWW_g([], , [])
, := bits.Add(uint(), uint(), 0)
, [] = Word(), Word()
+=
}
return
}
// q = ( x1 << _W + x0 - r)/y. m = floor(( _B^2 - 1 ) / d - _B). Requiring x1<y.
// An approximate reciprocal with a reference to "Improved Division by Invariant Integers
// (IEEE Transactions on Computers, 11 Jun. 2010)"
func divWW(, , , Word) (, Word) {
:= nlz()
if != 0 {
= << | >>(_W-)
<<=
<<=
}
:= uint()
// We know that
// m = ⎣(B^2-1)/d⎦-B
// ⎣(B^2-1)/d⎦ = m+B
// (B^2-1)/d = m+B+delta1 0 <= delta1 <= (d-1)/d
// B^2/d = m+B+delta2 0 <= delta2 <= 1
// The quotient we're trying to compute is
// quotient = ⎣(x1*B+x0)/d⎦
// = ⎣(x1*B*(B^2/d)+x0*(B^2/d))/B^2⎦
// = ⎣(x1*B*(m+B+delta2)+x0*(m+B+delta2))/B^2⎦
// = ⎣(x1*m+x1*B+x0)/B + x0*m/B^2 + delta2*(x1*B+x0)/B^2⎦
// The latter two terms of this three-term sum are between 0 and 1.
// So we can compute just the first term, and we will be low by at most 2.
, := bits.Mul(uint(), uint())
, := bits.Add(, uint(), 0)
, _ = bits.Add(, uint(), )
// The quotient is either t1, t1+1, or t1+2.
// We'll try t1 and adjust if needed.
:=
// compute remainder r=x-d*q.
, := bits.Mul(, )
, := bits.Sub(uint(), , 0)
, := bits.Sub(uint(), , )
// The remainder we just computed is bounded above by B+d:
// r = x1*B + x0 - d*q.
// = x1*B + x0 - d*⎣(x1*m+x1*B+x0)/B⎦
// = x1*B + x0 - d*((x1*m+x1*B+x0)/B-alpha) 0 <= alpha < 1
// = x1*B + x0 - x1*d/B*m - x1*d - x0*d/B + d*alpha
// = x1*B + x0 - x1*d/B*⎣(B^2-1)/d-B⎦ - x1*d - x0*d/B + d*alpha
// = x1*B + x0 - x1*d/B*⎣(B^2-1)/d-B⎦ - x1*d - x0*d/B + d*alpha
// = x1*B + x0 - x1*d/B*((B^2-1)/d-B-beta) - x1*d - x0*d/B + d*alpha 0 <= beta < 1
// = x1*B + x0 - x1*B + x1/B + x1*d + x1*d/B*beta - x1*d - x0*d/B + d*alpha
// = x0 + x1/B + x1*d/B*beta - x0*d/B + d*alpha
// = x0*(1-d/B) + x1*(1+d*beta)/B + d*alpha
// < B*(1-d/B) + d*B/B + d because x0<B (and 1-d/B>0), x1<d, 1+d*beta<=B, alpha<1
// = B - d + d + d
// = B+d
// So r1 can only be 0 or 1. If r1 is 1, then we know q was too small.
// Add 1 to q and subtract d from r. That guarantees that r is <B, so
// we no longer need to keep track of r1.
if != 0 {
++
-=
}
// If the remainder is still too large, increment q one more time.
if >= {
++
-=
}
return Word(), Word( >> )
}
// reciprocalWord return the reciprocal of the divisor. rec = floor(( _B^2 - 1 ) / u - _B). u = d1 << nlz(d1).
func reciprocalWord( Word) Word {
:= uint( << nlz())
:= ^
:= uint(_M)
, := bits.Div(, , ) // (_B^2-1)/U-_B = (_B*(_M-C)+_M)/U
return Word()
}
![]() |
The pages are generated with Golds v0.7.7-preview. (GOOS=linux GOARCH=amd64) Golds is a Go 101 project developed by Tapir Liu. PR and bug reports are welcome and can be submitted to the issue list. Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds. |