View source for 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 (integers and rational numbers) in an easy to use form. It is based on or guided by Peter Olson's public domain [https://github.com/peterolson/BigInteger.js BigInteger.js] and [https://github.com/peterolson/BigRational.js BigRational.js] libraries 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.

;BigInt class

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 class 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.

;BigRat class

This follows the lines of the Rat class in the [https://rosettacode.org/wiki/Category:Wren-rat Wren-rat] module though I have been guided by [https://github.com/peterolson/BigRational.js BigRational.js] when coding some of the trickier parts.

The ''BigRat.new'' constructor accepts a BigInt numerator and denominator (or just a numerator on its own). However, you can pass in Nums or Strings if a BigInt can be built from them

There are also separate methods to enable you to to generate a BigRat from a Rat object, from a string in rational form (i.e. "n/d"), from a mixed string (e.g. "1_2/3") from a decimal string or value (e.g. "1.234") or from a Num.

As rational numbers can easily be created from or displayed as decimal numbers, there seems little point in adding a BigDecimal class to the module as well.

;General observations

The original Javascript libraries 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 or BigRats. 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 or BigRats 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) {
            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) ? y.count : x.count
        if (n <= 30) return multiplyLong_(x, y)
        n = (n/2).floor
        var a = x[0...n]
        var b = x[n..-1]
        var c = y[0...n]
        var d = y[n..-1]
        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 the factorial of 'n'.
    static factorial(n) {
        if (!(n is Num && n >= 0)) Fiber.abort("Argument must be a non-negative integer")
        if (n < 2) return BigInt.one
        var fact = BigInt.one
        for (i in 2..n) fact = fact * i
        return fact
    }

    // 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 (n.isZero) return this
        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 (n.isZero) return this
        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)
    }

    // Cube the current instance.
    cube { square * this }

    // Returns true if the current instance is a perfect square, false otherwise.
    isSquare {
        var root = isqrt
        return root.square == this
    }

    // Returns true if the current instance is a perfect cube, false otherwise.
    isCube {
        var root = icbrt
        return root.square * root == this
    }

    // Returns the integer n'th root of the current instance 
    // i.e. the precise n'th root truncated towards zero if not an integer.
    // Throws an error if the current instance is negative and n is even.
    iroot(n) {
        if (!((n is Num) && n.isInteger && n > 0)) {
            Fiber.abort("Argument must be a positive integer.")
        }
        if (n == 1) return this
        var t = copy()
        var neg = t < 0
        if (neg) {
            if (n % 2 == 0) {
                Fiber.abort("Cannot take the %(n)th root of a negative number.")
            } else {
                t = -t
            }
        }
        n = n - 1
        var s = t + 1
        var u = t
        while (u < s) {
            s = u
            u = ((u * n) + t / u.pow(n)) / (n + 1)
        }
        return (neg) ? -s : s
    }

    // Returns the cube root of the current instance i.e. the largest integer 'r' such that
    // r.cube <= this.
    icbrt { 
        if (isSmall) return BigInt.small_(toSmall.cbrt.floor)
        return iroot(3) 
    }

    // 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 (isNegative) Fiber.abort("Cannot take the square root of a negative number.")
        if (isSmall) return BigInt.small_(toSmall.sqrt.floor)
        var one = BigInt.one
        var a = one << ((bitLength + one) >> one)
        while (true) {
            var b = (this/a + a) >> one
            if (b >= a) return a
            a = b
        }
    } 
 
    // 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
    }

     // Returns true if the 'n'th bit of the current instance is set or false otherwise. 
    testBit(n) {
        if (n.type != Num || !n.isInteger || n < 0) Fiber.abort("Argument must be a non-negative integer.")
        return (this >> n) & BigInt.one != BigInt.zero
    }

    // 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
    }

    /* Prime factorization methods. */
 
    // Private worker method for Pollard's Rho algorithm.
    static pollardRho_(m, seed, c) {
        var g = Fn.new { |x| (x*x + c) % m }
        var x = BigInt.two
        var y = BigInt.new(seed)
        var z = BigInt.one
        var d = BigInt.one
        var count = 0
        while (true) {
            x = g.call(x)
            y = g.call(g.call(y))
            d = (x - y).abs % m
            z = z * d
            count = count + 1
            if (count == 100) {
                d = BigInt.gcd(z, m)
                if (d != BigInt.one) break
                z = BigInt.one
                count = 0
            }
        }
        if (d == m) return BigInt.zero
        return d
    }
 
    // Returns a factor (BigInt) of 'm' (a BigInt or an integral Num) using the
    // Pollard's Rho algorithm. Both the 'seed' and 'c' can be set to integers.
    // Returns BigInt.zero in the event of failure.
    static pollardRho(m, seed, c) {
        if (m < 2) return BigInt.zero
        if (m is Num) m = BigInt.new(m)
        if (m.isProbablePrime(10)) return m.copy() 
        if (m.isSquare) return m.isqrt
        for (p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]) {
            if (m.isDivisibleBy(p)) return BigInt.new(p)
        }
        return pollardRho_(m, seed, c)
    }
 
    // Convenience version of the above method which uses a seed of 2 and a value for c of 1.
    static pollardRho(m) { pollardRho(m, 2, 1) }
 
    // Private method for factorizing smaller numbers (BigInt) using a wheel with basis [2, 3, 5].
    static primeFactorsWheel_(m) {
        var n = m.copy()
        var inc = [4, 2, 4, 2, 4, 6, 2, 6]
        var factors = []
        var k = BigInt.new(37)
        var i = 0        
        while (k * k <= n) {
            if (n.isDivisibleBy(k)) {
                factors.add(k.copy())
                n = n / k
            } else {
                k = k + inc[i]
                i = (i + 1) % 8
            }
        }
        if (n > BigInt.one) factors.add(n)
        return factors
    }
 
    // Private worker method (recursive) to obtain the prime factors of a number (BigInt). 
    static primeFactors_(m, trialDivs) {
        if (m.isProbablePrime(10)) return [m.copy()]
        var n = m.copy()
        var factors = []
        var seed = 2
        var c = 1
        var checkPrime = true
        var threshold = 1e11 // from which using PR may be advantageous
        if (trialDivs) {
            for (p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]) {
                while (n.isDivisibleBy(p)) {
                    factors.add(BigInt.new(p))
                    n = n / p
                }
            }
        }
        while (n > BigInt.one) {
            if (checkPrime && n.isProbablePrime(10)) {
                factors.add(n)
                break
            }
            if (n >= threshold) {                   
                var d = pollardRho_(n, seed, c)
                if (d != BigInt.zero) {
                    factors.addAll(primeFactors_(d, false))
                    n = n / d
                    checkPrime = true
                } else if (c == 1) {
                    if (n.isSquare) {
                        n = n.isqrt
                        var pf = primeFactors_(n, false)
                        factors.addAll(pf)
                        factors.addAll(pf)
                        break
                    } else {
                        c = 2
                        checkPrime = false
                    }
 
                } else if (c < 101) {
                    c = c + 1
                } else if (seed < 101) {
                    seed = seed + 1
                } else {
                    factors.addAll(primeFactorsWheel_(n))
                    break
                }                    
            } else {
                factors.addAll(primeFactorsWheel_(n))
                break
            }
        }
        factors.sort()
        return factors
    }
 
    // Returns a list of the primes factors (BigInt) of 'm' (a Bigint or an integral Num)
    // using the wheel based factorization and/or Pollard's Rho algorithm as appropriate. 
    static primeFactors(m) {
       if (m < 2) return []
       if (m is Num) m = BigInt.new(m)
       return primeFactors_(m, true)
    }
}

