相关疑难解决方法(0)

假设我们有一个问题，某个算法（我们称之为算法_1）的时间复杂度为 ，O(n^2)另一个算法（我们称之为算法_2）的时间复杂度为O(n)，但实际上我们看到n < 1000算法_1 更快，否则算法_2 更快是比较快的。

为什么我们不能直接写这样的代码：

if ( n < 1000)
  do algorithm_1
else
  do algorithm_2

这是程序员真正做的事情还是有缺点？

对于较小的程序，这似乎是一个好主意。

当我正在学习C时,我只是经历了一些基本的东西.我遇到了一个问题,即在不使用*运算符的情况下将数字乘以7.基本上就是这样的

      (x << 3) - x;

现在我知道基本的位操作操作,但我不知道如何在不使用*运算符的情况下将数字乘以任何其他奇数？这是一般的算法吗？

给定大小为N的整数数组A,我想计算

这是过去大学间编程竞赛中的一个问题.我们必须写这将解决了这个问题的5实例程序,与ñ  ≤200,000,每一个_我  ≤20万辆,20秒运行时间限制内.显然,O(N ²)解决方案将超过时限.根据社论,预期的解决方案涉及使用快速傅里叶变换的多项式乘法.我正在寻找可以比没有FFT(也不是NTT)的朴素O(N ²)算法更快地解决这个问题的替代算法.这个问题有没有简单而优雅的解决方案？

已知事实:

mod可以在产品内"分布",因为(x*y)%m =((x%m)*(y%m))%m

更新:这是比赛期间的输入/输出测试用例文件:如果它在20秒内通过,它将被接受.输入:https ://www.dropbox.com/s/nw81hts9rniter5/algol.in?dl =0输出:https://www.dropbox.com/s/kpa7wit35xr4xm4/algol.out? dl =0

我在一些在线论坛上看到了以下面试问题.对此有什么好的解决方案？

获取5 ^ 1234566789893943的最后1000位数字

I wanted to use NTT for fast squaring (see Fast bignum square computation), but the result is slow even for really big numbers .. more than 12000 bits.

So my question is:

1. Is there a way to optimize my NTT transform? I did not mean to speed it by parallelism (threads); this is low-level layer only.
2. Is there a way to speed up my modular arithmetics?

This is my (already optimized) source code in C++ for NTT (it's complete …

免责声明:家庭作业问题.我正在寻找一个提示......

F. Lake教授告诉他的班级,对n位整数进行平方而不是乘以两个n位整数是渐进式的.他们应该相信他吗？

我相信通过shift/add将两个n位的整数相乘是一个O(n)运算,但我不明白为什么对n位int进行平方会有所不同.我错过了什么吗？

我试图在硬件中实现一个32位浮点硬件分频器,我想知道我是否可以得到任何关于不同算法之间的权衡的建议？

我的浮点单元目前支持乘法和加法/减法,但我不打算将其切换到融合乘法 - 加法(FMA)浮点架构,因为这是一个嵌入式平台,我试图最小化区域使用.

我将大整数编码为一个数组size_t.我已经有其他操作工作(加,减,乘); 以及一位数的划分.但是如果可能的话,我想匹配乘法算法的时间复杂度(目前Toom-Cook).

我收集有线性时间算法,用于采用我的红利的乘法逆的各种概念.这意味着我理论上可以在与乘法相同的时间复杂度中实现除法,因为无论如何,线性时间操作通过比较是"无关紧要的".

我的问题是,我该怎么做呢？什么类型的乘法逆在实践中最好？模数64^digitcount？当我将乘法逆乘以我的除数时,我可以推卸计算由于整数截断而丢弃的数据部分吗？任何人都可以提供C或C++伪代码或准确解释应该如何做到这一点？

或者是否存在比基于逆的方法更好的专用除法算法？

编辑:我挖出了上面提到的"反向"方法.在"Art of Computer Programming,Volume 2:Seminumerical Algorithms"的第312页上,Knuth提供了"算法R",它是一种高精度的倒数.他说它的时间复杂度小于乘法的时间复杂度.然而,将它转换为C并测试它并且不清楚将消耗多少开销内存等,直到我对其进行编码,这将花费一些时间,这是非常重要的.如果没有人打败我,我会发布它.

我使用除法算法。

根据https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations，除法具有时间复杂度（以下之一）：

O(n log n log log n)
O(n log n 2O(log* n))
O(n**2)
O(M(n))

到目前为止，我在 Python 中使用了这个算法，但我需要在平台上独立描述它。对于今天的 Python（或类似语言）用户来说，这些时间复杂度定义中的哪一个是正确的？

作为一个业余爱好项目,我正在努力寻找真正庞大的素数.对此的素性测试包含模幂运算,即a ^ modn.让我们称之为modpow操作,以使解释变得简单.我想加快这个特定的计算.

目前我正在使用GMP的mpz_pown函数,但是,它有点慢.我认为它太慢的原因是因为对GMP的modpow的函数调用比对相同大数字的PFGW软件的完整素性测试要慢.(所以要清楚,这只是GMP的modpow部分,而不是我正在比较的整个自定义素性测试程序).PFGW被认为是其领域中最快的,对于我的用例,它使用了Brillhart-Lehmer-Selfridge素性测试 - 它也使用了modpow程序 - 所以不是因为数学上的聪明,PFGW在这方面更快(请纠正我,如果我错了.)看起来GMP的瓶颈是modpow操作.数字的示例运行时间略超过20,000个数字:GMP的modpow操作大约需要45秒,而PFGW在9秒内完成整个素数测试(包括一个modpow).对于更大的数字,差异变得更加令人印象深刻.GMP使用FFT乘法和蒙哥马利减少进行此测试比较,请参阅下面这篇文章的评论.

我做了一些研究.到目前为止,我理解modpow算法通过平方,整数乘法和模数减少使用取幂 - 这些对我来说都非常熟悉.几种辅助方法可以改善整数乘法的运行时间:

• 蒙哥马利乘法
• FFT乘法

为了通过平方部分来改善取幂的运行时间,可以使用有符号的数字表示来减少乘法的数量(即,比特表示为0,1或-1,并且比特串以这样的方式表示,使得它包含的零比原始的base-2表示更多 - 这通过平方减少了求幂的运行时间.

为了优化操作的模数部分,我知道这些方法:

• 蒙哥马利减少

所以这是150,000美元的问题:有一个软件库可以在给定非常大的基数,指数和模数的情况下有效地进行modpow操作吗？(我的目标是数百万的数字).如果您想建议一个选项,请尝试解释算法的内部工作原理,包括基数,模数和指数的数百万位数,因为有些库根据位数使用不同的算法.基本上我正在寻找一个支持上述技术的库(或者可能更聪明的技术),并且它在运行算法时应该运行良好(至少比GMP好).到目前为止,我已经搜索,发现并尝试了GMP和PFGW,但没有发现这些令人满意(PFGW很快,但我只对modpow操作感兴趣并且没有直接的编程接口).我希望可能是该领域的专家可以建议具有这些功能的库,因为似乎很少有能够处理这些要求的库.

编辑:使问题更简洁,因为它标记得太宽泛.