新未名空间

Fnhdx 写了： 2025年 5月 1日 14:22 位数多了怎么表示，11-9-7-5-3？

ɓuoɥɔɓuɐnɥ 写了： 2025年 4月 30日 23:42 举个，比如7-5-3进制数，可以表示0-104，105个整数

7-5-3进制数跟10进制数的转换

0-0-0表示0
1-1-1表示1
2-2-2表示2
3-3-0表示3
4-4-1表示4
5-0-2表示5

以此类推

6-4-2表示104

10进制数转换为7-5-3进制数很容易，求余即可。反过来，7-5-3进制数转换为十进制数可用中国剩余定理算a-b-c to (a*15 + b*21 + c*70) mod 105.

显而易见，7-5-3进制数的加法:

a-b-c + x-y-z = (a+x)-(b+y)-(c+z)，只需要对每位计算一次，完全不需要考虑进位。当然这个并不是大问题，计算机算加法也是可以同时并行计算每一位，并不是手算那种需要考虑进位的依赖。

有意思的是乘法:

a-b-c * x-y-z = (a*x) mod 7-(b*y) mod 5-(c*z) mod 3

n位的乘法只需要O(n)，而非小学学的O(n^2)，也比基于FFT的O(n*log n* log log n)快

我认为其中最大的优点是可并行计算，只要计算单元够多，一步就能计算出乘法结果而没有进位的依赖.

再补充一下：如果只计算一次乘法，这个办法并没有优势，用中国剩余定理转换为原10进制数仍然需要做一次很大的乘加。如果需要做很多次乘法，可以在多进制下计算出结果，再进行一次乘加转换回10进制.当然，如果不需要转换回10进制就没有这个限制

ɓuoɥɔɓuɐnɥ 写了： 2025年 4月 30日 23:42 举个，比如7-5-3进制数，可以表示0-104，105个整数

7-5-3进制数跟10进制数的转换

0-0-0表示0
1-1-1表示1
2-2-2表示2
3-3-0表示3
4-4-1表示4
5-0-2表示5

以此类推

6-4-2表示104

10进制数转换为7-5-3进制数很容易，求余即可。反过来，7-5-3进制数转换为十进制数可用中国剩余定理算a-b-c to (a*15 + b*21 + c*70) mod 105.

显而易见，7-5-3进制数的加法:

a-b-c + x-y-z = (a+x)-(b+y)-(c+z)，只需要对每位计算一次，完全不需要考虑进位。当然这个并不是大问题，计算机算加法也是可以同时并行计算每一位，并不是手算那种需要考虑进位的依赖。

有意思的是乘法:

a-b-c * x-y-z = (a*x) mod 7-(b*y) mod 5-(c*z) mod 3

n位的乘法只需要O(n)，而非小学学的O(n^2)，也比基于FFT的O(n*log n* log log n)快

我认为其中最大的优点是可并行计算，只要计算单元够多，一步就能计算出乘法结果而没有进位的依赖.

再补充一下：如果只计算一次乘法，这个办法并没有优势，用中国剩余定理转换为原10进制数仍然需要做一次很大的乘加。如果需要做很多次乘法，可以在多进制下计算出结果，再进行一次乘加转换回10进制.当然，如果不需要转换回10进制就没有这个限制

ɓuoɥɔɓuɐnɥ 写了： 2025年 4月 30日 23:42 举个，比如7-5-3进制数，可以表示0-104，105个整数

7-5-3进制数跟10进制数的转换

0-0-0表示0
1-1-1表示1
2-2-2表示2
3-3-0表示3
4-4-1表示4
5-0-2表示5

以此类推

6-4-2表示104

10进制数转换为7-5-3进制数很容易，求余即可。反过来，7-5-3进制数转换为十进制数可用中国剩余定理算a-b-c to (a*15 + b*21 + c*70) mod 105.

显而易见，7-5-3进制数的加法:

a-b-c + x-y-z = (a+x)-(b+y)-(c+z)，只需要对每位计算一次，完全不需要考虑进位。当然这个并不是大问题，计算机算加法也是可以同时并行计算每一位，并不是手算那种需要考虑进位的依赖。

有意思的是乘法:

a-b-c * x-y-z = (a*x) mod 7-(b*y) mod 5-(c*z) mod 3

n位的乘法只需要O(n)，而非小学学的O(n^2)，也比基于FFT的O(n*log n* log log n)快

我认为其中最大的优点是可并行计算，只要计算单元够多，一步就能计算出乘法结果而没有进位的依赖.

再补充一下：如果只计算一次乘法，这个办法并没有优势，用中国剩余定理转换为原10进制数仍然需要做一次很大的乘加。如果需要做很多次乘法，可以在多进制下计算出结果，再进行一次乘加转换回10进制.当然，如果不需要转换回10进制就没有这个限制

FoxMe 写了： 2025年 5月 2日 12:23 这叫residue number system，早就有人用了。但是复杂度不可能是O(n)。你的公式中：

(a*15 + b*21 + c*70) mod 105.

70很接近105. 也就是说如果N=2ⁿ, 你的复杂度可能接近2ⁿ。

ɓuoɥɔɓuɐnɥ 写了： 2025年 5月 2日 12:26 如果在多进制里面计算，不转换回十进制就没有这个cost

比如大量的乘法

FoxMe 写了： 2025年 5月 2日 12:45 哦，有点道理。瓶颈在CRT，如果一直在多进制里面计算，就不用转换。

如果数据是十进制的，如果只是开始结尾做一次,可能有好处？但是求余数是通过除法实现的，除法的复杂度和乘法是一样的吧？