问题描述
免责声明：家庭作业问题。我正在寻找提示……
Disclaimer: Homework question. I'm looking for a hint…
L教授告诉他的班级，对一个n位整数进行平方比用两个n位整数相乘的渐近速度更快。他们应该相信他吗？
Professor F. Lake tells his class that it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers. Should they believe him?
我相信通过shift / add将两个n位整数相乘是O（n）运算，但是我看不出为什么对n位int将有所不同。我错过了什么吗？
I believe that multiplying two n-bit ints via shift/add is an O(n) operation, but I can't see why squaring an n-bit int would be any different. Am I missing something?
推荐答案
由于只需要一个提示，答案来自以下等式：（ a + b）^ 2 = a ^ 2 + b ^ 2 + 2 * a * b
Since you wanted only a hint, answer comes from this equation: (a + b)^2 = a^2 + b^2 + 2*a*b
为了不破坏这个难题，我已发布完整的解决方案：）
To not spoil the puzzle, I've posted complete solution separately :)
这篇关于平方n位整数与两个n位整数相乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！