/*  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 } }
}

/* BigRat represents a rational number as a BigInt numerator and (non-zero) denominator
   expressed in their lowest terms. BigRat objects are immutable.
*/
class BigRat is Comparable {
    // Private helper function to check that 'o' is a suitable type and throw an error otherwise.
    // Rational numbers, numbers and numeric strings are returned as BigRats.
    static check_(o) {
        if (o is BigRat) return o
        if (o is BigInt) return BigRat.new(o, BigInt.one)
        if (o.type.toString == "Rat") return BigRat.fromRat(o)
        if (o is Num) return BigRat.fromFloat(o)
        if (o is String) return (o.contains("_") && o.contains("/")) ? fromMixedString(o) :
                                 o.contains("/") ? fromRationalString(o) : fromDecimal(o)
        Fiber.abort("Argument must either be a rational number, a number or a numeric string.")
    }

    // Constants.
    static minusOne { BigRat.new(BigInt.minusOne, BigInt.one) }
    static zero     { BigRat.new(BigInt.zero,     BigInt.one) }
    static one      { BigRat.new(BigInt.one,      BigInt.one) }
    static two      { BigRat.new(BigInt.two,      BigInt.one) }
    static ten      { BigRat.new(BigInt.ten,      BigInt.one) }
    static half     { BigRat.new(BigInt.one,      BigInt.two) }
    static tenth    { BigRat.new(BigInt.one,      BigInt.ten) }

