平方n位int与两位n位int相乘

Question

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

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

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

Answer 1

既然你只想要一个提示,答案来自这个等式: (a + b)^2 = a^2 + b^2 + 2*a*b

为了不破坏的困扰,我已经发布了完整的解决方案分别 :)

Answer 2

想象一下,平方实际上渐近更快.然后,如果你有一个*b,你可以计算:

a = m + n
b = m - n

然后求解这个方程系统给出:

m = (a+b)/2
n = (a-b)/2

但是我们有

a * b = (m+n)*(m-n) = m² - n²

或没有中间变量:

a * b = ((a+b)² - (a-b)²)/4

所以你可以用两个平方运算代替任何乘法(和一些加法和除以4,这只是一个位移,并且这些都可以被渐近的复杂性忽略).因此,乘法的复杂性至多是平方复杂度的两倍.当然,"两次"是一个常数因子,这意味着两者具有相同的渐近复杂性.

Answer 3

考虑计算机完成这些任务所需采取的步骤。请记住，计算机的工作方式与人截然不同。