Beyond 128-bit integers

December 24, 2017

General Coding, Reference

Comments Off on Beyond 128-bit integers


I just finished a post related to the top range of integer values that are supported by Swift.

https://kenb.us/big-integers

The conclusion was that we can use the Decimal type to hold integer values with up to nearly 128 bits. That’s an impressively large number.

It’s hard to imagine a case where you would require both a larger number and precision at the least significant figures. However, it does make an interesting exercise so let’s give it a shot.

Long Form

We know that there aren’t any built-in types for Swift that will handle arbitrarily large integers. However, Swift does offer some containers that can hold an arbitrary amount of data. Of these Array and String are probably the easiest to manipulate. Further, Array can be typed to Int which sounds quite like what we need.

If you think about how you would do arithmetic on paper, you do the operation one digit at a time. We can replicate that with Array<UInt>. We can store values like so.

let value: Array<UInt> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] // 1234567890

That’s great, now we can hold arbitrarily large numbers. Although, you might ask, what good is that? So let’s add some basic arithmetic.

extension Array where Element == UInt {
    private func reduceOverflow() -> [UInt] {
        var corrected = reversed().reduce(into: ([UInt](),0)) { result, value in
            var value = value + result.1
            result.1 = 0
            if value > 9 {
                result.1 = value / 10
                value -= (value / 10) * 10
            }
            result.0.append(value)
        }
        if corrected.1 > 0 { corrected.0.append(corrected.1) }
        return corrected.0.reversed()
    }
    
    private func resizedWithLeadingZeros(count: Int) -> [UInt] {
        var a = Array(repeating: 0, count: Swift.max(0,count-self.count))
        a.append(contentsOf: self)
        return a
    }
    
    func adding(_ rhs: [UInt]) -> [UInt] {
        let lhs = self.resizedWithLeadingZeros(count: rhs.count)
        let rhs = rhs.resizedWithLeadingZeros(count: lhs.count)
        
        return zip(lhs, rhs)
            .map { $0 + $1 }
            .reduceOverflow()
    }
    
    func multiplying(_ rhs: [UInt]) -> [UInt] {
        var result = Array(repeatElement(0, count: count+rhs.count-1))
        (0..<count).forEach { i in
            (0..<rhs.count).forEach { j in
                let k = i + j
                result[k] += self[i] * rhs[j]
            }
        }
        return result.reduceOverflow()
    }
}

As you can see performing addition and multiplication isn’t too difficult. Let’s try out some numbers.

[5,5,5,5,5].adding([5,5,5,5,5]) // [1, 1, 1, 1, 1, 0]
[2,2,2,2,2].adding([2,2,2,2,2]) // [4, 4, 4, 4, 4]
[9].adding([9,9]) // [1, 0, 8]
[9,9,9].adding([9,9]) // [1, 0, 9, 8]

[5,5,5,5,5].multiplying([5,5,5,5,5]) // [3, 0, 8, 6, 3, 5, 8, 0, 2, 5] = 3,086,358,025
[2,2,2,2,2].multiplying([2,2,2,2,2]) // [4, 9, 3, 8, 1, 7, 2, 8, 4] = 493,817,284
[9].multiplying([9,9]) // [8, 9, 1] = 891
[9,9,9].multiplying([9,9]) // [9, 8, 9, 0, 1] = 98901
// calculate 2^128
var Two128 = [2]
for _ in 1..<128 {
    Two128 = Two128.multiplying([2])
}
print(Two128) // [3, 4, 0, 2, 8, 2, 3, 6, 6, 9, 2, 0, 9, 3, 8, 4, 6, 3, 4, 6, 3, 3, 7, 4, 6, 0, 7, 4, 3, 1, 7, 6, 8, 2, 1, 1, 4, 5, 6]

So this is actually pretty cool, we can do some basic math on arbitrarily large numbers!

There’s just one big problem here. It’s not easy to read. The inputs and outputs are in an ugly format. Maybe Strings can help after all.

extension String {
    func adding(_ rhs: String) -> String {
        return self.map { UInt(String($0))! }
            .adding(rhs.map({ UInt(String($0))! }))
            .map { String($0) }
            .joined(separator: "")
    }
    
