Efficiency Analysis
Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up. In particular, if n is 2k, for some integer k, and the recursion stops only when n is 1, then the number of single-digit multiplications is 3k, which is nc where c = log23.
Since one can extend any inputs with zero digits until their length is a power of two, it follows that the number of elementary multiplications, for any n, is at most .
Since the additions, subtractions, and digit shifts (multiplications by powers of B) in Karatsuba's basic step take time proportional to n, their cost becomes negligible as n increases. More precisely, if t(n) denotes the total number of elementary operations that the algorithm performs when multiplying two n-digit numbers, then
for some constants c and d. For this recurrence relation, the master theorem gives the asymptotic bound .
It follows that, for sufficiently large n, Karatsuba's algorithm will perform fewer shifts and single-digit additions than longhand multiplication, even though its basic step uses more additions and shifts than the straightforward formula. For small values of n, however, the extra shift and add operations may make it run slower than the longhand method. The point of positive return depends on the computer platform and context. As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits.
Read more about this topic: Karatsuba Algorithm
Famous quotes containing the words efficiency and/or analysis:
““Never hug and kiss your children! Mother love may make your children’s infancy unhappy and prevent them from pursuing a career or getting married!” That’s total hogwash, of course. But it shows on extreme example of what state-of-the-art “scientific” parenting was supposed to be in early twentieth-century America. After all, that was the heyday of efficiency experts, time-and-motion studies, and the like.”
—Lawrence Kutner (20th century)
“Whatever else American thinkers do, they psychologize, often brilliantly. The trouble is that psychology only takes us so far. The new interest in families has its merits, but it will have done us all a disservice if it turns us away from public issues to private matters. A vision of things that has no room for the inner life is bankrupt, but a psychology without social analysis or politics is both powerless and very lonely.”
—Joseph Featherstone (20th century)