Long Addition & The Somethingness of Nothingness

Challenge Accepted

Recently, I completed a Kata on CodeWars. The challenge was to accurately add two big integers together and return the sum as a string. The catch was there could be no abstraction in the return; the return needed to be an untouched mantissa. Also, using the bigInt() method, was not permitted.

If You’re Like, ‘Yup'

If the paragraph above didn't make your eyes glaze over, you can skip the next section, The Groundwork, and learn about how I solved the challenge in the simplest, most essential way I could imagine. If you are feeling real scrappy, try and solve the challenge before reading this article!

If You’re Like ‘..Whaat?'

If I've about lost you with mantissas, bigInts, and number abstractions, oh my, please read on for a quick summary of what the first paragraph is about.

The Groundwork

JavaScript can hit about 16 digits in a number before things get unpredictable. The maximum integer (MAX_SAFE_INTEGER) it can handle is 9007199254740991. Numbers of that size are called 'bigInts' or big integers (fancy term, I know). Once JS hits numbers beyond the max_safe_integer, things get weird. I won't get into all the ways in which it gets weird, because chances are you don't care a whole bunch; but if you do care a whole bunch it’s better to research the matter in the MDN Docs, because they get all kinds of into it.

For our purposes, all we need to know is that after the mantissa hits the max_safe_integer value, things start to get Alice and Wonderland. But developers need to work with big numbers all the time: think about how many millions and millions of users use a social media platform... Think of all those users with all those troll comments, and troll comments on troll comments on troll comments... going all the way back to the early 2000s. If that doesn't inspire you (it probably doesn't) think of the massive amounts of data an organization like NASA needs to keep for all it's maps of celestial bodies and distances (ah, that's so much nicer! The internet, like a bridge, wasn't just made for trolls after all!).

Engineers and developers often need to handle numbers beyond the conceptual powers of present day humanity. But hardware still has its limitations (for now), so numbers are contained to 52 bits.

Interestingly, number datatypes are limited to 52 bits, but string datatypes are not limited in that way; not by character count. A string datatype is a set of quotes and anything you put between them. So "hello world!" Is a string. "2525" is a string. "$&%(@)" is a string. "" is even a string.

Strings can be really long: They can be many, many, many paragraphs long. No problem. Now, if you think on that for a minute you can maybe sense some potential for handling big numbers with strings.

“I had no systematic way of learning but proceeded like a quilt maker, a patch of knowledge here a patch there but lovingly knitted. I would hungrily devour the intellectual scraps and leftovers of the learned.” ― Ishmael Reed, Mumbo Jumbo

If you imagine each letter, space, and special character in the string above to be digits, well, that is one super long number, no? Well, great! Easy-peasy, right? Let's just add "4959603037485948" to "48458593020548473948239483"! They are strings, so what the heck is the problem and why are we talking about any of this?

Strings as datatypes have different rules of operation than numbers, of course. If you add 2 + 2, you will get 4. BUT if you add "2" + "2", you will get... "22". Whoa, what-the-what? Your math teachers won't like that!

Math applies to numbers, but concatenation applies to strings. That means if you add two strings together it's sort of just like when you are writing. “Hello" + “ World!" Will get you "Hello World!".

So we can store giant mantissa's in a string, but we can't mess around with them with math unless we convert them to numbers. As soon as we convert them to numbers, though, they become abstracted: 1244839e33, for example. That is the mantissa in the front, followed by the e for exponent, and the exponent value -- AKA the big integer interpreted in scientific notation. Not what we want if we want to avoid abstraction.

The task in the CodeWars challenge is to find a way to add two big integers together and return the sum as the non-abstracted, full mantissa in string form.

The Method

I solved the challenge in my favorite way of approaching any algorithm: I try to take the challenge apart to its most simple aspects and build the whole thing from the ground up. This doesn't always get the sleekest solution or use the newest, coolest methods, but as a junior developer it has so many wonderful benefits.

First, it helps me do push ups with my left brain. Breaking up a complex challenge into simpler, smaller parts, is good for the brain and helps find potential problems the algorithm will need to address. Second, it keeps me focused on the essential behavior of JavaScript (how it thinks, how it approaches tasks, how it prioritizes its jobs, etc.), which improves my coding skills all around.

There are more reasons I like to approach algorithms this way, but those are the top two reasons. It's fun, too, because once I get something working, I can refactor it later to be fancier: maybe more DRY (Do Not Repeat Yourself), maybe easier to read, maybe replace some manual loops or functions with some built in methods to reduce lines of code, or make it more performant. You will find that I’m refactoring my solution even as I write this blog! Real time!

