Working with very large numbers in Swift —  BigInt

Numbers are fundamental to every programming language in existence. Depending on the systems architecture that you’re programming for, there are restrictions the size of the numbers it can support.

Engineers writing code for an 8-bit system such as the NES, only had access to integers between -128 to 127 (signed). However with some tricks, such as breaking the numbers into smaller pieces, any cpu is capable of working with numbers of any size.

This method of breaking the numbers up can be performed at the hardware level, but there are some software tricks we can use too.

The following table describes some common available integer sizes.

╔═══════╦═════════════════════════════════════════════════════════╗
║ Type  ║                      Output Range                       ║
╠═══════╬═════════════════════════════════════════════════════════╣
║ int8  ║ -128 to 127                                             ║
║ int16 ║ -32,768 to 32,767                                       ║
║ int32 ║ -2,147,483,648 to 2,147,483,647                         ║
║ int64 ║ -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 ║
╚═══════╩═════════════════════════════════════════════════════════╝

Notice the int64 range. You may have seen these numbers somewhere before. 🌚 Back when Game Center was a thing...

Using strings to represent numbers

What we’re going to do is create our own number type. A type that can handle operations on obscenely large numbers, and we’re going to use Strings to do this.

Currently there’s no way to add, subtract, multiply or divide integers with strings directly in Swift. So we need to construct our own type to handle this.

We’ll start out with a new struct and call it BigInt.

struct BigInt {  
    var value: String
}

We’ll start out with a variable called value. There's also no need to create an initializer because Swift will provide this for us.

Calculations

Our BigInt is pretty useless without being able to perform a few calculations. So lets jump right into something a little tricky like multiplication.

We’ll use the same method you did when learning how to multiply larger numbers on paper in school.

We start by splitting both values into arrays, where a single character is mapped to each index. The arrays are then reversed to make things a little easier. Finally we loop over both arrays, and multiply the single digits found at each index with each other.

func multiply(left: String, right: String) -> String {
    var leftCharacterArray = left.characters.reversed().map { Int(String($0))! }
    var rightCharacterArray = right.characters.reversed().map { Int(String($0))! }
    var result = [Int](repeating: 0, count: leftCharacterArray.count+rightCharacterArray.count)
    
    for leftIndex in 0..<leftCharacterArray.count {
        for rightIndex in 0..<rightCharacterArray.count {
            
            let resultIndex = leftIndex + rightIndex
            
            result[resultIndex] = leftCharacterArray[leftIndex] * rightCharacterArray[rightIndex] + (resultIndex >= result.count ? 0 : result[resultIndex])
            if result[resultIndex] > 9 {
                result[resultIndex + 1] = (result[resultIndex] / 10) + (resultIndex+1 >= result.count ? 0 : result[resultIndex + 1])
                result[resultIndex] -= (result[resultIndex] / 10) * 10
            }
            
        }
        
    }
    
    result = Array(result.reversed())
    return result.map { String($0) }.joined(separator: "")
}

multiply(left: "2844858348834855723432430", right: "134534523453454540998798789")

There’s a lot going on here, you be fine to copy and paste it into a playground if you want a closer look at what’s going on.

This method isn’t the most performant or safest piece of code.

There’s also nothing stopping someone from entering a character that isn’t a number, which would of course result in a crash.

Now this is just a stand alone function. Which really could just be added anywhere within our project and do a good job as it is. However, we want something that will work with our BigInt type.

We want to be able to do something like this:

let int1 = BigInt("10")  
let int2 = BigInt("5")  
let product = int1 * int2  

BigInt

Alright so let’s add the function to our struct and alter it a bit to make it more to our liking.

struct BigInt {

    var value: String

    func multiply(right: String) -> String {
        // We'll change this line to use value
        var leftCharacterArray = value.characters.reversed().map { Int(String($0))! }
        var rightCharacterArray = right.characters.reversed().map { Int(String($0))! }
    ...


// Now we can do this
let int1 = BigInt(value: "34")  
let int2 = BigInt(value: "45")  
let product = int1.multiply(int2.value)

Close but still doesn’t give us what we’re after.

Let’s remove the String requirement and pass our BigInt right into our multiply function.

func multiply(right: BigInt) -> BigInt {

    var a1 = value.characters.reversed().map { Int(String($0))! }
    var a2 = right.value.characters.reversed().map { Int(String($0))! }
    ...
    ...

    // And change the last line
    return BigInt(value: result.map { String($0) }.joined(separator: ""))
}

// Our calculation now looks like this.
let int1 = BigInt(value: "34")  
let int2 = BigInt(value: "45")  
let product = int1.multiply(int2)  

A bit cleaner, but lets go all the way and define our own * operator.

Operator Overloading *

All you need to do is add this line somewhere outside our BigInt struct.

func * (left: BigInt, right: BigInt) -> BigInt { return left.multiply(right) }

Operator overloading allows you to change how existing operators behave with types that both already exist (Int, Float, String), and any custom types you have created. In this example, we’re letting our program know how to multiply two BigInt types the same way we would any other primitive number type.

Finally

This is what it should all look like once you’re done.

import UIKit
import Foundation

struct BigInt {
    
    var value: String
    
    func multiply(right: BigInt) -> BigInt {
        var leftCharacterArray = value.characters.reversed().map { Int(String($0))! }
        var rightCharacterArray = right.value.characters.reversed().map { Int(String($0))! }
        var result = [Int](repeating: 0, count: leftCharacterArray.count+rightCharacterArray.count)
        
        for leftIndex in 0..<leftCharacterArray.count {
            for rightIndex in 0..<rightCharacterArray.count {
                
                let resultIndex = leftIndex + rightIndex
                
                result[resultIndex] = leftCharacterArray[leftIndex] * rightCharacterArray[rightIndex] + (resultIndex >= result.count ? 0 : result[resultIndex])
                if result[resultIndex] > 9 {
                    result[resultIndex + 1] = (result[resultIndex] / 10) + (resultIndex+1 >= result.count ? 0 : result[resultIndex + 1])
                    result[resultIndex] -= (result[resultIndex] / 10) * 10
                }
                
            }
            
        }
        
        result = Array(result.reversed())

        while result.count > 0 && result.first == 0 {
            result.removeFirst(1)
        }
        
        return  BigInt(value: result.map { String($0) }.joined(separator: ""))
    }
    
}

func * (left: BigInt, right: BigInt) -> BigInt { return left.multiply(right: right) }

Multiplying two BigInts together should be as simple as:

let int1 = BigInt(value: "34757377374573285823949593499549646311234")  
let int2 = BigInt(value: "45123498348958923845838948528381283721377123454345")  
let product = int1 * int2  
// result: 1568374460575699918065222772187576926314538959488859994856690985365041943440429553059611730

There you have it. It’s not perfect, but it does give you an idea of how we can work around some of the hardware restrictions we face as developers.