模法导论(番外)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

说说两个有趣的关于求模的算法.

第一个是阶乘求模.这个么,其实规模小的时候$\left( {a!\bmod n\quad a < n < {{10}^6}} \right)$也没什么优化可用.硬刚吧.

  1. 先朴素的把这个数算出来然后求模0.23s,good.
  2. 自己造个轮子把数算出来然后求模,0.70s,233,说了不要自己造轮子.
  3. 用Fold折叠列表,边乘边模,0.12s,Excellent! 如果是Haskell的话应该会更快吧,第一有惰性计算,第二乘法计算速度真的丧心病狂,当初刷OJ直接写a*b过了大数乘法,而且还是第一.......
  4. 所以我们想能不能从两边一起折叠这个列表,Sorry,MMA没有这种的,然后想到要是对折这个列表岂不是可以有${\log _2}n$的算法了?想得美,0.82s.
  5. 好吧对折太慢了,应该一次折叠100重,0.23s.Well,看来多出来的那么多次乘法和取模不管怎样反而消耗了更多的资源呐.
  6. 所以我们来用循环吧!1.02s,666,说了MMA里能不用循环就不要用循环,特别是不编译直接正面刚,而且用了编译还不如全部用C#写然后Link进来.我用C#写了个naïve的循环确实是0.1s左右.
  7. 想到个折中的办法,Nest尾递归一个二元组就不用维护列表了.0.16s,唔,不是很懂怎么搞的,会比Fold慢好玄学啊.

Read More