I know it's easy to get caught up in using the built in methods and trying to write algorithms that do a ton on a single line of a bunch of chained methods and maybe even utilize advanced mathematics. It looks cool to see advanced developers do that sort of stuff. We all could watch Jet Li for hours, but you might not want to watch the neighbor kid do straight punches (Choku-zuki) for hours on end. But that neighbor kid needs to do straight punches for hours on end before moving to more advanced karate. Daniel (in the Karate Kid) needed to paint some fences before he could even learn some basic moves, and that’s real.

A junior developer can aim for DRY, cool looking code, but on the road to mastery we all need to write a million, million lines of code. We need to get the reflex work down, the patience; all that repetition leads to seeing patterns and learning the way JS behaves and how you build a relationship with it. Writing cool looking code will come with time and mastery, but it's wasting energy to try to get there ahead of real experience.

And I'll be honest: initially, while spinning my wheels on this challenge, I definitely tried to just slice the 'e' out of the abstracted return with the slice() method and bash some weird numbers in there with some whacky for loops and a concatenation or two. Obviously that effort passed no tests, but that wasn't my goal. It is fun to code ridiculous things when one is short on solutions. Sometimes you even find new knowledge when you're messing around with weird lines of code. Play is so important!

I think of it like sketching to prepare for the big painting to come. You might be painting a realistic landscape of some waterlilies on commission, but in your sketchbook it's always safe to draw Godzilla's head peaking out from under the lilies, or eating them all up. The IDE (integrated development environment) is a place to play and try things out as much as it is a place to deliver clean, DRY, performant, readable code.

The Solution

My idea was to think about the challenge in its most essential and basic math: long addition. As kids, when we do long addition we are already doing all those complex computations like JS does: the numbers we write with our #2 pencils are as much strings as anything, and as much numbers, too. I solved the first test by adding two big integers together by hand. Next, I reflected on how my brain worked through the math and how that process translated on paper. Lastly, I reverse engineered the process of doing long addition by hand into something the computer could understand and duplicate (a ton faster!).

Below is the solution I arrived at, which passed all the tests for all kinds of numbers, small to enormous. I will break down each part of the algorithm and explain my process and what is going on in the equation.

