# Implementing Advanced Type-Level Arithmetic in TypeScript part 2

Mieszko Sabo Welcome to the second and final installment of our journey to implement advanced `Add` and `Subtract` types that work with both positive and negative whole numbers, with the absolutely ridiculous absolute upper limit of 9007199254740991 (`Number.MAX_SAFE_INTEGER`) 😅:

``````Add<-123, -52>; // -175

In the previous part, we implemented `MinusOne` and `PlusOne` types that allow us to increment and decrement any numeric type literal:

``````MinusOne<42> // 41
MinusOne<0> // -1

PlusOne<10> // 11
// etc.``````

## Solution overview

Let's start by defining our solution in pseudocode. Then, we'll break it down into smaller subproblems and start implementing them as type-level algorithms.

To make it easier to understand, we'll ignore any edge cases and consider the core problem of adding two positive numbers together:

``123 + 42``

Given that we have `PlusOne`, a first idea could be to just recursively apply `PlusOne` to `123` 42 times. While this would work for the example above, TypeScript has a hardcoded depth limit for recursive calls of 1000, and we want to add numbers much bigger than 1000. So, we need to think of something smarter.

Let's think of addition this way: to add 123 to any number, we can add `1` three times, then we add `10` two times, and finally, we add `100` once. Generally, we can express any number as a sum of powers of `10`, e.g:

``````|---------------------------------------|
| |---------------|                     |
| |               |                     |
1234 = 4 * 10^0 + 3 * 10^1 + 2 * 10^2 + 1 * 10^3
| |---|                     |
|                           |
|---------------------------|``````