    // Constructs a new BigRat object by passing it a numerator and a denominator.
    // These must either be BigInts or Nums/Strings which are capable of creating one
    // when passed to the BigInt.new constructor.
    construct new(n, d) {
        n = (n is BigInt) ? n.copy() : BigInt.new(n)
        d = (d is BigInt) ? d.copy() : BigInt.new(d)
        if (d == BigInt.zero) Fiber.abort("Denominator must be a non-zero integer.")
        if (n == BigInt.zero) {
            d = BigInt.one
        } else if (d < BigInt.zero) {
            n = -n
            d = -d
        }
        var g = BigInt.gcd(n, d).abs
        if (g > BigInt.one) {
            n = n / g
            d = d / g
        }
        _n = n
        _d = d
    }

    // Convenience method which constructs a new BigRat object by passing it just a numerator.
    static new(n) { BigRat.new(n, BigInt.one) }

    // Constructs a BigRat object from a Rat object. To use this method the Rat class needs
    // to be imported from the Wren-rat module as, to minimize dependencies,
    // this module does not do so.
    static fromRat(r) {
        if (r.type.toString != "Rat") Fiber.abort("Argument must be a rational number.")
        return BigRat.new(r.num, r.den)
    }

    // Constructs a BigRat object from a string of the form "n/d".
    // Improper fractions are allowed.
    static fromRationalString(s) {
        var nd = s.split("/")
        if (nd.count != 2) Fiber.abort("Argument is not a suitable string.")
        var n = BigInt.new(nd[0])
        var d = BigInt.new(nd[1])
        return BigRat.new(n, d)
    }

    // Constructs a BigRat object from a string of the form "i_n/d" where 'i' is an integer.
    // Improper and negative fractional parts are allowed.
    static fromMixedString(s) {
        var ind = s.split("_")
        if (ind.count != 2) Fiber.abort("Argument is not a suitable string.")
        var nd = fromRationalString(ind[1])
        var i = BigRat.new(ind[0])
        var neg = i.isNegative || (i.isZero && ind[0][0] == "-")
        return neg ? i - nd : i + nd
    }

    // Constructs a BigRat object from a decimal numeric string or value.
    static fromDecimal(s) {
        if (!(s is String)) s = s.toString
        if (s == "") Fiber.abort("Argument cannot be an empty string.")
        s = BigInt.lower_(s)
        var parts = s.split("e")
        if (parts.count > 2) Fiber.abort("Argument is invalid scientific notation.")
        if (parts.count == 2) {
            var isPositive = true
            if (parts[1][0] == "-") {
                parts[1] = parts[1][1..-1]
                isPositive = false
            }
            if (parts[1][0] == "+") parts[1] = parts[1][1..-1]
            var significand = fromDecimal(parts[0])
            var p = BigInt.new(parts[1])
            var exponent = BigRat.new(BigInt.ten.pow(p), BigInt.one)
            return (isPositive) ? significand * exponent : significand / exponent
        }
        s = s.trim().trimStart("0")
        if (s == "") return BigRat.zero
        if (s.startsWith(".")) s = "0" + s
        if (!s.contains(".")) {
            return BigRat.new(s)
        } else {
             s = s.trimEnd("0")
        }
        if (s.endsWith(".")) return BigRat.new(s[0..-2])
        var splits = s.split(".")
        if (splits.count != 2) Fiber.abort("Argument is not a decimal.")
        var num = splits[0]
        var isNegative = false
        if (num.startsWith("-")) {
            isNegative = true
            num = num[1..-1]
        } else if (num.startsWith("+")) {
            num = num[1..-1]
        }
        var den = splits[1]
        if (!num.all { |c| "0123456789".contains(c) } || !den.all { |c| "0123456789".contains(c) }) {
            Fiber.abort("Argument is not a decimal.")
        }
        num = BigInt.new(num + den)
        if (isNegative) num = -num
        den = BigInt.ten.pow(den.count)
        return BigRat.new(num, den)
    }

