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

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

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

实现的结果

如何实现

String -> Number[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 就是做这个事的,考略到后面方便逐位相加,所以结果处理成倒序。

一位数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 种情况,为了提高性能,我选择了打表。如果给 A, B 再排一下序,表的体积还能再缩小一半。

处理进位

1
2
3
4
5
6
7
8
9
10
11
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 []。

多位数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 的返回作为累加的结果,我用伪代码描述一下这部分逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 提示框中,我不禁

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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>>>;
Posted on

2021-09-11

Updated on

2021-10-19

Licensed under

Comments