用 TS 类型系统实现大数加法

实现的结果

如何实现

网上有很多实现 TS 加法的奇淫技巧，但是都有很多限制，没法实现太大的数字计算，如何实现一种高效的大数加法呢？

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]

首先我会把 String 转为 Number 数组，ToDigitList 就是做这个事的，考虑到后面方便逐位相加，所以结果处理成倒序。

一位数相加

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

一位数相加，总共也就只有 100 种情况，为了提高性能，我选择了打表。因为 AdditionMap[x][y] == AdditionMap[y][x]，所以再给 A, B 再排一下序，使 A > B，那么表的体积还能再缩小一半。

处理进位

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

Carry 的第一个参数 T 是上一步一位数加法 AddOneDigit 返回的结果，结果范围 0 ~ 19，为什么不是 0 ~ 18 呢？因为还可能有进位 1。因为情况较少，所以还是使用打表计算。第二个参数 R 是前面 N 位计算的结果，类型是 Digit[]。

返回的结果是一个 Array，第一个值是进位 0 | 1，第二个值是新增了一位后的结果，类型是 Digit []。

多位数相加

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为空, B为空
      ? ACC[0] extends 1 ? AddDigitList<[1], [], [0, ACC[1]]> : ACC[1]
      // A为空, B非空
      : AddDigitList<A, Shift<B>, Carry<AddOneDigit<B[0], ACC[0]>, ACC[1]>>
    : B['length'] extends 0
       // A非空, B为空
      ? AddDigitList<Shift<A>, B, Carry<AddOneDigit<A[0], ACC[0]>, ACC[1]>>
       // A非空, B非空
      : 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]>; // [1,0,3]

重点来了，AddDigitList 接受两个 Digit[] 类型，返回同样是 Digit[] 类型加法的结果。我用参数 ACC 承载上一步 Carry 的返回作为累加的结果，我用伪代码描述一下这部分逻辑：

function fn(a: number[], b: number[], acc = [0, []]) {
  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])
      )
    }
  }
}

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

最后的处理，将 Digit[] 转为 String，看到结果顺滑的显示在我的 VSCode 提示框中，我不禁

最后贴上完整代码

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