function add(a, b) {

let shortNumber = “”;

let carryOver = 0;

let sumArray = [];

if (a.length > 14 || b.length > 14) {

let aArr = a.split("").reverse();

let bArr = b.split(“").reverse();

let columnSum = "";

if (b.length > a.length) {

for (let i = 0; i < b.length - a.length; i++) {

shortNumber += "0";

}

shortNumber += a;

aArr = shortNumber.split("").reverse();

} else {

for (let i = 0; i < a.length - b.length; i++) {

shortNumber += "0";

}

shortNumber += b;

bArr = shortNumber.split("").reverse();

}

for (let i = 0; i < aArr.length; i++) {

columnSum = (Number(aArr[i]) + Number(bArr[i]) + carryOver).toString();

if (columnSum.length > 1) {

sumArray.push(columnSum[1]);

carryOver = 1;

} else {

sumArray.push(columnSum[0]);

carryOver = 0;

}

}

if (carryOver === 1) {

sumArray.push(carryOver);

}

return sumArray.reverse().join("");

}

return (Number(a) + Number(b)).toString();

}

To keep things speedy, we don't want to waste time doing long addition on any parameters that are less than 15 characters (not really big integers) because we can just do normal math. if you look, you'll see the only thing going on in this algorithm is

return (Number(a) + Number(b)).toString();

That's if the length of the a and b arguments are less than 14 characters long. There is still some cool stuff happening, there, though. We're using the Number() method to convert a and b to numbers (the challenge in CodeWars gives you two string arguments), which JS knows to do before it adds them together with the addition operator (+). Notice all that bit is wrapped in brackets, too, so JS knows it needs to complete that part of the line first (like in algebra) before proceeding to the next bit, which is a chained method: toString(). You can guess, I'm sure, that toString() will make our sum back into a string again, as the challenge requires.

The Fun Stuff

if (a.length > 14 || b.length > 14) {

Here is where we do all the fun stuff. Technically, JS can handle numbers with more than 14 characters, but I felt it was better to err on the side of caution as we approach the really big numbers. If either of the argument strings (a, b) are longer than 14 characters, we create two mutable variables that will do some important work with:

let aArr = a.split("").reverse();

let bArr = b.split(“").reverse();

The names, ‘aArr’ and ‘bArr’ just mean ‘a array’ and ‘b array’; when we use the split method, the string will be automatically returned as a new array. That array will contain each letter from the source string: an array of tiny strings. I.e.: [“1”, “2”, “3”] instead of “123”. As soon as we have that array, the reverse method is chained, so now our array will be: [“3”, “2”, “1”].

We split the string up so we can access each individual number, but why reverse it? Without further directions, JavaScript is going to want to add the numbers first to last, but that won’t work in long addition: we need to add the number furthest to the left and work our way to the right for the math to work. Now with aArr and bArr, we have a and b almost ready for some math. There is just one more step to prepare the arrays — something that is implicit when we add by hand, but not implicit for JavaScript.

If a or b is shorter, when JS goes to add the longer number to the shorter and nothing is there, it will return NaN (AKA ‘Not a Number’).

When we do the addition by hand, we imagine there are zeros there under those over hanging numbers. Our go-to is to imagine a somethingness to a nothingness, whereas JS will not imagine at all. It will perceive only a nothingness to a nothingness, and you can’t add nothingness to a value. So it will concretely tell you that nothingness is ‘Not a Number’, which is true on so many levels.

Zero is not nothingness: it is an absence of a value, which is still something. JS can handle zeros, but it can’t make assumptions about that which is not there like humans can.

To prevent getting a NaN returned, which would ruin our long addition fun times, we need to give JS zeros to orient itself too. The two arrays need to be the same length, and the shorter array will need zeros at it’s beginning to make that happen. I chose to handle concatenating the shortest argument at the string level, before it goes to the array, because I felt it was more readable and reduced the need for reassignments and array manipulations on the aArr and bArr arrays.

I set up three global variable:

let shortNumber = “”;

let carryOver = 0;

let sumArray = [];

Though, as I’m working on this blog post, I’m thinking I’d rather that shortNumber variable be scoped inside the first if-statement of the algorithm. There really isn’t reason it needs to be global as it’s only used temporarily to tidy up whichever argument is shortest. If a variable has no reason to be global, best practices dictates that it should be scoped instead. The carryOver and sumArray variables DO need to be global because, as you’ll find out, I need to access them outside the scope of the if-statement that wraps all the fun code.

Anyway, here we add the zeros to whichever string is shortest by setting them to the shortNumber variable:

for (let i = 0; i < b.length - a.length; i++) {

shortNumber += "0";

}

shortNumber += a;

aArr = shortNumber.split("").reverse();

} else {

for (let i = 0; i < a.length - b.length; i++) {

shortNumber += "0";

}

shortNumber += b;

bArr = shortNumber.split("").reverse();

}

One of the above for-loops will trigger, depending on which string is longer. Inside either for-loop, for each iteration, AKA each time the code runs, AKA for each character that the string is shorter than the other, shortNumber will be concatenated with a zero (+= “0”).

After the correct number of zeros have been added, the shorter string will be concatenated to that string of zeros (shortNumber += a). Then I reassign aArr or bArr appropriately.

Now we need another for-loop that will continue until we reach aArr or bArr’s length (remember, they are both equal in length at this point). While we are in the loop we are going to assign to columnSum the sum of each aligning value (plus the carryOver if there is one). If the sum is a double digit (10 or greater), we push the first digit to the sumArray (so if the sum is 14, we push the 4 to sumArray), and set the carryOver to 1. The carryOver can never be more than 1, because there are no two single digit numbers you can add that will get past 19 -- even with the carry over -- cool, huh?

for (let i = 0; i < aArr.length; i++) {

columnSum = (Number(aArr[i]) + Number(bArr[i]) + carryOver).toString();

if (columnSum.length > 1) {

sumArray.push(columnSum[1]);

carryOver = 1;

} else {

sumArray.push(columnSum[0]);

carryOver = 0;

}

}

If the sum of the two values is just a single digit, we push it to the sumArray and set the carryOver back to 0 in case it had previously set to 1.

We are almost there! Just two things left to do: once the for-loop closes we need to check if there is anything left in the carryOver. If so, we need to push that to the sumArray.

if (carryOver === 1) {

sumArray.push(carryOver);

}

Now remember that we added everything in reverse order to the sumArray. Again, this is because it is how we do long addition: adding the numbers in reverse so the cumulation of their value reaches up to the higher values. It is also much less complex and performant to push to an array and not use the unset() method to add entries to the start of an array.

The unset() method can be real handy for certain things, but it’s important to know that it’s behavior is to loop through the entire array each time it fires — so that it can reset the index values of everything in the array. We do not want to do that many loops! The push() method just sets the new array entry to the end, which doesn’t require any looping or reassigning of indexes. In that way, we can just do one reverse at the end, which only adds one extra for-loop (hidden in the built in reverse() method), one time for the sumArray. We can do that right in our final return:

return sumArray.reverse().join("");

The join() method neatly smooshes every entry in the sumArray back together after the reverse and we are able to return the answer without abstraction in a clean little string just like the challenge asked for! Voila!

For big integers, the return will look something like: "4968468246984629456271912039518351"

Whew! Thanks for making it to the end! Your readership is not nothingness to me!