Estimate project
← All posts

Building Advanced Type-Level Arithmetic in TypeScript, part 2

This is the second and last stage of our adventure with building advanced "Add" and "Subtract" types in TypeScript.

8 min read
Typescriptadvanced TypeScripttype level programingarithmeticaddition

This is the second and last part of our adventure in building advanced Add and Subtract types that handle both positive and negative integers, all the way up to the utterly absurd upper bound 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

We have already built the MinusOne and PlusOne types, which let us increment and decrement any numeric literal type:

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

PlusOne<10> // 11
// etc.

Solution overview

We’ll begin by describing the solution in pseudocode. After that, we’ll split it into smaller subproblems and implement each of them as a type-level algorithm.

To keep things easy to follow, we’ll set edge cases aside and focus on the core task of adding two positive numbers:

123 + 42

Since we already have PlusOne, an obvious first thought is to recursively apply PlusOne to 123 42 times. That would do the job for the example above, but TypeScript caps recursive calls at a hardcoded depth of 1000, and we want to add numbers far larger than 1000. We need a cleverer approach.

Let’s look at addition from another angle: adding 123 to a number means adding 1 three times, then adding 10 twice, and lastly adding 100 once. In general, every number can be written as a sum of powers of 10, for example:

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

Decomposing numbers this way lets us add arbitrarily large numbers (as long as they fit in JavaScript’s number range) without hitting TypeScript’s recursion limit. Very roughly, the reasoning goes like this: MAX_SAFE_INTEGER has twenty-odd digits, let’s say 30, which bounds the “outer loop”. The inner loop is bounded by 10, as there are 10 digits. So even in the worst case, we should never exceed 30 * 10 = 300 (< 1000) nested recursive calls.

With the outline of the solution in place, let’s build it one step at a time.

Create a power of 10 to k

We’ll warm up with an easier subproblem. These are the first few powers of 10:

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

This tells us that 10 raised to the power k, for a natural number k, is simply a 1 followed by k zeros:

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

Doesn’t declarative programming feel great? We still lack a definition of the Repeat function, though, so let’s write it:

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

We begin with an empty accumulator (acc), and as long as n is greater than 0, we call Repeat recursively with a decremented n and with T (the string being repeated) appended to the accumulator. Once n reaches 0, we just return the accumulator. Note that MinusOne is already proving useful, even inside utility types!

Not so hard, right? Hopefully that warmed you up, because adding 10^k to an arbitrary number is a whole other story 😅

Adding 10^k to any number

Adding 10^k to a number n requires handling three cases:

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

When k is 0
This case is trivial: 10^0 equals 1, so we simply return PlusOne<n>.

When 10^k > n
This case is fairly simple too; here’s a visualization:

1000000
+   123
-------
1000123

Let d denote the number of digits in n. The string representing 10^k + n is then just 10^k with its final d zeros swapped for n. Put differently: a 1, then k - d zeros, then the string form of n:

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

To avoid needing subtraction in the implementation, we’ll go with the first formulation (the final d zeros swapped for n). That means removing the last d digits of 10^k and putting n there instead:

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

For this, we need two helper 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
Implementing this case is even more entertaining. Once again, a few examples will help us picture it:

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

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

Let m be the number we get by removing the final k digits of n. The visualizations above show that the result is just PlusOne<m> with the final two digits of n tacked on.

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

To skip unnecessary number-to-string conversions, we reuse the InternalPlusOne utility type.

Implementing Greater

One subproblem remains: how do we compare 10^k with n to find out whether 10^k is greater than, less than or equal to n? For that, we’ll write a Greater<A extends number, B extends number> type which evaluates to true when A is greater than B.

By now it probably won’t surprise you that strings will be our tool once again 😅. Here is the plan:

  • Treat both numbers as strings.
  • When A is shorter than B, return false.
  • When B is shorter than A, return true.
  • When both have the same length:
    • Scanning from the left, locate the first position where A and B differ, with digits a and b.
    • When a > b, return true.
    • When b > a, return false.

The isShorter type is quite simple:

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 equal length is trickier. According to our high-level algorithm, we must be able to compare any pair of digits. I solved this with 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;

Given any digits a and b, looking up GTTable[a][b] yields “>”, “=” or “<”!

Combining everything, we get:

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

Now the types above can be merged into one Plus10ToPower type, which adds 10 raised to Power to any number N!

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>;

Everything is in place for the addition algorithm. A quick reminder of how it works:

To add A to B, we walk through each digit d together with its index i in the reversed number B (that is, going backwards) and compute sum += Plus10ToPower<A, i> * d. Rather than multiplying by d, we’ll recursively add Plus10ToPower<A, i> d times. A small helper function makes this easier:

type AddPowerOf10NTimes<
  sum extends number,
  power extends number,
  N extends number
> = N extends 0
  ? sum
  : AddPowerOf10NTimes<Plus10ToPower<sum, power>, power, MinusOne<N>>;

And here is everything combined:

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 hide the clumsiness of reversed strings, let’s define SimpleAdd:

type SimpleAdd<A extends number, B extends number> 
 = Adder<A, ReverseString<`${B}`>>;

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

Why the name SimpleAdd rather than just Add? As you may recall, so far we only handle adding two positive numbers. Making SimpleAdd work with negative numbers is an excellent exercise, and I’ll leave it to you as a challenge.

To help you get going, here is a sketch of the steps involved:

  • Write the Subtract type, mirroring the Adder.

  • Write the isNonNegative and Abs types.

  • Write the actual Add according to this 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>

Thank you very much for reading! If you’ve made it this far, I’d be glad to read your opinion on this article in the comments. And as usual, if you liked the post, think about subscribing to our newsletter and passing it on to your friends and coworkers.