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

实现的型系现结果

如何实现

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

String -> Number[]type DigitRangeMap = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

type Digit = DigitRangeMap[number];

type ToDigit=

T extends keyof DigitRangeMap

? DigitRangeMap[T]

: never;

type ToDigitList=

T extends `${ infer First}${ infer Rest}`

? ToDigitList, ...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 = 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 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 [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, Carry, ACC[1]>>

: B[length] extends 0

// A非空, B为空

? AddDigitList

// A非空, B非空

: AddDigitList<

Shift, Shift, Carry<

ACC[0] extends 0

? AddOneDigit

: IncMap[AddOneDigit],

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[] -> Stringtype StrDigitRangeMap = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

type DigitListToString=

T extends [infer First, ...infer Rest]

? DigitListToString<

Rest,

`${ R}${ First extends number ? StrDigitRangeMap[First] : n }`

>

: R;

type Add =

DigitListToString, ToDigitList>>;

// 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 keyof DigitRangeMap

? DigitRangeMap[T]

: never;

type ToDigitList=

T extends `${ infer First}${ infer Rest}`

? ToDigitList, ...R]>

: R;

type Shift=

T extends [infer First, ...infer Rest]

? Rest

: never;

type Carry=

T extends keyof RoundMap

? [1, [RoundMap[T], ...R]]

: [0, [T, ...R]];

type AddOneDigit = 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, Carry, ACC[1]>>

: B[length] extends 0

? AddDigitList

: AddDigitList<

Shift, Shift, Carry<

ACC[0] extends 0

? AddOneDigit

: IncMap[AddOneDigit],

ACC[1]

>

>;

type DigitListToString=

T extends [infer First, ...infer Rest]

? DigitListToString<

Rest,

`${ R}${ First extends number ? StrDigitRangeMap[First] : n }`

>

: R;

type Add =

DigitListToString<AddDigitList<ToDigitList<A>, ToDigitList<B>>>;