Sign In Sign Up Ask an AI advisor
Sebs1
Sebs1
06.05.2020 • 
Mathematics

The conventional way of multiplying two n-bit integers requires O(n2) time. There are much better ways of multiplying long integers, based on a divide-and-conquer approach. For example, we can break each n-bit integer into n/2-bit halves, and produce the result by making 3 recursive calls to n/2-bit multiplications (which are themselves done in this clever way) and several additions of n/2-bit integers. Since addition of n-bit numbers only requires O(n) time, you get a recurrence for the running time of T(n) = 3T(n/2) + cn for some constant c (which, asymptotically, doesn't matter). This algorithm is sometimes referred to as the "Karatsuba-Ofman (KO) Algorithm." Hypothetically, we can beat the KO approach if we can break our two n-bit numbers into y pieces of length n/y, and perform the multiplication of n-bit numbers by using x recursive multiplications of n/y bit numbers plus any constant number of additions of n/y-bit numbers. What is the relationship between x and y that would make this hypothetical algorithm have a lower running time than the KO Algorithm? Identify one such pair below. Note, because the exact calculation requires the computation of logarithms, you may wish to find and use a scientific calculator of some sort.

Solved
Show answers

Ask an AI advisor a question

I want advice