BigInt for swiftのソースコードを記述します。
まず下記のディレクトリ構造を用意してください。
Documents
｜ー swift ソースコード
｜＿ BigInt
｜__ Sources
｜＿BigInt
｜＿BigInt.swift
下記のコードをテキストエディタにコピー＆ペーストし、ファイル名を BigInt.swift に変更します。拡張子は .swift としてください。下記のソースコードはかなり長いです。次の作業は明日にします。
import Foundation
public struct BigInt: ExpressibleByStringLiteral, ExpressibleByIntegerLiteral, Comparable, CustomStringConvertible {
public var digits: [UInt8]
public var isNegative: Bool
// MARK: - 初期化
public init(digits: [UInt8], isNegative: Bool = false) {
var trimmed = digits
while trimmed.count > 1 && trimmed.last == 0 { trimmed.removeLast() }
self.digits = trimmed
self.isNegative = trimmed == [0] ? false : isNegative
}
public init(_ value: Int) {
var num = value
self.isNegative = num < 0
num = Swift.abs(num)
if num == 0 { self.digits = [0] }
else {
var arr: [UInt8] = []
while num > 0 {
arr.append(UInt8(num % 10))
num /= 10
}
self.digits = arr
}
}
public init(_ number: String) {
var str = number.trimmingCharacters(in: .whitespaces)
if str.hasPrefix("-") { isNegative = true; str.removeFirst() }
else { isNegative = false }
let significant = str.drop(while: { $0 == "0" })
let trimmed = String(significant)
if trimmed.isEmpty { digits = [0]; isNegative = false }
else { digits = trimmed.reversed().compactMap { UInt8(String($0)) } }
}
public init(stringLiteral value: StringLiteralType) { self.init(value) }
public init(integerLiteral value: Int) { self.init(value) }
// MARK: - 表示
public var description: String {
let num = digits.reversed().map { String($0) }.joined()
return (isNegative && num != "0" ? "-" : "") + num
}
// MARK: - 比較
public static func == (lhs: BigInt, rhs: BigInt) -> Bool {
lhs.isNegative == rhs.isNegative && lhs.digits == rhs.digits
}
public static func < (lhs: BigInt, rhs: BigInt) -> Bool {
if lhs.isNegative != rhs.isNegative { return lhs.isNegative }
if lhs.digits.count != rhs.digits.count {
return lhs.isNegative ? lhs.digits.count > rhs.digits.count : lhs.digits.count < rhs.digits.count
}
for (a, b) in zip(lhs.digits.reversed(), rhs.digits.reversed()) {
if a != b { return lhs.isNegative ? a > b : a < b }
}
return false
}
// MARK: - ユーティリティ
public var isEven: Bool { digits.first! % 2 == 0 }
public var isOdd: Bool { !isEven }
public func digitCount() -> Int { digits.count }
public func abs() -> BigInt { BigInt(digits: digits, isNegative: false) }
// MARK: - 演算子
public static func + (lhs: BigInt, rhs: BigInt) -> BigInt {
if lhs.isNegative == rhs.isNegative { return add(lhs, rhs, sign: lhs.isNegative) }
else {
if lhs.abs() >= rhs.abs() { return subtract(lhs, rhs, sign: lhs.isNegative) }
else { return subtract(rhs, lhs, sign: rhs.isNegative) }
}
}
public static func - (lhs: BigInt, rhs: BigInt) -> BigInt { lhs + BigInt(digits: rhs.digits, isNegative: !rhs.isNegative) }
public static func * (lhs: BigInt, rhs: BigInt) -> BigInt {
var result = [UInt8](repeating: 0, count: lhs.digits.count + rhs.digits.count)
for (i, a) in lhs.digits.enumerated() {
var carry = 0
for (j, b) in rhs.digits.enumerated() {
let sum = Int(result[i + j]) + Int(a) * Int(b) + carry
result[i + j] = UInt8(sum % 10)
carry = sum / 10
}
if carry > 0 { result[i + rhs.digits.count] += UInt8(carry) }
}
return BigInt(digits: result, isNegative: lhs.isNegative != rhs.isNegative)
}
public static func / (lhs: BigInt, rhs: BigInt) -> BigInt {
precondition(rhs != BigInt(0), "Division by zero")
if lhs.abs() < rhs.abs() { return BigInt(0) }
var quotient = [UInt8]()
var remainder = BigInt(0)
for digit in lhs.digits.reversed() {
remainder.digits.insert(digit, at: 0)
remainder = BigInt(digits: remainder.digits, isNegative: false)
var count = 0
while remainder >= rhs.abs() {
remainder = remainder - rhs.abs()
count += 1
}
quotient.append(UInt8(count))
}
quotient.reverse()
return BigInt(digits: quotient.reversed(), isNegative: lhs.isNegative != rhs.isNegative)
}
public static func % (lhs: BigInt, rhs: BigInt) -> BigInt { lhs - (lhs / rhs) * rhs }
// MARK: - 複合代入
public static func += (lhs: inout BigInt, rhs: BigInt) { lhs = lhs + rhs }
public static func -= (lhs: inout BigInt, rhs: BigInt) { lhs = lhs - rhs }
public static func *= (lhs: inout BigInt, rhs: BigInt) { lhs = lhs * rhs }
public static func /= (lhs: inout BigInt, rhs: BigInt) { lhs = lhs / rhs }
// MARK: - 単項マイナス
public static prefix func - (value: BigInt) -> BigInt { BigInt(digits: value.digits, isNegative: !value.isNegative) }
// MARK: - 内部加減算
private static func add(_ lhs: BigInt, _ rhs: BigInt, sign: Bool) -> BigInt {
let maxLength = max(lhs.digits.count, rhs.digits.count)
var result = [UInt8]()
var carry = 0
for i in 0..<maxLength {
let sum = (i < lhs.digits.count ? Int(lhs.digits[i]) : 0) + (i < rhs.digits.count ? Int(rhs.digits[i]) : 0) + carry
result.append(UInt8(sum % 10))
carry = sum / 10
}
if carry > 0 { result.append(UInt8(carry)) }
return BigInt(digits: result, isNegative: sign)
}
private static func subtract(_ lhs: BigInt, _ rhs: BigInt, sign: Bool) -> BigInt {
var result = [UInt8](), borrow = 0
for i in 0..<lhs.digits.count {
var diff = Int(lhs.digits[i]) - (i < rhs.digits.count ? Int(rhs.digits[i]) : 0) - borrow
if diff < 0 { diff += 10; borrow = 1 } else { borrow = 0 }
result.append(UInt8(diff))
}
return BigInt(digits: result, isNegative: sign)
}
}
// MARK: - 数学関数
public extension BigInt {
static func pow(_ base: BigInt, _ exp: Int) -> BigInt {
guard exp >= 0 else { fatalError("Negative exponent") }
var result = BigInt(1), baseCopy = base, exponent = exp
while exponent > 0 {
if exponent % 2 == 1 { result *= baseCopy }
baseCopy *= baseCopy
exponent /= 2
}
return result
}
static func modPow(_ base: BigInt, _ exp: BigInt, _ mod: BigInt) -> BigInt {
var result = BigInt(1), baseCopy = base % mod, exponent = exp
while exponent > BigInt(0) {
if exponent.isOdd { result = (result * baseCopy) % mod }
baseCopy = (baseCopy * baseCopy) % mod
exponent /= BigInt(2)
}
return result
}
static func factorial(_ n: Int) -> BigInt {
guard n >= 0 else { fatalError("Negative factorial") }
var result: BigInt = 1
for i in 2...n { result *= BigInt(i) }
return result
}
static func gcd(_ a: BigInt, _ b: BigInt) -> BigInt {
var x = a.abs(), y = b.abs()
while y != BigInt(0) { let t = y; y = x % y; x = t }
return x
}
static func lcm(_ a: BigInt, _ b: BigInt) -> BigInt {
(a.abs() / gcd(a, b)) * b.abs()
}
static func sqrt(of n: BigInt) -> BigInt {
precondition(!n.isNegative, "Negative sqrt")
if n == BigInt(0) || n == BigInt(1) { return n }
var low = BigInt(0), high = n, ans = BigInt(0)
while low <= high {
let mid = (low + high) / BigInt(2), sq = mid * mid
if sq == n { return mid }
else if sq < n { ans = mid; low = mid + BigInt(1) }
else { high = mid - BigInt(1) }
}
return ans
}
static func isPerfectSquare(_ n: BigInt) -> Bool {
let r = sqrt(of: n)
return r * r == n
}
static func isProbablePrime(_ n: BigInt, k: Int = 5) -> Bool {
if n <= BigInt(1) { return false }
if n == BigInt(2) || n == BigInt(3) { return true }
if n.isEven { return false }
var d = n - BigInt(1), r = 0
while d.isEven { d /= BigInt(2); r += 1 }
for _ in 0..<k {
let a = BigInt.random(in: BigInt(2)...(n - BigInt(2)))
var x = modPow(a, d, n)
if x == BigInt(1) || x == n - BigInt(1) { continue }
var cont = false
for _ in 1..<r {
x = modPow(x, 2, n)
if x == n - BigInt(1) { cont = true; break }
}
if !cont { return false }
}
return true
}
}
// MARK: - 乱数
public extension BigInt {
static func random(digits count: Int) -> BigInt {
precondition(count > 0)
var result: [UInt8] = [UInt8(Int.random(in: 1...9))]
for _ in 1..<count { result.append(UInt8(Int.random(in: 0...9))) }
return BigInt(digits: result.reversed())
}
static func random(in range: ClosedRange<BigInt>) -> BigInt {
var diff = range.upperBound - range.lowerBound
var rand = BigInt.random(digits: diff.digitCount())
while rand > diff { rand = BigInt.random(digits: diff.digitCount()) }
return range.lowerBound + rand
}
}
// MARK: - 表示 & 変換
public extension BigInt {
func formatted() -> String {
let str = self.digits.reversed().map(String.init).joined()
var result = "", count = 0
for char in str.reversed() {
if count > 0 && count % 3 == 0 { result.append(",") }
result.append(char); count += 1
}
return String(result.reversed())
}
func toHexString() -> String {
if self == BigInt(0) { return "0" }
let hexChars = Array("0123456789ABCDEF")
var value = self.isNegative ? -self : self
var result = ""
while value > BigInt(0) {
let (q, r) = value.divmod(BigInt(16))
result.append(hexChars[r.toIntSafe()])
value = q
}
return (isNegative ? "-" : "") + String(result.reversed())
}
static func fromHexString(_ hex: String) -> BigInt {
var str = hex.uppercased()
var isNeg = false
if str.hasPrefix("-") { isNeg = true; str.removeFirst() }
var result = BigInt(0)
for char in str {
result *= BigInt(16)
if let val = "0123456789ABCDEF".firstIndex(of: char)?.utf16Offset(in: "0123456789ABCDEF") {
result += BigInt(val)
}
}
return isNeg ? -result : result
}
func toBinaryString() -> String {
if self == BigInt(0) { return "0" }
var value = self.isNegative ? -self : self
var result = ""
while value > BigInt(0) {
let (q, r) = value.divmod(BigInt(2))
result.append(r.toIntSafe() == 1 ? "1" : "0")
value = q
}
return (isNegative ? "-" : "") + String(result.reversed())
}
func toBaseString(_ base: Int) -> String {
precondition((2...36).contains(base), "Base must be 2...36")
let chars = Array("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ")
if self == BigInt(0) { return "0" }
var value = self.isNegative ? -self : self
var result = ""
while value > BigInt(0) {
let (q, r) = value.divmod(BigInt(base))
result.append(chars[r.toIntSafe()])
value = q
}
return (isNegative ? "-" : "") + String(result.reversed())
}
func divmod(_ divisor: BigInt) -> (BigInt, BigInt) {
precondition(divisor != BigInt(0), "Division by zero")
var quotient = BigInt(0)
var remainder = BigInt(0)
for digit in self.digits.reversed() {
remainder.digits.insert(digit, at: 0)
remainder = BigInt(digits: remainder.digits, isNegative: false)
var count = 0
while remainder >= divisor {
remainder = remainder - divisor
count += 1
}
quotient.digits.append(UInt8(count))
}
while quotient.digits.count > 1 && quotient.digits.last == 0 {
quotient.digits.removeLast()
}
return (BigInt(digits: quotient.digits.reversed()), remainder)
}
private func toIntSafe() -> Int {
var value = 0
for digit in digits.reversed() { value = value * 10 + Int(digit) }
return value
}
}
