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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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:
Thanks for joining me in this little experiment. May you have an awesome day!