    // Constructs a rational number from a floating point number provided the latter is an integer
    // or has a decimal string representation.
    static fromFloat(n) {
        if (!(n is Num)) Fiber.abort("Argument must be a number.")
        if (n.isInteger) return BigRat.new(n, BigInt.one)
        return fromDecimal(n)
    }

    // Returns the greater of two BigRat objects.
    static max(r1, r2) { (r1 < r2) ? r2 : r1 }

    // Returns the smaller of two BigRat objects.
    static min(r1, r2) { (r1 < r2) ? r1 : r2 }

    // Determines whether a BigRat object is always shown as such or, if integral, as an integer.
    static showAsInt     { __showAsInt }
    static showAsInt=(b) { __showAsInt = b }

    // Basic properties.
    num        { _n }                   // numerator
    den        { _d }                   // denominator
    ratio      { [_n, _d] }             // a two element list of the above
    isInteger  { _d == 1 }              // checks if integral or not
    isPositive { _n > BigInt.zero }     // checks if positive
    isNegative { _n < BigInt.zero }     // checks if negative
    isUnit     { _n.abs == BigInt.one } // checks if plus or minus one
    isZero     { _n == BigInt.zero }    // checks if zero

    // Rounding methods (similar to those in Num class).
    ceil { // higher integer
        if (isInteger) return this
        var div = _n/_d
        if (!this.isNegative) div = div.inc
        return BigRat.new(div, BigInt.one)
    }

    floor { // lower integer
        if (isInteger) return this
        var div = _n/_d
        if (this.isNegative) div = div.dec
        return BigRat.new(div, BigInt.one)
    }

    truncate { this.isNegative ? ceil : floor } // lower integer, towards zero

    round { // nearer integer
        if (isInteger) return this
        var div = _n / _d
        if (_d == 2) {
            div = isNegative ? div.dec : div.inc // round 1/2 away from zero
            return BigRat.new(div, BigInt.one)
        }
        return (this + BigRat.half).floor
    }

    fraction { this - truncate } // fractional part (same sign as this.num)

    // Reciprocal
    inverse  { BigRat.new(_d, _n) }

    // Integer division.
    idiv(o)  { (this/o).truncate }

    // Negation.
    -{ BigRat.new(-_n, _d) }

    // Arithmetic operators (work with numbers and numeric strings as well as other rationals).
    +(o) { (o = BigRat.check_(o)) && BigRat.new(_n * o.den + _d * o.num, _d * o.den) }
    -(o) { (o = BigRat.check_(o)) && (this + (-o)) }
    *(o) { (o = BigRat.check_(o)) && BigRat.new(_n * o.num, _d * o.den) }
    /(o) { (o = BigRat.check_(o)) && BigRat.new(_n * o.den, _d * o.num) }
    %(o) { (o = BigRat.check_(o)) && (this - idiv(o) * o) }

    // Computes integral powers.
    pow(i) {
        if (!((i is Num) && i.isInteger)) Fiber.abort("Argument must be an integer.")
        if (i == 0) return this
        var np = _n.pow(i.abs)
        var dp = _d.pow(i.abs)
        return (i > 0) ? BigRat.new(np, dp) : BigRat.new(dp, np)
    }

    // Returns the square of the current instance.
    square { BigRat.new(_n * _n , _d *_d) }

    // Returns the square root of the current instance to 'digits' decimal places.
    // Five more decimals is used to try to ensure accuracy though this is not guaranteed.
    sqrt(digits) {
        if (!((digits is Num) && digits.isInteger && digits >= 0)) {
            Fiber.abort("Digits must be a non-negative integer.")
        }
        digits = digits + 5
        var powd = BigInt.ten.pow(digits)
        var sqtd = (powd.square * _n / _d).isqrt
        return BigRat.new(sqtd, powd)
    }
   
    // Convenience version of the above method which uses 14 decimal places.
    sqrt { sqrt(14) }

    // Other methods.
    inc  { this + BigRat.one }                  // increment
    dec  { this - BigRat.one }                  // decrement
    abs  { (_n >= BigInt.zero) ? this : -this } // absolute value
    sign { _n.sign }                            // sign

    // The inherited 'clone' method just returns 'this' as BigRat objects are immutable.
    // If you need an actual copy use this method instead.
    copy() { BigRat.new(_n, _d) }
 
