Category talk:Wren-big
Arbitrary precision arithmetic
Many tasks on RC require the use of very large numbers (usually integers) often outside the 64-bit range.
Wren is unable to deal natively and precisely with integers outside a 53-bit range and so either has to limit such tasks to integers which it can deal with or is unable to offer a realistic solution at all.
This module aims to remedy that situation by providing classes for arbitrary precision arithmetic (initially limited to integers) in an easy to use form. It is based on Peter Olson's public domain BigInteger.js library for Javascript, a language which until the recent addition of native BigInt support was in the same boat as Wren regarding the 53-bit limitation.
Some changes or simplifications have been made to fit Wren's ethos more closely. In particular:
- There is no separate SmallInt class; instead integers with a magnitude of less than 2^53 are implemented as a subset of BigInt objects whose value is represented by a simple Num rather than a list of integers.
- There is no support for bases below 2 or (as far as the public interface is concerned) above 36 as practical applications for such bases are very limited. Similarly, support for user-defined digit alphabets has also been excluded.
- As currently written, this module always uses the Random module for random number generation. The latter is an optional part of the Wren distribution and can be used by either embedded or CLI scripts. Although it would not be difficult to allow for other RNGs to be 'plugged in', this would probably only be useful if Wren were being used for secure cryptographic purposes which, realistically, seems unlikely to be the case.
The BigInt.new constructor accepts either a string or a safe integer (i.e. within the normal 53-bit limitation). I couldn't see much point in accepting larger numbers (or floats) as this would inevitably mean that the BigInt object would be imprecise from the outset. Passing an empty string will also produce an error (rather than a zero object) as it's just as easy to pass 0 and an empty string may well be a mistake in any case.
If you need to generate a BigInt from a string in a non-decimal base or from another BigInt, you can use the fromBaseString or copy methods, respectively.
The original Javascript library and this module are easy to use as they try to mimic native arithmetic by always producing immutable objects and by implicitly converting suitable operands into BigInts. This is accentuated further by Wren's support for operator overloading which means that all the familiar operations on numbers can be used.
Of course, such a system inevitably keeps the garbage collector busy and is not going to be as fast and efficient as systems where BigInts are mutable and where memory usage can therefore be managed by the user. On the other hand the latter systems can be difficult or unpleasant to use and it is therefore felt that the present approach is a good fit for Wren where ease of use is paramount.
Source code
<lang ecmascript>/* Module "big.wren" */
import "/trait" for Comparable import "random" for Random
/*
BigInt represents an arbitrary length integer allowing arithmetic operations on integers of unlimited size. Internally, there are two kinds: 'small' (up to a magnitude of 2^53 -1) and 'big' (magnitude >= 2^53). The former are stored as ordinary Nums and the latter as a little-endian list of integers using a base of 1e7. In both cases, there is an additional Bool to indicate whether the integer is signed or not. BigInt objects are immutable.
- /
class BigInt is Comparable {
// Constants.
static minusOne { BigInt.small_(-1) }
static zero { BigInt.small_( 0) }
static one { BigInt.small_( 1) }
static two { BigInt.small_( 2) }
static three { BigInt.small_( 3) }
static four { BigInt.small_( 4) }
static five { BigInt.small_( 5) }
static ten { BigInt.small_(10) }
// Private method to initialize static fields.
static init_() {
// All possible digits for bases 2 to 36.
__alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
// Maximum 'small' integer = 2^53 - 1
__maxSmall = 9007199254740991
// Random number generator.
__rand = Random.new()
// Threshold between small and big integers in 'list' format.
__threshold = smallToList_(9007199254740992)
// List of powers of 2 up to 1e7.
__powersOfTwo = powersOfTwo_
// Length of __powersOfTwo (pre-computed).
__powers2Length = 24
// Last element of __powersOfTwo (pre-computed).
__highestPower2 = 8388608
}
// Returns the maximum 'small' BigInt = 2^53-1.
static maxSmall { BigInt.small_(__maxSmall) }
// Private property which returns powers of 2 up to 1e7.
static powersOfTwo_ {
var pot = [1]
while (2 * pot[-1] <= 1e7) pot.add(2 * pot[-1])
return pot
}
// Private method which returns the lowest one bit of a BigInt (rough).
static roughLOB_(n) {
var lobmask_i = 1 << 30
var v = n.value_
var x
if (n.isSmall) {
x = v | lobmask_i
} else {
var base = 1e7
var lobmask_bi = (base & -base) * (base & -base) | lobmask_i
x = v[0] + v[1]*base | lobmask_bi
}
return x & -x
}
// Private method to return the integer logarithm of 'value' with respect to base 'base'
// i.e.the number of times 'base' can be multiplied by itself without exceeding 'value'.
static integerLogarithm_(value, base) {
if (base <= value) {
System.write("") // guard against VM recursion bug
var tmp = integerLogarithm_(value, base.square)
var p = tmp[0]
var e = tmp[1]
var t = p * base
return (t <= value) ? [t, e*2 + 1] : [p, e * 2]
}
return [one, 0]
}
// Private method to determine whether a number is a small integer or not.
static isSmall_(n) { (n is Num) && n.isInteger && n.abs <= __maxSmall }
// Private method to convert a small integer to list format.
static smallToList_(n) {
if (n < 1e7) return [n]
if (n < 1e14) return [n % 1e7, (n/1e7).floor]
return [n % 1e7, ((n/1e7).floor) % 1e7, (n/1e14).floor]
}
// Private method to convert a list to a small integer where possible.
static listToSmall_(a) {
trim_(a)
var length = a.count
var base = 1e7
if (length < 4 && compareAbs_(a, __threshold) < 0) {
if (length == 0) return 0
if (length == 1) return a[0]
if (length == 2) return a[0] + a[1]*base
return a[0] + (a[1] + a[2]*base) * base
}
return a
}
// Private method to check whether the magnitude of a number n <= 1e7.
static shiftIsSmall_(n) { n.abs <= 1e7 }
// Private method to remove any trailing zero elements from a list.
static trim_(a) {
var i = a.count - 1
while(i >= 0 && a[i] == 0) {
a.removeAt(i)
i = i - 1
}
}
// Private method to compare two lists, first by length and then by contents.
static compareAbs_(a, b) {
if (a.count != b.count) return (a.count > b.count) ? 1 : -1
var i = a.count - 1
while (i >= 0) {
if (a[i] != b[i]) return (a[i] > b[i]) ? 1 : -1
i = i - 1
}
return 0
}
// Private method to add two lists where a.count >= b.count.
static add_(a, b) {
var la = a.count
var lb = b.count
var r = List.filled(la, 0)
var carry = 0
var base = 1e7
var sum = 0
var i = 0
while (i < lb) {
sum = a[i] + b[i] + carry
carry = (sum >= base) ? 1 : 0
r[i] = sum - carry*base
i = i + 1
}
while (i < la) {
sum = a[i] + carry
carry = (sum == base) ? 1 : 0
r[i] = sum - carry*base
i = i + 1
}
if (carry > 0) r.add(carry)
return r
}
// Private method to add two lists regardless of length.
static addAny_(a, b) { (a.count >= b.count) ? add_(a, b) : add_(b, a) }
// Private method to add 'carry' (0 <= carry <= maxSmall) to a list 'a'.
static addSmall_(a, carry) {
var l = a.count
var r = List.filled(l, 0)
var base = 1e7
var sum = 0
for (i in 0...l) {
sum = a[i] - base + carry
carry = (sum/base).floor
r[i] = sum - carry*base
carry = carry + 1
}
while (carry > 0) {
r.add(carry % base)
carry = (carry/base).floor
}
return r
}
// Private method to subtract two lists where a.count >= b.count.
static subtract_(a, b) {
var la = a.count
var lb = b.count
var r = List.filled(la, 0)
var borrow = 0
var base = 1e7
var diff = 0
var i = 0
while (i < lb) {
diff = a[i] - borrow - b[i]
if (diff < 0) {
diff = diff + base
borrow = 1
} else borrow = 0
r[i] = diff
i = i + 1
}
while (i < la) {
diff = a[i] - borrow
if (diff < 0) {
diff = diff + base
} else {
r[i] = diff
i = i + 1
break
}
r[i] = diff
i = i + 1
}
while (i < la) {
r[i] = a[i]
i = i + 1
}
trim_(r)
return r
}
// Private method to subtract lists regardless of length.
static subtractAny_(a, b, signed) {
var value
if (compareAbs_(a, b) >= 0) {
value = subtract_(a, b)
} else {
value = subtract_(b, a)
signed = !signed
}
value = listToSmall_(value)
if (value is Num) {
if (signed) value = -value
return BigInt.small_(value)
}
return BigInt.big_(value, signed)
}
// Private method to subtract 'b' (0 <= b <= maxSmall) from a list 'a'.
static subtractSmall_(a, b, signed) {
var l = a.count
var r = List.filled(l, 0)
var carry = -b
var base = 1e7
for (i in 0...l) {
var diff = a[i] + carry
carry = (diff/base).floor
diff = diff % base
r[i] = (diff < 0) ? diff + base : diff
}
r = listToSmall_(r)
if (r is Num) {
if (signed) r = -r
return BigInt.small_(r)
}
return BigInt.big_(r, signed)
}
// Private method to multiply two lists.
static multiplyLong_(a, b) {
var la = a.count
var lb = b.count
var l = la + lb
var r = List.filled(l, 0)
var base = 1e7
for (i in 0...la) {
var ai = a[i]
for (j in 0...lb) {
var bj = b[j]
var prod = ai*bj + r[i + j]
var carry = (prod/base).floor
r[i + j] = prod - carry*base
r[i + j + 1] = r[i + j + 1] + carry
}
}
trim_(r)
return r
}
/// Private method to multiply a list 'a' by 'b' (|b| < 1e7).
static multiplySmall_(a, b) {
var l = a.count
var r = List.filled(l, 0)
var base = 1e7
var carry = 0
for (i in 0...l) {
var prod = a[i]*b + carry
carry = (prod/base).floor
r[i] = prod - carry*base
}
while (carry > 0) {
r.add(carry % base)
carry = (carry/base).floor
}
return r
}
// Private helper method for multiplyKaratsuba_ method.
static shiftLeft_(x, n) {
var r = []
while (n > 0) {
n = n - 1
r.add(0)
}
return r + x
}
// Private method to multiply two lists 'x' and 'y' using the Karatsuba algorithm.
static multiplyKaratsuba_(x, y) {
var n = (x.count > y.count) ? x.count : y.count
if (n <= 30) return multiplyLong_(x, y)
n = (n/2).ceil
var a = x[0...n]
var b = x[n..-1]
var c = y[0...n]
var d = y[n..-1]
System.write("") // guard against VM recursion bug
var ac = multiplyKaratsuba_(a, c)
var bd = multiplyKaratsuba_(b, d)
var abcd = multiplyKaratsuba_(addAny_(a, b), addAny_(c, d))
var s = subtract_(subtract_(abcd, ac), bd)
var prod = addAny_(addAny_(ac, shiftLeft_(s, n)), shiftLeft_(bd, 2 * n))
trim_(prod)
return prod
}
// Private method to determine whether Karatsuba multiplication may be beneficial.
static useKaratsuba_(l1, l2) { -0.012*l1 - 0.012*l2 + 0.000015*l1*l2 > 0 }
// Private method to multiply a small integer 'a' (a >= 0) by a list 'b'.
static multiplySmallAndList_(a, b, signed) {
if (a < 1e7) return BigInt.big_(multiplySmall_(b, a), signed)
return BigInt.big_(multiplyLong_(b, smallToList_(a)), signed)
}
// Private method to square a list.
static square_(a) {
var l = a.count
var r = List.filled(l + l, 0)
var base = 1e7
for (i in 0...l) {
var ai = a[i]
var carry = 0 - ai*ai
var j = i
while (j < l) {
var aj = a[j]
var prod = 2*ai*aj + r[i + j] + carry
carry = (prod/base).floor
r[i + j] = prod - carry*base
j = j + 1
}
r[i + l] = carry
}
trim_(r)
return r
}
// Private method to 'div/mod' two lists, better for smaller sizes.
static divMod1_(a, b) {
var la = a.count
var lb = b.count
var base = 1e7
var result = List.filled(la - lb + 1, 0)
var divMostSigDigit = b[-1]
// normalization
var lambda = (base/(2*divMostSigDigit)).ceil
var remainder = multiplySmall_(a, lambda)
var divisor = multiplySmall_(b, lambda)
if (remainder.count <= la) remainder.add(0)
divisor.add(0)
divMostSigDigit = divisor[lb-1]
var shift = la - lb
while (shift >= 0) {
var quotDigit = base - 1
if (remainder[shift+lb] != divMostSigDigit) {
quotDigit = ((remainder[shift+lb]*base + remainder[shift+lb-1])/divMostSigDigit).floor
}
var carry = 0
var borrow = 0
var l = divisor.count
for (i in 0...l) {
carry = carry + quotDigit*divisor[i]
var q = (carry/base).floor
borrow = borrow + remainder[shift+i] - (carry - q*base)
carry = q
if (borrow < 0) {
remainder[shift+i] = borrow + base
borrow = -1
} else {
remainder[shift+i] = borrow
borrow = 0
}
}
while (borrow != 0) {
quotDigit = quotDigit - 1
carry = 0
for (i in 0...l) {
carry = carry + remainder[shift+i] - base + divisor[i]
if (carry < 0) {
remainder[shift+i] = carry + base
carry = 0
} else {
remainder[shift+i] = carry
carry = 1
}
}
borrow = borrow + carry
}
result[shift] = quotDigit
shift = shift - 1
}
// denormalization
remainder = divModSmall_(remainder, lambda)[0]
return [listToSmall_(result), listToSmall_(remainder)]
}
// Private method to 'div/mod' two lists, better for larger sizes.
static divMod2_(a, b) {
var la = a.count
var lb = b.count
var result = []
var part = []
var base = 1e7
while (la != 0) {
la = la - 1
part = a[la..la] + part
trim_(part)
if (compareAbs_(part, b) < 0) {
result.add(0)
} else {
var xlen = part.count
var highx = part[xlen-1]*base + part[xlen-2]
var highy = b[lb-1]*base + b[lb-2]
if (xlen > lb) highx = (highx + 1) * base
var guess = (highx/highy).ceil
var check
while (true) {
check = multiplySmall_(b, guess)
if (compareAbs_(check, part) <= 0) break
guess = guess - 1
if (guess == 0) break
}
result.add(guess)
part = subtract_(part, check)
}
}
result = result[-1..0]
return [listToSmall_(result), listToSmall_(part)]
}
// Private method to 'div/mod' a list 'value' with an integer 'lambda'.
static divModSmall_(value, lambda) {
var length = value.count
var quot = List.filled(length, 0)
var base = 1e7
var remainder = 0
var i = length - 1
while (i >= 0) {
var divisor = remainder*base + value[i]
var q = (divisor/lambda).truncate
remainder = divisor - q*lambda
quot[i] = q | 0
i = i - 1
}
return [quot, remainder | 0]
}
// Private method to 'div/mod' any two BigInts.
static divModAny_(self, n) {
var a = self.value_
if (!(n is BigInt)) n = BigInt.new(n)
var b = n.value_
if (b == 0) Fiber.abort("Cannot divide by zero.")
if (self.isSmall) {
if (n.isSmall) {
var c = (a/b).truncate
return [BigInt.small_(c), BigInt.small_(a % b)]
}
return [zero, self]
}
var quotient
if (n.isSmall) {
if (b == 1) return [self, zero]
if (b == -1) return [-self, zero]
var ab = b.abs
if (ab < 1e7) {
var value = divModSmall_(a, ab)
quotient = listToSmall_(value[0])
var remainder = value[1]
if (self.signed_) remainder = -remainder
if (quotient is Num) {
if (self.signed_ != n.signed_) quotient = -quotient
return [BigInt.small_(quotient), BigInt.small_(remainder)]
}
return [BigInt.big_(quotient, self.signed_ != n.signed_), BigInt.small_(remainder)]
}
b = smallToList_(ab)
}
var comparison = compareAbs_(a, b)
if (comparison == -1) return [BigInt.zero, self]
if (comparison == 0) return [(self.signed_ == n.signed_) ? one : minusOne, zero]
// divMod1 is faster on smaller input sizes
var value = (a.count + b.count <= 200) ? divMod1_(a, b) : divMod2_(a, b)
quotient = value[0]
var qSign = self.signed_ != n.signed_
var mod = value[1]
var mSign = self.signed_
if (quotient is Num) {
if (qSign) quotient = -quotient
quotient = BigInt.small_(quotient)
} else quotient = BigInt.big_(quotient, qSign)
if (mod is Num) {
if (mSign) mod = -mod
mod = BigInt.small_(mod)
} else mod = BigInt.big_(mod, mSign)
return [quotient, mod]
}
// Private method to determine if a BigInt is a basic prime or not.
static isBasicPrime_(n) {
if (!(n is BigInt)) n = BigInt.new(n)
if (n.isUnit) return false
if (n == two || n == three || n == five) return true
if (n.isEven || n.isDivisibleBy(three) || n.isDivisibleBy(five)) return false
if (n < 49) return true
return null // unknown if prime or not
}
// Private method to apply the Miller-Rabin test.
static millerRabinTest_(n, a) {
var nPrev = n.dec
var b = nPrev
var r = 0
while (b.isEven) {
b = b / two
r = r + 1
}
for (i in 0...a.count) {
if (n >= a[i]) {
var x = (a[i] is BigInt) ? a[i] : BigInt.new(a[i])
x = x.modPow(b, n)
if (!x.isUnit && x != nPrev) {
var d = r - 1
var next = false
while (d != 0) {
x = x.square % n
if (x.isUnit) return false
if (x == nPrev) {
next = true
break
}
d = d - 1
}
if (!next) return false
}
}
}
return true
}
// Private method to perform bitwise operations depending on the 'fn' passed in.
static bitwise_(x, y, fn) {
if (!(y is BigInt)) y = BigInt.new(y)
var xSign = x.isNegative
var ySign = y.isNegative
var xRem = xSign ? ~x : x
var yRem = ySign ? ~y : y
var result = []
while (!xRem.isZero || !yRem.isZero) {
var xDivMod = divModAny_(xRem, __highestPower2)
var xDigit = xDivMod[1].toNum
if (xSign) {
xDigit = __highestPower2 - 1 - xDigit // two's complement for negative numbers
}
var yDivMod = divModAny_(yRem, __highestPower2)
var yDigit = yDivMod[1].toNum
if (ySign) {
yDigit = __highestPower2 - 1 - yDigit // two's complement for negative numbers
}
xRem = xDivMod[0]
yRem = yDivMod[0]
result.add(fn.call(xDigit, yDigit))
}
var sum = fn.call(xSign ? 1 : 0, ySign ? 1 : 0) != 0 ? minusOne : zero
var i = result.count - 1
var hp2 = BigInt.small_(__highestPower2)
while (i >= 0) {
sum = sum * hp2 + BigInt.new(result[i])
i = i - 1
}
return sum
}
// Returns the greater of two BigInts.
static max(a, b) {
if (!(a is BigInt)) a = BigInt.new(a)
if (!(b is BigInt)) b = BigInt.new(b)
return (a > b) ? a : b
}
// Returns the lesser of two BigInts.
static min(a, b) {
if (!(a is BigInt)) a = BigInt.new(a)
if (!(b is BigInt)) b = BigInt.new(b)
return (a < b) ? a : b
}
// Returns the greatest common denominator of a and b.
static gcd(a, b) {
if (!(a is BigInt)) a = BigInt.new(a)
if (!(b is BigInt)) b = BigInt.new(b)
a = a.abs
b = b.abs
if (a == b) return a
if (a.isZero) return b
if (b.isZero) return a
var c = one
while (a.isEven && b.isEven) {
var d = min(roughLOB_(a), roughLOB_(b))
a = a / d
b = b / d
c = c * d
}
while (a.isEven) a = a / roughLOB_(a)
while (true) {
while (b.isEven) b = b / roughLOB_(b)
if (a > b) {
var t = b
b = a
a = t
}
b = b - a
if (b.isZero) break
}
return c.isUnit ? a : a * c
}
// Returns the least common multiple of a and b.
static lcm(a, b) {
if (!(a is BigInt)) a = BigInt.new(a)
if (!(b is BigInt)) b = BigInt.new(b)
return a / gcd(a, b) * b
}
// Returns whether or not 'n' is an instance of BigInt.
static isInstance(n) { n is BigInt }
// Private helper method for 'randBetween'.
static fromList_(digits, base, isNegative) {
var digits2 = digits.map { |d| BigInt.new(d) }.toList
return parseBaseFromList_(digits2, BigInt.new(base || 10), isNegative)
}
// Returns a random number between 'a' (inclusive) and 'b' (exclusive).
static randBetween(a, b) {
if (!(a is BigInt)) a = BigInt.new(a)
if (!(b is BigInt)) b = BigInt.new(b)
var low = min(a, b)
var high = max(a, b)
var range = high - low + one
if (range.isSmall) return low + (range.value_ * __rand.float()).floor
var digits = toBase_(range, 1e7)[0]
var result = []
var restricted = true
for (i in 0...digits.count) {
var top = restricted ? digits[i] : 1e7
var digit = (top * __rand.float()).truncate
result.add(digit)
if (digit < top) restricted = false
}
return low + fromList_(result, 1e7, false)
}
// Private method to provide the components for converting a BigInt to a different base.
static toBase_(n, base) {
if (!(base is BigInt)) base = BigInt.new(base)
if (base < two) Fiber.abort("Bases less than 2 are not supported.")
var neg = false
if (n.isNegative) {
neg = true
n = n.abs
}
var out = []
var left = n
while (left.isNegative || left.compareAbs(base) >= 0) {
var divmod = left.divMod(base)
left = divmod[0]
var digit = divmod[1]
if (digit.isNegative) {
digit = (base - digit).abs
left = left.inc
}
out.add(digit.toNum)
}
out.add(left.toNum)
return [out[-1..0], neg]
}
// Private method to parse a list, in a given base, to a BigInt.
static parseBaseFromList_(digits, base, isNegative) {
var val = zero
var pow = one
var i = digits.count - 1
while (i >= 0) {
val = val + digits[i]*pow
pow = pow * base
i = i - 1
}
return isNegative ? -val : val
}
// Private method to parse a numeric string, in a given base (2 to 36), to a BigInt.
static parseBase_(text, base) {
text = text.trim()
if (text.count == 0) Fiber.abort("Invalid base string.")
if (base > 10) text = lower_(text)
var alphabet = __alphabet[0...base]
var isNegative = text[0] == "-"
if (isNegative || text[0] == "+") {
text = text[1..-1]
if (text.count == 0) Fiber.abort("Invalid base string.")
}
text = text.trimStart("0")
if (text == "") text = "0"
base = BigInt.small_(base)
var digits = []
for (c in text) {
var ix = alphabet.indexOf(c)
if (ix == - 1) Fiber.abort("%(c) is not a valid digit in base %(base).")
digits.add(BigInt.small_(ix))
}
return parseBaseFromList_(digits, base, isNegative)
}
// Private helper function to convert a string to lower case.
static lower_(s) { s.codePoints.map { |c|
return String.fromCodePoint((c >= 65 && c <= 90) ? c + 32 : c)
}.join() }
// Private method to parse a base 10 numeric string 'v' to the components for a BigInt.
static parseString_(v) {
v = v.trim()
if (v.count == 0) Fiber.abort("Invalid integer.")
var signed = v[0] == "-"
if (signed || v[0] == "+") {
v = v[1..-1]
if (v.count == 0) Fiber.abort("Invalid integer.")
}
v = v.trimStart("0")
if (v == "") v = "0"
v = lower_(v)
var split = v.split("e")
if (split.count > 2) Fiber.abort("Invalid integer.")
if (split.count == 2) {
var exp = split[1]
if (exp[0] == "+") exp = exp[1..-1]
exp = Num.fromString(exp)
if (!isSmall_(exp)) Fiber.abort("Exponent is not valid.")
var text = split[0]
var dp = text.indexOf(".")
if (dp >= 0) {
exp = exp - (text.count - dp - 1)
text = text[0...dp] + text[dp+1..-1]
}
if (exp < 0) Fiber.abort("Exponent cannot be negative.")
text = text + ("0" * exp)
v = text
}
var isValid = v.count > 0 && v.all { |d| "0123456789".contains(d) }
if (!isValid) Fiber.abort("Invalid integer.")
if (v.count <= 16) {
var n = Num.fromString(v)
if (isSmall_(n)) return (signed) ? [-n, true] : [n, false]
}
var r = []
var max = v.count
var lb = 7
var min = max - lb
while (max > 0) {
r.add(Num.fromString(v[min...max]))
min = min - lb
if (min < 0) min = 0
max = max - lb
}
trim_(r)
return [r, signed]
}
// Constructs a BigInt object from either a numeric base 10 string or a 'safe' integer.
construct new(value) {
if (!(value is String) && !BigInt.isSmall_(value)) {
Fiber.abort("Value must be a base 10 numeric string or a safe integer.")
}
if (value is String) {
var res = BigInt.parseString_(value)
_value = res[0]
_signed = res[1]
} else {
_value = value
_signed = value < 0
}
}
// Creates a BigInt object from an (unprefixed) numeric string in a given base (2 to 36).
static fromBaseString(s, base) {
if (!(s is String)) Fiber.abort("Value must be a numeric string in the given base.")
if (!((base is Num) && base.isInteger && base >= 2 && base <= 36)) {
Fiber.abort("Base must be an integer between 2 and 36.")
}
if (base == 10) return BigInt.new(s)
return parseBase_(s, base)
}
// Private constructor which creates a BigInt object from a list of integers and a bool.
construct big_(a, signed) {
_value = a
_signed = signed
}
// Private constructor which creates a BigInt object from a 'safe' integer and a bool.
construct small_(a) {
_value = a
_signed = a < 0
}
// Private properties for internal use.
value_ { _value }
signed_ { _signed }
// Public self-evident properties.
isSmall { !(_value is List) }
isEven { (this.isSmall) ? (_value & 1) == 0 : (_value[0] & 1) == 0 }
isOdd { (this.isSmall) ? (_value & 1) == 1 : (_value[0] & 1) == 1 }
isPositive { (this.isSmall) ? (_value > 0) : !_signed }
isNegative { (this.isSmall) ? (_value < 0) : _signed }
isUnit { (this.isSmall) ? _value.abs == 1 : false }
isZero { (this.isSmall) ? _value == 0 : false }
isDivisibleBy(n) {
if (!(n is BigInt)) n = BigInt.new(n)
if (n.isZero) return false
if (n.isUnit) return true
if (n.compareAbs(BigInt.two) == 0) return this.isEven
return (this % n).isZero
}
// Returns true if the current instance is prime, false otherwise.
// Setting 'strict' to true enforces the GRH-supported lower bound of 2*log(N)^2.
isPrime(strict) {
if (!(strict is Bool)) Fiber.abort("Argument must be a boolean.")
var isbp = BigInt.isBasicPrime_(this)
if (isbp != null) return isbp
var n = this.abs
var bits = n.bitLength
if (bits <= 64) {
return BigInt.millerRabinTest_(n, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])
}
var logN = 2.log * bits.toNum
var t = ((strict) ? (2 * logN.pow(2)) : logN).ceil
var a = []
for (i in 0...t) a.add(BigInt.new(i+2))
return BigInt.millerRabinTest_(n, a)
}
// Returns true if the current instance is very likely to be prime, false otherwise.
// The larger the number of 'iterations', the lower the chance of a false positive.
isProbablePrime(iterations) {
if (!((iterations is Num) && iterations.isInteger && iterations > 0)) {
Fiber.abort("Iterations must be a positive integer.")
}
var isbp = BigInt.isBasicPrime_(this)
if (isbp != null) return isbp
var n = this.abs
var a = []
for (i in 0...iterations) a.add(BigInt.randBetween(BigInt.two, n - BigInt.two))
return BigInt.millerRabinTest_(n, a)
}
// Convenience versions of the above methods which use default parameter values.
isPrime { isPrime(false) }
isProbablePrime { isProbablePrime(5) }
// Negates a BigInt.
- { (this.isSmall) ? BigInt.small_(-_value) : BigInt.big_(_value, !_signed) }
// Private method which adds a BigInt to a 'small' current instance.
smallAdd_(n) {
var a = _value
if (_signed != n.signed_) return this - (-n)
var b = n.value_
if (n.isSmall) {
var c = a + b
if (BigInt.isSmall_(c)) return BigInt.small_(c)
b = BigInt.smallToList_(b.abs)
}
return BigInt.big_(BigInt.addSmall_(b, a.abs), _signed)
}
// Adds a BigInt to the current instance.
+ (n) {
if (!(n is BigInt)) n = BigInt.new(n)
if (this.isSmall) return smallAdd_(n)
if (_signed != n.signed_) return this - (-n)
var a = _value
var b = n.value_
if (n.isSmall) {
return BigInt.big_(BigInt.addSmall_(a, b.abs), _signed)
}
return BigInt.big_(BigInt.addAny_(a, b), _signed)
}
// Private method which subtracts a BigInt from a 'small' current instance.
smallSubtract_(n) {
var a = _value
if (_signed != n.signed_) return this + (-n)
var b = n.value_
if (n.isSmall) return BigInt.small_(a - b)
return BigInt.subtractSmall_(b, a.abs, !_signed)
}
// Subtracts a BigInt from the current instance.
- (n) {
if (!(n is BigInt)) n = BigInt.new(n)
if (this.isSmall) return smallSubtract_(n)
if (_signed != n.signed_) return this + (-n)
var a = _value
var b = n.value_
if (n.isSmall) return BigInt.subtractSmall_(a, b.abs, _signed)
return BigInt.subtractAny_(a, b, _signed)
}
// Private method which multiplies the current instance by a 'small' BigInt.
multiplyBySmall_(a) {
if (this.isSmall) {
var c = a.value_ * _value
if (BigInt.isSmall_(c)) return BigInt.small_(c)
c = a.value_.abs
return BigInt.multiplySmallAndList_(c, BigInt.smallToList_(_value.abs), _signed != a.signed_)
}
if (a.value_ == 0) return BigInt.zero
if (a.value_ == 1) return this
if (a.value_ == -1) return -this
return BigInt.multiplySmallAndList_(a.value_.abs, _value, _signed != a.signed_)
}
// Multiplies the current instance by a BigInt.
* (n) {
if (!(n is BigInt)) n = BigInt.new(n)
if (this.isSmall) return n.multiplyBySmall_(this)
var a = _value
var b = n.value_
var signed = _signed != n.signed_
if (n.isSmall) {
if (b == 0) return BigInt.zero
if (b == 1) return this
if (b == -1) return -this
var ab = b.abs
if (ab < 1e7) return BigInt.big_(BigInt.multiplySmall_(a, ab), signed)
b = BigInt.smallToList_(ab)
}
if (BigInt.useKaratsuba_(a.count, b.count)) {
return BigInt.big_(BigInt.multiplyKaratsuba_(a, b), signed)
}
return BigInt.big_(BigInt.multiplyLong_(a, b), signed)
}
// Square the current instance.
square {
if (this.isSmall) {
var value = _value * _value
if (BigInt.isSmall_(value)) return BigInt.small_(value)
return BigInt.big_(BigInt.square_(BigInt.smallToList_(_value.abs)), false)
}
return BigInt.big_(BigInt.square_(_value), false)
}
// Returns the integer square root of the current instance i.e. the largest integer 'r' such that
// r.square <= this. Throws an error if the current instance is negative.
isqrt {
if (this.isNegative) Fiber.abort("Cannot take the square root of a negative number.")
var q = BigInt.one
while (q <= this) q = q * 4
var z = this.copy()
var r = BigInt.zero
while (q > BigInt.one) {
q = q / 4
var t = z - r - q
r = r / 2
if (t >= 0) {
z = t
r = r + q
}
}
return r
}
// Returns a list containing the quotient and the remainder after dividing the current instance
// by a BigInt. The sign of the remainder will match the sign of the dividend.
divMod(n) {
if (!(n is BigInt)) n = BigInt.new(n)
return BigInt.divModAny_(this, n)
}
// Divides the current instance by a BigInt.
/(n) {
if (!(n is BigInt)) n = BigInt.new(n)
return BigInt.divModAny_(this, n)[0]
}
// Returns the remainder after dividing the current instance by a BigInt.
// The sign of the remainder will match the sign of the dividend.
%(n) {
if (!(n is BigInt)) n = BigInt.new(n)
return BigInt.divModAny_(this, n)[1]
}
// Returns the current instance raised to the power of a 'small' BigInt.
// If the exponent is less than 0, returns 0. O.pow(0) returns one.
pow(n) {
if (!(n is BigInt)) n = BigInt.new(n)
var a = _value
var b = n.value_
if (b == 0) return BigInt.one
if (a == 0) return BigInt.zero
if (a == 1) return BigInt.one
if (a == -1) return n.isEven ? BigInt.one : BigInt.minusOne
if (n.signed_) return BigInt.zero
if (!n.isSmall) Fiber.abort("The exponent %(n) is too large.")
if (this.isSmall) {
var value = a.pow(b)
if (BigInt.isSmall_(value)) return BigInt.small_(value.truncate)
}
var x = this
var y = BigInt.one
while (true) {
if ((b & 1) == 1) {
y = y * x
b = b - 1
}
if (b == 0) break
b = b / 2
x = x.square
}
return y
}
// Returns the current instance to the power 'exp' modulo 'mod'.
modPow(exp, mod) {
if (!(exp is BigInt)) exp = BigInt.new(exp)
if (!(mod is BigInt)) mod = BigInt.new(mod)
if (mod.isZero) Fiber.abort("Cannot take modPow with modulus 0.")
var r = BigInt.one
var base = this % mod
if (exp.isNegative) {
exp = exp * BigInt.minusOne
base = base.modInv(mod)
}
while (exp.isPositive) {
if (base.isZero) return BigInt.zero
if (exp.isOdd) r = (r * base) % mod
exp = exp / BigInt.two
base = base.square % mod
}
return r
}
// Returns the multiplicative inverse of the current instance modulo 'r'.
modInv(n) {
if (!(n is BigInt)) n = BigInt.new(n)
var r = n
var newR = this.abs
var t = BigInt.zero
var newT = BigInt.one
while (!newR.isZero) {
var q = r / newR
var lastT = t
var lastR = r
t = newT
r = newR
newT = lastT - q*newT
newR = lastR - q*newR
}
if (!r.isUnit) Fiber.abort("%(this) and %(n) are not co-prime.")
if (t.compare(BigInt.zero) == -1) t = t + n
if (this.isNegative) return -t
return t
}
// Returns the sign of the current instance: 0 if zero, 1 if positive and -1 otherwise.
sign { (this.isZero) ? 0 : (this.isPositive) ? 1 : -1 }
// Increments the current instance by one.
inc {
var value = _value
if (this.isSmall) {
if (value + 1 <= __maxSmall) return BigInt.small_(value + 1)
return BigInt.big_(__threshold, false)
}
if (_signed) return BigInt.subtractSmall_(value, 1, _signed)
return BigInt.big_(BigInt.addSmall_(value, 1), _signed)
}
// Decrements the current instance by one.
dec {
var value = _value
if (this.isSmall) {
if (value - 1 >= -__maxSmall) return BigInt.small_(value - 1)
return BigInt.big_(__threshold, true)
}
if (_signed) return BigInt.big_(BigInt.addSmall_(value, 1), true)
return BigInt.subtractSmall_(value, 1, _signed)
}
// Bitwise operators. The operands are treated as if they were represented
// using two's complement representation.
~ { (-this).dec }
&(n) { BigInt.bitwise_(this, n, Fn.new { |a, b| a & b }) }
|(n) { BigInt.bitwise_(this, n, Fn.new { |a, b| a | b }) }
^(n) { BigInt.bitwise_(this, n, Fn.new { |a, b| a ^ b }) }
<<(n) {
if (!(n is BigInt)) n = BigInt.new(n)
n = n.toNum
if (!BigInt.shiftIsSmall_(n)) Fiber.abort("%(n) is too large for shifting.")
if (n < 0) return this >> (-n)
var result = this
if (result.isZero) return result
var hp2 = BigInt.small_(__highestPower2)
while (n >= __powers2Length) {
result = result * hp2
n = n - (__powers2Length - 1)
}
return result * __powersOfTwo[n]
}
>>(n) {
if (!(n is BigInt)) n = BigInt.new(n)
n = n.toNum
if (!BigInt.shiftIsSmall_(n)) Fiber.abort("%(n) is too large for shifting.")
if (n < 0) return this << (-n)
var result = this
var remQuo
var hp2 = BigInt.small_(__highestPower2)
while (n >= __powers2Length) {
if (result.isZero || (result.isNegative && result.isUnit)) return result
remQuo = BigInt.divModAny_(result, hp2)
result = remQuo[1].isNegative ? remQuo[0].dec : remQuo[0]
n = n - (__powers2Length - 1)
}
remQuo = BigInt.divModAny_(result, __powersOfTwo[n])
return remQuo[1].isNegative ? remQuo[0].dec : remQuo[0]
}
// Returns the absolute value of the current instance.
abs { (this.isSmall) ? BigInt.small_(_value.abs) : BigInt.big_(_value, false) }
// Compares the current instance with a BigInt. If they are equal returns 0.
// If 'this' is greater, returns 1. Otherwise returns -1.
// Also allows a comparison with an infinite number.
compare(n) {
if ((n is Num) && n.isInfinity) return -n.sign
if (!(n is BigInt)) n = BigInt.new(n)
var a = _value
var b = n.value_
if (this.isSmall) {
if (n.isSmall) return (a == b) ? 0 : a > b ? 1 : -1
if (_signed != n.signed_) return (_signed) ? -1 : 1
return _signed ? 1 : -1
}
if (_signed != n.signed_) return n.signed_ ? 1 : -1
if (n.isSmall) return _signed ? -1 : 1
return BigInt.compareAbs_(a, b) * (_signed ? -1 : 1)
}
// As 'compare' but compares absolute values.
compareAbs(n) {
if ((n is Num) && n.isInfinity) return -n.sign
if (!(n is BigInt)) n = BigInt.new(n)
if (this.isSmall) {
var a = _value.abs
var b = n.value_
if (n.isSmall) {
b = b.abs
return (a == b) ? 0 : (a > b) ? 1 : -1
}
return -1
}
if (n.isSmall) return 1
return BigInt.compareAbs_(_value, n.value_)
}
// Returns the number of digits required to represent the current instance in binary.
bitLength {
var n = this
if (n.isNegative) n = (-n) - BigInt.one
if (n.isZero) return BigInt.zero
return BigInt.new(BigInt.integerLogarithm_(n, BigInt.two)[1]) + BigInt.one
}
// The inherited 'clone' method just returns 'this' as BigInt objects are immutable.
// If you need an actual copy use this method instead.
copy() { (this.isSmall) ? BigInt.small_(_value) : BigInt.big_(_value, _signed) }
// Converts the current instance to a 'small' integer where possible.
// Otherwise returns null.
toSmall { (this.isSmall) ? _value : null }
// Converts the current instance to a Num where possible.
// Will probably lose accuracy if the current instance is not 'small'.
toNum { Num.fromString(this.toString) }
// Returns the string representation of the current instance in a given base (2 to 36).
toBaseString(base) {
if (!((base is Num) && base.isInteger && base >= 2 && base <= 36)) {
Fiber.abort("Base must be an integer between 2 and 36.")
}
if (base == 10) return this.toString
var lst = BigInt.toBase_(this, base)
return (lst[1] ? "-" : "") + lst[0].map { |d| __alphabet[d] }.join("")
}
// Returns the string representation of the current instance in base 10.
toString {
var v = (this.isSmall) ? BigInt.smallToList_(_value.abs) : _value
var l = v.count - 1
var str = v[l].toString
var zeros = "0000000"
var digit = ""
l = l - 1
while (l >= 0) {
digit = v[l].toString
str = str + zeros[digit.count..-1] + digit
l = l - 1
}
var sign = _signed ? "-" : ""
return sign + str
}
}
/* BigInts contains various routines applicable to lists of big integers. */ class BigInts {
static sum(a) { a.reduce(BigInt.zero) { |acc, x| acc + x } }
static prod(a) { a.reduce(BigInt.one) { |acc, x| acc * x } }
static max(a) { a.reduce { |acc, x| (x > acc) ? x : acc } }
static min(a) { a.reduce { |acc, x| (x < acc) ? x : acc } }
}
// Type aliases for classes in case of any name clashes with other modules. var Big_BigInt = BigInt var Big_BigInts = BigInts var Big_Comparable = Comparable // in case imported indirectly
// Initialize static fields. BigInt.init_()</lang>