Implementing Advanced Type-Level Arithmetic in TypeScript part 2

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
Add<123, -52>; // 71
Add<-123, 52> // -71
Add<123456789, 9988776655>; // 10112233444
Add<9007199254740989, 2>; // 9007199254740991

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
  ? ParseInt<AddBiggerPowerOf10ToN<`${Create10ToPower<Power>}`, `${N}`>>
  : AddSmallerPowerOf10ToN<Power, N>;

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
  : AddPowerOf10NTimes<Plus10ToPower<sum, power>, power, MinusOne<N>>;

And putting it all together:

type Adder<
  sum extends number,
  reversedDigits,
  currentPower extends number = 0
> = reversedDigits extends `${infer d extends number}${infer rest}`
  ? Adder<AddPowerOf10NTimes<sum, currentPower, d>, rest, PlusOne<currentPower>>
  : 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> 
 = Adder<A, ReverseString<`${B}`>>;

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.