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 ║
int64 range. You may have seen these numbers somewhere before. 🌚
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
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.
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.
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
We want to be able to do something like this:
Alright so let’s add the function to our struct and alter it a bit to make it more to our liking.
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.
A bit cleaner, but lets go all the way and define our own
All you need to do is add this line somewhere outside our BigInt struct.
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.
This is what it should all look like once you’re done.
BigInts together should be as simple as:
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.