    // Compares this BigRat with another one to enable comparison operators via Comparable trait.
    compare(other) {
        if ((other is Num) && other.isInfinity) return -other.sign
        other = BigRat.check_(other)
        if (_d == other.den) return _n.compare(other.num)
        return (_n * other.den).compare(other.num * _d)
    }

    // As above but compares the absolute values of the BigRats.
    compareAbs(other) { this.abs.compare(other.abs) }

    // Returns this BigRat expressed as a BigInt with any fractional part truncated.
    toBigInt { _n/_d }

    // Converts the current instance to a Num where possible.
    // Will probably lose accuracy if the numerator and/or denominator are not 'small'.
    toFloat { Num.fromString(this.toDecimal(14)) }

    // Converts the current instance to an integer where possible with any fractional part truncated.
    // Will probably lose accuracy if the numerator and/or denominator are not 'small'.
    toInt { this.toFloat.truncate }

    // Returns the decimal representation of this BigRat object to 'digits' decimal places.
    // If 'rounded' is true, the value is rounded to that number of places with halves 
    // being rounded away from zero. Otherwise the value is truncated to that number of places.
    // If 'zfill' is true, any unfilled decimal places are filled with zeros.
    toDecimal(digits, rounded, zfill) {
        if (!(digits is Num && digits.isInteger && digits >= 0)) {
            Fiber.abort("Digits must be a non-negative integer")
        }
        if (rounded.type != Bool) Fiber.abort("Rounded must be true or false.")
        if (zfill.type != Bool) Fiber.abort("Zfill must be true or false.")        
        var qr = _n.divMod(_d) 
        var rem = BigRat.new(qr[1].abs, _d)
        // need to allow an extra digit if 'rounding' is true
        var digits2 = (rounded) ? digits + 1 : digits
        var shiftedRem = rem * BigRat.new("1e" + digits2.toString, BigInt.one)
        var decPart = (shiftedRem.num / shiftedRem.den).toString
        if (rounded) {
            var finalByte = decPart[-1].bytes[0]
            if (finalByte >= 53) {  // last character >= 5
                decPart = (BigInt.new(decPart) + 5).toString
                if (digits == 0) {
                    qr[0] = isNegative ? qr[0].dec : qr[0].inc
                } else if (decPart.count == digits2 + 1) {          
                    qr[0] = isNegative ? qr[0].dec : qr[0].inc
                    decPart = decPart[1..-1]
                }
            }
            decPart = decPart[0...-1]  // remove last digit
        }
        if (decPart.count < digits) {
            decPart = ("0" * (digits - decPart.count)) + decPart
        }
        if ((shiftedRem.num % shiftedRem.den) == BigInt.zero)  {
            decPart = decPart.trimEnd("0")
        }
        if (digits < 1 || digits == 1 && decPart == "0") decPart = ""
        var intPart = qr[0].toString
        if (this.isNegative && qr[0] == 0) intPart = "-" + intPart
        if (decPart == "") {
             if (digits > 0) return intPart + (zfill ? "." + ("0" * digits) : "")
             return intPart
        } 
        return intPart + "." + decPart + (zfill ? ("0" * (digits - decPart.count)) : "")
    }

    // Convenience versions of the above which use default values for some or all parameters.
    toDecimal(digits, rounded) { toDecimal(digits, rounded, false) } // never trailing zeros
    toDecimal(digits)          { toDecimal(digits, true, false)    } // always rounded, never trailing zeros
    toDecimal                  { toDecimal(14, true, false)        } // 14 digits, always rounded, never trailing zeros

    // Returns a string represenation of this instance in the form "i_n/d" where 'i' is an integer.
    toMixedString {
        var q = _n / _d
        var r = _n % _d
        if (r.isNegative) r = -r
        return q.toString + "_" + r.toString + "/" + _d.toString
    }

    // Returns the string representation of this BigRat object depending on 'showAsInt'.
    toString { (BigRat.showAsInt && _d == BigInt.one) ? "%(_n)" : "%(_n)/%(_d)" }
}

/*  BigRats contains various routines applicable to lists of big rational numbers */
class BigRats {
    static sum(a)  { a.reduce(BigRat.zero) { |acc, x| acc + x } }
    static mean(a) { sum(a)/a.count }
    static prod(a) { a.reduce(BigRat.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_BigRat  = BigRat
var Big_BigRats = BigRats
var Big_Comparable = Comparable // in case imported indirectly

// Initialize static fields.
BigInt.init_()</lang>