/*
* Copyright (c) Huawei Technologies Co., Ltd. 2025. All rights reserved.
* This source file is part of the Cangjie project, licensed under Apache-2.0
* with Runtime Library Exception.
*
* See https://cangjie-lang.cn/pages/LICENSE for license information.
*/
// The Cangjie API is in Beta. For details on its capabilities and limitations, please refer to the README file.
package std.math.numeric
import std.math.*
import std.random.*
const DIGIT_DIFF: UInt8 = 0x30
const LETTER_UPPER_DIFF: UInt8 = 0x41 - 0x0A
const LETTER_LOWER_DIFF: UInt8 = 0x61 - 0x0A
let EMPTY_ARRAY: Array<UInt32> = Array<UInt32>()
public struct BigInt <: Comparable<BigInt> & Hashable & ToString {
/**
* Return the signum function of this BigInt.
*
* @return:
* -1: if this BigInt is negative;
* 0: if this BigInt equals to zero;
* 1: if this BigInt is positive.
*/
public prop sign: Int64 {
get() {
if (int == 0 && intArr.size == 0) {
return 0
}
return if (negSign) {
-1
} else {
1
}
}
}
/**
* Return the minmum of the number of bits that can present this BigInt.
* For example, using the fewest bits to present decimal -3 is 101,
* so, if a BigInt's value is decimal -3, it bitLen is 3.
*
* @return: the minmum of the number of bits to present this BigInt.
*/
public prop bitLen: Int64 {
get() {
if (sign == 0) {
return 1
}
// abs in (2^n, 2^(n+1)] return n+2
// such as -5: 1011
// -8: 1000
if (negSign) {
let oneMore = if (isPowerOfTwo()) {
0
} else {
1
}
if (intArr.size == 0) {
// -1: 11
if (int == 1) {
return 2
}
return Int64(64 - leadingZeros(int)) + oneMore
} else {
return 32 * intArr.size - Int64(leadingZeros(intArr[intArr.size - 1])) + 64 + oneMore
}
// abs in [2^n, 2^(n+1)) return n+1
// such as 8: 1000
// 15: 1111
} else {
if (intArr.size == 0) {
return Int64(64 - leadingZeros(int))
} else {
return 32 * intArr.size - Int64(leadingZeros(intArr[intArr.size - 1])) + 64
}
}
}
}
BigInt(
let int: UInt64,
let intArr: Array<UInt32>,
let negSign: Bool
) {}
/**
* Constructs a prime of a BigInt, which is in the range of [0, 2 ^ {bitLen} - 1].
* The probability that the BigInt constructed is not a prime is at most (1 / 4 ^ {@p certainty}).
*
* @param bitLen: the number of bits to construct the BigInt;
* @param certainty: a measure of a probability that the result is not a prime;
* @param rand: source of randomness to construct the BigInt.
*
* @throw IllegalArgumentException, if @p bitLen <= 1.
*/
public static func randomProbablePrime(bitLen: Int64, certainty: UInt64, rand!: Random = Random()): BigInt {
if (bitLen <= 1) {
throw IllegalArgumentException("The bitLen of the BigInt must > 1.")
}
var randBig = BigInt(true, bitLen, rand: rand)
while (!randBig.isProbablePrime(certainty)) {
randBig = BigInt(true, bitLen, rand: rand)
}
return randBig
}
/**
* Translates a byte array @p bytes containing the two's-complement binary into a BigInt.
* @p bytes is in big-endian byte-order, which means that
* the most significant byte is @p bytes[0].
*
* @param bytes: a binary number to construct the BigInt.
*
* @throw IllegalArgumentException if the size of @p bytes is zero.
*/
public init(bytes: Array<Byte>) {
if (bytes.size == 0) {
throw IllegalArgumentException("The size of bytes cannot be zero!")
}
let negSign: Bool
let byteArray: Array<Byte>
if ((bytes[0] >> 7) == 1) {
negSign = true
byteArray = removeLeftZero(compToMag(bytes))
} else {
negSign = false
byteArray = removeLeftZero(bytes)
}
if (byteArray.size <= 8) {
this.int = fromBigBytesToU64(byteArray)
this.intArr = EMPTY_ARRAY
} else {
this.int = fromBigBytesToU64(removeLeftZero(byteArray[byteArray.size - 8..]))
this.intArr = fromBigBytesToSmallU32Array(byteArray[..byteArray.size - 8])
}
this.negSign = negSign
}
/**
* Translates a sign-magnitude, whose sign is @p sign and magnitude is @p magnitude, into a BigInt.
* @p magnitude is in big-endian byte-order.
* Note that if the size of @p bytes is zero, translating magnitude = 0 to the BigInt.
*
* @param sign: signum of the number, false for negitive and true for non-negtive;
* @param magnitude: big-endian binary representation of the magnitude of the number
*
* @throw IllegalArgumentException if the value of @p magnitude is 0 and @p sign = false.
*/
public init(sign: Bool, magnitude: Array<Byte>) {
this.negSign = !sign
let byteArray = removeLeftZero(magnitude)
if (byteArray.size == 0) {
if (sign) {
this.int = 0
this.intArr = EMPTY_ARRAY
return
} else {
throw IllegalArgumentException("The size or the value of magnitude cannot be zero if sign is true!")
}
}
if (byteArray.size <= 8) {
this.int = fromBigBytesToU64(byteArray)
this.intArr = EMPTY_ARRAY
} else {
this.int = fromBigBytesToU64(removeLeftZero(byteArray[byteArray.size - 8..]))
this.intArr = fromBigBytesToSmallU32Array(byteArray[..byteArray.size - 8])
}
}
/**
* Translate an Int8 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: Int8) {
this.intArr = EMPTY_ARRAY
(this.int, this.negSign) = if (n >= 0) {
(UInt64(n), false)
} else {
if (n == Int8.Min) {
(UInt64(0x80), true)
} else {
(UInt64(-n), true)
}
}
}
/**
* Translate an Int16 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: Int16) {
this.intArr = EMPTY_ARRAY
(this.int, this.negSign) = if (n >= 0) {
(UInt64(n), false)
} else {
if (n == Int16.Min) {
(UInt64(0x8000), true)
} else {
(UInt64(-n), true)
}
}
}
/**
* Translate an Int32 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: Int32) {
this.intArr = EMPTY_ARRAY
(this.int, this.negSign) = if (n >= 0) {
(UInt64(n), false)
} else {
if (n == Int32.Min) {
(UInt64(0x8000_0000), true)
} else {
(UInt64(-n), true)
}
}
}
/**
* Translate an Int64 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: Int64) {
this.intArr = EMPTY_ARRAY
(this.int, this.negSign) = if (n >= 0) {
(UInt64(n), false)
} else {
if (n == Int64.Min) {
(UInt64(1) << 63, true)
} else {
(UInt64(-n), true)
}
}
}
/**
* Translate an UInt8 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: UInt8) {
this(UInt64(n))
}
/**
* Translate an UInt16 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: UInt16) {
this(UInt64(n))
}
/**
* Translate an UInt32 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: UInt32) {
this(UInt64(n))
}
/**
* Translate an UInt64 type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: UInt64) {
this.int = n
this.intArr = EMPTY_ARRAY
this.negSign = false
}
/**
* Translate an UIntNative type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: UIntNative) {
this(UInt64(n))
}
/**
* Translate an IntNative type value @p val into a BigInt.
*
* @param n: a value translated to a BigInt.
*/
public init(n: IntNative) {
this.intArr = EMPTY_ARRAY
(this.int, this.negSign) = if (n >= 0) {
(UInt64(n), false)
} else {
if (n == IntNative.Min) {
(!UInt64(UIntNative.Max >> 1), true)
} else {
(UInt64(-n), true)
}
}
}
/**
* Translate an Float16 type value @p n into a BigInt.
* Any fractional part of this Float will be discarded.
*
* @param n: a value translated to a BigInt.
*/
public init(n: Float16) {
let tmp = Decimal(n).toBigInt()
(this.int, this.intArr, this.negSign) = (tmp.int, tmp.intArr, tmp.negSign)
}
/**
* Translate an Float32 type value @p n into a BigInt.
* Any fractional part of this Float will be discarded.
*
* @param n: a value translated to a BigInt.
*/
public init(n: Float32) {
let tmp = Decimal(n).toBigInt()
(this.int, this.intArr, this.negSign) = (tmp.int, tmp.intArr, tmp.negSign)
}
/**
* Translate an Float64 type value @p n into a BigInt.
* Any fractional part of this Float will be discarded.
*
* @param n: a value translated to a BigInt.
*/
public init(n: Float64) {
let tmp = Decimal(n).toBigInt()
(this.int, this.intArr, this.negSign) = (tmp.int, tmp.intArr, tmp.negSign)
}
/**
* Construct a sign-magnitude, whose sign is @p sign and
* magnitude is generated randomly in the range of [0, 2 ^ {bitLen} - 1]
*
* @param sign: signum of the number, false for negitive and true for non-negtive;
* @param bitLen: the maximum number of bits in magnitude;
* @param rand: source of randomness to construct @p magnitude.
*
* @throw IllegalArgumentException, if @p bitLen <= 0.
*/
public init(sign: Bool, bitLen: Int64, rand!: Random = Random()) {
if (bitLen <= 0) {
throw IllegalArgumentException("The bitLen of the BigInt must > 0.")
}
if (bitLen <= 64) {
int = rand.nextBits(UInt64(bitLen))
intArr = EMPTY_ARRAY
if (int == 0) {
negSign = false
} else {
negSign = !sign
}
return
}
let (arrIndex, uInt32Len) = arrIndexAndU32Index(bitLen)
int = rand.nextUInt64()
let uInt32Arr: Array<UInt32>
if (uInt32Len == 0) {
uInt32Arr = Array<UInt32>(arrIndex, repeat: 0)
} else {
uInt32Arr = Array<UInt32>(arrIndex + 1, repeat: 0)
uInt32Arr[arrIndex] = UInt32(rand.nextBits(UInt64(uInt32Len)))
}
for (i in 0..arrIndex) {
uInt32Arr[i] = rand.nextUInt32()
}
intArr = normalize(uInt32Arr)
if (int == 0 && intArr.size == 0) {
negSign = false
} else {
negSign = !sign
}
}
/**
* Translate a value presented by string @p value into a BigInt.
* Here, @p value is a string form of a @p base base number.
* The form of @p value string follows the BNF 'IntegerString' shown below.
*
* IntegerString
* : (SignString)? ValueString
*
* SignString
* : + | -
*
* ValueString
* : digit digits
*
* digit
* : r'0' ~ r'9' | r'A' ~ r'Z' | r'a' ~ r'z'
*
* where the digit follows the restriction:
* - if digit belongs to 0 ~ 9, then (digit - r'0') < base;
* - if digit belongs to r'A' ~ r'Z', then (digit - r'A') + 10 < base;
* - if digit belongs to r'a' ~ r'z', then (digit - r'A') + 10 < base.
*
* @param value: the string form of the specific base number to translate to the BigInt;
* @param base: the base of the number in translation.
*
* @throws IllegalArgumentException
* - if @p val does match the required string format, or
* - if @p base does not in the range of [2, 36].
*/
@Deprecated[message: "Use member function `public static func parse(value: String, radix!: Int64): BigInt` instead."]
public init(s: String, base!: Int64 = 10) {
if (base < 2 || base > 36) {
throw IllegalArgumentException("The base should in the range of [2, 36].")
}
(this.int, this.intArr, this.negSign) = parseString(s, UInt64(base))
}
/**
* Return the value of the bit at the specified index in this BigInt.
*
* @param index: index of bit to test.
*
* @return: true, if (this & (1 << @p index) != 0); otherwise, false.
*
* @throw IllegalArgumentException, if @p index < 0.
*/
public func testBit(index: Int64): Bool {
if (index < 0) {
throw IllegalArgumentException("The index must >= 0.")
}
if (sign == 0) {
return false
}
// x = !(x_abs - 1)
if (negSign) {
let (bitInt, bitArr) = subOne(int, intArr, false)
if (index < 64) {
return (bitInt & (1 << index)) == 0
}
let (arrIndex, u32Index) = arrIndexAndU32Index(index)
if (arrIndex > bitArr.size - 1) {
return true
}
return (bitArr[arrIndex] & (1 << u32Index)) == 0
} else {
if (index < 64) {
return (int & (1 << index)) != 0
}
let (arrIndex, u32Index) = arrIndexAndU32Index(index)
if (arrIndex > intArr.size - 1) {
return false
}
return (intArr[arrIndex] & (1 << u32Index)) != 0
}
}
/**
* Search the index of the rightmost (lowest-order) one bit in this BigInt.
* If there is no one bit in this BigInt, return -1.
*
* @return:
* - index of the rightmost one bit in this BigInt, if exists;
* - otherwise, -1.
*/
@Deprecated[message: "Use global function `public func trailingZeros(x: BigInt): Int64` instead."]
public func lowestOneBit(): Int64 {
return trailingZeros(this)
}
/**
* Construct a new BigInt by modifying the bit at @p index to one in this BigInt.
*
* @param index: index of bit to set.
*
* @return: this | (1 << @p index)
*
* @throw IllegalArgumentException, if @p index < 0.
*/
public func setBit(index: Int64): BigInt {
if (index < 0) {
throw IllegalArgumentException("The index must >= 0.")
}
if (sign == 0) {
if (index < 64) {
return BigInt(UInt64(1) << index, EMPTY_ARRAY, false)
}
let (arrIndex, u32Index) = arrIndexAndU32Index(index)
let arr = Array<UInt32>(arrIndex + 1, repeat: 0)
arr[arrIndex] = UInt32(1) << u32Index
return BigInt(0, arr, false)
}
// (!(1<<index) & (x_abs - 1)) + 1
if (negSign) {
let arrIndex = (index - 64) >> 5
if (index >= 64 && arrIndex > intArr.size - 1) {
return BigInt(int, intArr.clone(), true)
}
let (bitInt, bitArr) = subOne(int, intArr, true)
if (index < 64) {
// one bit of bitInt is set to 0. Therefore, adding 1 will not overflow.
return BigInt((!(UInt64(1) << index) & (bitInt)) + 1, normalize(bitArr), true)
}
let u32Index = (index - 64) & 0x1F
bitArr[arrIndex] = !(UInt32(1) << u32Index) & bitArr[arrIndex]
if (bitInt == 0xFFFF_FFFF_FFFF_FFFF) {
return BigInt(0, addInSitu(bitArr, EMPTY_ARRAY, 1), true)
}
return BigInt(bitInt + 1, normalize(bitArr), true)
} else {
return posBitOrOrXor(this, index, Or)
}
}
/**
* Construct a new BigInt by modifying the bit at @p index to zero in this BigInt.
*
* @param index: index of bit to clear.
*
* @return: this & ~ (1 << @p index)
*
* @throw IllegalArgumentException, if @p index < 0.
*/
public func clearBit(index: Int64): BigInt {
if (index < 0) {
throw IllegalArgumentException("The index must >= 0.")
}
if (sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
// ((1<<index) | (x_abs -1)) + 1
if (negSign) {
return negBitOrOrXor(this, index, Or)
} else {
let arrIndex = (index - 64) >> 5
let bitArr = intArr.clone()
if (index >= 64 && arrIndex > bitArr.size - 1) {
return BigInt(int, bitArr, false)
}
if (index < 64) {
return BigInt(!(UInt64(1) << index) & int, bitArr, false)
}
let u32Index = (index - 64) & 0x1F
bitArr[arrIndex] = !(UInt32(1) << u32Index) & bitArr[arrIndex]
// the most significant UInt32 may be zero, so normalize is needed
// such as: 0x00000001_12345678_12345678
// to 0x00000000_12345678_12345678
return BigInt(int, normalize(bitArr), false)
}
}
/**
* Construct a new BigInt by flipping the bit at @p index in this BigInt.
*
* @param index: index of bit to flip.
*
* @return: this ^ (1 << @p index)
*
* @throw IllegalArgumentException, if @p index < 0.
*/
public func flipBit(index: Int64): BigInt {
if (index < 0) {
throw IllegalArgumentException("The index must >= 0.")
}
if (sign == 0) {
return setBit(index)
}
// ((1<<index) ^ (x_abs -1)) + 1
if (negSign) {
return negBitOrOrXor(this, index, Xor)
} else {
return posBitOrOrXor(this, index, Xor)
}
}
/**
* Test whether this BigInt is a prime.
* The probability that such method views a composite as a prime is at most (1 / 4 ^ {@p certainty}).
*
* @param certainty: a measure of a probability that such method views a composite as a prime;
*/
public func isProbablePrime(certainty: UInt64): Bool {
if (certainty == 0) {
return true
}
// only positive integers can be prime
if (sign <= 0) {
return false
}
// 1 is not a prime
if (int == 1 && intArr.size == 0) {
return false
}
// the only even prime
if (int == 2 && intArr.size == 0) {
return true
}
// an even number greater than 2 must be a composite
if ((int & 1) == 0) {
return false
}
// test odd numbers
var certaintyTimes = certainty
while (certaintyTimes > 0x7FFF_FFFF_FFFF_FFFF) {
if (!checkCertaintyTimes(0x7FFF_FFFF_FFFF_FFFF)) {
return false
}
certaintyTimes -= 0x7FFF_FFFF_FFFF_FFFF
}
if (!checkCertaintyTimes(Int64(certaintyTimes))) {
return false
}
// n(this BigInt) may be a prime
return true
}
func checkCertaintyTimes(certainty: Int64): Bool {
for (_ in 0..Int64(certainty)) {
var a: BigInt
// the basis for witness can not be 0 or 1
do {
a = BigInt(true, bitLen)
} while (a.int == 0 || a.int == 1 && a.intArr.size == 0 || a == this)
// witness returning true means n(this BigInt) is a composite
if (witness(a, this)) {
return false
}
}
// n(this BigInt) may be a prime
return true
}
/**
* Return a BigInt, whose value is (this + @p other).
*
* @param other: the value to be added to this BigInt;
*
* @return: the result of (this + @p other).
*/
public operator func +(other: BigInt): BigInt {
if (this.sign == 0) {
return BigInt(other.int, other.intArr.clone(), other.negSign)
}
if (other.sign == 0) {
return BigInt(this.int, this.intArr.clone(), this.negSign)
}
if (this.sign == other.sign) {
let (int, intArr) = addAbs(this.int, this.intArr, other.int, other.intArr)
return BigInt(int, intArr, this.negSign)
} else {
let (int, resultArr, isNeg) = subAbs(this.int, this.intArr, other.int, other.intArr, this.negSign)
return BigInt(int, resultArr, isNeg)
}
}
/**
* Return a BigInt, whose value is (this - @p other).
*
* @param other: the value to be substracted from this BigInt;
*
* @return: the result of (this - @p other).
*/
public operator func -(other: BigInt): BigInt {
if (this.sign == 0) {
return -other
}
if (other.sign == 0) {
return BigInt(this.int, this.intArr.clone(), this.negSign)
}
if (this.sign == other.sign) {
let (int, resultArr, isNeg) = subAbs(this.int, this.intArr, other.int, other.intArr, this.negSign)
return BigInt(int, resultArr, isNeg)
} else {
let (int, intArr) = addAbs(this.int, this.intArr, other.int, other.intArr)
return BigInt(int, intArr, this.negSign)
}
}
/**
* Return a BigInt, whose value is (this * @p other).
*
* @param other: the value to be multiplied by this BigInt;
*
* @return: the result of (this * @p other).
*/
public operator func *(other: BigInt): BigInt {
if (this.sign == 0 || other.sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
let (rInt, rArr) = mul(this.int, this.intArr, other.int, other.intArr)
return BigInt(rInt, rArr, this.negSign != other.negSign)
}
/**
* Return a BigInt, whose value is (this / @p other).
* The result of the quotient is rounding towards zero.
* For exampke, -7 divided by 2 is (-3.5), so the result is -3.
*
* @param other: the value other this BigInt is to be divided;
*
* @return: the result of (this / @p other).
*
* @throws ArithmeticException if @p other == 0.
*/
public operator func /(other: BigInt): BigInt {
let (dInt, dArr, dNegSign) = div(other.int, other.intArr, other.negSign)
return BigInt(dInt, dArr, dNegSign)
}
/**
* Return a BigInt, whose value is (this % @p other).
* The result satisfies the following restrictions:
* - If this BigInt is a positive, the result is non-negative;
* - If this BigInt is a negative, the result is negative or zero.
* For example, -7 / 2 = -3 --- (-1), so the result is -1.
*
* @param other: the value that this BigInt is to be divided;
*
* @return: the result of (this % @p other).
*
* @throws ArithmeticException if @p other == 0.
*/
public operator func %(other: BigInt): BigInt {
let (mInt, mArr) = mod(int, intArr, other.int, other.intArr)
let mNegSign = if (mInt == 0 && mArr.size == 0) {
false
} else {
negSign
}
return BigInt(mInt, mArr, mNegSign)
}
/**
* Return a pair containing (this / @p other) and (this % @p other).
* The result of the quotient is rounding towards zero.
*
* @param other: the value that this BigInt is to be divided;
*
* @return: the pair containing (this / @p other) and (this % @p other).
*
* @throws ArithmeticException if @p other == 0.
*/
public func divAndMod(other: BigInt): (BigInt, BigInt) {
let (dInt, dArr, dNegSign, mInt, mArr, mNegSign) = privateDivAndMod(other.int, other.intArr, other.negSign)
return (BigInt(dInt, dArr, dNegSign), BigInt(mInt, mArr, mNegSign))
}
/**
* Return a BigInt, whose value equals to this BigInt divided by @p other.
* The caculation follows Euclidean division.
*
* @param other: the value that this BigInt is to be divided;
*
* @return: the quotient of this BigInt divided by @p other.
*
* @throws ArithmeticException if @p other == 0.
*/
@Deprecated[message: "Use member function `public func divAndMod(other: BigInt): (BigInt, BigInt)` instead."]
public func quo(other: BigInt): BigInt {
let (dInt, dArr, dNegSign, mInt, mArr, _) = privateDivAndMod(other.int, other.intArr, other.negSign)
if (sign == -1 && !(mInt == 0 && mArr.size == 0)) {
let (qInt, qArr) = addOneAndOverSize(dInt, dArr)
return BigInt(qInt, qArr, negSign != other.negSign)
}
return BigInt(dInt, dArr, dNegSign)
}
/**
* Return a BigInt, whose value equals to the reminder of this BigInt divided by @p other.
* The result is always non-negative.
*
* @param other: the value that this BigInt is to be divided;
*
* @return: the reminder of this BigInt divided by @p other.
*
* @throws ArithmeticException if @p other == 0.
*/
@Deprecated[message: "Use member function `public func divAndMod(other: BigInt): (BigInt, BigInt)` instead."]
public func rem(other: BigInt): BigInt {
let (mInt, mArr) = mod(int, intArr, other.int, other.intArr)
if (sign == -1 && !(mInt == 0 && mArr.size == 0)) {
return modAddAbsOfDivisor(mInt, mArr, other)
}
return BigInt(mInt, mArr, false)
}
/**
* Return a BigInt, which is a pair of the quotient and the reminder of this BigInt divided by @p other.
* The caculation follows Eculidean division.
*
* @param other: the value that this BigInt is to be divided;
*
* @return: the reminder of this BigInt divided by @p other.
*
* @throws ArithmeticException if @p other == 0.
*/
@Deprecated[message: "Use member function `public func divAndMod(other: BigInt): (BigInt, BigInt)` instead."]
public func quoAndRem(other: BigInt): (BigInt, BigInt) {
let (dInt, dArr, dNegSign, mInt, mArr, _) = privateDivAndMod(other.int, other.intArr, other.negSign)
if (sign == -1 && !(mInt == 0 && mArr.size == 0)) {
let (qInt, qArr) = addOneAndOverSize(dInt, dArr)
let rBig = modAddAbsOfDivisor(mInt, mArr, other)
return (BigInt(qInt, qArr, negSign != other.negSign), rBig)
}
return (BigInt(dInt, dArr, dNegSign), BigInt(mInt, mArr, false))
}
/**
* Return a BigInt v, where ((this * v) % (@p other) == 1).
*
* @param other: the modulus.
*
* @return: a modular multiplicative inverse of this BigInt.
*
* @throws IllegalArgumentException if this BigInt and @p other are not relatively prime.
*/
public func modInverse(other: BigInt): BigInt {
if (other.int == 1 && other.intArr.size == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
if (this.sign == 0 || other.sign == 0) {
throw IllegalArgumentException("The BigInt is not relatively prime with the input.")
}
let (x, _) = exgcdToInverse(this, other)
if (this.negSign != x.negSign) {
let (rInt, rArr, _) = subAbs(other.int, other.intArr, x.int, x.intArr, false)
return BigInt(rInt, rArr, negSign)
}
return x
}
/**
* Return a BigInt, whose value is (- this).
*
* @return: the result of (- this).
*/
public operator func -(): BigInt {
if (sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
return BigInt(this.int, this.intArr.clone(), !this.negSign)
}
/**
* Return a BigInt, whose value is (this ** (@p n)).
*
* @param n: power to raise this BigInt to.
*
* @return: the result of (this ** (@p n)).
*/
public operator func **(n: UInt64): BigInt {
if (n == 0) {
return BigInt(1, EMPTY_ARRAY, false)
}
if (sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
let isNeg = (n & 1) == 1 && negSign
if (int == 1 && intArr.size == 0) {
return BigInt(1, EMPTY_ARRAY, isNeg)
}
var resultInt: UInt64 = 1
var resultArr: Array<UInt32> = EMPTY_ARRAY
var powerInt: UInt64 = this.int
var powerArr: Array<UInt32> = this.intArr
var exponent = n
while (exponent != 0) {
if ((exponent & 1) == 1) {
// modify resultInt and resultArr in situ
(resultInt, resultArr) = mul(resultInt, resultArr, powerInt, powerArr)
}
(powerInt, powerArr) = mul(powerInt, powerArr, powerInt, powerArr)
exponent = exponent >> 1
}
return BigInt(resultInt, resultArr, isNeg)
}
/**
* Return a BigInt, whose value is ((this ** (@p n)) % (@p m)).
* The result is rounding towards to zero.
*
* @param n: power to raise this BigInt to.
* @param m: the modulus, None means no modular operation.
*
* @return: the result of ((this ** (@p n)) % (@p m).
*
* @throw IllegalArgumentException if @p n < 0;
* @throw ArithmeticException if @p m equals to zero.
*/
public func modPow(n: BigInt, m!: ?BigInt = None): BigInt {
if (n.sign == -1) {
throw IllegalArgumentException("The exponent can not be negative.")
}
if (m?.sign == 0) {
throw ArithmeticException("Divided by zero!")
}
if (m?.int == 1 && m?.intArr.size == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
if (n.sign == 0) {
return BigInt(1, EMPTY_ARRAY, false)
}
if (sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
let isNeg = ((n.int & 1) == 1 && negSign)
if (int == 1 && intArr.size == 0) {
return BigInt(1, EMPTY_ARRAY, isNeg)
}
var resultInt: UInt64 = 1
var resultArr: Array<UInt32> = EMPTY_ARRAY
var (powerInt, powerArr) = modOption(int, intArr, m)
var eInt = n.int
var eArr = n.intArr.clone()
while (eInt != 0 || eArr.size != 0) {
if ((eInt & 1) == 1) {
// modify resultInt and resultArr in situ
(resultInt, resultArr) = mul(resultInt, resultArr, powerInt, powerArr)
(resultInt, resultArr) = modOption(resultInt, resultArr, m)
}
(powerInt, powerArr) = mul(powerInt, powerArr, powerInt, powerArr)
(powerInt, powerArr) = modOption(powerInt, powerArr, m)
(eInt, eArr) = divBy2Insitu(eInt, eArr)
eArr = normalize(eArr)
}
return BigInt(resultInt, resultArr, isNeg)
}
/**
* Return a BigInt, whose value is (this & (@p other)).
*
* @param other: value to be AND'ed with this BigInt.
*
* @return: the result of (this & (@p other)).
*/
public operator func &(other: BigInt): BigInt {
if (sign == 0 || other.sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
if (negSign == other.negSign) {
// _abs means the absolute value
// x_abs & y_abs
if (!negSign) {
let (rInt, rArr) = and(int, intArr, other.int, other.intArr)
return BigInt(rInt, rArr, false)
}
// ((x_abs - 1) | (y_abs - 1)) + 1
let (rInt, rArr) = subOneOrOrXor(int, intArr, other.int, other.intArr, Or)
let (rIntPlus, rArrPlus) = addOneAndOverSize(rInt, normalize(rArr))
return BigInt(rIntPlus, rArrPlus, true)
}
// x_abs & !(y_abs - 1)
// &, the size of the result array is up to the size of x_abs
if (!negSign) {
let (intSubOne, rArr) = resetSizeAndSubOne(other.int, other.intArr, intArr.size, true)
let rInt = !intSubOne & int
for (i in 0..intArr.size) {
rArr[i] = !rArr[i] & intArr[i]
}
return BigInt(rInt, normalize(rArr), false)
}
// y_abs & !(x_abs - 1)
// &, the size of the result array is up to the size of y_abs
let (intSubOne, rArr) = resetSizeAndSubOne(int, intArr, other.intArr.size, true)
let rInt = !intSubOne & other.int
for (i in 0..other.intArr.size) {
rArr[i] = !rArr[i] & other.intArr[i]
}
return BigInt(rInt, normalize(rArr), false)
}
/**
* Return a BigInt, whose value is (this | (@p other)).
*
* @param other: value to be OR'ed with this BigInt.
*
* @return: the result of (this | (@p other)).
*/
public operator func |(other: BigInt): BigInt {
if (sign == 0) {
return BigInt(other.int, other.intArr.clone(), other.negSign)
}
if (other.sign == 0) {
return BigInt(int, intArr.clone(), negSign)
}
if (negSign == other.negSign) {
// _abs means the absolute value
// x_abs | y_abs
if (!negSign) {
let (rInt, rArr) = orOrXor(this, other, Or)
return BigInt(rInt, rArr, false)
}
// ((x_abs - 1) & (y_abs - 1)) + 1
let (rInt, rArr) = subOneAnd(int, intArr, other.int, other.intArr)
let (rIntPlus, rArrPlus) = addOneAndOverSize(rInt, normalize(rArr))
return BigInt(rIntPlus, rArrPlus, true)
}
// (!x_abs & (y_abs - 1)) + 1
// &, the size of the result array is up to the size of (y_abs - 1)
let rInt: UInt64
let intSubOne: UInt64
let rArr: Array<UInt32>
if (!negSign) {
(intSubOne, rArr) = subOne(other.int, other.intArr, true)
rInt = !int & intSubOne
for (i in 0..min(rArr.size, intArr.size)) {
rArr[i] = !intArr[i] & rArr[i]
}
// (!y_abs & (x_abs - 1)) + 1
// &, the size of the result array is up to the size of (x_abs - 1)
} else {
(intSubOne, rArr) = subOne(int, intArr, true)
rInt = !other.int & intSubOne
for (i in 0..min(rArr.size, other.intArr.size)) {
rArr[i] = !other.intArr[i] & rArr[i]
}
}
let (rIntPlus, rArrPlus) = addOneAndOverSize(rInt, normalize(rArr))
return BigInt(rIntPlus, rArrPlus, true)
}
/**
* Return a BigInt, whose value is (this ^ (@p other)).
*
* @param other: value to be XOR'ed with this BigInt.
*
* @return: the result of (this ^ (@p other)).
*/
public operator func ^(other: BigInt): BigInt {
if (sign == 0) {
return BigInt(other.int, other.intArr.clone(), other.negSign)
}
if (other.sign == 0) {
return BigInt(int, intArr.clone(), negSign)
}
if (negSign == other.negSign) {
// _abs means the absolute value
// x_abs ^ y_abs
if (!negSign) {
let (rInt, rArr) = orOrXor(this, other, Xor)
return BigInt(rInt, normalize(rArr), false)
}
// (x_abs - 1) ^ (y_abs - 1)
let (rInt, rArr) = subOneOrOrXor(int, intArr, other.int, other.intArr, Xor)
return BigInt(rInt, normalize(rArr), false)
}
// (x_abs ^ (y_abs - 1)) + 1
// ^, the size of the result array is up to the size of the longer one in (x_abs and (y_abs - 1))
let rInt: UInt64
let intSubOne: UInt64
let rArr: Array<UInt32>
let (maxSize, minSize) = if (intArr.size >= other.intArr.size) {
(intArr.size, other.intArr.size)
} else {
(other.intArr.size, intArr.size)
}
if (!negSign) {
(intSubOne, rArr) = resetSizeAndSubOne(other.int, other.intArr, maxSize, true)
rInt = int ^ intSubOne
for (i in 0..minSize) {
rArr[i] = intArr[i] ^ rArr[i]
}
if (intArr.size >= other.intArr.size) {
intArr.copyTo(rArr, minSize, minSize, maxSize - minSize)
}
// (y_abs ^ (x_abs - 1)) + 1
// ^, the size of the result array is up to the size of the longer one in (y_abs and (x_abs - 1))
} else {
(intSubOne, rArr) = resetSizeAndSubOne(int, intArr, maxSize, true)
rInt = other.int ^ intSubOne
for (i in 0..minSize) {
rArr[i] = other.intArr[i] ^ rArr[i]
}
if (intArr.size < other.intArr.size) {
other.intArr.copyTo(rArr, minSize, minSize, maxSize - minSize)
}
}
let (rIntPlus, rArrPlus) = addOneAndOverSize(rInt, normalize(rArr))
return BigInt(rIntPlus, rArrPlus, true)
}
/**
* Return a BigInt, whose value is (! this).
*
* @return: the result of (! this).
*/
public operator func !(): BigInt {
// x_abs + 1
if (!negSign) {
let (rInt, rArr) = addOneAndOverSize(int, intArr.clone())
return BigInt(rInt, rArr, true)
}
// x_abs - 1
let (rInt, rArr) = subOne(int, intArr, true)
return BigInt(rInt, normalize(rArr), false)
}
/**
* Return a BigInt by shifting this BigInt right n bits.
*
* @param: the number of bit to shift.
*
* @throw ArithmeticException if @p n < 0.
*/
public operator func >>(n: Int64): BigInt {
if (n < 0) {
throw ArithmeticException("The parameter n must >= 0.")
}
if (sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
// ((x_abs - 1) >> n) + 1
let (intT, intArrT) = if (negSign) {
subOne(int, intArr, false)
// x_abs >> n
} else {
(int, intArr)
}
var leadingZeros = if (intArrT.size > 0) {
Int64(leadingZeros(intArrT[intArrT.size - 1]))
} else {
0
}
var (deltaSize, shift) = deltaSizeAndU32Shift(n)
let delta = deltaSize
if (shift >= 32 - leadingZeros) {
deltaSize += 1
}
let rArr = if (intArrT.size - deltaSize > 0) {
Array<UInt32>(intArrT.size - deltaSize, repeat: 0)
} else {
EMPTY_ARRAY
}
var carryRight: UInt32 = 0
for (i in intArrT.size - 1..=delta : -1) {
let shiftResult = (intArrT[i] >> shift) | carryRight
carryRight = if (shift > 0) {
intArrT[i] << (32 - shift)
} else {
0
}
if (i - delta >= rArr.size) {
continue
}
rArr[i - delta] = shiftResult
}
let rInt = shiftRightToUInt64(intT, intArrT, delta, shift, carryRight)
// x_abs >> n
if (!negSign) {
return BigInt(rInt, rArr, false)
}
// ((x_abs - 1) >> n) + 1
let (rIntPlus, rArrPlus) = addOneAndOverSize(rInt, normalize(rArr))
return BigInt(rIntPlus, rArrPlus, true)
}
/**
* Return a BigInt by shifting this BigInt right n bits.
*
* @param: the number of bit to shift.
*
* @throw ArithmeticException if @p n < 0.
*/
public operator func <<(n: Int64): BigInt {
if (n < 0) {
throw ArithmeticException("The parameter n must >= 0.")
}
if (sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
var leadingZeros = if (intArr.size > 0) {
Int64(leadingZeros(intArr[intArr.size - 1]))
} else {
Int64(leadingZeros(int))
}
if (n <= leadingZeros && intArr.size == 0) {
return BigInt(int << n, EMPTY_ARRAY, negSign)
}
var (deltaSize, shift32) = deltaSizeAndU32Shift(n)
if (shift32 > leadingZeros) {
deltaSize += 1
}
let rArr = Array<UInt32>(intArr.size + deltaSize, repeat: 0)
intArr.copyTo(rArr, 0, 0, intArr.size)
let (rInt, _) = shiftLeftInSitu(int, rArr, n, deltaSize)
return BigInt(rInt, normalize(rArr), negSign)
}
/**
* Report whether this BigInt is equal to another BigInt.
*
* @param other: the BigInt for comparison.
*
* @return: true if this BigInt is equal to @p other, otherwise false.
*/
public operator func ==(other: BigInt): Bool {
return this.sign == other.sign && this.int == other.int && this.intArr == other.intArr
}
/**
* Report whether this BigInt is not equal to another BigInt.
*
* @param other: the BigInt for comparison.
*
* @return: true if this BigInt is not equal to @p other, otherwise false.
*/
public operator func !=(other: BigInt): Bool {
return !(this == other)
}
/**
* Report whether this BigInt is greater than another BigInt.
*
* @param other: the BigInt for comparison.
*
* @return: true if this BigInt is greater than @p other, otherwise false.
*/
public operator func >(other: BigInt): Bool {
if (this.sign > other.sign) {
return true
}
if (this.sign < other.sign) {
return false
}
let c = compareAbsArr(this.intArr, other.intArr, 0)
if (c * this.sign > 0) {
return true
}
if (c == 0 && ((this.int > other.int && this.sign > 0) || (this.int < other.int && this.sign < 0))) {
return true
}
return false
}
/**
* Report whether this BigInt is greater than or equal to another BigInt.
*
* @param other: the BigInt for comparison.
*
* @return: true if this BigInt is greater than or equal to @p other, otherwise false.
*/
public operator func >=(other: BigInt): Bool {
if (this.sign > other.sign) {
return true
}
if (this.sign < other.sign) {
return false
}
if (this.sign == 0) {
return true
}
let c = compareAbsArr(this.intArr, other.intArr, 0)
if (c * this.sign > 0) {
return true
}
if (c == 0 && ((this.int >= other.int && this.sign >= 0) || (this.int <= other.int && this.sign <= 0))) {
return true
}
return false
}
/**
* Report whether this BigInt is less than another BigInt.
*
* @param other: the BigInt for comparison.
*
* @return: true if this BigInt is less than @p other, otherwise false.
*/
public operator func <(other: BigInt): Bool {
return !(this >= other)
}
/**
* Report whether this BigInt is less than or equal to another BigInt.
*
* @param other: the BigInt for comparison.
*
* @return: true if this BigInt is less than or equal to @p other, otherwise false.
*/
public operator func <=(other: BigInt): Bool {
return !(this > other)
}
/**
* Compare the relationship between this BigInt and another BigInt.
*
* @param other: the BigInt for comparison
*
* @return: the relationship between two BigInt instances.
*/
public func compare(other: BigInt): Ordering {
match {
case this < other => Ordering.LT
case this > other => Ordering.GT
case _ => Ordering.EQ
}
}
/**
* Obtain the hash value of this BigInt.
*
* @return: hash value of this BigInt.
*/
@OverflowWrapping
public func hashCode(): Int64 {
var hashCode: UInt64 = 0
for (i in intArr.size - 1..=0 : -1) {
hashCode *= 31
hashCode += UInt64(intArr[i])
}
hashCode *= 31
hashCode += int >> 32
hashCode *= 31
hashCode += int & 0xFFFF_FFFF
return Int64(hashCode)
}
/**
* Return this BigInt as a decimal-based string.
*
* @return: the string representation of this BigDecimal.
*/
public func toString(): String {
return convertToString(10)
}
/**
* Return a byte array of the two's-complement representation of this BigInteger.
* The byte array is in big-endian byte-order.
*/
public func toBytes(): Array<Byte> {
if (sign == 0) {
return Array<Byte>(1, repeat: 0)
}
if (!negSign) {
if (intArr.size == 0) {
let byteArr = Array<Byte>(Int64((64 - leadingZeros(int)) / 8) + 1, repeat: 0)
fromU64ToBigBytes(byteArr, int)
return byteArr
}
let byteArr = Array<Byte>(intArr.size * 4 + Int64((64 - leadingZeros(intArr[intArr.size - 1])) / 8) + 1,
repeat: 0)
fromU64ToBigBytes(byteArr[byteArr.size - 8..], int)
fromSmallU32ArrayToBigBytes(byteArr[..byteArr.size - 8], intArr)
return byteArr
}
// x < 0, if x_abs == 2**(8*n-1), n is a postive integer
// x's byteArr.size == x_abs's byteArr.size - 1
// such as: x = -128, x's byteArr: [128]
// x_abs's byteArr: [0, 128]
if (intArr.size == 0) {
let bitLen = 64 - leadingZeros(int)
let byteArr = if ((bitLen & 0b111) == 0 && (int ^ (1 << (bitLen - 1))) == 0) {
Array<Byte>(Int64(bitLen / 8), repeat: 0)
} else {
Array<Byte>(Int64(bitLen / 8) + 1, repeat: 0)
}
fromU64ToBigBytes(byteArr, int)
return compToMag(byteArr)
}
let mostSignificantUInt32 = intArr[intArr.size - 1]
let bitLen = 32 - leadingZeros(mostSignificantUInt32)
// 32/8 = 4
let byteArr = if ((bitLen & 0b111) == 0 && (mostSignificantUInt32 ^ (1 << (bitLen - 1))) == 0 && isAllZero(
intArr[..intArr.size - 1])) {
Array<Byte>(intArr.size * 4 + Int64(bitLen / 8) + 4, repeat: 0)
} else {
Array<Byte>(intArr.size * 4 + Int64(bitLen / 8) + 5, repeat: 0)
}
fromU64ToBigBytes(byteArr[byteArr.size - 8..], int)
fromSmallU32ArrayToBigBytes(byteArr[..byteArr.size - 8], intArr)
return compToMag(byteArr)
}
/**
* Return the String representation of this BigInteger in the given radix.
*
* @param radix: the radix of this BigInt.
*
* @return: string representation of this BigInteger in the given radix.
*
* @throws IllegalArgumentException if @p radix does not in the range of [2, 36]
*/
func convertToString(radix: Int64): String {
if (radix < 2 || radix > 36) {
throw IllegalArgumentException("The radix should in the range of [2, 36].")
}
if (int == 0 && intArr.size == 0) {
return "0"
}
var begin = 0
if (intArr.size == 0) {
let absStrSize = calculateBaseStrSize(radix)
let stringUtf8Arr = Array<Byte>(absStrSize + 1, repeat: b'0')
begin = toBaseString(stringUtf8Arr, absStrSize, int, UInt64(radix))
if (negSign) {
stringUtf8Arr[begin] = b'-'
begin--
}
begin++
return unsafe { String.fromUtf8Unchecked(stringUtf8Arr[begin..]) }
}
let (digits, anyBase) = calculateLenAndBase(UInt64(radix))
let stringArr = Array<UInt64>(calculateStrArrSize(anyBase), repeat: 0)
let stringArrBound = calculateStrArr(stringArr, this, 1, anyBase)
let stringUtf8Arr = Array<Byte>(stringArrBound * digits + 1, repeat: b'0')
begin = toBaseString(stringUtf8Arr, digits, stringArr[stringArrBound - 1], UInt64(radix))
if (negSign) {
stringUtf8Arr[begin] = b'-'
begin--
}
begin++
for (i in stringArrBound - 2..=0 : -1) {
toBaseString(stringUtf8Arr, digits * (stringArrBound - i), stringArr[i], UInt64(radix))
}
return unsafe { String.fromUtf8Unchecked(stringUtf8Arr[begin..]) }
}
/**
* Converts this BigInt to a Int8.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding Int8 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of Int8 and the overflow handling of Throwing is selected
*/
public func toInt8(overflowHandling!: OverflowStrategy = Throwing): Int8 {
if (this.intArr.isEmpty()) {
if (!this.negSign && this.int <= 127) {
return Int8(this.int)
}
if (this.negSign && this.int <= 128) {
return Int8(-Int64(this.int))
}
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the Int8.")
case Wrapping => toInt8Wrapping()
case Saturating =>
if (this.negSign) {
Int8.Min
} else {
Int8.Max
}
}
}
@OverflowWrapping
private func toInt8Wrapping(): Int8 {
if (!this.negSign) {
return Int8(this.int)
} else {
let u: UInt8 = UInt8((this.int - 1) & 0xff)
return Int8(!u)
}
}
/**
* Converts this BigInt to a Int16.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding Int16 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of Int16 and the overflow handling of Throwing is selected
*/
public func toInt16(overflowHandling!: OverflowStrategy = Throwing): Int16 {
if (this.intArr.isEmpty()) {
if (!this.negSign && this.int <= 32767) {
return Int16(this.int)
}
if (this.negSign && this.int <= 32768) {
return Int16(-Int64(this.int))
}
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the Int16.")
case Wrapping => toInt16Wrapping()
case Saturating =>
if (this.negSign) {
Int16.Min
} else {
Int16.Max
}
}
}
@OverflowWrapping
private func toInt16Wrapping(): Int16 {
if (!this.negSign) {
return Int16(this.int)
} else {
let u: UInt16 = UInt16((this.int - 1) & 0xffff)
return Int16(!u)
}
}
/**
* Converts this BigInt to a Int32.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding Int32 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of Int32 and the overflow handling of Throwing is selected
*/
public func toInt32(overflowHandling!: OverflowStrategy = Throwing): Int32 {
if (this.intArr.isEmpty()) {
if (!this.negSign && this.int <= 2147483647) {
return Int32(this.int)
}
if (this.negSign && this.int <= 2147483648) {
return Int32(-Int64(this.int))
}
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the Int32.")
case Wrapping => toInt32Wrapping()
case Saturating =>
if (this.negSign) {
Int32.Min
} else {
Int32.Max
}
}
}
@OverflowWrapping
private func toInt32Wrapping(): Int32 {
if (!this.negSign) {
return Int32(this.int)
} else {
let u: UInt32 = UInt32((this.int - 1) & 0xffffffff)
return Int32(!u)
}
}
/**
* Converts this BigInt to a Int64.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding Int64 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of Int64 and the overflow handling of Throwing is selected
*/
public func toInt64(overflowHandling!: OverflowStrategy = Throwing): Int64 {
if (this.intArr.isEmpty()) {
if (!this.negSign && this.int <= 9223372036854775807) {
return Int64(this.int)
}
if (this.negSign && this.int < 9223372036854775808) {
return -Int64(this.int)
}
if (this.negSign && this.int == 9223372036854775808) {
return Int64.Min
}
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the Int64.")
case Wrapping => toInt64Wrapping()
case Saturating =>
if (this.negSign) {
Int64.Min
} else {
Int64.Max
}
}
}
@OverflowWrapping
private func toInt64Wrapping(): Int64 {
if (!this.negSign) {
return Int64(this.int)
} else {
let u: UInt64 = (this.int - 1) & 0xffffffffffffffff
return Int64(!u)
}
}
public func toIntNative(overflowHandling!: OverflowStrategy = Throwing): IntNative {
let len: IntNative = intNativeLen()
return match (len) {
case 19 => IntNative(this.toInt64(overflowHandling: overflowHandling))
case 10 => IntNative(this.toInt32(overflowHandling: overflowHandling))
case _ => throw Exception("Unrecognized IntNative.")
}
}
public func toFloat16(): Float16 {
return Decimal(this).toFloat16()
}
public func toFloat32(): Float32 {
return Decimal(this).toFloat32()
}
public func toFloat64(): Float64 {
return Decimal(this).toFloat64()
}
private func intNativeLen(): IntNative {
var num: IntNative = 0
var n: IntNative = IntNative.Max
while (n != 0) {
n /= 10
num += 1
}
return num
}
/**
* Converts this BigInt to a UInt8.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding UInt8 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of UInt8 and the overflow handling of Throwing is selected
*/
public func toUInt8(overflowHandling!: OverflowStrategy = Throwing): UInt8 {
if (this.intArr.isEmpty() && !this.negSign && this.int <= 255) {
return UInt8(this.int)
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the UInt8.")
case Wrapping => toUInt8Wrapping()
case Saturating =>
if (this.negSign) {
UInt8.Min
} else {
UInt8.Max
}
}
}
@OverflowWrapping
private func toUInt8Wrapping(): UInt8 {
if (!this.negSign) {
return UInt8(this.int)
} else {
let u: UInt8 = !UInt8((this.int - 1) & 0xff)
return u
}
}
/**
* Converts this BigInt to a UInt16.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding UInt16 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of UInt16 and the overflow handling of Throwing is selected
*/
public func toUInt16(overflowHandling!: OverflowStrategy = Throwing): UInt16 {
if (this.intArr.isEmpty() && !this.negSign && this.int <= 65535) {
return UInt16(this.int)
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the UInt16.")
case Wrapping => toUInt16Wrapping()
case Saturating =>
if (this.negSign) {
UInt16.Min
} else {
UInt16.Max
}
}
}
@OverflowWrapping
private func toUInt16Wrapping(): UInt16 {
if (!this.negSign) {
return UInt16(this.int)
} else {
let u: UInt16 = !UInt16((this.int - 1) & 0xffff)
return u
}
}
/**
* Converts this BigInt to a UInt32.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding UInt32 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of UInt32 and the overflow handling of Throwing is selected
*/
public func toUInt32(overflowHandling!: OverflowStrategy = Throwing): UInt32 {
if (this.intArr.isEmpty() && !this.negSign && this.int <= 4294967295) {
return UInt32(this.int)
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the UInt32.")
case Wrapping => toUInt32Wrapping()
case Saturating =>
if (this.negSign) {
UInt32.Min
} else {
UInt32.Max
}
}
}
@OverflowWrapping
private func toUInt32Wrapping(): UInt32 {
if (!this.negSign) {
return UInt32(this.int)
} else {
let u: UInt32 = !UInt32((this.int - 1) & 0xffffffff)
return u
}
}
/**
* Converts this BigInt to a UInt64.
*
* @param overflowHandling: handling policy when overflow occurs.
*
* @return: the corresponding UInt64 value is returned based on the overflow handling.
*
* @throws OverflowException if the value of the BigInt exceeds the range of UInt64 and the overflow handling of Throwing is selected
*/
public func toUInt64(overflowHandling!: OverflowStrategy = Throwing): UInt64 {
if (this.intArr.isEmpty() && !this.negSign) {
return this.int
}
match (overflowHandling) {
case Throwing => throw OverflowException("Out of range of the UInt64.")
case Wrapping => toUInt64Wrapping()
case Saturating =>
if (this.negSign) {
UInt64.Min
} else {
UInt64.Max
}
}
}
@OverflowWrapping
private func toUInt64Wrapping(): UInt64 {
if (!this.negSign) {
return this.int
} else {
let u: UInt64 = !(this.int - 1)
return u
}
}
public func toUIntNative(overflowHandling!: OverflowStrategy = Throwing): UIntNative {
let len: UIntNative = uintNativeLen()
return match (len) {
case 20 => UIntNative(this.toUInt64(overflowHandling: overflowHandling)) // 18446744073709551615
case 10 => UIntNative(this.toUInt32(overflowHandling: overflowHandling)) // 4294967295
case _ => throw Exception("Unrecognized UIntNative.")
}
}
private func uintNativeLen(): UIntNative {
var num: UIntNative = 0
var n: UIntNative = UIntNative.Max
while (n != 0) {
n /= 10
num += 1
}
return num
}
// calculate the size need to store string
// log_{2^m}(2^(32*(intArr.size+2))), round up
private func calculateStrArrSize(anyBase: UInt64): Int64 {
let powerOfTwo = 64 - leadingZeros(anyBase) - 1
return (32 * (intArr.size + 2) / Int64(powerOfTwo) + 1)
}
private func calculateBaseStrSize(base: Int64): Int64 {
let u64Base = UInt64(base)
var n: UInt64 = 1
var uInt = int / u64Base + 1
var size = 1
while (n < uInt) {
size++
n *= u64Base
}
return size
}
func isPowerOfTwo(): Bool {
if (intArr.size == 0) {
return (UInt64(1) << trailingZeros(int)) == int
} else {
if (int != 0) {
return false
}
for (i in 0..intArr.size - 1) {
if (intArr[i] != 0) {
return false
}
}
return (UInt32(1) << trailingZeros(intArr[intArr.size - 1])) == intArr[intArr.size - 1]
}
}
func div(thatInt: UInt64, thatArr: Array<UInt32>, thatNegSign: Bool): (UInt64, Array<UInt32>, Bool) {
if (thatInt == 0 && thatArr.size == 0) {
throw ArithmeticException("Divided by zero!")
}
if (this.sign == 0) {
return (0, EMPTY_ARRAY, false)
}
if (this.intArr.size == 0 && thatArr.size == 0) {
return (this.int / thatInt, EMPTY_ARRAY, this.negSign != thatNegSign)
}
let c = compareAbsArr(this.intArr, thatArr, 0)
if (c == 0) {
if (this.int >= thatInt) {
return (1, EMPTY_ARRAY, this.negSign != thatNegSign)
}
return (0, EMPTY_ARRAY, false)
}
if (c == -1) {
return (0, EMPTY_ARRAY, false)
}
let rArr: Array<UInt32>
let rInt: UInt64
if (thatArr.size == 0) {
// if the bit length of the abs of divisor does not exceed 32 bits
if (thatInt <= 0xFFFF_FFFF) {
// because it's up to 64 bits, it has to be calculated separately
// dividend: rem*2^64 + this.int
// divisor: that.int
//
// division / :
// (ab+c)/d = (ab/d + c/d + (ab%d+c%d)/d)
// = a*(b/d) + a*(b%d)/d + c/d + (ab%d+c%d)/d
let rem: UInt64
(rArr, rem) = divByUInt32InSitu(this.intArr.clone(), thatInt)
let remInt0 = ((0x8000_0000_0000_0000 % thatInt) * (2 * rem % thatInt)) % thatInt
// (ab+c)/d
// the divisor is greater than the remainder, so the next line will nor overflow
rInt = 2 * rem * (0x8000_0000_0000_0000 / thatInt) + (2 * rem * (0x8000_0000_0000_0000 % thatInt)) /
thatInt + (this.int / thatInt) + (this.int % thatInt + remInt0) / thatInt
} else {
(rInt, rArr, _, _) = knuthDivAndMod(thatInt, needMod: false)
}
// otherwise, use Knuth division algorithm
} else {
(rInt, rArr, _, _) = knuthDivAndMod(thatInt, thatArr, needMod: false)
}
return (rInt, rArr, this.negSign != thatNegSign)
}
private func privateDivAndMod(thatInt: UInt64, thatArr: Array<UInt32>, thatNegSign: Bool): (UInt64, Array<UInt32>,
Bool, UInt64, Array<UInt32>, Bool) {
if (thatInt == 0 && thatArr.size == 0) {
throw ArithmeticException("Divided by zero!")
}
if (this.sign == 0) {
return (0, EMPTY_ARRAY, false, 0, EMPTY_ARRAY, false)
}
if (this.intArr.size == 0 && thatArr.size == 0) {
return (this.int / thatInt, EMPTY_ARRAY, this.negSign != thatNegSign, this.int % thatInt, EMPTY_ARRAY, this
.negSign)
}
let c = compareAbsArr(this.intArr, thatArr, 0)
if (c == 0) {
if (this.int >= thatInt) {
return (1, EMPTY_ARRAY, this.negSign != thatNegSign, this.int - thatInt, EMPTY_ARRAY, this.negSign)
}
return (0, EMPTY_ARRAY, false, this.int, this.intArr.clone(), this.negSign)
}
if (c == -1) {
return (0, EMPTY_ARRAY, false, this.int, this.intArr.clone(), this.negSign)
}
let rArr: Array<UInt32>
let remArr: Array<UInt32>
let rInt: UInt64
let remInt: UInt64
if (thatArr.size == 0) {
// if the bit length of the abs of divisor does not exceed 32 bits
if (thatInt <= 0xFFFF_FFFF) {
let rem: UInt64
(rArr, rem) = divByUInt32InSitu(this.intArr.clone(), thatInt)
// because it's up to 64 bits, it has to be calculated separately
// dividend: rem*2^64 + this.int
// divisor: thatInt
//
// division / :
// (ab+c)/d = (ab/d + c/d + (ab%d+c%d)/d)
// = a*(b/d) + a*(b%d)/d + c/d + (ab%d+c%d)/d
// mod % :
// (ab+c)%d = ((ab)%d + c%d )%d
// ab%d = ((a%d)*(b%d))%d
//
// ab%d
let remInt0 = ((0x8000_0000_0000_0000 % thatInt) * (2 * rem % thatInt)) % thatInt
// (ab+c)/d
// the divisor is greater than the remainder, so the next line will nor overflow
rInt = 2 * rem * (0x8000_0000_0000_0000 / thatInt) + (2 * rem * (0x8000_0000_0000_0000 % thatInt)) /
thatInt + (this.int / thatInt) + (this.int % thatInt + remInt0) / thatInt
// (ab+c)%d
remInt = (remInt0 + this.int % thatInt) % thatInt
remArr = EMPTY_ARRAY
} else {
(rInt, rArr, remInt, remArr) = knuthDivAndMod(thatInt)
}
// otherwise, use Knuth division algorithm
} else {
(rInt, rArr, remInt, remArr) = knuthDivAndMod(thatInt, thatArr)
}
return (rInt, rArr, this.negSign != thatNegSign, remInt, remArr, this.negSign)
}
// if the bit length of the abs of divisor exceeds 64 bits
private func knuthDivAndMod(thatInt: UInt64, thatArr: Array<UInt32>, needMod!: Bool = true): (UInt64, Array<UInt32>,
UInt64, Array<UInt32>) {
let sizeDD = intArr.size + 1 + 2
let sizeD = thatArr.size + 2
// normalize, let the most significant UInt32 larger than 0x8000_0000
let l = leadingZeros(thatArr[thatArr.size - 1])
let normalizedDividend = knuthNormalize(sizeDD, this.int, this.intArr, l)
let normalizedDivisor = knuthNormalize(sizeD, thatInt, thatArr, l)
// initialize j
var j = sizeDD - sizeD - 1
// the quotient should be j+1 size, and UInt64 occupies two size
// therefore, when j+1 is less than or equal to 2, no array is required
var rArr: Array<UInt32> = EMPTY_ARRAY
var rInt: UInt64 = 0
if (j >= 2) {
rArr = Array<UInt32>(j - 1, repeat: 0)
}
// loop
while (j >= 0) {
let q = knuthDivGuessQ(normalizedDividend, normalizedDivisor, sizeD, j)
if (j >= 2) {
rArr[j - 2] = UInt32(q)
} else {
rInt = rInt << 32
rInt += q
}
j--
}
if (!needMod) {
return (rInt, normalize(rArr), 0, EMPTY_ARRAY)
}
// unnormalize
let remArr = shiftRightInSitu(normalizedDividend, l)
let remInt = UInt64(remArr[0]) + (UInt64(remArr[1]) << 32)
return (rInt, normalize(rArr), remInt, normalize(remArr[2..]))
}
// if the bit length of the abs of divisor exceeds 32 bits but does not exceed 64 bits
private func knuthDivAndMod(that: UInt64, needMod!: Bool = true): (UInt64, Array<UInt32>, UInt64, Array<UInt32>) {
let sizeDD = intArr.size + 1 + 2
// normalize, let the most significant UInt32 larger than 0x8000_0000
let l = leadingZeros(that)
let normalizedDividend = knuthNormalize(sizeDD, this.int, this.intArr, l)
let normalizedDivisor = that << l
// initialize j
var j = intArr.size
var rArr: Array<UInt32> = EMPTY_ARRAY
var rInt: UInt64 = 0
if (j >= 2) {
rArr = Array<UInt32>(j - 1, repeat: 0)
}
// loop
while (j >= 0) {
let q = knuthDivGuessQ(normalizedDividend, normalizedDivisor, j)
if (j >= 2) {
rArr[j - 2] = UInt32(q)
} else {
rInt = rInt << 32
rInt += q
}
j--
}
if (!needMod) {
return (rInt, normalize(rArr), 0, EMPTY_ARRAY)
}
// unnormalize
let remArr = shiftRightInSitu(normalizedDividend, l)
let remInt = UInt64(remArr[0]) + (UInt64(remArr[1]) << 32)
return (rInt, normalize(rArr), remInt, normalize(remArr[2..]))
}
func compareMagnitude(that: BigInt): Int64 {
let c = compareAbsArr(this.intArr, that.intArr, 0)
if (c == 0) {
return if (this.int > that.int) {
1
} else if (this.int < that.int) {
-1
} else {
0
}
}
return c
}
func compareDouble(that: BigInt): Int64 {
let double = that << 1
return -compareMagnitude(double)
}
func isOdd() {
return (this.int & 1) == 1
}
}
/**
* Return a BigInt, whose value is the absolute value of @p i BigInt.
*
* @return: a BigInt equals to abs(@p i).
*/
public func abs(i: BigInt): BigInt {
return BigInt(i.int, i.intArr.clone(), false)
}
/**
* Returns a BigInt, whose value is the square root of BigInt @p i.
* The result is non-negative and rounding towards zero.
*
* @return: the result of sqrt(@p i).
*
* @throws IllegalArgumentException if this < 0.
*/
public func sqrt(i: BigInt): BigInt {
if (i.sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
if (i.negSign) {
throw IllegalArgumentException("The BigInt be used to calculate the square root must >= 0.")
}
var xInt = i.int
if (i.intArr.size == 0) {
var y: UInt64 = if (xInt == 0xFFFF_FFFF_FFFF_FFFF) {
0x8000_0000_0000_0000
} else {
(xInt + i.int / xInt) / 2
}
while (xInt > y) {
xInt = y
y = (xInt + i.int / xInt) / 2
}
return BigInt(xInt, EMPTY_ARRAY, false)
}
var xArr = Array<UInt32>(i.intArr.size + 1, repeat: 0)
i.intArr.copyTo(xArr, 0, 0, i.intArr.size)
// Newton's method
// x = i
// y = (x+i/x)/2
// while (x>y) {
// x = y
// y = (x+i/x)/2
// }
let (qInt, qArr, _) = i.div(xInt, normalize(xArr), false)
if (isNoLessThan(qInt, qArr, xInt, xArr)) {
return BigInt(xInt, normalize(xArr), false)
}
let (resultInt, carry) = addUInt64(xInt, qInt)
addInSitu(xArr, qArr, carry)
// y = (x + i/x)/2
(xInt, xArr) = divBy2Insitu(resultInt, xArr)
while (true) {
let (qInt, qArr, _) = i.div(xInt, normalize(xArr), false)
if (isNoLessThan(qInt, qArr, xInt, xArr)) {
break
}
let (resultInt, carry) = addUInt64(xInt, qInt)
addInSitu(xArr, qArr, carry)
// y = (x + i/x)/2
(xInt, xArr) = divBy2Insitu(resultInt, xArr)
}
return BigInt(xInt, normalize(xArr), false)
}
/**
* Return the greatest common divisor of @p i1 and @p i2.
* The result is alway non-negtive.
*
* @param i1: value with which the gcd is to be computed;
* @param i2: value with which the gcd is to be computed.
*
* @return: the greatest common divisor of @p i1 and @p i2.
*/
public func gcd(i1: BigInt, i2: BigInt): BigInt {
if (i1.sign == 0) {
return BigInt(i2.int, i2.intArr.clone(), false)
}
if (i2.sign == 0) {
return BigInt(i1.int, i1.intArr.clone(), false)
}
let (i1Int, i1Arr) = gcd(i1.int, i1.intArr, i2.int, i2.intArr)
return BigInt(i1Int, i1Arr, false)
}
/**
* Return the least common multiple of @p i1 and @p i2.
* The result is alway non-negtive.
*
* @param i1: value with which the lcm is to be computed;
* @param i2: value with which the lcm is to be computed.
*
* @return: the least common multiple of @p i1 and @p i2.
*/
public func lcm(i1: BigInt, i2: BigInt): BigInt {
if (i1.sign == 0 || i2.sign == 0) {
return BigInt(0, EMPTY_ARRAY, false)
}
let (i1Int, i1Arr) = gcd(i1.int, i1.intArr, i2.int, i2.intArr)
let (qInt, qArr, _) = i1.div(i1Int, i1Arr, false)
let (rInt, rArr) = mul(qInt, qArr, i2.int, i2.intArr)
return BigInt(rInt, rArr, false)
}
@Deprecated[message: "Use global function `public func countOnes(i: BigInt): Int64` instead."]
public func countOne(i: BigInt): Int64 {
return countOnes(i)
}
/**
* Calculate the number of one in the two's-complement binary,
* which can present BigInt @p i with minmum of the number of bits.
*
* @param i: value that is calculated the number of one.
*
* @return: the number of one in the two's-complement binary of @p i.
*/
public func countOnes(i: BigInt): Int64 {
if (i.sign == 0) {
return 0
}
if (i.isPowerOfTwo()) {
return 1
}
var count = 0
if (!i.negSign) {
count += countOnes(i.int)
for (index in i.intArr.size - 1..=0 : -1) {
count += countOnes(i.intArr[index])
}
return count
}
// such as: 5 to -5
// 0101 -> 1010 -> 1011
// 10 to -10
// 01010 -> 10101 -> 10110
if (i.intArr.size == 0) {
count += countZero(i.int)
return count + 1 - Int64(trailingZeros(i.int)) + 1
}
count += 64 - countOnes(i.int)
for (index in i.intArr.size - 2..=0 : -1) {
count += 32 - countOnes(i.intArr[index])
}
count += countZero(i.intArr[i.intArr.size - 1])
var bTrailingZeros = Int64(trailingZeros(i.int))
if (bTrailingZeros == 64) {
var int32TrailingZeros = 0
var index = 0
do {
int32TrailingZeros = Int64(trailingZeros(i.intArr[index]))
bTrailingZeros += int32TrailingZeros
index++
} while (int32TrailingZeros == 32)
}
return count + 1 - bTrailingZeros + 1
}
/**
* Obtains the number of consecutive 0s starting from the least significant bits.
*
* @param x some value.
* @return number of consecutive 0s starting from the least significant bit of @p x.
*
*/
public func trailingZeros(x: BigInt): Int64 {
if (x.sign == 0) {
return -1
}
if (x.int != 0) {
return Int64(trailingZeros(x.int))
}
var index = 64
for (i in 0..x.intArr.size) {
if (x.intArr[i] == 0) {
index += 32
} else {
index += Int64(trailingZeros(x.intArr[i]))
}
}
return index
}
enum Operator {
| Xor
| Or
func op(x: UInt64, y: UInt64): UInt64 {
match (this) {
case Xor => return x ^ y
case Or => return x | y
}
}
func op(x: UInt32, y: UInt32): UInt32 {
match (this) {
case Xor => return x ^ y
case Or => return x | y
}
}
}
func countOnes(int64: UInt64): Int64 {
var count64 = 0
var val = int64
while (val != 0) {
count64 += Int64(val & 1)
val >>= 1
}
return count64
}
func countOnes(int: UInt32): Int64 {
var count32 = 0
var val = int
while (val != 0) {
count32 += Int64(val & 1)
val >>= 1
}
return count32
}
// count zero
// such as: 5: 101 return 1
// 8: 1000 return 3
func countZero(int64: UInt64): Int64 {
var countZero64 = 0
var val = int64
while (val != 0) {
countZero64 += Int64((val ^ 1) & 1)
val >>= 1
}
return countZero64
}
func countZero(int: UInt32): Int64 {
var countZero32 = 0
var val = int
while (val != 0) {
countZero32 += Int64((val ^ 1) & 1)
val >>= 1
}
return countZero32
}
func and(thisInt: UInt64, thisArr: Array<UInt32>, thatInt: UInt64, thatArr: Array<UInt32>): (UInt64, Array<UInt32>) {
let rInt = thisInt & thatInt
let size = min(thisArr.size, thatArr.size)
if (size == 0) {
return (rInt, EMPTY_ARRAY)
}
let rArr = Array<UInt32>(size, repeat: 0)
for (i in 0..size) {
rArr[i] = thisArr[i] & thatArr[i]
}
return (rInt, rArr)
}
func orOrXor(thisBig: BigInt, thatBig: BigInt, bitOperator: Operator): (UInt64, Array<UInt32>) {
let rInt = bitOperator.op(thisBig.int, thatBig.int)
if (thisBig.intArr.size == 0 && thatBig.intArr.size == 0) {
return (rInt, EMPTY_ARRAY)
}
let rArr: Array<UInt32>
if (thisBig.intArr.size > thatBig.intArr.size) {
rArr = thisBig.intArr.clone()
for (i in 0..thatBig.intArr.size) {
rArr[i] = bitOperator.op(rArr[i], thatBig.intArr[i])
}
} else {
rArr = thatBig.intArr.clone()
for (i in 0..thisBig.intArr.size) {
rArr[i] = bitOperator.op(rArr[i], thisBig.intArr[i])
}
}
return (rInt, rArr)
}
func subOneAnd(thisInt: UInt64, thisArr: Array<UInt32>, thatInt: UInt64, thatArr: Array<UInt32>): (UInt64, Array<UInt32>) {
var rInt: UInt64
let rArr: Array<UInt32>
let bitInt: UInt64
let bitArr: Array<UInt32>
if (thisArr.size < thatArr.size) {
(rInt, rArr) = subOne(thisInt, thisArr, true)
(bitInt, bitArr) = resetSizeAndSubOne(thatInt, thatArr, thisArr.size, false)
} else {
(rInt, rArr) = subOne(thatInt, thatArr, true)
(bitInt, bitArr) = resetSizeAndSubOne(thisInt, thisArr, thatArr.size, false)
}
rInt &= bitInt
for (i in 0..rArr.size) {
rArr[i] &= bitArr[i]
}
return (rInt, rArr)
}
func subOneOrOrXor(thisInt: UInt64, thisArr: Array<UInt32>, thatInt: UInt64, thatArr: Array<UInt32>,
bitOperator: Operator): (UInt64, Array<UInt32>) {
var rInt: UInt64
let rArr: Array<UInt32>
let bitInt: UInt64
let bitArr: Array<UInt32>
if (thisArr.size > thatArr.size) {
(rInt, rArr) = subOne(thisInt, thisArr, true)
(bitInt, bitArr) = subOne(thatInt, thatArr, false)
} else {
(rInt, rArr) = subOne(thatInt, thatArr, true)
(bitInt, bitArr) = subOne(thisInt, thisArr, false)
}
rInt = bitOperator.op(rInt, bitInt)
for (i in 0..bitArr.size) {
rArr[i] = bitOperator.op(rArr[i], bitArr[i])
}
return (rInt, rArr)
}
// sub one
// if shouldClone is true, intArr is cloned even if the intArr does not change
func subOne(int: UInt64, intArr: Array<UInt32>, shouldClone: Bool): (UInt64, Array<UInt32>) {
let rInt: UInt64
let rArr: Array<UInt32>
if (int >= 1) {
rInt = int - 1
if (shouldClone) {
rArr = intArr.clone()
} else {
rArr = intArr
}
} else {
rInt = 0xFFFF_FFFF_FFFF_FFFF
rArr = intArr.clone()
subAndBorrow(rArr, 0, 1)
}
return (rInt, rArr)
}
// reset the size to size and sub one
// if shouldClone is true, intArr is cloned even if the intArr does not change
func resetSizeAndSubOne(int: UInt64, intArr: Array<UInt32>, size: Int64, shouldClone: Bool): (UInt64, Array<UInt32>) {
let rInt: UInt64
let rArr: Array<UInt32>
if (int >= 1) {
rInt = int - 1
if (shouldClone) {
rArr = Array<UInt32>(size, repeat: 0)
intArr.copyTo(rArr, 0, 0, min(intArr.size, size))
} else {
rArr = intArr[..size]
}
} else {
rInt = 0xFFFF_FFFF_FFFF_FFFF
if (size == 0) {
return (rInt, EMPTY_ARRAY)
}
rArr = Array<UInt32>(size, repeat: 0)
intArr.copyTo(rArr, 0, 0, min(intArr.size, size))
rArr[0] = if (rArr[0] >= 1) {
rArr[0] - 1
} else {
var j = 1
while (j < rArr.size && rArr[j] == 0) {
rArr[j] = 0xFFFF_FFFF
j++
}
if (j < rArr.size) {
rArr[j] -= 1
}
0xFFFF_FFFF
}
}
return (rInt, rArr)
}
// add one in situ
func addOneAndOverSize(int: UInt64, intArr: Array<UInt32>): (UInt64, Array<UInt32>) {
if (int == 0xFFFF_FFFF_FFFF_FFFF) {
for (i in intArr.size - 1..=0 : -1) {
if (intArr[i] != 0xFFFF_FFFF) {
return (0, addInSitu(intArr, EMPTY_ARRAY, 1))
}
}
let oneMoreSizeArr = Array<UInt32>(intArr.size + 1, repeat: 0)
oneMoreSizeArr[intArr.size] = 1
return (0, oneMoreSizeArr)
}
return (int + 1, intArr)
}
func negBitOrOrXor(thisBig: BigInt, index: Int64, bitOperator: Operator): BigInt {
// carry case
// such as: -7(1...1001): sign: -, abs: 111
// to (1...1000): sign: -, abs: 1000
if (index == 0 && thisBig.int == 0xFFFF_FFFF_FFFF_FFFF) {
var rArrPlus = thisBig.intArr.clone()
for (i in rArrPlus.size - 1..=0 : -1) {
if (rArrPlus[i] != 0xFFFF_FFFF) {
addInSitu(rArrPlus, EMPTY_ARRAY, 1)
return BigInt(0, rArrPlus, true)
}
}
rArrPlus = Array<UInt32>(thisBig.intArr.size + 1, repeat: 0)
rArrPlus[thisBig.intArr.size] = 1
return BigInt(0, rArrPlus, true)
}
if (index < 64) {
let (bitInt, bitArr) = subOne(thisBig.int, thisBig.intArr, true)
let rInt = bitOperator.op((UInt64(1) << index), bitInt)
if (rInt == 0xFFFF_FFFF_FFFF_FFFF) {
return BigInt(0, addInSitu(bitArr, EMPTY_ARRAY, 1), true)
}
return BigInt(rInt + 1, normalize(bitArr), true)
}
let (arrIndex, u32Index) = arrIndexAndU32Index(index)
let size = max(arrIndex + 1, thisBig.intArr.size)
let bitArr = Array<UInt32>(size, repeat: 0)
thisBig.intArr.copyTo(bitArr, 0, 0, thisBig.intArr.size)
if (thisBig.int == 0) {
subAndBorrow(bitArr, 0, 1)
}
bitArr[arrIndex] = bitOperator.op((UInt32(1) << u32Index), bitArr[arrIndex])
if (thisBig.int == 0) {
return BigInt(0, addInSitu(bitArr, EMPTY_ARRAY, 1), true)
}
return BigInt(thisBig.int, normalize(bitArr), true)
}
func posBitOrOrXor(thisBig: BigInt, index: Int64, bitOperator: Operator): BigInt {
if (index < 64) {
return BigInt(bitOperator.op((UInt64(1) << index), thisBig.int), thisBig.intArr.clone(), false)
}
let (arrIndex, u32Index) = arrIndexAndU32Index(index)
let size = max(arrIndex + 1, thisBig.intArr.size)
let bitArr = Array<UInt32>(size, repeat: 0)
thisBig.intArr.copyTo(bitArr, 0, 0, thisBig.intArr.size)
bitArr[arrIndex] = bitOperator.op((UInt32(1) << u32Index), bitArr[arrIndex])
return BigInt(thisBig.int, normalize(bitArr), false)
}
func arrIndexAndU32Index(index: Int64): (Int64, Int64) {
return ((index - 64) >> 5, (index - 64) & 0x1F)
}
func deltaSizeAndU32Shift(index: Int64): (Int64, Int64) {
return (index >> 5, index & 0x1F)
}
// shift UInt64 left and divide it into three UInt32
func shiftLeftUInt64(int: UInt64, shift64: Int64): (UInt32, UInt32, UInt32) {
let carry: UInt32
let rArr0: UInt32
let left: UInt32
if (shift64 >= 32) {
let carry64 = int >> (64 - shift64)
carry = UInt32(carry64 >> 32)
rArr0 = UInt32(carry64 & 0xFFFF_FFFF)
left = UInt32(int & 0xFFFF_FFFF) << (shift64 - 32)
} else {
carry = if (shift64 > 0) {
UInt32(int >> (64 - shift64))
} else {
0
}
let left64 = int << shift64
left = UInt32(left64 & 0xFFFF_FFFF)
rArr0 = UInt32(left64 >> 32)
}
return (carry, rArr0, left)
}
// obtain the UInt64 after the right shift
func shiftRightToUInt64(int: UInt64, intArr: Array<UInt32>, delta: Int64, shift: Int64, carryRight: UInt32): UInt64 {
var rInt: UInt64 = 0
var carry = carryRight
if (delta >= 2) {
var shiftResult: UInt32
if (intArr.size >= delta) {
shiftResult = (intArr[delta - 1] >> shift) | carry
carry = if (shift > 0) {
intArr[delta - 1] << (32 - shift)
} else {
0
}
rInt = UInt64(shiftResult) << 32
}
if (intArr.size >= delta - 1) {
shiftResult = (intArr[delta - 2] >> shift) | carry
rInt |= UInt64(shiftResult)
}
} else if (delta == 1) {
if (intArr.size >= 1) {
var shiftResult = (intArr[delta - 1] >> shift) | carry
carry = if (shift > 0) {
intArr[delta - 1] << (32 - shift)
} else {
0
}
rInt = (UInt64(shiftResult) << 32)
}
rInt |= UInt64(carry)
rInt |= (int >> (shift + 32))
} else {
rInt = (UInt64(carry) << 32) | (int >> shift)
}
return rInt
}
// remove the 0s in most significant index
func removeLeftZero(bytes: Array<Byte>): Array<Byte> {
var i = 0
while (i < bytes.size) {
if (bytes[i] != 0) {
break
}
i++
}
return bytes[i..]
}
// converting complementary codes into magnitude
func compToMag(bytes: Array<Byte>): Array<Byte> {
let mag = Array<Byte>(bytes.size, {i => !bytes[i]})
for (i in mag.size - 1..=0 : -1) {
if (mag[i] == 255) {
mag[i] = 0
} else {
mag[i] += 1
break
}
}
return mag
}
// remove leading 0s before calling
func fromBigBytesToSmallU32Array(bytes: Array<Byte>): Array<UInt32> {
if (bytes.size == 0) {
return EMPTY_ARRAY
}
// 3: 0b11
// whether it can be divisible by 4
let oneMore = if ((bytes.size & 3) == 0) {
0
} else {
1
}
let size = bytes.size >> 2
let smallU32 = Array<UInt32>(size + oneMore, repeat: 0)
var index = bytes.size - 1
for (i in 0..size) {
var u32: UInt32 = 0
for (j in 0..4) {
u32 = u32 | UInt32(bytes[index]) << (j * 8)
index--
}
smallU32[i] = u32
}
if (index >= 0) {
var u32: UInt32 = UInt32(bytes[0])
for (i in 1..=index) {
u32 = u32 << 8
u32 = u32 | UInt32(bytes[i])
}
smallU32[size] = u32
}
return smallU32
}
// remove leading 0s before calling
func fromBigBytesToU64(bytes: Array<Byte>): UInt64 {
if (bytes.size == 0) {
return 0
}
var u64: UInt64 = UInt64(bytes[0])
for (i in 1..bytes.size) {
u64 = u64 << 8
u64 = u64 | UInt64(bytes[i])
}
return u64
}
// modify bytes in situ
func fromU64ToBigBytes(byteArr: Array<Byte>, int: UInt64) {
var j = 0
for (i in byteArr.size - 1..=0 : -1) {
if (j == 8) {
return
}
byteArr[i] = UInt8((int & (0xFF << (8 * j))) >> (8 * j))
j++
}
}
// modify bytes in situ
func fromSmallU32ArrayToBigBytes(byteArr: Array<Byte>, intArr: Array<UInt32>) {
var i = byteArr.size - 1
var j = 0
var index = 0
while (i >= 0) {
if (j == 4) {
j = 0
index++
if (index >= intArr.size) {
break
}
}
byteArr[i] = UInt8((intArr[index] & (0xFF << (8 * j))) >> (8 * j))
j++
i--
}
}
func isAllZero(intArr: Array<UInt32>): Bool {
for (i in intArr.size - 1..=0 : -1) {
if (intArr[i] != 0) {
return false
}
}
return true
}
// mul between two UInt64s, return one UInt64 and two UInt32 carry
func uInt64Mul(thisInt: UInt64, thatInt: UInt64): (UInt64, UInt32, UInt32) {
let thisInt0: UInt64 = thisInt & 0xFFFF_FFFF
let thisInt1: UInt64 = thisInt >> 32
let thatInt0: UInt64 = thatInt & 0xFFFF_FFFF
let thatInt1: UInt64 = thatInt >> 32
var resultInt0 = thisInt0 * thatInt0
var resultInt1 = (thisInt0 * thatInt1) + (resultInt0 >> 32)
resultInt0 = resultInt0 & 0xFFFF_FFFF
var resultInt2 = resultInt1 >> 32
resultInt1 = (resultInt1 & 0xFFFF_FFFF) + (thisInt1 * thatInt0)
resultInt2 += (resultInt1 >> 32)
resultInt1 = resultInt1 & 0xFFFF_FFFF
resultInt2 += (thisInt1 * thatInt1)
let resultInt3 = (resultInt2 >> 32)
resultInt2 = (resultInt2 & 0xFFFF_FFFF)
let int = resultInt0 | (resultInt1 << 32)
return (int, UInt32(resultInt2), UInt32(resultInt3))
}
// convert a binary number to an anyBase number, stored in stringArr
func calculateStrArr(stringArr: Array<UInt64>, big: BigInt, bound: Int64, anyBase: UInt64): Int64 {
var stringArrBound = bound
var i = big.intArr.size - 1
while (i >= 0) {
stringArrBound = calculateStrArr(stringArr, UInt64(big.intArr[i]), stringArrBound, anyBase)
i--
}
stringArrBound = calculateStrArr(stringArr, big.int >> 32, stringArrBound, anyBase)
return calculateStrArr(stringArr, big.int & 0xFFFF_FFFF, stringArrBound, anyBase)
}
func calculateStrArr(stringArr: Array<UInt64>, int: UInt64, bound: Int64, anyBase: UInt64): Int64 {
var stringArrBound = bound
for (j in stringArrBound - 1..=0 : -1) {
stringArr[j] <<= 32
}
stringArr[0] += int
for (j in 0..stringArrBound - 1) {
stringArr[j + 1] += stringArr[j] / anyBase
stringArr[j] %= anyBase
}
var rem = stringArr[stringArrBound - 1] / anyBase
stringArr[stringArrBound - 1] %= anyBase
while (rem > 0) {
stringArr[stringArrBound] = rem
stringArrBound++
rem = stringArr[stringArrBound - 1] / anyBase
stringArr[stringArrBound - 1] %= anyBase
}
return stringArrBound
}
// modify stringUtf8Arr in situ
func toBaseString(stringUtf8Arr: Array<Byte>, index: Int64, int: UInt64, base: UInt64): Int64 {
var i = index
var quo = int
while (quo != 0) {
let rem = UInt8(quo % UInt64(base))
if (rem < 10) {
stringUtf8Arr[i] = rem + DIGIT_DIFF
} else {
stringUtf8Arr[i] = rem + LETTER_UPPER_DIFF
}
quo = quo / UInt64(base)
i--
}
return i
}
func normalize(value: Array<UInt32>): Array<UInt32> {
var preZeroNum = value.size - 1
while (preZeroNum >= 0 && value[preZeroNum] == 0) {
preZeroNum--
}
return value[..=preZeroNum]
}
func parseString(s: String, base: UInt64): (UInt64, Array<UInt32>, Bool) {
let (isNeg, start) = parseSign(s)
let (int, arr) = parseDigits(s, start, base)
if (int == 0 && arr.size == 0) {
return (int, arr, false) // no -0 for bigint
}
return (int, arr, isNeg)
}
/**
* @return (int, arr)
*/
func parseDigits(s: String, idx: Int64, radix: UInt64): (UInt64, Array<UInt32>) {
if (idx >= s.size) {
throw IllegalArgumentException("Invalid string.")
}
var numberArray = initNumArray(s, idx, UInt8(radix))
let (digits, _) = calculateLenAndBase(radix)
let size = (s.size - idx) / digits + 1
if (size <= 2) {
var int: UInt64 = 0
for (i in 0..numberArray.size) {
int *= radix
int += UInt64(numberArray[i])
}
if (int == 0) {
return (0, EMPTY_ARRAY)
}
return (int, EMPTY_ARRAY)
}
return calculateUInt32Arr(size - 2, numberArray, radix)
}
/**
* @return (isNeg, sign length)
*/
func parseSign(s: String): (Bool, Int64) {
if (s.size == 0) {
throw IllegalArgumentException("Invalid string.")
}
return match (s[0]) {
case b'-' => (true, 1)
case b'+' => (false, 1)
case _ => (false, 0)
}
}
/**
* @return (radix, base length)
*/
func parseBase(s: String, idx: Int64): (UInt64, Int64) {
if (idx >= s.size) {
throw IllegalArgumentException("Invalid string.")
}
if (s[idx] != b'0' || idx + 1 == s.size) {
return (10, 0) // no base prefix, default radix is 10
}
return match (s[idx + 1]) {
case b'b' | b'B' => (2, 2)
case b'o' | b'O' => (8, 2)
case b'x' | b'X' => (16, 2)
case _ => (10, 0)
}
}
func calculateLenAndBase(base: UInt64): (Int64, UInt64) {
var anyBase = base
var digits = 1
while (anyBase < 0xFFFF_FFFF) {
anyBase *= base
digits++
}
anyBase /= base
digits--
return (digits, anyBase)
}
func calculateUInt32Arr(size: Int64, numberArray: Array<UInt8>, base: UInt64): (UInt64, Array<UInt32>) {
let resultArr = Array<UInt32>(size, repeat: 0)
var int: UInt64 = 0
// the first two UInt32 is UInt64
var index = -2
var numbers = numberArray
var numSize = numbers.size
while (numSize != 0) {
var nextSize = 0
var dividend: UInt64 = 0
var i = 0
while (i < numSize) {
dividend *= base
dividend += UInt64(numbers[i])
i++
let quo = dividend >> 32
if (quo == 0) {
if (nextSize != 0) {
numberArray[nextSize] = UInt8(quo)
nextSize++
}
continue
}
numberArray[nextSize] = UInt8(quo)
nextSize++
dividend = dividend & 0xFFFF_FFFF
}
if (index == -2) {
int = dividend & 0xFFFF_FFFF
} else if (index == -1) {
int |= (dividend & 0xFFFF_FFFF) << 32
} else {
resultArr[index] = UInt32(dividend & 0xFFFF_FFFF)
}
index++
numSize = nextSize
}
return (int, normalize(resultArr))
}
func initNumArray(s: String, index: Int64, base: UInt8): Array<UInt8> {
let numberArray = Array<UInt8>(s.size, repeat: 0)
for (i in index..s.size) {
if (s[i].isAsciiNumber() && s[i] - DIGIT_DIFF < base) {
numberArray[i] = s[i] - DIGIT_DIFF
} else if (s[i].isAsciiLowerCase() && s[i] - LETTER_LOWER_DIFF < base) {
numberArray[i] = s[i] - LETTER_LOWER_DIFF
} else if (s[i].isAsciiUpperCase() && s[i] - LETTER_UPPER_DIFF < base) {
numberArray[i] = s[i] - LETTER_UPPER_DIFF
} else {
throw IllegalArgumentException("Invalid string.")
}
}
return numberArray
}
// for quoAndRem
func modAddAbsOfDivisor(int: UInt64, intArr: Array<UInt32>, thatBig: BigInt): BigInt {
let isIntNeg: Bool
var resultIntAbs: UInt64
if (thatBig.int >= int) {
isIntNeg = false
resultIntAbs = thatBig.int - int
} else {
isIntNeg = true
resultIntAbs = int - thatBig.int
}
let resultArr = thatBig.intArr.clone()
if (isIntNeg) {
subAndBorrow(resultArr, 0, 1)
resultIntAbs = 0xFFFF_FFFF_FFFF_FFFF - resultIntAbs + 1
}
subInSitu(resultArr, intArr, 0)
return BigInt(resultIntAbs, normalize(resultArr), false)
}
// add abs
func addAbs(thisInt: UInt64, thisArr: Array<UInt32>, thatInt: UInt64, thatArr: Array<UInt32>): (UInt64, Array<UInt32>) {
let (resultInt, carry) = addUInt64(thisInt, thatInt)
if (thisArr.size == 0 && thatArr.size == 0) {
if (carry == 1) {
return (resultInt, Array<UInt32>(1, repeat: 1))
}
return (resultInt, EMPTY_ARRAY)
}
let (addend1, addend2) = if (thisArr.size > thatArr.size) {
(thisArr, thatArr)
} else {
(thatArr, thisArr)
}
let resultArr = Array<UInt32>(addend1.size + 1, repeat: 0)
addend1.copyTo(resultArr, 0, 0, addend1.size)
addInSitu(resultArr, addend2, carry)
return (resultInt, normalize(resultArr))
}
func addUInt64(thisInt: UInt64, thatInt: UInt64): (UInt64, UInt64) {
var resultInt = (thisInt & 0x7FFF_FFFF_FFFF_FFFF) + (thatInt & 0x7FFF_FFFF_FFFF_FFFF)
let leftResult = (resultInt >> 63) + (thisInt >> 63) + (thatInt >> 63)
let carry: UInt64 = if (leftResult == 3) {
resultInt = resultInt | 0x8000_0000_0000_0000
1
// carry
} else if (leftResult == 2) {
resultInt = resultInt & 0x7FFF_FFFF_FFFF_FFFF
1
} else if (leftResult == 1) {
resultInt = resultInt | 0x8000_0000_0000_0000
0
} else {
0
}
return (resultInt, carry)
}
// add in situ
// summand has the leading 0 to carry the carry, and summand.size >= addend.size
func addInSitu(summand: Array<UInt32>, addend: Array<UInt32>, carry: UInt64): Array<UInt32> {
var c: UInt64 = carry
for (i in 0..addend.size) {
let sum = UInt64(summand[i]) + UInt64(addend[i]) + c
summand[i] = UInt32(sum & 0xFFFF_FFFF)
c = sum >> 32
}
for (i in addend.size..summand.size) {
if (c == 0) {
break
}
let sum = UInt64(summand[i]) + c
summand[i] = UInt32(sum & 0xFFFF_FFFF)
c = sum >> 32
}
return normalize(summand)
}
func subAbs(thisInt: UInt64, thisArr: Array<UInt32>, thatInt: UInt64, thatArr: Array<UInt32>, negSign: Bool): (UInt64,
Array<UInt32>, Bool) {
let isIntNeg: Bool
var resultIntAbs: UInt64
if (thisInt >= thatInt) {
isIntNeg = false
resultIntAbs = thisInt - thatInt
} else {
isIntNeg = true
resultIntAbs = thatInt - thisInt
}
let c = compareAbsArr(thisArr, thatArr, 0)
if (c == 0) {
return (resultIntAbs, EMPTY_ARRAY, isIntNeg != negSign)
}
let minuend: Array<UInt32>
let subtrahend: Array<UInt32>
let isArrNeg: Bool
if (c == 1) {
minuend = thisArr
subtrahend = thatArr
isArrNeg = false
} else {
minuend = thatArr
subtrahend = thisArr
isArrNeg = true
}
let resultArr = minuend.clone()
if (isIntNeg != isArrNeg && resultIntAbs != 0) {
subAndBorrow(resultArr, 0, 1)
resultIntAbs = 0xFFFF_FFFF_FFFF_FFFF - resultIntAbs + 1
}
subInSitu(resultArr, subtrahend, 0)
return (resultIntAbs, normalize(resultArr), isArrNeg != negSign)
}
// sub in situ
// ensure that the weight of the minuend array is greater than that of the subtrahend array
func subInSitu(minuend: Array<UInt32>, subtrahend: Array<UInt32>, offset: Int64): Array<UInt32> {
for (i in 0..subtrahend.size) {
subAndBorrow(minuend, i + offset, subtrahend[i])
}
return normalize(minuend)
}
// sub in situ
func subAndBorrow(minuend: Array<UInt32>, index: Int64, subtrahend: UInt32): Unit {
minuend[index] = if (minuend[index] >= subtrahend) {
minuend[index] - subtrahend
} else {
var j = index + 1
while (minuend[j] == 0) {
minuend[j] = 0xFFFF_FFFF
j++
}
minuend[j] -= 1
0xFFFF_FFFF - subtrahend + minuend[index] + 1
}
}
func knuthNormalize(size: Int64, int: UInt64, intArr: Array<UInt32>, l: Int64): Array<UInt32> {
let normalized = Array<UInt32>(size, repeat: 0)
intArr.copyTo(normalized, 0, 2, intArr.size)
normalized[0] = UInt32(int & 0xFFFF_FFFF)
normalized[1] = UInt32(int >> 32)
shiftLeftInSitu(normalized, l)
return normalized
}
// << in situ
func shiftLeftInSitu(arr: Array<UInt32>, shift: Int64): Array<UInt32> {
if (shift == 0) {
return arr
}
var carry: UInt32 = 0
for (i in 0..arr.size) {
let shiftResult = (arr[i] << shift) | carry
carry = arr[i] >> (32 - shift)
arr[i] = shiftResult
}
return arr
}
// << in situ
func shiftLeftInSitu(int: UInt64, rArr: Array<UInt32>, shift: Int64, deltaSize: Int64): (UInt64, Array<UInt32>) {
let shift64 = shift & 0x3F
let shift32 = shift & 0x1F
let delta = shift >> 5
var carry: UInt32 = if (shift32 > 0 && rArr.size - deltaSize > 0) {
rArr[rArr.size - deltaSize - 1] >> (32 - shift32)
} else {
0
}
if (carry != 0) {
rArr[rArr.size - 1] = carry
}
for (i in rArr.size - deltaSize - 1..0 : -1) {
carry = if (shift32 > 0) {
rArr[i - 1] >> (32 - shift32)
} else {
0
}
rArr[i + delta] = (rArr[i] << shift32) | carry
if (delta != 0) {
rArr[i] = 0
}
}
let rArr0: UInt32
let left: UInt32
(carry, rArr0, left) = shiftLeftUInt64(int, shift64)
// UInt64 shift to Array
if (delta != rArr.size) {
rArr[delta] = (rArr[0] << shift32) | carry
if (delta != 0) {
rArr[0] = 0
}
}
let rInt: UInt64
if (delta >= 2) {
rArr[delta - 1] = rArr0
rArr[delta - 2] = left
rInt = 0
} else if (delta == 1) {
rArr[delta - 1] = rArr0
rInt = UInt64(left) << 32
} else {
rInt = int << shift64
}
return (rInt, rArr)
}
// >> in situ
func shiftRightInSitu(arr: Array<UInt32>, shift: Int64): Array<UInt32> {
if (shift == 0) {
return arr
}
var carry: UInt32 = 0
for (i in arr.size - 1..=0 : -1) {
let rightResult = (arr[i] >> shift) | carry
carry = arr[i] << (32 - shift)
arr[i] = rightResult
}
return arr
}
// divded by 2 in situ
// >> 1
func divBy2Insitu(int: UInt64, arr: Array<UInt32>): (UInt64, Array<UInt32>) {
var carry: UInt32 = 0
for (i in arr.size - 1..=0 : -1) {
let rightResult = (arr[i] >> 1) | carry
carry = arr[i] << 31
arr[i] = rightResult
}
let rInt = (int >> 1) | (UInt64(carry) << 32)
return (rInt, arr)
}
// div in situ
// the bit length of the abs of divisor does not exceed 32 bits
func divByUInt32InSitu(dividend: Array<UInt32>, divisor: UInt64): (Array<UInt32>, UInt64) {
var rem: UInt64 = 0
for (i in dividend.size - 1..=0 : -1) {
let dividendN = UInt64(dividend[i]) + (rem << 32)
dividend[i] = UInt32(dividendN / divisor)
rem = dividendN % divisor
}
return (normalize(dividend), rem)
}
// mod
// the bit length of the abs of divisor does not exceed 32 bits
func modByUInt32(dividend: Array<UInt32>, divisor: UInt64): UInt64 {
var rem: UInt64 = 0
for (i in dividend.size - 1..=0 : -1) {
let dividendN = UInt64(dividend[i]) + (rem << 32)
rem = dividendN % divisor
}
return rem
}
// mod
func mod(thisInt: UInt64, thisArr: Array<UInt32>, thatInt: UInt64, thatArr: Array<UInt32>): (UInt64, Array<UInt32>) {
if (thisArr.size == 0 && thatArr.size == 0) {
return (thisInt % thatInt, EMPTY_ARRAY)
}
let c = compareAbsArr(thisArr, thatArr, 0)
if (c == 0) {
if (thisInt >= thatInt) {
return (thisInt - thatInt, EMPTY_ARRAY)
}
return (thisInt, thisArr.clone())
}
if (c == -1) {
return (thisInt, thisArr.clone())
}
let remArr: Array<UInt32>
let remInt: UInt64
if (thatArr.size == 0) {
// if the bit length of the abs of divisor does not exceed 32 bits
if (thatInt <= 0xFFFF_FFFF) {
// mod % :
// (ab+c)%d = ((ab)%d + c%d )%d
// ab%d = ((a%d)*(b%d))%d
//
// ab%d
let rem = modByUInt32(thisArr, thatInt)
let remInt0 = ((0x8000_0000_0000_0000 % thatInt) * (2 * rem % thatInt)) % thatInt
remInt = (remInt0 + thisInt % thatInt) % thatInt
remArr = EMPTY_ARRAY
} else {
let shift = leadingZeros(thatInt)
// dividend's size equals Array<UInt32>'s size plus 2(UInt64 takes up two UInt32), then plus 1(may overflow)
let normalizedDividend = knuthNormalize(thisArr.size + 3, thisInt, thisArr, shift)
let normalizedDivisor = thatInt << shift
(remInt, remArr) = knuthMod(normalizedDividend, normalizedDivisor, shift)
}
// otherwise, use Knuth division algorithm
} else {
// normalize, let the most significant UInt32 larger than 0x8000_0000
let shift = leadingZeros(thatArr[thatArr.size - 1])
// dividend's size equals Array<UInt32>'s size plus 2(UInt64 takes up two UInt32), then plus 1(may overflow)
let normalizedDividend = knuthNormalize(thisArr.size + 3, thisInt, thisArr, shift)
let normalizedDivisor = knuthNormalize(thatArr.size + 2, thatInt, thatArr, shift)
// divisor's size equals Array<UInt32>'s size plus 2(UInt64 takes up two UInt32)
(remInt, remArr) = knuthMod(normalizedDividend, normalizedDivisor, shift)
}
return (remInt, remArr)
}
func modOption(int: UInt64, intArr: Array<UInt32>, m: ?BigInt): (UInt64, Array<UInt32>) {
if (let Some(m_) <- m) {
if (!isNoLessThan(m_.int, m_.intArr, int, intArr)) {
return mod(int, intArr, m_.int, m_.intArr)
}
}
return (int, intArr)
}
// if the bit length of the abs of divisor exceeds 64 bits
func knuthMod(normalizedDividend: Array<UInt32>, normalizedDivisor: Array<UInt32>, shift: Int64): (UInt64, Array<UInt32>) {
let sizeDD = normalizedDividend.size
let sizeD = normalizedDivisor.size
// initialize j
var j = sizeDD - sizeD - 1
// loop
while (j >= 0) {
knuthDivGuessQ(normalizedDividend, normalizedDivisor, sizeD, j)
j--
}
// unnormalize
let remArr = shiftRightInSitu(normalizedDividend, shift)
let remInt = UInt64(remArr[0]) + (UInt64(remArr[1]) << 32)
return (remInt, normalize(remArr[2..]))
}
// if the bit length of the abs of divisor exceeds 32 bits but does not exceed 64 bits
func knuthMod(normalizedDividend: Array<UInt32>, normalizedDivisor: UInt64, shift: Int64): (UInt64, Array<UInt32>) {
let sizeDD = normalizedDividend.size
// initialize j
var j = sizeDD - 2 - 1
// loop
while (j >= 0) {
knuthDivGuessQ(normalizedDividend, normalizedDivisor, j)
j--
}
// unnormalize
let remArr = shiftRightInSitu(normalizedDividend, shift)
let remInt = UInt64(remArr[0]) + (UInt64(remArr[1]) << 32)
return (remInt, normalize(remArr[2..]))
}
// mul in situ
// multiplicator <= 0xFFFF_FFFF
// multiplicand has the leading 0 to carry the carry
func mulByUInt32InSitu(multiplicand: Array<UInt32>, multiplicator: UInt64): Array<UInt32> {
var carry: UInt64 = 0
for (i in 0..multiplicand.size) {
let product = UInt64(multiplicand[i]) * multiplicator + carry
multiplicand[i] = UInt32(product & 0xFFFF_FFFF)
carry = product >> 32
}
return normalize(multiplicand)
}
// mul, modify rArr in situ
// parameters are result array, multiplicand array, multiplicator and the weight of multiplicator
func mulByUInt32InSitu(rArr: Array<UInt32>, multiplicand: Array<UInt32>, multiplicator: UInt64, index: Int64) {
var carry: UInt64 = 0
for (i in 0..multiplicand.size) {
// 0xFFFF_FFFF*0xFFFF_FFFF+FFFF_FFFF+FFFF_FFFF = 0xFFFF_FFFF_FFFF_FFFF
// never overflow
let product = UInt64(multiplicand[i]) * multiplicator + UInt64(rArr[i + index]) + carry
rArr[i + index] = UInt32(product & 0xFFFF_FFFF)
carry = product >> 32
}
var i = 0
while (carry != 0) {
let superCarry = UInt64(rArr[multiplicand.size + index + i]) + carry
rArr[multiplicand.size + index + i] = UInt32(superCarry & 0xFFFF_FFFF)
carry = superCarry >> 32
i++
}
}
// mul
func mul(mInt: UInt64, mArr: Array<UInt32>, mulInt: UInt64, mulArr: Array<UInt32>): (UInt64, Array<UInt32>) {
let (int, rArr0, rArr1) = uInt64Mul(mInt, mulInt)
if (mArr.size == 0 && mulArr.size == 0) {
if (rArr0 == 0 && rArr1 == 0) {
return (int, EMPTY_ARRAY)
}
let arr = Array<UInt32>(2, repeat: rArr0)
arr[1] = rArr1
return (int, normalize(arr))
}
let rArr = Array<UInt32>(mArr.size + mulArr.size + 2, repeat: 0)
rArr[0] = rArr0
rArr[1] = rArr1
mulByUInt32InSitu(rArr, mArr, mulInt & 0xFFFF_FFFF, 0)
mulByUInt32InSitu(rArr, mArr, mulInt >> 32, 1)
mulByUInt32InSitu(rArr, mulArr, mInt & 0xFFFF_FFFF, 0)
mulByUInt32InSitu(rArr, mulArr, mInt >> 32, 1)
// mul of array
for (i in 0..mArr.size) {
mulByUInt32InSitu(rArr, mulArr, UInt64(mArr[i]), i + 2)
}
return (int, normalize(rArr))
}
// compare the intArr
func compareAbsArr(thisArr: Array<UInt32>, thatArr: Array<UInt32>, offset: Int64): Int64 {
if (thisArr.size > thatArr.size + offset) {
return 1
} else if (thisArr.size < thatArr.size + offset) {
return -1
}
for (i in thatArr.size - 1..=0 : -1) {
if (thisArr[i + offset] > thatArr[i]) {
return 1
} else if (thisArr[i + offset] < thatArr[i]) {
return -1
}
}
for (i in 0..offset) {
if (thisArr[i] != 0) {
return 1
}
}
return 0
}
func isNoLessThan(thisInt: UInt64, thisArr: Array<UInt32>, thatInt: UInt64, thatArr: Array<UInt32>): Bool {
let c = compareAbsArr(normalize(thisArr), normalize(thatArr), 0)
if (c == 0) {
return thisInt >= thatInt
}
return c == 1
}
// gcd
func gcd(int1: UInt64, int1Arr: Array<UInt32>, int2: UInt64, int2Arr: Array<UInt32>): (UInt64, Array<UInt32>) {
if (int1Arr.size == 0 && int2Arr.size == 0) {
return (gcd(int1, int2), EMPTY_ARRAY)
}
var i1Int = int1
var i1Arr = int1Arr.clone()
var i2Int = int2
var i2Arr = int2Arr.clone()
var shift = 0
while (i1Int != i2Int || normalize(i1Arr) != normalize(i2Arr)) {
while ((i1Int & 1) == 0) {
(i1Int, i1Arr) = divBy2Insitu(i1Int, i1Arr)
if ((i2Int & 1) == 0) {
(i2Int, i2Arr) = divBy2Insitu(i2Int, i2Arr)
shift++
}
}
while ((i2Int & 1) == 0) {
(i2Int, i2Arr) = divBy2Insitu(i2Int, i2Arr)
}
if (i1Int == i2Int && normalize(i1Arr) == normalize(i2Arr)) {
break
}
if (!isNoLessThan(i1Int, i1Arr, i2Int, i2Arr)) {
(i1Int, i2Int) = (i2Int, i1Int)
(i1Arr, i2Arr) = (i2Arr, i1Arr)
}
var isIntNeg = false
i1Int = if (i1Int >= i2Int) {
i1Int - i2Int
} else {
isIntNeg = true
i2Int - i1Int
}
if (isIntNeg) {
subAndBorrow(i1Arr, 0, 1)
i1Int = 0xFFFF_FFFF_FFFF_FFFF - i1Int + 1
}
subInSitu(i1Arr, normalize(i2Arr), 0)
}
let deltaSize = i1Arr.size - normalize(i1Arr).size
(i1Int, i1Arr) = shiftLeftInSitu(i1Int, i1Arr, shift, deltaSize)
return (i1Int, normalize(i1Arr))
}
func exgcdToInverse(thisBig: BigInt, thatBig: BigInt): (BigInt, BigInt) {
if (thatBig.sign == 0) {
// the gcd of thisBig and thatBig must be 1
if (thisBig.int != 1 || thisBig.intArr.size != 0) {
throw IllegalArgumentException("The BigInt is not relatively prime with the input.")
}
return (BigInt(1), BigInt(0))
}
let (quo, rem) = thisBig.quoAndRem(thatBig)
let (x, y) = exgcdToInverse(thatBig, rem)
return (y, x - quo * y)
}
func knuthDivGuessQ(normalizedDividend: Array<UInt32>, normalizedDivisor: Array<UInt32>, sizeD: Int64, j: Int64): UInt64 {
// guess q
let dd = (UInt64(normalizedDividend[sizeD + j]) << 32) + UInt64(normalizedDividend[sizeD + j - 1])
let d = UInt64(normalizedDivisor[sizeD - 1])
var q = dd / d
// if q == 0, there is no need to go into the following steps.
if (q == 0) {
return q
}
var r = dd % d
while (r <= 0xFFFF_FFFF) {
if (q > 0xFFFF_FFFF || q * UInt64(normalizedDivisor[sizeD - 2]) > (r << 32) + UInt64(normalizedDividend[sizeD + j -
2])) {
q--
r += d
} else {
break
}
}
var product = Array<UInt32>(sizeD + 1, repeat: 0)
normalizedDivisor.copyTo(product, 0, 0, sizeD)
product = mulByUInt32InSitu(product, q)
if (compareAbsArr(normalize(normalizedDividend), product, j) == -1) {
q--
product = subInSitu(product, normalizedDivisor, 0)
subInSitu(normalize(normalizedDividend), product, j)
} else {
subInSitu(normalize(normalizedDividend), product, j)
}
return q
}
func knuthDivGuessQ(normalizedDividend: Array<UInt32>, normalizedDivisor: UInt64, j: Int64): UInt64 {
// guess q
// the UInt64 int of the dividend is copyed in normalizedDividend array
// the UInt64 int occupys two size
let dd = (UInt64(normalizedDividend[j + 2]) << 32) + UInt64(normalizedDividend[j + 1])
let d = normalizedDivisor >> 32
let d0 = normalizedDivisor & 0xFFFF_FFFF
var q = dd / d
// if q == 0, there is no need to go into the following steps.
if (q == 0) {
return q
}
var r = dd % d
while (r <= 0xFFFF_FFFF) {
if (q > 0xFFFF_FFFF || q * d0 > (r << 32) + UInt64(normalizedDividend[j])) {
q--
r += d
} else {
break
}
}
var product = Array<UInt32>(3, repeat: 0)
product[0] = UInt32(d0)
product[1] = UInt32(d)
product = mulByUInt32InSitu(product, q)
subInSitu(normalize(normalizedDividend), product, j)
return q
}
// for Miller-Rabin test
// looking for the nontrivial square root of 1
// (x^2 mod n = 1, the square root except ±1)
// if find one, n is composite, this function will return true
func witness(a: BigInt, n: BigInt): Bool {
let (subOneInt, subOneArr) = subOne(n.int, n.intArr, false)
let subOne = BigInt(subOneInt, normalize(subOneArr), false)
let t = trailingZeros(subOne)
let u = subOne >> t
// only four cases,
// see flowing:
let x0 = a.modPow(u, m: n)
var x0Int = x0.int
var x0Arr = x0.intArr
// 1. X = <1,1,...,1>
// return false
if (x0Int == 1 && x0Arr.size == 0) {
return false
}
for (_ in 0..t) {
// 2. X = <...,-1,1,...,1>
// return false
if (x0Int == subOneInt && x0Arr == subOneArr) {
return false
}
var (x1Int, x1Arr) = mul(x0Int, x0Arr, x0Int, x0Arr)
(x1Int, x1Arr) = mod(x1Int, x1Arr, n.int, n.intArr)
// 3. X = <...,d,1,...,1>
// return true
// find the nontrivial square root of 1
if (x1Int == 1 && x1Arr.size == 0) {
return true
}
x0Int = x1Int
x0Arr = x1Arr
}
// 4. X = <...,d>
// return true
// by Fermat's theorem
if (x0Int != 1 || x0Arr.size != 0) {
return true
}
return false
}
extend BigInt <: Number<BigInt> {}
extend BigInt <: Integer<BigInt> {
public static func isSigned(): Bool {
true
}
}