Question

Professor F. Lake tells his class that it is asymptotically faster to square an -bit integer than to multiply two n-bit integers. Should they believe him?

Short answer

No, the statement of Professor F. Lake is wrong.

Step-by-step solution

Introduction

Evaluate the following details:

• The algorithm's execution time is determined using asymptotic notations.

• According to the Professor, the n-bit integer algorithm squaring is faster than multiplying two n-bit integers.

• The algorithm's asymptotic value is determined by the number of items and actions in the algorithm.

Correct Fact

“No”, students should not believe the professor.

Description:

• When an n-bit integer is squared, numerous cross-terms become equal.

• As a result, there's no need to do it again.

• Take the 3-bit integer "1012" as an example.

• This number is written as a₂, a₁ , and a₀ from left to right.

• If you square this number, you'll obtain 9 terms.

• In the matrix below, the terms are listed.

$\left[\begin{array}{ccc}{a}_2{a}_2& a_2{a}_1& a_2{a}_0\\ a_1{a}_2& a_1{a}_1& a_1{a}_0\\ a_0{a}_2& a_0{a}_1& a_0{a}_0\end{array}\right]$

• This is a symmetric matrix. Because the primary diagonal's components are all the same.

• In other words, certain elements do not require calculation.

• As a result, this approach for squaring n-bit values is not asymptotically superior.

• This algorithm will benefit from a steady pace.,

As a result, Professor is incorrect in his assertion that the fast-squaring method may be improved at a constant pace.