Comment

Comment by less_less

Yeah, that shift-and-add algorithm is sometimes used on microcontrollers, either in software if there's no hardware multiplier, or in hardware if you want the bare minimum in acceleration at a tiny cost in area.

Adds are not really considered negligible; the article is just sloppy. (Some shifts might be negligible in some models because a fixed shift requires no logic gates.) The cost of the adds in Karatsuba is significant both theoretically and in practice, and determines the cutoff where Karatsuba is useful. But the exponent in O(n^(log_2 3)) is dominated by the recursive multiplications; the adds only affect the leading constant hidden in the O().

parent less_less 3 months ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton