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

富春平头

实现的结果如何实现网上有很多实现 TS 加法的奇淫技巧，但是都有很多限制，没法实现太大的数字计算，如何实现一种高效的大数加法呢？String -> Number[]typeDigitRangeMap=[0,1,2,3,4,5,6,7,8,9];typeDigit=DigitRangeMap[number];typeToDigit=TextendskeyofDigitRangeMapDigitRangeMap[T]:never;typeToDigitList=Textends`${inferFirst}${inferRest}`ToDigitList,...R]>:R;//debugtypetest=ToDigitList;//[4,3,2,1]首先我会把 String 转为 Number 数组，ToDigitList 就是做这个事的，考虑到后面方便逐位相加，所以结果处理成倒序。一位数相加typeAdditionMap=[[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]];typeAddOneDigit=AdditionMap[A][B];//debugtypetest=AddOneDigit;//17一位数相加，总共也就只有 100 种情况，为了提高性能，我选择了打表。因为 AdditionMap[x][y] == AdditionMap[y][x]，所以再给 A, B 再排一下序，使 A > B，那么表的体积还能再缩小一半。处理进位typeRoundMap={10:0;11:1;12:2;13:3;14:4;15:5;16:6;17:7;18:8;19:9};typeCarry=TextendskeyofRoundMap[1,[RoundMap[T],...R]]:[0,[T,...R]];//debugtypetest=Carry;//[1,[5,3,2,1]]Carry 的第一个参数 T 是上一步一位数加法 AddOneDigit 返回的结果，结果范围 0 ~ 19，为什么不是 0 ~ 18 呢？因为还可能有进位 1。因为情况较少，所以还是使用打表计算。第二个参数 R 是前面 N 位计算的结果，类型是 Digit[]。返回的结果是一个 Array，第一个值是进位 0 | 1，第二个值是新增了一位后的结果，类型是 Digit []。多位数相加typeIncMap=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];typeShift=Textends[inferFirst,...inferRest]Rest:never;typeAddDigitList=A['length']extends0B['length']extends0//A为空,B为空ACC[0]extends1AddDigitList:ACC[1]//A为空,B非空:AddDigitList,Carry,ACC[1]>>:B['length']extends0//A非空,B为空AddDigitList,B,Carry,ACC[1]>>//A非空,B非空:AddDigitList,Shift,Carry:IncMap[AddOneDigit],ACC[1]>>;//debugtypetest=AddDigitList;//[1,0,3]重点来了，AddDigitList 接受两个 Digit[] 类型，返回同样是 Digit[] 类型加法的结果。我用参数 ACC 承载上一步 Carry 的返回作为累加的结果，我用伪代码描述一下这部分逻辑：functionfn(a:number[],b:number[],acc=[0,[]]){if(a.length===0){if(b.length===0){returnacc[0]==1fn([1],[],[0,acc[1]]):acc[1];}else{returnfn(a,b.slice(1),carry(add(b[0],acc[0]),acc[0]))}}else{if(b.length===0){returnfn(a.slice(1),b,carry(add(a[0],acc[0]),acc[0]))}else{returnfn(a.slice(1),b.slice(1),carry(add(add(a[0],b[0]),acc[0]),acc[0]))}}}Number[] -> StringtypeStrDigitRangeMap=['0','1','2','3','4','5','6','7','8','9'];typeDigitListToString=Textends[inferFirst,...inferRest]DigitListToString:R;typeAdd=DigitListToString,ToDigitList>>;//debugtyperesult=Add;最后的处理，将 Digit[] 转为 String，看到结果顺滑的显示在我的 VSCode 提示框中，我不禁最后贴上完整代码typeDigitRangeMap=[0,1,2,3,4,5,6,7,8,9];typeStrDigitRangeMap=['0','1','2','3','4','5','6','7','8','9'];typeRoundMap={10:0;11:1;12:2;13:3;14:4;15:5;16:6;17:7;18:8;19:9};typeAdditionMap=[[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]];typeIncMap=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];typeDigit=DigitRangeMap[number];typeToDigit=TextendskeyofDigitRangeMapDigitRangeMap[T]:never;typeToDigitList=Textends`${inferFirst}${inferRest}`ToDigitList,...R]>:R;typeShift=Textends[inferFirst,...inferRest]Rest:never;typeCarry=TextendskeyofRoundMap[1,[RoundMap[T],...R]]:[0,[T,...R]];typeAddOneDigit=AdditionMap[A][B];typeAddDigitList=A['length']extends0B['length']extends0ACC[0]extends1AddDigitList:ACC[1]:AddDigitList,Carry,ACC[1]>>:B['length']extends0AddDigitList,B,Carry,ACC[1]>>:AddDigitList,Shift,Carry:IncMap[AddOneDigit],ACC[1]>>;typeDigitListToString=Textends[inferFirst,...inferRest]DigitListToString:R;typeAdd=DigitListToString,ToDigitList>>;