Summing Really Big Numbers In Rust
Tags: rust, arithmetic, mathematics
Published: 2021-10-08 08:26:25

# Intro

Whilst trying to generate the Fibonacci sequence I quickly discovered that I needed to sum numbers that get really big really quickly, especially if I don’t want to be capped to just the lower few numbers in the sequence. This sent me down a bit of a rabbit hole to see if I can implement some way to do this without having too much of a time penalty.

# Addition

Generating the Fibonacci sequence just requires addition so we’ll focus on that. I will state however that the way I did it might not be the best nor the most efficient but it does work and pretty well I might add. To get things started we’ll create a new function called __**addition**__. The function will take two parameters, both of type __**String**__ and it will return a __**String**__.

``` Rust
fn addition(num1: String, num2: String) -> String {

}
```

The approach we’ll go with is one that you should have learned back in primary school, although it's not quite as easy to translate it to programming. To start off with we’ll need a few mutable variables.

```Rust
fn addition(num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();
}
```

__**additive_string**__ will be the end result that we pass back. __**overflow**__ will keep track of the number that we need to add to the next pass. __**number1**__ and __**number2**__ are __**vectors**__ of __**chars**__ so that we can __**pop()**__ off the numbers as we sum them. Next, we need to figure out which number is larger so that we can use that as the reference for our for-loop.

```Rust
fn addition(&self, num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();

  // Get the length of the longest number.
  let longest_len = number1.len().max(number2.len());
}
```

With the setup completed, we can finally move onto the for-loop that will do all the heavy lifting for us. We __**pop()**__ the last character off of each __**vector**__ of __**chars**__ and convert it to a __**u8**__. We use a __**u8**__ because the number will be between 0 and 9 and it won’t be a negative number, so we don’t really need much more than that. We will only concern ourselves with positive numbers since we’re just doing addition, but in theory, we could have written a subtraction function but since you don’t really need to do subtractions to get the Fibonacci sequence, we’ll just say that you can try it out yourself. Our function will error out if the user tried to pass anything other than numbers.

```Rust
fn addition(&self, num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();

  // Get the length of the longest number.
  let longest_len = number1.len().max(number2.len());

  // Do simple primary school addition with each value in the number.
  for _ in 0..longest_len {
    // Convert the first number to u8.
    let first: u8 = match number1.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };

    // Convert the second number to u8.
    let second: u8 = match number2.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };
  }        
}
```

Notice that the __**pop()**__ function returns an __**`Option<char>`**__ so we use a match statement to convert the character to a __**u8**__ and then return it or return 0 if the __**pop()**__ function return __**None**__. This will ensure that we can still add numbers that are different in length. Now in theory we should have two __**u8**__’s which we can just add together like you normally would. We also add the __**overflow**__ value and then convert the __**sum**__ to a __**String**__ so that we can add it to the __**additive_string**__ variable. We reverse the order of the numbers so that we can __**pop()**__ the bigger number off and set the __**overflow**__ variable equal to it.

```Rust
fn addition(&self, num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();

  // Get the length of the longest number.
  let longest_len = number1.len().max(number2.len());

  // Do simple primary school addition with each value in the number.
  for _ in 0..longest_len {
    // Convert the first number to u8.
    let first: u8 = match number1.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };

    // Convert the second number to u8.
    let second: u8 = match number2.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };
    
    // Add the two numbers together and turn it into a string.
    let mut sum: String = (first + second + overflow)
      .to_string()
      .chars()
      .rev()
      .collect();
  }        
}
```

We can make an assumption that the sum of the three numbers will never be bigger than two digits. If it is two digits then we have overflow and should __**pop()**__ the last number off, otherwise overflow should be set to 0.

```Rust
fn addition(&self, num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();

  // Get the length of the longest number.
  let longest_len = number1.len().max(number2.len());

  // Do simple primary school addition with each value in the number.
  for _ in 0..longest_len {
    // Convert the first number to u8.
    let first: u8 = match number1.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };

    // Convert the second number to u8.
    let second: u8 = match number2.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };
    
    // Add the two numbers together and turn it into a string.
    let mut sum: String = (first + second + overflow)
      .to_string()
      .chars()
      .rev()
      .collect();
    
    // If the string has more than 1 number in it, it means we have to pass
    // the overflow value onto the next round of addition.
    overflow = if sum.len() > 1 {
      sum.pop().unwrap().to_string().parse().unwrap()
    } else {
      // Set the overflow back to 0 just in case.
      0
    };
  }        
}
```

Lastly, we just add the __**sum**__ to the __**additive_string**__ although note because we are adding the number to the back of the __**String**__ the number is currently in reverse order, but we’ll deal with that when we return the result.

```Rust
fn addition(&self, num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();

  // Get the length of the longest number.
  let longest_len = number1.len().max(number2.len());

  // Do simple primary school addition with each value in the number.
  for _ in 0..longest_len {
    // Convert the first number to u8.
    let first: u8 = match number1.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };

    // Convert the second number to u8.
    let second: u8 = match number2.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };
    
    // Add the two numbers together and turn it into a string.
    let mut sum: String = (first + second + overflow)
      .to_string()
      .chars()
      .rev()
      .collect();
    
    // If the string has more than 1 number in it, it means we have to pass
    // the overflow value onto the next round of addition.
    overflow = if sum.len() > 1 {
      sum.pop().unwrap().to_string().parse().unwrap()
    } else {
      // Set the overflow back to 0 just in case.
      0
    };
    
    // Add the sum of the two values to the string.
    additive_string.push(*sum.chars().collect::<Vec<char>>().first().unwrap());
  }        
}
```

