Big Int

Big Int.swift

import Swift

struct BigInt {
	var value : [UInt64] = [0]
}

extension BigInt : CustomDebugStringConvertible {
	var debugDescription : String {
		return String(value)
	}
}

extension BigInt : Equatable { }

func ==(x: BigInt, y: BigInt) -> Bool {
	return x.value == y.value
}

extension BigInt : Comparable { }

func <(lhs: BigInt, rhs: BigInt) -> Bool {
	if lhs.value.count < rhs.value.count {
		return true
	}
	
	if lhs.value.count > rhs.value.count {
		return false
	}
	
	return lhs.value.last < rhs.value.last
}

BigInt() < BigInt()

struct ZipWithDefault<T: CollectionType, U: CollectionType where T.Generator.Element == U.Generator.Element> : SequenceType {
    typealias Element = (T.Generator.Element, U.Generator.Element)
    
    let s1 : T
    let s2 : U
    let defaultValue : T.Generator.Element
    
    func generate() -> AnyGenerator<Element> {
        var g1 = s1.generate()
        var g2 = s2.generate()
        
        return anyGenerator({ () -> Element? in
            let next = (g1.next(), g2.next())
            switch next {
            case (nil, nil): return nil
            default: return (next.0 ?? self.defaultValue, next.1 ?? self.defaultValue)
            }
        })
    }
}

func +(lhs: BigInt, rhs: BigInt) -> BigInt {
    let zippedBigInts = ZipWithDefault(s1: lhs.value, s2: rhs.value, defaultValue: 0)
    
    let intermediate = zippedBigInts.map(UInt64.addWithOverflow)
    let f = intermediate.reduce(([], false)) { (acc: ([UInt64], incomingOverflow: Bool), elem: (val: UInt64, overflow: Bool)) in
        if acc.incomingOverflow {
            let adjustedSum = UInt64.addWithOverflow(elem.val, 1)
            
            return (acc.0 + [adjustedSum.0], elem.overflow || adjustedSum.overflow)
            
        } else {
            return (acc.0 + [elem.val], elem.overflow)
        }
    }
    
    if f.1 {
        return BigInt(value: f.0 + [1])
    } else {
        return BigInt(value: f.0)
    }
}

print(
	BigInt() + BigInt() == BigInt()
)

extension BigInt : ArrayLiteralConvertible {
    init(arrayLiteral elements: UInt64...) {
        for e in elements {
            value.append(e)
        }
    }
}

let zero = BigInt(value: [0])
let one = BigInt(value: [1])

print(
	zero + one == one
)

print(
	BigInt(value: [UInt64.max]) + one == BigInt(value: [0, 1])
)

print(
    BigInt(value: [0, 1]) + one == BigInt(value: [1, 1])
)

print(
    BigInt(value: [UInt64.max, UInt64.max]) + one == BigInt(value: [0, 0, 1])
)

extension BigInt : ForwardIndexType {
    func successor() -> BigInt {
        return self + BigInt(value: [1])
    }
}