平方n位整数与两个n位整数相乘

本文介绍了平方n位整数与两个n位整数相乘的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

免责声明：家庭作业问题。我正在寻找提示……

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 :)