Result of implementation

How to implement

There are many strange techniques for TS addition on the Internet, but there are many limitations, can not achieve too large number calculation, how to achieve an efficient large number addition?

String -> Number[]

type DigitRangeMap = [0.1.2.3.4.5.6.7.8.9];
type Digit = DigitRangeMap[number];

type ToDigit<T extends string> =
  T extends keyof DigitRangeMap
    ? DigitRangeMap[T]
    : never;

type ToDigitList<T, R extends any[] = []>  =
  T extends `${infer First}${infer Rest}`
    ? ToDigitList<Rest, [ToDigit<First>, ...R]>
    : R;

// debug
type test = ToDigitList<"1234">; // [4, 3, 2, 1]
Copy the code

First, I’m going to convert String to Number array, and that’s what ToDigitList does, so it’s in reverse order for bit-by-bit addition.

Sum of one digit

type AdditionMap = [
  [0.1.2.3.4.5.6.7.8.9],
  [1.2.3.4.5.6.7.8.9.10],
  [2.3.4.5.6.7.8.9.10.11],
  [3.4.5.6.7.8.9.10.11.12],
  [4.5.6.7.8.9.10.11.12.13],
  [5.6.7.8.9.10.11.12.13.14],
  [6.7.8.9.10.11.12.13.14.15],
  [7.8.9.10.11.12.13.14.15.16],
  [8.9.10.11.12.13.14.15.16.17],
  [9.10.11.12.13.14.15.16.17.18]].type AddOneDigit<A extends Digit, B extends Digit> = AdditionMap[A][B];

// debug
type test = AddOneDigit<9.8>; / / 17
Copy the code

In order to improve performance, I chose tabulating. AdditionMap[x][y] == AdditionMap[y][x]

Processing carry

type RoundMap = {
  10:0; 11:1; 12:2; 13:3; 14:4; 15:5; 16:6; 17:7; 18:8; 19:9
};

type Carry<T extends number, R extends number[] = []> =
  T extends keyof RoundMap
    ? [1, [RoundMap[T], ...R]]
    : [0, [T, ...R]];

