举个🌰，比如 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 (a15 + b21 + 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 = (ax) mod 7-(by) mod 5-(c*z) mod 3
n 位的乘法只需要 O(n)，而非小学学的 O(n^2)，也比基于 FFT 的 O(nlog n log log n)快
其中最大的优点是可并行计算，只要计算单元够多，O(1)就能计算出乘法结果而没有进位的依赖.
 |
1
qwertyegg OP 前面一段排版有点问题，
0-0-0 表示 0 1-1-1 表示 1 2-2-2 表示 2 3-3-0 表示 3 4-4-1 表示 4 5-0-2 表示 5 |
 |
2
KeShih 12 天前
时间复杂度是一个渐进的概念，只考虑有限输入规模是没有意义的。只考虑限定输入大小时候，你会自然的把一些和输入规模相关的量当成常数，而得到一个错误的时间复杂度
目前 n-bit 整数相乘最快的算法时间复杂度是 O(n log n)，21 年发表在数学四大上 "Integer multiplication in time O(n log n)", Annals of Mathematics, 2021 论文地址： https://annals.math.princeton.edu/2021/193-2/p01 |
 |
3
murmurkerman 12 天前 via iPhone
写下你的算法测试下就好了，o(n)不太可能实现。
|
 |
4
msg7086 12 天前
另外提一句，时间复杂度是计算时间增量与输入量增量的关系，不是计算时间与输入量的关系。
O(n)并不见得会比 O(nlogn)快，只是说 O(n)对于 n 增加的时候，计算时间增加的速度比 O(nlogn)少。 可能有一种算法，复杂度是 O(n)，对于输入位数 10 的计算时间是 100 ，另一种算法，复杂度是 O(nlogn)，对于输入位数 10 的计算时间是 10log10 ，后者还是会比前者快。 |
 |
5
woaiwinnie2 11 天前
这个数值下乘法的性质还不错，但不知道怎样对应的问题可以用上这样的结构，毕竟看起来把它转回 10 进制的 cost 对应 c*70 mod 105 这个运算，这个运算可一点都不便宜
|
 |
6
vvhy 11 天前 via Android
进制转换那一步用到了十进制乘法，估计整个算法比十进制更慢
另外怎么计算除法 |
 |
7
Ljxtt 11 天前
感觉上复杂度应该是 O(nm)，其中 n 是进制的基数个数，m 是和基数的位数有关的数（平均？），这里看起来是 O(n) 大概率是因为 7 ，5 ，3 都是 1 位数，当基数的位数上去时，这个数值应该是不可忽视的。
|
Select Language