Breaking it down like this allows us to add arbitrary big numbers (within JavaScript's number range) without exceeding TypeScript's limit on recursive calls. A very rough argumentation is the following: `MAX_SAFE_INTEGER` has 20-something digits, say 30, so the "outer loop" is bounded by this number. The inner loop is bounded by 10, since there are 10 digits. So even in the most pessimistic scenario, we shouldn't go deeper than 30 * 10 = 300 (< 1000) nested recursion calls.

Now that we have an outline of the solution let's implement it step by step.

### Create a power of 10 to `k`

Let's start with a simpler subproblem. Here's how the first few powers of 10 look like:

``````10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
...``````

From that, we infer that 10 to the power of `k` for some natural number `k` is just a `1` with `k` zeros attached to it:

``````type Create10ToPower<Power extends number>
= ParseInt<`1\${Repeat<"0", Power>}`>;``````

Being a declarative programmer feels good, right? But we notice that we're missing a definition for the `Repeat` function, so let's add it:

``````type Repeat<
T extends string,
n extends number,
acc extends string = ""
> = n extends 0 ? acc : Repeat<T, MinusOne<n>, `\${acc}\${T}`>;``````

We start off with an empty accumulator (`acc`), and while `n` is bigger than `0`, we recursively call `Repeat` again, but with decreased `n`, and `T` (the string to repeat) appended to the accumulator. When `n` is 0, we simply return the current accumulator. Notice how `MinusOne` already comes in handy, even for utility types!

That wasn't too bad, was it? I hope that got you warmed up because adding `10^k` to any number is going to be a different beast 😅

### Adding `10^k` to any number

To add `10^k` to some number `n`, we need to consider three cases:

1. `k` is 0
2. `10^k > n`
3. `10^k <= n`

When `k` is 0
This one is easy: since `10^0` is 1, we just return `PlusOne<n>`.

When `10^k > n`
This one is also pretty straightforward, let's visualize it:

``````1000000
+   123
-------
1000123``````

Let `d` be the number of digits of `n`. Then the string representing `10^k + n` is just `10^k` with the last `d` zeros replaced by `n`. In other words: `1` followed by `k - d` zeros, followed by the string representation of `n`:

``````
1 000 000 <- 6 0s, so k is 6
+     123 <- 3 digits, so d is 3
---------
1 000 123
^^^ ^^^
k-d  d``````

In order to implement it without subtraction, let's use the first definition (last `d` zeros replaced with `n`). To do so, we'll drop the last `d` digits from `10^k` and put `n` in its place:

``````type AddBiggerPowerOf10ToN<
PowerOf10 extends string,
N extends string
> = `\${ReverseString<Drop<ReverseString<PowerOf10>, LengthOfString<N>>>}\${N}`;``````

This requires us to implement two auxiliary types, `LengthOfString` and `Drop`:

``````export type LengthOfString<
S extends string,
len extends number = 0
> = S extends `\${infer _}\${infer rest}`
? LengthOfString<rest, PlusOne<len>>
: len;

type Drop<S extends string, N extends number> = N extends 0
? S
: S extends `\${infer _}\${infer Rest}`
? Drop<Rest, MinusOne<N>>
: S;``````

When `10^k <= n`
This one is even more fun to implement. Again, let's visualize it on some examples:

``````123 456
+   100
------
123 556

1234   56
+  1   00
------
1235   56
``````

Let `m` be a number obtained by dropping the last `k` digits from `n`. Then, from the visualizations above, we can see that our answer is simply `PlusOne<m>` with the last two digits of `n` appended to it.

``````type AddSmallerPowerOf10ToN<Power extends number, N extends number> = ParseInt<
ReverseString<`\${Take<ReverseString<`\${N}`>, Power>}\${InternalPlusOne<
Drop<ReverseString<`\${N}`>, Power>
>}`>
>;``````

We use the previous article's `InternalPlusOne` utility type to avoid needless conversion between number and string.

### Implementing `Greater`

The last subproblem we need to solve is how we are going to compare `10^k` with `n` to determine whether `10^k` is greater, less, or equal to `n`? To do so, we'll implement a `Greater<A extends number, B extends number>` type that will evaluate to `true` if `A` is greater than `B`.

At this point, it shouldn't surprise you that we're going to implement it using strings 😅. Our strategy is the following:

• We consider both numbers as strings.
• If A is shorter than B, then return false.
• If B is shorter than A, then return true.
• If they are of the same length:
• Going from left, find the first index where A and B have different digits, `a` and `b`.

• If `a > b`, then return true.

• If `b > a`, then return false.

The `isShorter` type is rather straightforward:

``````type isShorter<
A extends string,
B extends String
> = A extends `\${infer Head}\${infer Rest}`
? B extends `\${infer Head2}\${infer Rest2}`
? isShorter<Rest, Rest2>
: false
: B extends `\${infer Head2}\${infer Rest2}`
? true
: false;``````

Comparing two numbers of the same length is more challenging. Based on our high-level algorithm, we need to be able to compare any two digits. My solution is to use a comparison table:

``````type GTTable = [
["=", "<", "<", "<", "<", "<", "<", "<", "<", "<"],
[">", "=", "<", "<", "<", "<", "<", "<", "<", "<"],
[">", ">", "=", "<", "<", "<", "<", "<", "<", "<"],
[">", ">", ">", "=", "<", "<", "<", "<", "<", "<"],
[">", ">", ">", ">", "=", "<", "<", "<", "<", "<"],
[">", ">", ">", ">", ">", "=", "<", "<", "<", "<"],
[">", ">", ">", ">", ">", ">", "=", "<", "<", "<"],
[">", ">", ">", ">", ">", ">", ">", "=", "<", "<"],
[">", ">", ">", ">", ">", ">", ">", ">", "=", "<"],
[">", ">", ">", ">", ">", ">", ">", ">", ">", "="]
];

type GTSameLength<
A extends string,
B extends string
> = A extends `\${infer DigitA extends number}\${infer RestA}`
? B extends `\${infer DigitB extends number}\${infer RestB}`
? GTTable[DigitA][DigitB] extends ">"
? true
: GTTable[DigitA][DigitB] extends "<"
? false
: GTSameLength<RestA, RestB>
: false
: false;``````

For any digit `a` and `b`, we can look up `GTTable[a][b]` and get either ">", "=", or "<"!

Putting it all together, we can write:

``````export type Greater<A extends number, B extends number> = InternalGT<
`\${A}`,
`\${B}`
>;

type InternalGT<A extends string, B extends string> = isShorter<
A,
B
> extends true
? false
: isShorter<B, A> extends true
? true
: GTSameLength<A, B>;``````

### Implementing `Plus10ToPower`

We can now combine the above types to create a single `Plus10ToPower` type that, given any number `N`, will add 10 to the power `Power` to it!

``````type Plus10ToPower<N extends number, Power extends number> = Power extends 0
? PlusOne<N>
: Greater<Create10ToPower<Power>, N> extends true

We are now ready to implement our addition algorithm. Let's quickly recall it:

To add `A` to `B`, we consider every digit `d` and its index `i` of the reversed number `B` (meaning, we go backward) and calculate `sum += Plus10ToPower<A, i> * d`. Instead of multiplying by `d`, we'll just recursively add `Plus10ToPower<A, i>` `d` times. To help us with that, let's create a handy function:

``````type AddPowerOf10NTimes<
sum extends number,
power extends number,
N extends number
> = N extends 0
? sum

And putting it all together:

``````type Adder<
sum extends number,
reversedDigits,
currentPower extends number = 0
> = reversedDigits extends `\${infer d extends number}\${infer rest}`
: sum;

type res = Adder<50, "24">; // 92, bacause "24" is reversed "42".``````

To make it less awkward with the reversed strings, let's create a `SimpleAdd`:

``````type SimpleAdd<A extends number, B extends number>

type res1 = SimpleAdd<42, 50>; // 92``````

Why did I call it `SimpleAdd` instead of just `Add`? Well, as you might remember, for now, we're considering only the addition of two positive numbers. Extending `SimpleAdd` to support negative numbers is a great exercise that I'd like to leave you as a challenge.

To get you started, here's an outline of what needs to be done to accomplish this task:

• Implement the `Subtract` type, analogous to the `Adder`.
• Implement the `isNonNegative` and `Abs` types.
• Implement the proper `Add` based on the following pseudocode:
``````Add<a, b> =
if a < 0 and b < 0 then `-{SimpleAdd<Abs<a>, Abs<b>>}`
if a < 0 and b > 0 then Subtract<b, Abs<a>>
if < > 0 and b > 0 then Subtract<a, Abs<b>>
if a > 0 and b > 0 then SimpleAdd<a, b>``````

Thanks so much for reading! If you reached the end, I'd love to hear your thoughts on this article in the comments. As always, if you enjoyed this post, consider subscribing to our newsletter and sharing it with your friends and colleagues.