// debug
type test = Carry<15[3.2.1>;// [1, [5, 3, 2, 1]
Copy the code

The first argument T to Carry is the result of the one-digit addition AddOneDigit of the previous step. The result ranges from 0 to 19. Why not 0 to 18? Because you could have carried a 1. Since there are few cases, we still use tabulation. The second argument, R, is the result of the previous N bit calculation and is of type Digit[].

The returned result is an Array, the first value is a binary 0 | 1, the second value is added as a result, after a type is a Digit [].

Multi-digit addition

type IncMap = [1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19];

type Shift<T extends any[]> =
  T extends [infer First, ...infer Rest]
    ? Rest
    : never;

type AddDigitList<
  A extends any[],
  B extends any[],
  ACC extends [0|1.number[]] = [0, []]
> =
  A['length'] extends 0
    ? B['length'] extends 0
      // A is empty, B is empty
      ? ACC[0] extends 1 ? AddDigitList<[1], [], [0, ACC[1]]> : ACC[1]
      // A is null, B is not null
      : AddDigitList<A, Shift<B>, Carry<AddOneDigit<B[0], ACC[0]>, ACC[1]>>
    : B['length'] extends 0
       // A is not empty, B is empty
      ? AddDigitList<Shift<A>, B, Carry<AddOneDigit<A[0], ACC[0]>, ACC[1] > >// A is not null, B is not null
      : AddDigitList<
          Shift<A>, Shift<B>, Carry<
            ACC[0] extends 0
              ? AddOneDigit<A[0], B[0]>
              : IncMap[AddOneDigit<A[0], B[0]>],
            ACC[1]
          >
        >;

// debug
type test = AddDigitList<[2.5], [1.5>;/ /,0,3 [1]
Copy the code

Here’s the thing: AddDigitList takes two Digit[] types and returns the same Digit[] addition. I use parameter ACC to Carry the return of the previous Carry as the result of accumulation. I use pseudocode to describe this part of logic:

function fn(a: number[], b: number[], acc = [0, [the]]) {
  if (a.length === 0) {
    if (b.length === 0) {
      return acc[0] = =1
        ? fn([1], [], [0, acc[1]])
        : acc[1];
    } else {
      return fn(
        a, b.slice(1),
        carry(add(b[0], acc[0]), acc[0))}}else {
    if (b.length === 0) {
      return fn(
        a.slice(1), b,
        carry(add(a[0], acc[0]), acc[0))}else {
      return fn(
        a.slice(1), b.slice(1),
        carry(add(add(a[0], b[0]), acc[0]), acc[0]))}}}Copy the code

Number[] -> String

type StrDigitRangeMap = ['0'.'1'.'2'.'3'.'4'.'5'.'6'.'7'.'8'.'9'];

type DigitListToString<T extends any[], R extends string = ' '> =
  T extends [infer First, ...infer Rest]
    ? DigitListToString<
        Rest,
        `${R}${First extends number ? StrDigitRangeMap[First] : 'n' }`
      >
    : R;

type Add<A extends string, B extends string> =
  DigitListToString<AddDigitList<ToDigitList<A>, ToDigitList<B>>>;

// debug
type result = Add<
  "1248859103109591728912488591031095917289"."32481239839485789343248123983948578934">;
Copy the code

As a final move, I converted Digit[] to String and saw the result appear smoothly in my VSCode prompt

Finally, post the complete code

type DigitRangeMap = [0.1.2.3.4.5.6.7.8.9];
type StrDigitRangeMap = ['0'.'1'.'2'.'3'.'4'.'5'.'6'.'7'.'8'.'9'];
type RoundMap = { 10:0; 11:1; 12:2; 13:3; 14:4; 15:5; 16:6; 17:7; 18:8; 19:9 };
type AdditionMap = [
  [0.1.2.3.4.5.6.7.8.9],
  [1.2.3.4.5.6.7.8.9.10],
  [2.3.4.5.6.7.8.9.10.11],
  [3.4.5.6.7.8.9.10.11.12],
  [4.5.6.7.8.9.10.11.12.13],
  [5.6.7.8.9.10.11.12.13.14],
  [6.7.8.9.10.11.12.13.14.15],
  [7.8.9.10.11.12.13.14.15.16],
  [8.9.10.11.12.13.14.15.16.17],
  [9.10.11.12.13.14.15.16.17.18]].type IncMap = [1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19];

type Digit = DigitRangeMap[number];

type ToDigit<T extends string> =
  T extends keyof DigitRangeMap
    ? DigitRangeMap[T]
    : never;

type ToDigitList<T, R extends any[] = []>  =
  T extends `${infer First}${infer Rest}`
    ? ToDigitList<Rest, [ToDigit<First>, ...R]>
    : R;

type Shift<T extends any[]> =
  T extends [infer First, ...infer Rest]
    ? Rest
    : never;

type Carry<T extends number, R extends number[] = []> =
  T extends keyof RoundMap
    ? [1, [RoundMap[T], ...R]]
    : [0, [T, ...R]];

type AddOneDigit<A extends Digit, B extends Digit> = AdditionMap[A][B];

type AddDigitList<
  A extends any[],
  B extends any[],
  ACC extends [0|1.number[]] = [0, []]
> =
  A['length'] extends 0
    ? B['length'] extends 0
      ? ACC[0] extends 1 ? AddDigitList<[1], [], [0, ACC[1]]> : ACC[1]
      : AddDigitList<A, Shift<B>, Carry<AddOneDigit<B[0], ACC[0]>, ACC[1]>>
    : B['length'] extends 0
      ? AddDigitList<Shift<A>, B, Carry<AddOneDigit<A[0], ACC[0]>, ACC[1]>>
      : AddDigitList<
          Shift<A>, Shift<B>, Carry<
            ACC[0] extends 0
              ? AddOneDigit<A[0], B[0]>
              : IncMap[AddOneDigit<A[0], B[0]>],
            ACC[1]
          >
        >;

type DigitListToString<T extends any[], R extends string = ' '> =
  T extends [infer First, ...infer Rest]
    ? DigitListToString<
        Rest,
        `${R}${First extends number ? StrDigitRangeMap[First] : 'n' }`
      >
    : R;

type Add<A extends string, B extends string> =
  DigitListToString<AddDigitList<ToDigitList<A>, ToDigitList<B>>>;
Copy the code