[算法]从 CU 抄过来的数学题一个。

lucifer

Post by arxor
楼上的兄弟....
两个高精数乘法最快能做到多少?
FFT实现只能做到O(nlog(n))....(n是乘数的在某进制下的位数)
这样乘法就不是O(1)的了

PS: fib的问题请看看我的帖子

高精度在某些情况下不可避免，考虑实际情况的话
至于fib，你说的是用((1,1)(1,0))来个n次幂那种方法吗？这个确实只需要logn次乘法，不过这个可是矩阵乘法啊

arxor

...
2*2矩阵相乘是O(1)的...

lucifer

理论上那样而已。事实上当需要计算的结果达到一定规模（例如2^1024位)为了保持精确，不得不用到高精度乘法的算法（为了保证只要log n次乘法）。不管是Karatsuba还是Strassen，O(1)肯定都是没有指望的。以上还没有考虑内存问题。

arxor

呵呵, 明显这时肯定比直接算有指望多了.
O(1)自然是有前提的: 因为取模, 而且模在64bit表示内, 而定义这个整数乘法为基本操作, 整数乘法是O(1), 2*2矩阵也是O(1).
而你举的例子里明显定义矩阵元素的乘法为基本操作是不合理的了, 这时我们只能定义高精数节点乘法为基本操作.
适用范围不一样了^_^
算法分析讨论的只是撇开次要因素的干扰去分析算法在某种假设下的性质, 如内存, 自然要求一个算法适用所有情况是不现实的,
如没有人会否定qsort比insertion sort好, 但是对于规模很小的case, insertion sort实际效率比qsort好, 因为这时常数已经重要到影响算法效率了.

Post by lucifer
理论上那样而已。事实上当需要计算的结果达到一定规模（例如2^1024位)为了保持精确，不得不用到高精度乘法的算法（为了保证只要log n次乘法）。不管是Karatsuba还是Strassen，O(1)肯定都是没有指望的。以上还没有考虑内存问题。

drowsyboy

汗……，不要欺负电脑

这里涉及到数论中，指数，原根等……

drowsyboy

数学啊，数学，只有数学才是算法的灵魂！

DoDo

支持楼上的观点!数学啊!算法啊!灵魂啊!

nuclearweapon

To some extents,it 's very easy to find b^n  mod m becasue this is a very classic proplem in discrete mathematics!
There is an efficient algorithm ,which can get the result in O ((log m)^2*log n)


by the way,in the cryptography,this algorithm is very important!