多进制数的乘法时间复杂度O(n)?

[ɓuoɥɔɓuɐnɥ]

举个，比如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进制就没有这个限制

[cublai]

有意思

[牛河梁]

没细看。觉得问题是表示是怎么表示更大的数。当位数少的时候，二进制乘法的与或非电路也不复杂。即使包括先行进位。53 CS们当年搞不好都画过。

[Fnhdx]

位数多了怎么表示，11-9-7-5-3？

[ɓuoɥɔɓuɐnɥ]

位数多了怎么表示，11-9-7-5-3？

阿基米德都给你证明好了，素数无穷多个

[m8d]

举个，比如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进制就没有这个限制

Mod 硬件复杂性更高。硬件48bits乘法器一个周期(f>1GHz)就完成了, o啥？64bits 我不大了解能做多快。

[cocojumbo]

我觉得这种讨论很不错，既然美帝逼土工另开赛道，不如就搞个基础上的突破。
比如上次有人提过3进制的计算机，那个可能不如这个，如果集成电路上可行，
这个搞不好至少在一类的计算运用中会有惊喜的发现。

举个，比如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]

这叫residue number system，早就有人用了。但是复杂度不可能是O(n)。你的公式中：

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

70很接近105，这里相乘的复杂度可能大了。

举个，比如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ɥ]

这叫residue number system，早就有人用了。但是复杂度不可能是O(n)。你的公式中：

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

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

如果在多进制里面计算，不转换回十进制就没有这个cost

比如大量的乘法

[FoxMe]

哦，有点道理。瓶颈在CRT，如果一直在多进制里面计算，就不用转换。

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

如果在多进制里面计算，不转换回十进制就没有这个cost

比如大量的乘法

[ɓuoɥɔɓuɐnɥ]

哦，有点道理。瓶颈在CRT，如果一直在多进制里面计算，就不用转换。

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

完了，求余似乎是硬伤

这样看，把n*n的乘法计算量转换成n_1*n_1 + n_2*n_2 + ... n_m*n_m, where sum(n_i) = n的小块乘法

[forecasting]

本不想回复，今天闲，就说两句消磨时间。

有计算理论的常识就知道，这不是个问题，计算复杂度不变，除非你改变进制为递归序列，但映射输入为另一个递归序列-base进制，再映射输出回来，所降低的复杂度也得加上去，还是没变，甚至更复杂。
三值逻辑或n值逻辑与二值逻辑不同，但是这种不属于进制不同。