After running through the loop there might still be an __**overflow**__ that we need to add to the end of __**additive_string**__.

```Rust
fn addition(&self, num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();

  // Get the length of the longest number.
  let longest_len = number1.len().max(number2.len());

  // Do simple primary school addition with each value in the number.
  for _ in 0..longest_len {
    // Convert the first number to u8.
    let first: u8 = match number1.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };

    // Convert the second number to u8.
    let second: u8 = match number2.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };
    
    // Add the two numbers together and turn it into a string.
    let mut sum: String = (first + second + overflow)
      .to_string()
      .chars()
      .rev()
      .collect();
    
    // If the string has more than 1 number in it, it means we have to pass
    // the overflow value onto the next round of addition.
    overflow = if sum.len() > 1 {
      sum.pop().unwrap().to_string().parse().unwrap()
    } else {
      // Set the overflow back to 0 just in case.
      0
    };
    
    // Add the sum of the two values to the string.
    additive_string.push(*sum.chars().collect::<Vec<char>>().first().unwrap());
  }     
  
  // Finally if there was a leftover overflow value, add it to the string.
  if overflow > 0 {
    additive_string.push(
      *overflow
        .to_string()
        .chars()
        .collect::<Vec<char>>()
        .first()
        .unwrap(),
    );
  }
}
```

In theory, we should now have the new number, but there is just one problem, it’s backward, so we should just reverse the order of the __**chars**__ and then return the __**String**__.

```Rust
fn addition(&self, num1: String, num2: String) -> String {
  let mut additive_string = String::new();
  let mut overflow = 0;
  let mut number1: Vec<char> = num1.chars().collect();
  let mut number2: Vec<char> = num2.chars().collect();

  // Get the length of the longest number.
  let longest_len = number1.len().max(number2.len());

  // Do simple primary school addition with each value in the number.
  for _ in 0..longest_len {
    // Convert the first number to u8.
    let first: u8 = match number1.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };

    // Convert the second number to u8.
    let second: u8 = match number2.pop() {
      Some(character) => character.to_string().parse().unwrap(),
      None => 0,
    };
    
    // Add the two numbers together and turn it into a string.
    let mut sum: String = (first + second + overflow)
      .to_string()
      .chars()
      .rev()
      .collect();
    
    // If the string has more than 1 number in it, it means we have to pass
    // the overflow value onto the next round of addition.
    overflow = if sum.len() > 1 {
      sum.pop().unwrap().to_string().parse().unwrap()
    } else {
      // Set the overflow back to 0 just in case.
      0
    };
    
    // Add the sum of the two values to the string.
    additive_string.push(*sum.chars().collect::<Vec<char>>().first().unwrap());
  }     
  
  // Finally if there was a leftover overflow value, add it to the string.
  if overflow > 0 {
    additive_string.push(
      *overflow
        .to_string()
        .chars()
        .collect::<Vec<char>>()
        .first()
        .unwrap(),
    );
  }
    
  // Reverse the order of the string and return it.
  additive_string.chars().rev().collect::<String>()
}
```

That’s it! We now have the means of adding two really big numbers with one another, and in theory, we can also multiply two really big numbers, we’ll just need to add a for-loop around the __**addition()**__ function, but again, we’ll just say that is up to you the reader. The same strategy can be used for all mathematical operations although I am not quite ready to try and write the function for division, subtraction, nor square roots.

# Proof of Concept

Before you go, I thought it would only be fair of me to show you that the function actually works and that it can work with really big numbers. Here is the __**main()**__ function where we can show the addition in action. We’ll start with some small numbers and then work our way up to summing __**u128::MAX**__ with itself.

```Rust
fn main() {
  println!("1 + 1 = {}", addition(1.to_string(), 1.to_string()));

  println!("10 + 10 = {}", addition(10.to_string(), 10.to_string()));

  println!("12345 + 789101112 = {}", addition(12345.to_string(), 789101112.to_string()));

  println!("{} + {} = {}", u16::MAX, u16::MAX, addition(u16::MAX.to_string(), u16::MAX.to_string()));

  println!("{} + {} = {}", u32::MAX, u32::MAX, addition(u32::MAX.to_string(), u32::MAX.to_string()));

  println!("{} + {} = {}", u64::MAX, u64::MAX, addition(u64::MAX.to_string(), u64::MAX.to_string()));

  println!("{} + {} = {}", u128::MAX, u128::MAX, addition(u128::MAX.to_string(), u128::MAX.to_string()));
}
```

Here is the output from my terminal after running the program:

![Capture.PNG](https://cdn.steemitimages.com/DQmQUv7m7rQ2uqE8NCCXPUCQK3BGJi9x3SuAuG18QxQdS7N/Capture.PNG)

Thanks for joining me in this little experiment. May you have an awesome day!