    func multiplying(_ rhs: String) -> String {
        return self.map { UInt(String($0))! }
            .multiplying(rhs.map({ UInt(String($0))! }))
            .map { String($0) }
            .joined(separator: "")
    }
}

This is just converting the String into an Array<UInt>, leveraging what we just wrote, then converting the result back to String. Let’s see what the usage looks like.

"55555".adding("55555") // "111110"
"22222".adding("22222") // "44444"
"9".adding("99") // "108"
"999".adding("99") // "1098"

"55555".multiplying("55555") // "3086358025"
"22222".multiplying("22222") // "493817284"
"9".multiplying("99") // "891"
"999".multiplying("99") // "98901"

var Two128 = "2"
for _ in 1..<128 {
    Two128 = Two128.multiplying("2")
}
print(Two128) // 340282366920938463463374607431768211456

This is so much easier to read! You could even add a little more code to remove and add commas to make it even easier to read these humungous numbers.

Again, this is a novelty, just a fun thought experiment to see how we can push through some boundaries. This is painfully slow and extremely limited in application.

 

Integer arrays

In the above scenario, each element of the array represents a digit of a base 10 number. That is to say, each element can be in the range [0, 9]. However, each element is represented by a 32-bit integer. Even if we used the smallest type UInt8 that’s a lot of wasted bytes.

Let’s instead let our elements represent the “digits” of a base UInt64.max system. Then to get a 256-bit integer value we can write something like this.

let value: Array<UInt64> = [0, 0, 1, 0] // 1 * (UInt64.max + 1)

With this, we can easily go beyond the initial 64-bit integer limit.

The big question is, how are we going to perform mathematical operations on this? By default, if we go beyond the limit of the type the result is a crash. Of course, we can use “&” to ignore the overflow issue, but what we really want to know is if an operation results in an overflow so that we can handle it. There are actually a few methods (depending on the operation) that tell us exactly that.

// add and multiply reporting overflow
func addingReportingOverflow(_ rhs: Self) -> (partialValue: Self, overflow: Bool)
func multipliedReportingOverflow(by rhs: Self) -> (partialValue: Self, overflow: Bool)

There are several more of these for different operations. They can be found at https://developer.apple.com/documentation/swift/fixedwidthinteger

Now how do we actually use that? Let’s see how we can do some addition. For simplicity let’s make the assumption that each side of the equation is the same size and we won’t handle overflow beyond our initially chosen size.

extension Array where Element == UInt64 {
    func adding(_ rhs: Array) -> [UInt64] {
        var carry = false
        return zip(self, rhs).reversed()
            .map { (lhs, rhs) in
                lhs.addingReportingOverflow(rhs)
            }
            .map { result, didOverflow in
                if carry {
                    let (carryResult, carryDidOverflow) = result.addingReportingOverflow(1)
                    carry = didOverflow || carryDidOverflow
                    return carryResult
                }
                else {
                    carry = didOverflow
                    return result
                }
            }
            .reversed()
    }
}

Addition is fairly easy, if there’s an overflow just carry a 1 to the next unit. Keep in mind that the carried 1 could create it’s own overflow.

var value: Array<UInt64> = [0, 0, 0, UInt64.max] // initialize 256-bit number with a value of UInt64.max
value.adding([0, 0, 0, 256]) // add 256 to UInt64.max
// result [0, 0, 1, 255]

var value: Array<UInt64> = [0, UInt64.max, UInt64.max, UInt64.max]
value.adding([0, 0, 0, 1]) // add 1
// result [1, 0, 0, 0]

That’s exactly what we should expect! We could extend this to do multiplication, division, subtraction etc.

At this point I’d also move away from implementing this in an array extension. That was nice as a proof of concept but this should be wrapped up in it’s own type with the details hidden to the user.

Luckily, some very smart people have already written math libraries which can handle this for you and so much more. For example, check out the BigInt library

My hope is that I got you to look at numbers a little differently. Thanks for reading!



Subscribe via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.





Swift Tweets