spb/os-vault Public
Self-custody, multi-chain crypto wallet for macOS. One recovery phrase, six chain families, zero API keys — nothing leaves your Mac.
Swift 96%
Shell 3.4%
Makefile 0.6%
1//2// ————————————————————————————————————————————————————————————————————————————————————————————3// |||||||||||||||| SMP Core.swift ||||||||||||||||4// ————————————————————————————————————————————————————————————————————————————————————————————5// Created by Marcel Kröker on 30.09.16.6// Copyright (c) 2016 Blubyte. All rights reserved.7//8//9//10// ——————————————————————————————————————————— v1.0 ———————————————————————————————————————————11// - Initial Release.12//13// ——————————————————————————————————————————— v1.1 ———————————————————————————————————————————14// - Improved String conversion, now about 45x faster, uses base 10^9 instead15// of base 10.16// - bytes renamed to limbs.17// - Uses typealias for limbs and digits.18//19// ——————————————————————————————————————————— v1.2 ———————————————————————————————————————————20// - Improved String conversion, now about 10x faster, switched from base 10^921// to 10^18 (biggest possible decimal base).22// - Implemented karatsuba multiplication algorithm, about 5x faster than the23// previous algorithm.24// - Addition is 1.3x faster.25// - Addtiton and subtraction omit trailing zeros, algorithms need less26// operations now.27// - Implemented exponentiation by squaring.28// - New storage (BStorage) for often used results.29// - Uses uint_fast64_t instead of UInt64 for Limbs and Digits.30//31// ——————————————————————————————————————————— v1.3 ———————————————————————————————————————————32// - Huge Perfomance increase by skipping padding zeros and new multiplication33// algotithms.34// - Printing is now about 10x faster, now on par with GMP.35// - Some operations now use multiple cores.36//37// ——————————————————————————————————————————— v1.4 ———————————————————————————————————————————38// - Reduced copying by using more pointers.39// - Multiplication is about 50% faster.40// - String to BInt conversion is 2x faster.41// - BInt to String also performs 50% better.42//43// ——————————————————————————————————————————— v1.5 ———————————————————————————————————————————44// - Updated for full Swift 3 compatibility.45// - Various optimizations:46// - Multiplication is about 2x faster.47// - BInt to String conversion is more than 3x faster.48// - String to BInt conversion is more than 2x faster.49//50// ——————————————————————————————————————————— v1.6 ———————————————————————————————————————————51// - Code refactored into modules.52// - Renamed the project to SMP (Swift Multiple Precision).53// - Added arbitrary base conversion.54//55// ——————————————————————————————————————————— v2.0 ———————————————————————————————————————————56// - Updated for full Swift 3 compatibility.57// - Big refactor, countless optimizations for even better performance.58// - BInt conforms to SignedNumeric and BinaryInteger, this makes it very easy to write59// generic code.60// - BDouble also conforms to SignedNumeric and has new functionalities.61//62//63//64// ————————————————————————————————————————————————————————————————————————————————————————————65// |||||||||||||||| Evolution ||||||||||||||||66// ————————————————————————————————————————————————————————————————————————————————————————————67//68//69//70// Planned features of BInt v3.0:71// - Implement some basic cryptography functions.72// - General code cleanup, better documentation.73// - More extensive tests.74// - Please contact me if you have any suggestions for new features!75//76//77//78// ————————————————————————————————————————————————————————————————————————————————————————————79// |||||||||||||||| Basic Project syntax conventions ||||||||||||||||80// ————————————————————————————————————————————————————————————————————————————————————————————81//82// Indentation: Tabs83//84// Align: Spaces85//86// Style: allman87// func foo(...)88// {89// ...90// }91//92// Single line if-statement:93// if condition { code }94//95// Maximum line length: 96 characters96//97// ————————————————————————————————————————————————————————————————————————————————————————————9899// MARK: - Imports100101// ————————————————————————————————————————————————————————————————————————————————————————————102// |||||||| Imports |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||103// ————————————————————————————————————————————————————————————————————————————————————————————104105import Foundation106107// MARK: - Typealiases108109// ————————————————————————————————————————————————————————————————————————————————————————————110// |||||||| Typealiases |||||||||||||||||||||||||||||||||||||||||||||||||||||||||111// ————————————————————————————————————————————————————————————————————————————————————————————112113// Limbs are basically single Digits in base 2^64. Each slot in an Limbs array stores one114// Digit of the number. The least significant digit is stored at index 0, the most significant115// digit is stored at the last index.116typealias Limbs = [UInt64]117typealias Limb = UInt64118119// A digit is a number in base 10^18. This is the biggest possible base that120// fits into an unsigned 64 bit number while maintaining the propery that the square root of121// the base is a whole number and a power of ten . Digits are required for printing BInt122// numbers. Limbs are converted into Digits first, and then printed.123typealias Digits = [UInt64]124typealias Digit = UInt64125126// MARK: - Imports127128// ————————————————————————————————————————————————————————————————————————————————————————————129// |||||||| Operators |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||130// ————————————————————————————————————————————————————————————————————————————————————————————131132precedencegroup ExponentiationPrecedence {133 associativity: left134 higherThan: MultiplicationPrecedence135 lowerThan: BitwiseShiftPrecedence136}137138// Exponentiation operator139infix operator **: ExponentiationPrecedence140141// MARK: - BInt142143// ————————————————————————————————————————————————————————————————————————————————————————————144// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||145// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||146// |||||||| BInt ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||147// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||148// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||149// ————————————————————————————————————————————————————————————————————————————————————————————150151/// BInt is an arbitrary precision integer value type. It stores a number in base 2^64 notation152/// as an array. Each element of the array is called a limb, which is of type UInt64, the whole153/// array is called limbs and has the type [UInt64]. A boolean sign variable determines if the154/// number is positive or negative. If sign == true, then the number is smaller than 0,155/// otherwise it is greater or equal to 0. It stores the 64 bit digits in little endian, that156/// is, the least significant digit is stored in the array index 0:157///158/// limbs == [] := undefined, should throw an error159/// limbs == [0], sign == false := 0, defined as positive160/// limbs == [0], sign == true := undefined, should throw an error161/// limbs == [n] := n if sign == false, otherwise -n, given 0 <= n < 2^64162///163/// limbs == [l0, l1, l2, ..., ln] :=164/// (l0 * 2^(0*64)) +165/// (11 * 2^(1*64)) +166/// (12 * 2^(2*64)) +167/// ... +168/// (ln * 2^(n*64))169public struct BInt:170 SignedNumeric, // Implies Numeric, Equatable, ExpressibleByIntegerLiteral171 BinaryInteger, // Implies Hashable, CustomStringConvertible, Strideable, Comparable172 ExpressibleByFloatLiteral173{174 //175 //176177 // MARK: - Internal data178179 // ————————————————————————————————————————————————————————————————————————————————————————180 // |||||||| Internal data |||||||||||||||||||||||||||||||||||||||||||||||||||181 // ————————————————————————————————————————————————————————————————————————————————————————182 //183 //184 //185186 internal var sign = false187 internal var limbs = Limbs()188189 // Required by protocol Numeric190 public typealias Magnitude = UInt64191192 // Required by protocol Numeric193 public var magnitude: UInt64 {194 limbs[0]195 }196197 public typealias Words = [UInt]198199 /// A collection containing the words of this value’s binary representation, in order from200 /// the least significant to most significant.201 public var words: BInt.Words {202 limbs.map { UInt($0) }203 }204205 //206 //207208 // MARK: - Initializers209210 // ————————————————————————————————————————————————————————————————————————————————————————211 // |||||||| Initializers ||||||||||||||||||||||||||||||||||||||||||||||||||||212 // ————————————————————————————————————————————————————————————————————————————————————————213 //214 //215 //216217 /// Root initializer for all other initializers. Because no sign is provided, the new218 /// instance is positive by definition.219 internal init(limbs: Limbs) {220 precondition(limbs != [], "BInt can't be initialized with limbs == []")221 self.limbs = limbs222 }223224 /// Create an instance initialized with a sign and a limbs array.225 internal init(sign: Bool, limbs: Limbs) {226 self.init(limbs: limbs)227 self.sign = sign228 }229230 /// Create an instance initialized with the value 0.231 init() {232 self.init(limbs: [0])233 }234235 /// Create an instance initialized to an integer value.236 init(_ z: Int) {237 // Since abs(Int.min) > Int.max, it is necessary to handle238 // z == Int.min as a special case.239 if z == Int.min {240 self.init(sign: true, limbs: [Limb(Int.max) + 1])241 return242 } else {243 self.init(sign: z < 0, limbs: [Limb(abs(z))])244 }245 }246247 /// Create an instance initialized to an unsigned integer value.248 init(_ n: UInt) {249 self.init(limbs: [Limb(n)])250 }251252 /// Create an instance initialized to a string value.253 public init(_ str: String) {254 var str = str255 var sign = false256 var base: Limbs = [1]257 var limbs: Limbs = [0]258259 limbs.reserveCapacity(Int(Double(str.count) / log10(pow(2.0, 64.0))))260261 if str.hasPrefix("-") {262 str.remove(at: str.startIndex)263 sign = str != "0"264 }265266 for chunk in String(str.reversed()).split(19).map({ String($0.reversed()) }) {267 if let num = Limb(String(chunk)) {268 limbs.addProductOf(multiplier: base, multiplicand: num)269 base = base.multiplyingBy([10_000_000_000_000_000_000])270 } else {271 fatalError("Error: String must only consist of Digits (0-9)")272 }273 }274275 self.init(sign: sign, limbs: limbs)276 }277278 // Requierd by protocol ExpressibleByFloatLiteral.279 public init(floatLiteral value: Double) {280 self.init(sign: value < 0, limbs: [Limb(value)])281 }282283 // Required by protocol ExpressibleByIntegerLiteral.284 public init(integerLiteral value: Int) {285 self.init(value)286 }287288 // Required by protocol Numeric289 public init?<T>(exactly source: T) where T: BinaryInteger {290 self.init(Int(source))291 }292293 /// Creates an integer from the given floating-point value, rounding toward zero.294 public init<T>(_ source: T) where T: BinaryFloatingPoint {295 self.init(Int(source))296 }297298 /// Creates a new instance from the given integer.299 public init<T>(_ source: T) where T: BinaryInteger {300 self.init(Int(source))301 }302303 /// Creates a new instance with the representable value that’s closest to the given integer.304 public init<T>(clamping source: T) where T: BinaryInteger {305 self.init(Int(source))306 }307308 /// Creates an integer from the given floating-point value, if it can be represented309 /// exactly.310 public init?<T>(exactly source: T) where T: BinaryFloatingPoint {311 self.init(source)312 }313314 /// Creates a new instance from the bit pattern of the given instance by sign-extending or315 /// truncating to fit this type.316 public init<T>(truncatingIfNeeded source: T) where T: BinaryInteger {317 self.init(source)318 }319320 //321 //322323 // MARK: - CustomStringConvertible conformance324325 // ————————————————————————————————————————————————————————————————————————————————————————326 // |||||||| CustomStringConvertible conformance |||||||||||||||||||||||||||||327 // ————————————————————————————————————————————————————————————————————————————————————————328 //329 //330 //331332 public var description: String {333 (sign ? "-" : "").appending(limbs.decimalRepresentation)334 }335336 public init(number: String, withBase base: Int) {337 self.init(number.convertingBase(from: base, toBase: 10))338 }339340 public func asString(withBase base: Int) -> String {341 let str = limbs.decimalRepresentation342 let newStr = str.convertingBase(from: 10, toBase: base)343344 if sign { return "-".appending(newStr) }345 return newStr346 }347348 //349 //350351 // MARK: - Struct functions352353 // ————————————————————————————————————————————————————————————————————————————————————————354 // |||||||| Struct functions ||||||||||||||||||||||||||||||||||||||||||||||||355 // ————————————————————————————————————————————————————————————————————————————————————————356 //357 //358 //359360 /// Returns BInt value as an integer, if possible.361 func toInt() -> Int? {362 // Conversion only works when self has only one limb thats smaller or363 // equal to abs(Int.min).364365 if limbs.count != 1 { return nil }366367 let number = limbs[0]368369 // Self is within the range of Int370 if number <= Limb(Int.max) {371 return sign ? -Int(number) : Int(number)372 }373374 // Special case: self == Int.min375 if number == (Limb(Int.max) + 1), sign {376 return Int.min377 }378379 return nil380 }381382 var rawValue: (sign: Bool, limbs: [UInt64]) {383 (self.sign, self.limbs)384 }385386 public func hash(into hasher: inout Hasher) {387 hasher.combine("\(sign)\(limbs)".hashValue)388 }389390 /// A Boolean value indicating whether this type is a signed integer type.391 public static var isSigned: Bool {392 true393 }394395 /// Returns -1 if this value is negative and 1 if it’s positive; otherwise, 0.396 public func signum() -> BInt {397 if isZero() { return BInt(0) }398 else if isPositive() { return BInt(1) }399 else { return BInt(-1) }400 }401402 func isPositive() -> Bool { !sign }403 func isNegative() -> Bool { sign }404 func isZero() -> Bool { limbs[0] == 0 && limbs.count == 1 }405 func isNotZero() -> Bool { limbs[0] != 0 || limbs.count > 1 }406 func isOdd() -> Bool { limbs[0] & 1 == 1 }407 func isEven() -> Bool { limbs[0] & 1 == 0 }408409 /// The number of bits in the current binary representation of this value.410 public var bitWidth: Int {411 limbs.bitWidth412 }413414 /// The number of trailing zeros in this value’s binary representation.415 public var trailingZeroBitCount: Int {416 var i = 0417 while true {418 if limbs.getBit(at: i) { return i }419 i += 1420 }421 }422423 //424 //425426 // MARK: - BInt Shifts427428 // ————————————————————————————————————————————————————————————————————————————————————————429 // |||||||| BInt Shifts |||||||||||||||||||||||||||||||||||||||||||||||||||||430 // ————————————————————————————————————————————————————————————————————————————————————————431 //432 //433 //434435 public static func << <T: BinaryInteger>(lhs: BInt, rhs: T) -> BInt {436 if rhs < 0 { return lhs >> rhs }437438 let limbs = lhs.limbs.shiftingUp(Int(rhs))439 let sign = lhs.isNegative() && !limbs.equalTo(0)440441 return BInt(sign: sign, limbs: limbs)442 }443444 public static func <<=< T: BinaryInteger > (lhs: inout BInt, rhs: T) {445 lhs.limbs.shiftUp(Int(rhs))446 }447448 public static func >> <T: BinaryInteger>(lhs: BInt, rhs: T) -> BInt {449 if rhs < 0 { return lhs << rhs }450 return BInt(sign: lhs.sign, limbs: lhs.limbs.shiftingDown(Int(rhs)))451 }452453 public static func >>= <T: BinaryInteger>(lhs: inout BInt, rhs: T) {454 lhs.limbs.shiftDown(Int(rhs))455 }456457 //458 //459460 // MARK: - BInt Bitwise AND461462 // ————————————————————————————————————————————————————————————————————————————————————————463 // |||||||| BInt BInt Bitwise AND |||||||||||||||||||||||||||||||||||||||||||464 // ————————————————————————————————————————————————————————————————————————————————————————465 //466 //467 //468469 /// Returns the result of performing a bitwise AND operation on the two given values.470 public static func & (lhs: BInt, rhs: BInt) -> BInt {471 var res: Limbs = [0]472473 for i in 0 ..< (64 * Swift.max(lhs.limbs.count, rhs.limbs.count)) {474 let newBit = lhs.limbs.getBit(at: i) && lhs.limbs.getBit(at: i)475 res.setBit(at: i, to: newBit)476 }477478 return BInt(sign: lhs.sign && rhs.sign, limbs: res)479 }480481 // static func &(lhs: Int, rhs: BInt) -> BInt482 // static func &(lhs: BInt, rhs: Int) -> BInt483484 /// Stores the result of performing a bitwise AND operation on the two given values in the485 /// left-hand-side variable.486 public static func &= (lhs: inout BInt, rhs: BInt) {487 let res = lhs & rhs488 lhs = res489 }490491 // static func &=(inout lhs: Int, rhs: BInt)492 // static func &=(inout lhs: BInt, rhs: Int)493494 //495 //496497 // MARK: - BInt Bitwise OR498499 // ————————————————————————————————————————————————————————————————————————————————————————500 // |||||||| BInt Bitwise OR |||||||||||||||||||||||||||||||||||||||||||||||||501 // ————————————————————————————————————————————————————————————————————————————————————————502 //503 //504 //505506 public static func | (lhs: BInt, rhs: BInt) -> BInt {507 var res: Limbs = [0]508509 for i in 0 ..< (64 * Swift.max(lhs.limbs.count, rhs.limbs.count)) {510 let newBit = lhs.limbs.getBit(at: i) || lhs.limbs.getBit(at: i)511 res.setBit(at: i, to: newBit)512 }513514 return BInt(sign: lhs.sign || rhs.sign, limbs: res)515 }516517 // static func |(lhs: Int, rhs: BInt) -> BInt518 // static func |(lhs: BInt, rhs: Int) -> BInt519 //520 public static func |= (lhs: inout BInt, rhs: BInt) {521 let res = lhs | rhs522 lhs = res523 }524525 // static func |=(inout lhs: Int, rhs: BInt)526 // static func |=(inout lhs: BInt, rhs: Int)527528 //529 //530531 // MARK: - BInt Bitwise OR532533 // ————————————————————————————————————————————————————————————————————————————————————————534 // |||||||| BInt Bitwise XOR ||||||||||||||||||||||||||||||||||||||||||||||||535 // ————————————————————————————————————————————————————————————————————————————————————————536 //537 //538 //539540 public static func ^ (lhs: BInt, rhs: BInt) -> BInt {541 var res: Limbs = [0]542543 for i in 0 ..< (64 * Swift.max(lhs.limbs.count, rhs.limbs.count)) {544 let newBit = lhs.limbs.getBit(at: i) != lhs.limbs.getBit(at: i)545 res.setBit(at: i, to: newBit)546 }547548 return BInt(sign: lhs.sign != rhs.sign, limbs: res)549 }550551 public static func ^= (lhs: inout BInt, rhs: BInt) {552 let res = lhs | rhs553 lhs = res554 }555556 //557 //558559 // MARK: - BInt Bitwise NOT560561 // ————————————————————————————————————————————————————————————————————————————————————————562 // |||||||| BInt Bitwise NOT ||||||||||||||||||||||||||||||||||||||||||||||||563 // ————————————————————————————————————————————————————————————————————————————————————————564 //565 //566 //567568 public static prefix func ~ (x: BInt) -> BInt {569 var res = x.limbs570 for i in 0 ..< (res.bitWidth) {571 res.setBit(at: i, to: !res.getBit(at: i))572 }573574 while res.last! == 0, res.count > 1 { res.removeLast() }575576 return BInt(sign: !x.sign, limbs: res)577 }578579 //580 //581582 // MARK: - BInt Addition583584 // ————————————————————————————————————————————————————————————————————————————————————————585 // |||||||| BInt Addition |||||||||||||||||||||||||||||||||||||||||||||||||||586 // ————————————————————————————————————————————————————————————————————————————————————————587 //588 //589 //590591 static prefix func + (x: BInt) -> BInt {592 x593 }594595 // Required by protocol Numeric596 public static func += (lhs: inout BInt, rhs: BInt) {597 if lhs.sign == rhs.sign {598 lhs.limbs.addLimbs(rhs.limbs)599 return600 }601602 let rhsIsMin = rhs.limbs.lessThan(lhs.limbs)603 lhs.limbs.difference(rhs.limbs)604 lhs.sign = (rhs.sign && !rhsIsMin) || (lhs.sign && rhsIsMin) // DNF minimization605606 if lhs.isZero() { lhs.sign = false }607 }608609 // Required by protocol Numeric610 public static func + (lhs: BInt, rhs: BInt) -> BInt {611 var lhs = lhs612 lhs += rhs613 return lhs614 }615616 static func + (lhs: Int, rhs: BInt) -> BInt { BInt(lhs) + rhs }617 static func + (lhs: BInt, rhs: Int) -> BInt { lhs + BInt(rhs) }618619 static func += (lhs: inout Int, rhs: BInt) { lhs += (BInt(lhs) + rhs).toInt()! }620 static func += (lhs: inout BInt, rhs: Int) { lhs += BInt(rhs) }621622 //623 //624625 // MARK: - BInt Negation626627 // ————————————————————————————————————————————————————————————————————————————————————————628 // |||||||| BInt Negation |||||||||||||||||||||||||||||||||||||||||||||||||||629 // ————————————————————————————————————————————————————————————————————————————————————————630 //631 //632 //633634 // Required by protocol SignedNumeric635 public mutating func negate() {636 if isNotZero() { sign = !sign }637 }638639 // Required by protocol SignedNumeric640 public static prefix func - (n: BInt) -> BInt {641 var n = n642 n.negate()643 return n644 }645646 //647 //648649 // MARK: - BInt Subtraction650651 // ————————————————————————————————————————————————————————————————————————————————————————652 // |||||||| BInt Subtraction ||||||||||||||||||||||||||||||||||||||||||||||||653 // ————————————————————————————————————————————————————————————————————————————————————————654 //655 //656 //657658 // Required by protocol Numeric659 public static func - (lhs: BInt, rhs: BInt) -> BInt {660 lhs + -rhs661 }662663 static func - (lhs: Int, rhs: BInt) -> BInt { BInt(lhs) - rhs }664 static func - (lhs: BInt, rhs: Int) -> BInt { lhs - BInt(rhs) }665666 // Required by protocol Numeric667 public static func -= (lhs: inout BInt, rhs: BInt) { lhs += -rhs }668 static func -= (lhs: inout Int, rhs: BInt) { lhs = (BInt(lhs) - rhs).toInt()! }669 static func -= (lhs: inout BInt, rhs: Int) { lhs -= BInt(rhs) }670671 //672 //673674 // MARK: - BInt Multiplication675676 // ————————————————————————————————————————————————————————————————————————————————————————677 // |||||||| BInt Multiplication |||||||||||||||||||||||||||||||||||||||||||||678 // ————————————————————————————————————————————————————————————————————————————————————————679 //680 //681 //682683 // Required by protocol Numeric684 public static func * (lhs: BInt, rhs: BInt) -> BInt {685 let sign = !(lhs.sign == rhs.sign || lhs.isZero() || rhs.isZero())686 return BInt(sign: sign, limbs: lhs.limbs.multiplyingBy(rhs.limbs))687 }688689 static func * (lhs: Int, rhs: BInt) -> BInt { BInt(lhs) * rhs }690 static func * (lhs: BInt, rhs: Int) -> BInt { lhs * BInt(rhs) }691692 // Required by protocol SignedNumeric693 public static func *= (lhs: inout BInt, rhs: BInt) { lhs = lhs * rhs }694 static func *= (lhs: inout Int, rhs: BInt) { lhs = (BInt(lhs) * rhs).toInt()! }695 static func *= (lhs: inout BInt, rhs: Int) { lhs = lhs * BInt(rhs) }696697 //698 //699700 // MARK: - BInt Exponentiation701702 // ————————————————————————————————————————————————————————————————————————————————————————703 // |||||||| BInt Exponentiation |||||||||||||||||||||||||||||||||||||||||||||704 // ————————————————————————————————————————————————————————————————————————————————————————705 //706 //707 //708709 public static func ** (lhs: BInt, rhs: Int) -> BInt {710 precondition(rhs >= 0, "BInts can't be exponentiated with exponents < 0")711 return BInt(sign: lhs.sign && (rhs % 2 != 0), limbs: lhs.limbs.exponentiating(rhs))712 }713714 func factorial() -> BInt {715 precondition(!sign, "Can't calculate the factorial of an negative number")716717 return BInt(limbs: Limbs.recursiveMul(0, Limb(toInt()!)))718 }719720 //721 //722723 // MARK: - BInt Division724725 // ————————————————————————————————————————————————————————————————————————————————————————726 // |||||||| BInt Division |||||||||||||||||||||||||||||||||||||||||||||||||||727 // ————————————————————————————————————————————————————————————————————————————————————————728 //729 //730 //731732 /// Returns the quotient and remainder of this value divided by the given value.733 public func quotientAndRemainder(dividingBy rhs: BInt) -> (quotient: BInt, remainder: BInt) {734 let limbRes = limbs.divMod(rhs.limbs)735 return (BInt(limbs: limbRes.quotient), BInt(limbs: limbRes.remainder))736 }737738 public static func / (lhs: BInt, rhs: BInt) -> BInt {739 let limbs = lhs.limbs.divMod(rhs.limbs).quotient740 let sign = (lhs.sign != rhs.sign) && !limbs.equalTo(0)741742 return BInt(sign: sign, limbs: limbs)743 }744745 static func / (lhs: Int, rhs: BInt) -> BInt { BInt(lhs) / rhs }746 static func / (lhs: BInt, rhs: Int) -> BInt { lhs / BInt(rhs) }747748 public static func /= (lhs: inout BInt, rhs: BInt) { lhs = lhs / rhs }749 static func /= (lhs: inout BInt, rhs: Int) { lhs = lhs / BInt(rhs) }750751 //752 //753754 // MARK: - BInt Modulus755756 // ————————————————————————————————————————————————————————————————————————————————————————757 // |||||||| BInt Modulus ||||||||||||||||||||||||||||||||||||||||||||||||||||758 // ————————————————————————————————————————————————————————————————————————————————————————759 //760 //761 //762763 public static func % (lhs: BInt, rhs: BInt) -> BInt {764 let limbs = lhs.limbs.divMod(rhs.limbs).remainder765 let sign = lhs.sign && !limbs.equalTo(0)766767 return BInt(sign: sign, limbs: limbs)768 }769770 static func % (lhs: Int, rhs: BInt) -> BInt { BInt(lhs) % rhs }771 static func % (lhs: BInt, rhs: Int) -> BInt { lhs % BInt(rhs) }772773 public static func %= (lhs: inout BInt, rhs: BInt) { lhs = lhs % rhs }774 static func %= (lhs: inout BInt, rhs: Int) { lhs = lhs % BInt(rhs) }775776 //777 //778779 // MARK: - BInt Comparing780781 // ————————————————————————————————————————————————————————————————————————————————————————782 // |||||||| BInt Comparing ||||||||||||||||||||||||||||||||||||||||||||||||||783 // ————————————————————————————————————————————————————————————————————————————————————————784 //785 //786 //787788 // Required by protocol Equatable789 public static func == (lhs: BInt, rhs: BInt) -> Bool {790 if lhs.sign != rhs.sign { return false }791 return lhs.limbs == rhs.limbs792 }793794 static func == <T: BinaryInteger>(lhs: BInt, rhs: T) -> Bool {795 if lhs.limbs.count != 1 { return false }796 return lhs.limbs[0] == rhs797 }798799 static func == <T: BinaryInteger>(lhs: T, rhs: BInt) -> Bool { rhs == lhs }800801 static func != (lhs: BInt, rhs: BInt) -> Bool {802 if lhs.sign != rhs.sign { return true }803 return lhs.limbs != rhs.limbs804 }805806 static func != <T: BinaryInteger>(lhs: BInt, rhs: T) -> Bool {807 if lhs.limbs.count != 1 { return true }808 return lhs.limbs[0] != rhs809 }810811 static func != <T: BinaryInteger>(lhs: T, rhs: BInt) -> Bool { rhs != lhs }812813 // Required by protocol Comparable814 public static func < (lhs: BInt, rhs: BInt) -> Bool {815 if lhs.sign != rhs.sign { return lhs.sign }816817 if lhs.sign { return rhs.limbs.lessThan(lhs.limbs) }818 return lhs.limbs.lessThan(rhs.limbs)819 }820821 static func < <T: BinaryInteger>(lhs: BInt, rhs: T) -> Bool {822 if lhs.sign != (rhs < 0) { return lhs.sign }823824 if lhs.sign {825 if lhs.limbs.count != 1 { return true }826 return rhs < lhs.limbs[0]827 } else {828 if lhs.limbs.count != 1 { return false }829 return lhs.limbs[0] < rhs830 }831 }832833 static func < (lhs: Int, rhs: BInt) -> Bool { BInt(lhs) < rhs }834 static func < (lhs: BInt, rhs: Int) -> Bool { lhs < BInt(rhs) }835836 // Required by protocol Comparable837 public static func > (lhs: BInt, rhs: BInt) -> Bool { rhs < lhs }838 static func > (lhs: Int, rhs: BInt) -> Bool { BInt(lhs) > rhs }839 static func > (lhs: BInt, rhs: Int) -> Bool { lhs > BInt(rhs) }840841 // Required by protocol Comparable842 public static func <= (lhs: BInt, rhs: BInt) -> Bool { !(rhs < lhs) }843 static func <= (lhs: Int, rhs: BInt) -> Bool { !(rhs < BInt(lhs)) }844 static func <= (lhs: BInt, rhs: Int) -> Bool { !(BInt(rhs) < lhs) }845846 // Required by protocol Comparable847 public static func >= (lhs: BInt, rhs: BInt) -> Bool { !(lhs < rhs) }848 static func >= (lhs: Int, rhs: BInt) -> Bool { !(BInt(lhs) < rhs) }849 static func >= (lhs: BInt, rhs: Int) -> Bool { !(lhs < BInt(rhs)) }850}851852//853//854855// MARK: - String operations856857// ————————————————————————————————————————————————————————————————————————————————————————————858// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||859// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||860// |||||||| String operations |||||||||||||||||||||||||||||||||||||||||||||||||||861// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||862// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||863// ————————————————————————————————————————————————————————————————————————————————————————————864//865//866//867868private extension String {869 // Splits the string into equally sized parts (exept for the last one).870 func split(_ count: Int) -> [String] {871 stride(from: 0, to: self.count, by: count).map { i -> String in872 let start = index(startIndex, offsetBy: i)873 let end = index(start, offsetBy: count, limitedBy: endIndex) ?? endIndex874 return String(self[start ..< end])875 }876 }877878 /// Assuming that this String represents a number in some base fromBase, return a String879 /// that contains the number converted to base toBase.880 func convertingBase(from: Int, toBase: Int) -> String {881 let chars: [Character] = [882 "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b",883 "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n",884 "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",885 "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L",886 "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X",887 "Y", "Z",888 ]889890 var res = ""891 var number = self892893 if number.hasPrefix("-") {894 res = "-"895 number.removeFirst()896 }897898 var sum = BInt(0)899 var multiplier = BInt(1)900901 for char in number.reversed() {902 if let digit = chars.firstIndex(of: char) {903 precondition(digit < from)904905 sum += digit * multiplier906 multiplier *= from907 } else {908 fatalError()909 }910 }911912 repeat {913 res.insert(chars[(sum % toBase).toInt()!], at: res.startIndex)914 sum /= BInt(toBase)915 } while sum != 0916917 return res918 }919}920921private let DigitBase: Digit = 1_000_000_000_000_000_000922private let DigitHalfBase: Digit = 1_000_000_000923private let DigitZeros = 18924925private extension Array where Element == Limb {926 var decimalRepresentation: String {927 // First, convert limbs to digits928 var digits: Digits = [0]929 var power: Digits = [1]930931 for limb in self {932 let digit = (limb >= DigitBase)933 ? [limb % DigitBase, limb / DigitBase]934 : [limb]935936 digits.addProductOfDigits(digit, power)937938 var nextPower: Digits = [0]939 nextPower.addProductOfDigits(power, [446_744_073_709_551_616, 18])940 power = nextPower941 }942943 // Then, convert digits to string944 var res = String(digits.last!)945946 if digits.count == 1 { return res }947948 for i in (0 ..< (digits.count - 1)).reversed() {949 let str = String(digits[i])950951 let leadingZeros = String(repeating: "0", count: DigitZeros - str.count)952953 res.append(leadingZeros.appending(str))954 }955956 return res957 }958}959960private extension Digit {961 mutating func addReportingOverflowDigit(_ addend: Digit) -> Bool {962 self = self &+ addend963 if self >= DigitBase { self -= DigitBase; return true }964 return false965 }966967 func multipliedFullWidthDigit(by multiplicand: Digit) -> (Digit, Digit) {968 let (lLo, lHi) = (self % DigitHalfBase, self / DigitHalfBase)969 let (rLo, rHi) = (multiplicand % DigitHalfBase, multiplicand / DigitHalfBase)970971 let K = (lHi * rLo) + (rHi * lLo)972973 var resLo = (lLo * rLo) + ((K % DigitHalfBase) * DigitHalfBase)974 var resHi = (lHi * rHi) + (K / DigitHalfBase)975976 if resLo >= DigitBase {977 resLo -= DigitBase978 resHi += 1979 }980981 return (resLo, resHi)982 }983}984985private extension Array where Element == Digit {986 mutating func addOneDigit(987 _ addend: Limb,988 padding paddingZeros: Int989 ) {990 let sc = count991992 if paddingZeros > sc { self += Digits(repeating: 0, count: paddingZeros &- sc) }993 if paddingZeros >= sc { append(addend); return }994995 // Now, i < sc996 var i = paddingZeros997998 let ovfl = self[i].addReportingOverflowDigit(addend)9991000 while ovfl {1001 i += 11002 if i == sc { append(1); return }1003 self[i] += 11004 if self[i] != DigitBase { return }1005 self[i] = 01006 }1007 }10081009 mutating func addTwoDigit(1010 _ addendLow: Limb,1011 _ addendHigh: Limb,1012 padding paddingZeros: Int1013 ) {1014 let sc = count10151016 if paddingZeros > sc { self += Digits(repeating: 0, count: paddingZeros &- sc) }1017 if paddingZeros >= sc { self += [addendLow, addendHigh]; return }10181019 // Now, i < sc1020 var i = paddingZeros1021 var newDigit: Digit10221023 let ovfl1 = self[i].addReportingOverflowDigit(addendLow)1024 i += 110251026 if i == sc {1027 newDigit = (addendHigh &+ (ovfl1 ? 1 : 0)) % DigitBase1028 append(newDigit)1029 if newDigit == 0 { append(1) }1030 return1031 }10321033 // Still, i < sc1034 var ovfl2 = self[i].addReportingOverflowDigit(addendHigh)1035 if ovfl1 {1036 self[i] += 11037 if self[i] == DigitBase { self[i] = 0; ovfl2 = true }1038 }10391040 while ovfl2 {1041 i += 11042 if i == sc { append(1); return }1043 self[i] += 11044 if self[i] != DigitBase { return }1045 self[i] = 01046 }1047 }10481049 mutating func addProductOfDigits(_ multiplier: Digits, _ multiplicand: Digits) {1050 let (mpc, mcc) = (multiplier.count, multiplicand.count)1051 reserveCapacity(mpc &+ mcc)10521053 var l, r, resLo, resHi: Digit10541055 for i in 0 ..< mpc {1056 l = multiplier[i]1057 if l == 0 { continue }10581059 for j in 0 ..< mcc {1060 r = multiplicand[j]1061 if r == 0 { continue }10621063 (resLo, resHi) = l.multipliedFullWidthDigit(by: r)10641065 if resHi == 0 {1066 addOneDigit(resLo, padding: i + j)1067 } else {1068 addTwoDigit(resLo, resHi, padding: i + j)1069 }1070 }1071 }1072 }1073}10741075//1076//10771078// MARK: - Limbs extension10791080// ————————————————————————————————————————————————————————————————————————————————————————————1081// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1082// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1083// |||||||| Limbs extension |||||||||||||||||||||||||||||||||||||||||||||||||||||1084// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1085// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1086// ————————————————————————————————————————————————————————————————————————————————————————————1087//1088//1089//10901091// Extension to Limbs type1092private extension Array where Element == Limb {1093 //1094 //10951096 // MARK: - Limbs bitlevel10971098 // ————————————————————————————————————————————————————————————————————————————————————————1099 // |||||||| Limbs bitlevel ||||||||||||||||||||||||||||||||||||||||||||||||||1100 // ————————————————————————————————————————————————————————————————————————————————————————1101 //1102 //1103 //11041105 /// Returns the number of bits that contribute to the represented number, ignoring all1106 /// leading zeros.1107 var bitWidth: Int {1108 var lastBits = 01109 var last = self.last!11101111 while last != 0 {1112 last >>= 11113 lastBits += 11114 }11151116 return ((count - 1) * 64) + lastBits1117 }11181119 /// Get bit i of limbs.1120 func getBit(at i: Int) -> Bool {1121 let limbIndex = Int(Limb(i) >> 6)11221123 if limbIndex >= count { return false }11241125 let bitIndex = Limb(i) & 0b11111111261127 return (self[limbIndex] & (1 << bitIndex)) != 01128 }11291130 /// Set bit i of limbs to b. b must be 0 for false, and everything else for true.1131 mutating func setBit(1132 at i: Int,1133 to bit: Bool1134 ) {1135 let limbIndex = Int(Limb(i) >> 6)11361137 if limbIndex >= count, !bit { return }11381139 let bitIndex = Limb(i) & 0b11111111401141 while limbIndex >= count { append(0) }11421143 if bit {1144 self[limbIndex] |= (1 << bitIndex)1145 } else {1146 self[limbIndex] &= ~(1 << bitIndex)1147 }1148 }11491150 //1151 //11521153 // MARK: - Limbs Shifting11541155 // ————————————————————————————————————————————————————————————————————————————————————————1156 // |||||||| Limbs Shifting ||||||||||||||||||||||||||||||||||||||||||||||||||1157 // ————————————————————————————————————————————————————————————————————————————————————————1158 //1159 //1160 //11611162 mutating func shiftUp(_ shift: Int) {1163 // No shifting is required in this case1164 if shift == 0 || equalTo(0) { return }11651166 let limbShifts = shift >> 61167 let bitShifts = Limb(shift) & 0x3F11681169 if bitShifts != 0 {1170 var previousCarry = Limb(0)1171 var carry = Limb(0)1172 var ele = Limb(0) // use variable to minimize array accesses11731174 for i in 0 ..< count {1175 ele = self[i]11761177 carry = ele >> (64 - bitShifts)11781179 ele <<= bitShifts1180 ele |= previousCarry // carry from last step1181 previousCarry = carry11821183 self[i] = ele1184 }11851186 if previousCarry != 0 { append(previousCarry) }1187 }11881189 if limbShifts != 0 {1190 insert(contentsOf: Limbs(repeating: 0, count: limbShifts), at: 0)1191 }1192 }11931194 func shiftingUp(_ shift: Int) -> Limbs {1195 var res = self1196 res.shiftUp(shift)1197 return res1198 }11991200 mutating func shiftDown(_ shift: Int) {1201 if shift == 0 || equalTo(0) { return }12021203 let limbShifts = shift >> 61204 let bitShifts = Limb(shift) & 0x3F12051206 if limbShifts >= count {1207 self = [0]1208 return1209 }12101211 removeSubrange(0 ..< limbShifts)12121213 if bitShifts != 0 {1214 var previousCarry = Limb(0)1215 var carry = Limb(0)1216 var ele = Limb(0) // use variable to minimize array accesses12171218 var i = count - 1 // use while for high performance1219 while i >= 0 {1220 ele = self[i]12211222 carry = ele << (64 - bitShifts)12231224 ele >>= bitShifts1225 ele |= previousCarry1226 previousCarry = carry12271228 self[i] = ele12291230 i -= 11231 }1232 }12331234 if last! == 0, count != 1 { removeLast() }1235 }12361237 func shiftingDown(_ shift: Int) -> Limbs {1238 var res = self1239 res.shiftDown(shift)1240 return res1241 }12421243 //1244 //12451246 // MARK: - Limbs Addition12471248 // ————————————————————————————————————————————————————————————————————————————————————————1249 // |||||||| Limbs Addition ||||||||||||||||||||||||||||||||||||||||||||||||||1250 // ————————————————————————————————————————————————————————————————————————————————————————1251 //1252 //1253 //12541255 mutating func addLimbs(_ addend: Limbs) {1256 let (sc, ac) = (count, addend.count)12571258 var (newLimb, ovfl) = (Limb(0), false)12591260 let minCount = Swift.min(sc, ac)12611262 var i = 01263 while i < minCount {1264 if ovfl {1265 (newLimb, ovfl) = self[i].addingReportingOverflow(addend[i])1266 newLimb = newLimb &+ 112671268 ovfl = ovfl || newLimb == 01269 } else {1270 (newLimb, ovfl) = self[i].addingReportingOverflow(addend[i])1271 }12721273 self[i] = newLimb1274 i += 11275 }12761277 while ovfl {1278 if i < sc {1279 if i < ac {1280 (newLimb, ovfl) = self[i].addingReportingOverflow(addend[i])1281 newLimb = newLimb &+ 11282 ovfl = ovfl || newLimb == 01283 } else {1284 (newLimb, ovfl) = self[i].addingReportingOverflow(1)1285 }12861287 self[i] = newLimb1288 } else {1289 if i < ac {1290 (newLimb, ovfl) = addend[i].addingReportingOverflow(1)1291 append(newLimb)1292 } else {1293 append(1)1294 return1295 }1296 }12971298 i += 11299 }13001301 if count < ac {1302 append(contentsOf: addend.suffix(from: i))1303 }1304 }13051306 /// Adding Limbs and returning result1307 func adding(_ addend: Limbs) -> Limbs {1308 var res = self1309 res.addLimbs(addend)1310 return res1311 }13121313 // CURRENTLY NOT USED:1314 /// Add the addend to Limbs, while using a padding at the lower end.1315 /// Every zero is a Limb, that means one padding zero equals 64 padding bits1316 mutating func addLimbs(1317 _ addend: Limbs,1318 padding paddingZeros: Int1319 ) {1320 let sc = count13211322 if paddingZeros > sc { self += Digits(repeating: 0, count: paddingZeros &- sc) }1323 if paddingZeros >= sc { self += addend; return }13241325 // Now, i < sc1326 let ac = addend.count &+ paddingZeros13271328 var (newLimb, ovfl) = (Limb(0), false)13291330 let minCount = Swift.min(sc, ac)13311332 var i = paddingZeros1333 while i < minCount {1334 if ovfl {1335 (newLimb, ovfl) = self[i].addingReportingOverflow(addend[i &- paddingZeros])1336 newLimb = newLimb &+ 11337 self[i] = newLimb1338 ovfl = ovfl || newLimb == 01339 } else {1340 (self[i], ovfl) = self[i].addingReportingOverflow(addend[i &- paddingZeros])1341 }13421343 i += 11344 }13451346 while ovfl {1347 if i < sc {1348 let adding = i < ac ? addend[i &- paddingZeros] &+ 1 : 11349 (self[i], ovfl) = self[i].addingReportingOverflow(adding)1350 ovfl = ovfl || adding == 01351 } else {1352 if i < ac {1353 (newLimb, ovfl) = addend[i &- paddingZeros].addingReportingOverflow(1)1354 append(newLimb)1355 } else {1356 append(1)1357 return1358 }1359 }13601361 i += 11362 }13631364 if count < ac {1365 append(contentsOf: addend.suffix(from: i &- paddingZeros))1366 }1367 }13681369 mutating func addLimb(1370 _ addend: Limb,1371 padding paddingZeros: Int1372 ) {1373 let sc = count13741375 if paddingZeros > sc { self += Digits(repeating: 0, count: paddingZeros &- sc) }1376 if paddingZeros >= sc { append(addend); return }13771378 // Now, i < lhc1379 var i = paddingZeros13801381 var ovfl: Bool1382 (self[i], ovfl) = self[i].addingReportingOverflow(addend)13831384 while ovfl {1385 i += 11386 if i == sc { append(1); return }1387 (self[i], ovfl) = self[i].addingReportingOverflow(1)1388 }1389 }13901391 /// Basically self.addLimb([addendLow, addendHigh], padding: paddingZeros), but faster1392 mutating func addTwoLimb(1393 _ addendLow: Limb,1394 _ addendHigh: Limb,1395 padding paddingZeros: Int1396 ) {1397 let sc = count13981399 if paddingZeros > sc { self += Digits(repeating: 0, count: paddingZeros &- sc) }1400 if paddingZeros >= sc { self += [addendLow, addendHigh]; return }14011402 // Now, i < sc1403 var i = paddingZeros1404 var newLimb: Limb14051406 var ovfl1: Bool1407 (self[i], ovfl1) = self[i].addingReportingOverflow(addendLow)1408 i += 114091410 if i == sc {1411 newLimb = addendHigh &+ (ovfl1 ? 1 : 0)1412 append(newLimb)1413 if newLimb == 0 { append(1) }1414 return1415 }14161417 // Still, i < sc1418 var ovfl2: Bool1419 (self[i], ovfl2) = self[i].addingReportingOverflow(addendHigh)14201421 if ovfl1 {1422 self[i] = self[i] &+ 11423 if self[i] == 0 { ovfl2 = true }1424 }14251426 while ovfl2 {1427 i += 11428 if i == sc { append(1); return }1429 (self[i], ovfl2) = self[i].addingReportingOverflow(1)1430 }1431 }14321433 //1434 //14351436 // MARK: - Limbs Subtraction14371438 // ————————————————————————————————————————————————————————————————————————————————————————1439 // |||||||| Limbs Subtraction ||||||||||||||||||||||||||||||||||||||||||||||||1440 // ————————————————————————————————————————————————————————————————————————————————————————1441 //1442 //1443 //14441445 /// Calculates difference between Limbs in left limb1446 mutating func difference(_ subtrahend: Limbs) {1447 var subtrahend = subtrahend1448 // swap to get difference1449 if lessThan(subtrahend) { swap(&self, &subtrahend) }14501451 let rhc = subtrahend.count1452 var ovfl = false14531454 var i = 014551456 // skip first zeros1457 while i < rhc, subtrahend[i] == 0 { i += 1 }14581459 while i < rhc {1460 if ovfl {1461 (self[i], ovfl) = self[i].subtractingReportingOverflow(subtrahend[i])1462 self[i] = self[i] &- 11463 ovfl = ovfl || self[i] == Limb.max1464 } else {1465 (self[i], ovfl) = self[i].subtractingReportingOverflow(subtrahend[i])1466 }14671468 i += 11469 }14701471 while ovfl {1472 if i >= count {1473 append(Limb.max)1474 break1475 }14761477 (self[i], ovfl) = self[i].subtractingReportingOverflow(1)14781479 i += 11480 }14811482 if count > 1, last! == 0 // cut excess zeros if required1483 {1484 var j = count - 21485 while j >= 1, self[j] == 0 { j -= 1 }14861487 removeSubrange((j + 1) ..< count)1488 }1489 }14901491 func differencing(_ subtrahend: Limbs) -> Limbs {1492 var res = self1493 res.difference(subtrahend)1494 return res1495 }14961497 //1498 //14991500 // MARK: - Limbs Multiplication15011502 // ————————————————————————————————————————————————————————————————————————————————————————1503 // |||||||| Limbs Multiplication |||||||||||||||||||||||||||||||||||||||||||||1504 // ————————————————————————————————————————————————————————————————————————————————————————1505 //1506 //1507 //15081509 mutating func addProductOf(1510 multiplier: Limbs,1511 multiplicand: Limbs1512 ) {1513 let (mpc, mcc) = (multiplier.count, multiplicand.count)15141515 reserveCapacity(mpc + mcc)15161517 // Minimize array subscript calls1518 var l, r, mulHi, mulLo: Limb15191520 for i in 0 ..< mpc {1521 l = multiplier[i]1522 if l == 0 { continue }15231524 for j in 0 ..< mcc {1525 r = multiplicand[j]1526 if r == 0 { continue }15271528 (mulHi, mulLo) = l.multipliedFullWidth(by: r)15291530 if mulHi != 0 {1531 addTwoLimb(mulLo, mulHi, padding: i + j)1532 } else {1533 addLimb(mulLo, padding: i + j)1534 }1535 }1536 }1537 }15381539 // Perform res += (lhs * r)1540 mutating func addProductOf(1541 multiplier: Limbs,1542 multiplicand: Limb1543 ) {1544 if multiplicand < 2 {1545 if multiplicand == 1 { addLimbs(multiplier) }1546 // If r == 0 then do nothing with res1547 return1548 }15491550 // Minimize array subscript calls1551 var l, mulHi, mulLo: Limb15521553 for i in 0 ..< multiplier.count {1554 l = multiplier[i]1555 if l == 0 { continue }15561557 (mulHi, mulLo) = l.multipliedFullWidth(by: multiplicand)15581559 if mulHi != 0 {1560 addTwoLimb(mulLo, mulHi, padding: i)1561 } else {1562 addLimb(mulLo, padding: i)1563 }1564 }1565 }15661567 func multiplyingBy(_ multiplicand: Limbs) -> Limbs {1568 var res: Limbs = [0]1569 res.addProductOf(multiplier: self, multiplicand: multiplicand)1570 return res1571 }15721573 func squared() -> Limbs {1574 var res: Limbs = [0]1575 res.reserveCapacity(2 * count)15761577 // Minimize array subscript calls1578 var l, r, mulHi, mulLo: Limb15791580 for i in 0 ..< count {1581 l = self[i]1582 if l == 0 { continue }15831584 for j in 0 ... i {1585 r = self[j]1586 if r == 0 { continue }15871588 (mulHi, mulLo) = l.multipliedFullWidth(by: r)15891590 if mulHi != 0 {1591 if i != j { res.addTwoLimb(mulLo, mulHi, padding: i + j) }1592 res.addTwoLimb(mulLo, mulHi, padding: i + j)1593 } else {1594 if i != j { res.addLimb(mulLo, padding: i + j) }1595 res.addLimb(mulLo, padding: i + j)1596 }1597 }1598 }15991600 return res1601 }16021603 //1604 //16051606 // MARK: - Limbs Exponentiation16071608 // ————————————————————————————————————————————————————————————————————————————————————————1609 // |||||||| Limbs Exponentiation ||||||||||||||||||||||||||||||||||||||||||||1610 // ————————————————————————————————————————————————————————————————————————————————————————1611 //1612 //1613 //16141615 // Exponentiation by squaring1616 func exponentiating(_ exponent: Int) -> Limbs {1617 if exponent == 0 { return [1] }1618 if exponent == 1 { return self }16191620 var base = self1621 var exponent = exponent1622 var y: Limbs = [1]16231624 while exponent > 1 {1625 if exponent & 1 != 0 { y = y.multiplyingBy(base) }16261627 base = base.squared()1628 exponent >>= 11629 }16301631 return base.multiplyingBy(y)1632 }16331634 /// Calculate (n + 1) * (n + 2) * ... * (k - 1) * k1635 static func recursiveMul(_ n: Limb, _ k: Limb) -> Limbs {1636 if n >= k - 1 { return [k] }16371638 let m = (n + k) >> 116391640 return recursiveMul(n, m).multiplyingBy(recursiveMul(m, k))1641 }16421643 func factorial(_ base: Int) -> BInt {1644 BInt(limbs: Limbs.recursiveMul(0, Limb(base)))1645 }16461647 //1648 //16491650 // MARK: - Limbs Division and Modulo16511652 // ————————————————————————————————————————————————————————————————————————————————————————1653 // |||||||| Limbs Division and Modulo |||||||||||||||||||||||||||||||||||||||1654 // ————————————————————————————————————————————————————————————————————————————————————————1655 //1656 //1657 //16581659 /// An O(n) division algorithm that returns quotient and remainder.1660 func divMod(_ divisor: Limbs) -> (quotient: Limbs, remainder: Limbs) {1661 precondition(!divisor.equalTo(0), "Division or Modulo by zero not allowed")16621663 if equalTo(0) { return ([0], [0]) }16641665 var (quotient, remainder): (Limbs, Limbs) = ([0], [0])1666 var (previousCarry, carry, ele): (Limb, Limb, Limb) = (0, 0, 0)16671668 // bits of lhs minus one bit1669 var i = (64 * (count - 1)) + Int(log2(Double(last!)))16701671 while i >= 0 {1672 // shift remainder by 1 to the left1673 for r in 0 ..< remainder.count {1674 ele = remainder[r]1675 carry = ele >> 631676 ele <<= 11677 ele |= previousCarry // carry from last step1678 previousCarry = carry1679 remainder[r] = ele1680 }1681 if previousCarry != 0 { remainder.append(previousCarry) }16821683 remainder.setBit(at: 0, to: getBit(at: i))16841685 if !remainder.lessThan(divisor) {1686 remainder.difference(divisor)1687 quotient.setBit(at: i, to: true)1688 }16891690 i -= 11691 }16921693 return (quotient, remainder)1694 }16951696 /// Division with limbs, result is floored to nearest whole number.1697 func dividing(_ divisor: Limbs) -> Limbs {1698 divMod(divisor).quotient1699 }17001701 /// Modulo with limbs, result is floored to nearest whole number.1702 func modulus(_ divisor: Limbs) -> Limbs {1703 divMod(divisor).remainder1704 }17051706 //1707 //17081709 // MARK: - Limbs Comparing17101711 // ————————————————————————————————————————————————————————————————————————————————————————1712 // |||||||| Limbs Comparing |||||||||||||||||||||||||||||||||||||||||||||||||1713 // ————————————————————————————————————————————————————————————————————————————————————————1714 //1715 //1716 //17171718 // Note:1719 // a < b iff b > a1720 // a <= b iff b >= a1721 // but:1722 // a < b iff !(a >= b)1723 // a <= b iff !(a > b)17241725 func lessThan(_ compare: Limbs) -> Bool {1726 let lhsc = count1727 let rhsc = compare.count17281729 if lhsc != rhsc {1730 return lhsc < rhsc1731 }17321733 var i = lhsc - 11734 while i >= 0 {1735 if self[i] != compare[i] { return self[i] < compare[i] }1736 i -= 11737 }17381739 return false // lhs == rhs1740 }17411742 func equalTo(_ compare: Limb) -> Bool {1743 self[0] == compare && count == 11744 }1745}17461747//1748//17491750// MARK: - Useful BInt math functions17511752// ————————————————————————————————————————————————————————————————————————————————————————————1753// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1754// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1755// |||||||| Useful BInt math functions ||||||||||||||||||||||||||||||||||||||||||1756// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1757// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1758// ————————————————————————————————————————————————————————————————————————————————————————————1759//1760//1761//17621763public class BIntMath {1764 /// Returns true iff (2 ** exp) - 1 is a mersenne prime.1765 static func isMersenne(_ exp: Int) -> Bool {1766 var mersenne = Limbs(repeating: Limb.max, count: exp >> 6)17671768 if (exp % 64) > 0 {1769 mersenne.append((Limb(1) << Limb(exp % 64)) - Limb(1))1770 }17711772 var res: Limbs = [4]17731774 for _ in 0 ..< (exp - 2) {1775 res = res.squared().differencing([2]).divMod(mersenne).remainder1776 }17771778 return res.equalTo(0)1779 }17801781 fileprivate static func euclid(_ a: Limbs, _ b: Limbs) -> Limbs {1782 var a = a1783 var b = b1784 while !b.equalTo(0) {1785 (a, b) = (b, a.divMod(b).remainder)1786 }17871788 return a1789 }17901791 fileprivate static func gcdFactors(_ lhs: Limbs, rhs: Limbs) -> (ax: Limbs, bx: Limbs) {1792 let gcd = euclid(lhs, rhs)1793 return (lhs.divMod(gcd).quotient, rhs.divMod(gcd).quotient)1794 }17951796 static func steinGcd(_ a: BInt, _ b: BInt) -> BInt {1797 if a.isZero() { return b }17981799 var a = a1800 var b = b1801 var k = 018021803 while a.isEven(), b.isEven() {1804 a = a >> 11805 b = b >> 11806 k += 11807 }18081809 var t = a.isOdd() ? -b : a18101811 while !t.isZero() {1812 while t.isEven() {1813 t = t >> 11814 }18151816 if t > 0 {1817 a = t1818 } else {1819 b = -t1820 }18211822 t = a - b1823 }18241825 return a << k1826 }18271828 static func gcd(_ a: BInt, _ b: BInt) -> BInt {1829 let limbRes = euclid(a.limbs, b.limbs)1830 return BInt(sign: a.sign && !limbRes.equalTo(0), limbs: limbRes)1831 }18321833 fileprivate static func lcmPositive(_ a: Limbs, _ b: Limbs) -> Limbs {1834 a.divMod(euclid(a, b)).quotient.multiplyingBy(b)1835 }18361837 static func lcm(_ a: BInt, _ b: BInt) -> BInt {1838 BInt(limbs: lcmPositive(a.limbs, b.limbs))1839 }18401841 static func fib(_ n: Int) -> BInt {1842 var a: Limbs = [0]1843 var b: Limbs = [1]1844 var t: Limbs18451846 for _ in 2 ... n {1847 t = b1848 b.addLimbs(a)1849 a = t1850 }18511852 return BInt(limbs: b)1853 }18541855 /// Order matters, repetition not allowed.1856 static func permutations(_ n: Int, _ k: Int) -> BInt {1857 // n! / (n-k)!1858 BInt(n).factorial() / BInt(n - k).factorial()1859 }18601861 /// Order matters, repetition allowed.1862 static func permutationsWithRepitition(_ n: Int, _ k: Int) -> BInt {1863 // n ** k1864 BInt(n) ** k1865 }18661867 /// Order does not matter, repetition not allowed.1868 static func combinations(_ n: Int, _ k: Int) -> BInt {1869 // (n + k - 1)! / (k! * (n - 1)!)1870 BInt(n + k - 1).factorial() / (BInt(k).factorial() * BInt(n - 1).factorial())1871 }18721873 /// Order does not matter, repetition allowed.1874 static func combinationsWithRepitition(_ n: Int, _ k: Int) -> BInt {1875 // n! / (k! * (n - k)!)1876 BInt(n).factorial() / (BInt(k).factorial() * BInt(n - k).factorial())1877 }18781879 static func randomBInt(bits n: Int) -> BInt {1880 let limbs = n >> 61881 let singleBits = n % 6418821883 var res = Limbs(repeating: 0, count: Int(limbs))18841885 for i in 0 ..< Int(limbs) {1886 res[i] = Limb(arc4random_uniform(UInt32.max)) |1887 (Limb(arc4random_uniform(UInt32.max)) << 32)1888 }18891890 if singleBits > 0 {1891 var last: Limb18921893 if singleBits < 32 {1894 last = Limb(arc4random_uniform(UInt32(2 ** singleBits)))1895 } else if singleBits == 32 {1896 last = Limb(arc4random_uniform(UInt32.max))1897 } else {1898 last = Limb(arc4random_uniform(UInt32.max)) |1899 (Limb(arc4random_uniform(UInt32(2 ** (singleBits - 32)))) << 32)1900 }19011902 res.append(last)1903 }19041905 return BInt(limbs: res)1906 }19071908 func isPrime(_ n: BInt) -> Bool {1909 if n <= 3 { return n > 1 }19101911 if ((n % 2) == 0) || ((n % 3) == 0) { return false }19121913 var i = 51914 while (i * i) <= n {1915 if ((n % i) == 0) || ((n % (i + 2)) == 0) {1916 return false1917 }1918 i += 61919 }1920 return true1921 }19221923 /// Quick exponentiation/modulo algorithm1924 /// FIXME: for security, this should use the constant-time Montgomery algorithm to thwart timing attacks1925 ///1926 /// - Parameters:1927 /// - b: base1928 /// - p: power1929 /// - m: modulus1930 /// - Returns: pow(b, p) % m1931 static func mod_exp(_ b: BInt, _ p: BInt, _ m: BInt) -> BInt {1932 precondition(m != 0, "modulus needs to be non-zero")1933 precondition(p >= 0, "exponent needs to be non-negative")1934 var base = b % m1935 var exponent = p1936 var result = BInt(1)1937 while exponent > 0 {1938 if exponent.limbs[0] % 2 != 0 {1939 result = result * base % m1940 }1941 exponent.limbs.shiftDown(1)1942 base *= base1943 base %= m1944 }1945 return result1946 }19471948 /// Non-negative modulo operation1949 ///1950 /// - Parameters:1951 /// - a: left hand side of the module operation1952 /// - m: modulus1953 /// - Returns: r := a % b such that 0 <= r < abs(m)1954 static func nnmod(_ a: BInt, _ m: BInt) -> BInt {1955 let r = a % m1956 guard r.isNegative() else { return r }1957 let p = m.isNegative() ? r - m : r + m1958 return p1959 }19601961 /// Convenience function combinding addition and non-negative modulo operations1962 ///1963 /// - Parameters:1964 /// - a: left hand side of the modulo addition1965 /// - b: right hand side of the modulo addition1966 /// - m: modulus1967 /// - Returns: nnmod(a + b, m)1968 static func mod_add(_ a: BInt, _ b: BInt, _ m: BInt) -> BInt {1969 nnmod(a + b, m)1970 }1971}19721973//1974//19751976// MARK: - BDouble19771978// ————————————————————————————————————————————————————————————————————————————————————————————1979// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1980// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1981// |||||||| BDouble |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1982// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1983// ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||1984// ————————————————————————————————————————————————————————————————————————————————————————————1985//1986//1987//19881989public struct BDouble:1990 ExpressibleByIntegerLiteral,1991 ExpressibleByFloatLiteral,1992 CustomStringConvertible,1993 SignedNumeric,1994 Comparable,1995 Hashable1996{1997 public static func -= (lhs: inout BDouble, rhs: BDouble) {1998 let res = lhs - rhs1999 lhs = res2000 }20012002 public static func += (lhs: inout BDouble, rhs: BDouble) {2003 let res = lhs + rhs2004 lhs = res2005 }20062007 public init?<T>(exactly _: T) where T: BinaryInteger {2008 self.init(0.0)2009 }20102011 public var magnitude: Double = 0.020122013 public typealias Magnitude = Double20142015 public static func *= (lhs: inout BDouble, rhs: BDouble) {2016 let res = lhs * rhs2017 lhs = res2018 }20192020 var sign = Bool()2021 var numerator = Limbs()2022 var denominator = Limbs()20232024 /**2025 Inits a BDouble with two Limbs as numerator and denominator20262027 - Parameters:2028 - numerator: The upper part of the fraction as Limbs2029 - denominator: The lower part of the fraction as Limbs20302031 Returns: A new BDouble2032 */20332034 init(sign: Bool, numerator: Limbs, denominator: Limbs) {2035 precondition(2036 !denominator.equalTo(0) && denominator != [] && numerator != [],2037 "Denominator can't be zero and limbs can't be []"2038 )20392040 self.sign = sign2041 self.numerator = numerator2042 self.denominator = denominator20432044 minimize()2045 }20462047 init(_ numerator: BInt, over denominator: BInt) {2048 self.init(2049 sign: numerator.sign != denominator.sign,2050 numerator: numerator.limbs,2051 denominator: denominator.limbs2052 )2053 }20542055 init(_ numerator: Int, over denominator: Int) {2056 self.init(2057 sign: (numerator < 0) != (denominator < 0),2058 numerator: [UInt64(abs(numerator))],2059 denominator: [UInt64(abs(denominator))]2060 )2061 }20622063 init(_ numerator: String, over denominator: String) {2064 self.init(BInt(numerator), over: BInt(denominator))2065 }20662067 public init(_ z: Int) {2068 self.init(z, over: 1)2069 }20702071 public init(_ d: Double) {2072 let nStr = String(d)20732074 if let exp = nStr.firstIndex(of: "e")?.encodedOffset {2075 let beforeExp = String(Array(nStr)[..<exp].filter { $0 != "." })2076 var afterExp = String(Array(nStr)[(exp + 1)...])2077 var sign = false20782079 if let neg = afterExp.firstIndex(of: "-")?.encodedOffset {2080 afterExp = String(Array(afterExp)[(neg + 1)...])2081 sign = true2082 }20832084 if sign {2085 let den = ["1"] + [Character](repeating: "0", count: Int(afterExp)!)2086 self.init(beforeExp, over: String(den))2087 return2088 } else {2089 let num = beforeExp + String([Character](repeating: "0", count: Int(afterExp)!))2090 self.init(num, over: "1")2091 return2092 }2093 }20942095 let i = nStr.firstIndex(of: ".")!.encodedOffset20962097 let beforePoint = String(Array(nStr)[..<i])2098 let afterPoint = String(Array(nStr)[(i + 1)...])20992100 if afterPoint == "0" {2101 self.init(beforePoint, over: "1")2102 } else {2103 let den = ["1"] + [Character](repeating: "0", count: afterPoint.count)2104 self.init(beforePoint + afterPoint, over: String(den))2105 }2106 }21072108 public init(integerLiteral value: Int) {2109 self.init(value)2110 }21112112 public init(floatLiteral value: Double) {2113 self.init(value)2114 }21152116 public var description: String {2117 var res = (sign ? "-" : "")21182119 res.append(numerator.decimalRepresentation)21202121 if denominator != [1] {2122 res.append("/".appending(denominator.decimalRepresentation))2123 }21242125 return res2126 }21272128 public func decimalExpansion(precisionAfterComma digits: Int) -> String {2129 let multiplier = [10].exponentiating(digits)21302131 let rawRes = numerator.multiplyingBy(multiplier).divMod(denominator).quotient21322133 var res = BInt(limbs: rawRes).description21342135 if digits > 0 {2136 res.insert(".", at: String.Index(encodedOffset: res.count - digits))2137 }21382139 return res2140 }21412142 public func hash(into hasher: inout Hasher) {2143 hasher.combine("\(sign)\(numerator)\(denominator)".hashValue)2144 }21452146 public func rawData() -> (sign: Bool, numerator: [UInt64], denominator: [UInt64]) {2147 return (sign, numerator, denominator)2148 }21492150 public func isPositive() -> Bool { !sign }2151 public func isNegative() -> Bool { sign }2152 public func isZero() -> Bool { numerator.equalTo(0) }21532154 public mutating func negate() {2155 if !isZero() {2156 sign = !sign2157 }2158 }21592160 public mutating func minimize() {2161 if numerator.equalTo(0) {2162 denominator = [1]2163 return2164 }21652166 let gcd = BIntMath.euclid(numerator, denominator)21672168 if gcd[0] > 1 || gcd.count > 1 {2169 numerator = numerator.divMod(gcd).quotient2170 denominator = denominator.divMod(gcd).quotient2171 }2172 }21732174 // public func sqrt(precision digits: Int) -> BDouble2175 // {2176 // // let self = v2177 // // Find x such that x*x=v <==> x = v/x2178//2179 // }2180}21812182/* \2183 /** \2184 /***\2185 /****\2186 /*****\2187 /******\2188 /*******\2189 /********\2190 /*********\2191 /**********\2192 //MARK: - BDouble Operators, needs to be more!2193 \**********/2194 \*********/2195 \********/2196 \*******/2197 \******/2198 \*****/2199 \****/2200 \***/2201 \**/2202 \ */22032204public func == (lhs: BDouble, rhs: BDouble) -> Bool {2205 if lhs.sign != rhs.sign { return false }2206 if lhs.numerator != rhs.numerator { return false }2207 if lhs.denominator != rhs.denominator { return false }22082209 return true2210}22112212public func != (lhs: BDouble, rhs: BDouble) -> Bool {2213 !(lhs == rhs)2214}22152216public func < (lhs: BDouble, rhs: BDouble) -> Bool {2217 if lhs.sign != rhs.sign { return lhs.sign }22182219 // more efficient than lcm version2220 let ad = lhs.numerator.multiplyingBy(rhs.denominator)2221 let bc = rhs.numerator.multiplyingBy(lhs.denominator)22222223 if lhs.sign { return bc.lessThan(ad) }22242225 return ad.lessThan(bc)2226}22272228public func > (lhs: BDouble, rhs: BDouble) -> Bool { rhs < lhs }2229public func <= (lhs: BDouble, rhs: BDouble) -> Bool { !(rhs < lhs) }2230public func >= (lhs: BDouble, rhs: BDouble) -> Bool { !(lhs < rhs) }22312232public func * (lhs: BDouble, rhs: BDouble) -> BDouble {2233 var res = BDouble(2234 sign: lhs.sign != rhs.sign,2235 numerator: lhs.numerator.multiplyingBy(rhs.numerator),2236 denominator: lhs.denominator.multiplyingBy(rhs.denominator)2237 )22382239 if res.isZero() { res.sign = false }2240 return res2241}22422243public func / (lhs: BDouble, rhs: BDouble) -> BDouble {2244 var res = BDouble(2245 sign: lhs.sign != rhs.sign,2246 numerator: lhs.numerator.multiplyingBy(rhs.denominator),2247 denominator: lhs.denominator.multiplyingBy(rhs.numerator)2248 )22492250 if res.isZero() { res.sign = false }2251 return res2252}22532254public func + (lhs: BDouble, rhs: BDouble) -> BDouble {2255 let ad = lhs.numerator.multiplyingBy(rhs.denominator)2256 let bc = rhs.numerator.multiplyingBy(lhs.denominator)2257 let bd = lhs.denominator.multiplyingBy(rhs.denominator)22582259 let resNumerator = BInt(sign: lhs.sign, limbs: ad) + BInt(sign: rhs.sign, limbs: bc)22602261 return BDouble(2262 sign: resNumerator.sign && !resNumerator.limbs.equalTo(0),2263 numerator: resNumerator.limbs,2264 denominator: bd2265 )2266}22672268public prefix func - (n: BDouble) -> BDouble {2269 var n = n2270 n.negate()2271 return n2272}22732274public func - (lhs: BDouble, rhs: BDouble) -> BDouble {2275 lhs + -rhs2276}22772278public func abs(_ lhs: BDouble) -> BDouble {2279 BDouble(2280 sign: false,2281 numerator: lhs.numerator,2282 denominator: lhs.denominator2283 )2284}2285