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!
ArrayIntIntegerLarge valueString
Beyond 128-bit integers
December 24, 2017
General Coding, Reference
Comments Off on Beyond 128-bit integers
Ken Boreham
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.
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.
As you can see performing addition and multiplication isn’t too difficult. Let’s try out some numbers.
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.
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.
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.
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.
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.
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.
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!
Share this:
ArrayIntIntegerLarge valueString