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

DoDo

20楼的兄弟也不要说得这么轻松,那你试试你算出那个问题需要多长时间吧

arxor

用不着高精
先搞清楚n^m可以用二分来达到O(log(m))的复杂度

1. 
   
2. power(n, m)
   
3.     r<- n
   
4.     f<- 1
   
5.     while m > 1
   
6.         if m (mod 2) = 1
   
7.             f <- f*r
   
8.         r <- r*r
   
9.         m <- m/2   
   
10. return f

复制代码

然后二项式展开就知道运算过程都可以采用mod运算
这样(n^m)%p就在O(log(m))内解决了

arxor

F_n的问题考虑
向量{F_(i),F(i-1)}向{F_(i+1),F(i)}的递推
可以用矩阵乘法来表示, 然后就和前面说的一样做了

lucifer

Post by DoDo
20楼的兄弟也不要说得这么轻松,那你试试你算出那个问题需要多长时间吧

as u wish:

COREDUMP:~ lucifer$ time python test.py
4

real    0m0.207s
user    0m0.033s
sys     0m0.050s

COREDUMP:~ lucifer$ cat test.py
print 3**1000%7

这个还包括了load python解释器，parse源码，编译到bytecode的时间

DoDo

Post by lucifer
as u wish:

COREDUMP:~ lucifer$ time python test.py
4

real    0m0.207s
user    0m0.033s
sys     0m0.050s

COREDUMP:~ lucifer$ cat test.py
print 3**1000%7

这个还包括了load python解释器，parse源码，编译到bytecode的时间

兄弟似乎理解错我的意思了. 谁会花力气去算3^1000%7这种问题呢? 楼主希望大家讨论的也不是这个简单的算术运算, 而是这种a^b%c类型的问题, 明白什么叫 "算法" 吗? 它是针对一类问题的, 而不是一道题. 你要是真的想知道直接硬算为什么不好, 那么不妨就算一下楼主的第二个问题 "第200000000个Fab数模89999931", 这也是我在上面的回帖中希望你来试一试的, 而不是第一题

lucifer

我的意思就是如果不考虑实际限制，那么模取幂运算讨论的最后结果我想不会比repeated squaring这个算法好到哪里去吧。而这个和直接算的复杂度差不多。
考虑实际限制的话，高精度算法是不可避免的（也就是自己算加乘）。这个参考计原的算法就足够了。
至于你说的，那个fib(200..00)之所以慢是因为要申请一堆内存先。而一般机器上这时就需要用虚拟内存从硬盘搞了。牵涉到IO想要不慢都不行啊。

lucifer

其实只要内存足够，实际试试就知道repeated squaring和直接算差不多的。我算3**1000就是这个意思。

arxor

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

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

DoDo

我也建议Lucifer兄弟至少把大家在这一个帖子中的讨论都看一下比较好,挺长见识,而且非常有趣

P.S.按照楼主最后提供的算法,根本不需要高精度运算

lucifer

我的意思是如果考虑实际情况的话高精是必须的
例如，考虑一下给出的数字存放在一个文件里面的情况，或者就是直接生成一个巨多的位的随机数...
只要a^b mod c 中的a，b，c有一个数字超过机器可以表示的上限，那么为了对它做运算就需要高精度了吧。
单纯的考虑理想情况确实不需要高精度，因为要得到结果根本就不用做幂运算的。