wild-inter.net Fast multiplication

Multiplying Binary Numbers

The identity Karatsuba exploits
The multiplication
Bit operations
bits the cost model's own growth, not a live run — stays fast at any n
Call stack
pseudocode

      
State
The cost model  ·  what counts as one bit operation

Both algorithms are charged in the same currency, so that the two counters can be compared:

  • one bit operation per execution of the inner-loop body of long multiplication (lines 4–6), which gives exactly n2 for an n×n-bit product;
  • one bit operation per bit position processed by an addition or a subtraction: adding two numbers of at most m bits costs m+1, subtracting costs m;
  • one bit operation for a single 1×1-bit product;
  • shifts, index arithmetic and reading a single bit are free — they are addressing, not arithmetic.

This is a model, not a theorem: it is chosen so that long multiplication costs exactly n2, matching the slide, and so that everything Karatsuba does outside its recursive calls is linear in the operand width. Constant factors in the chart below depend on these choices; the growth rates do not.

Both procedures  ·  the pseudocode this page executes
long multiplication
karatsuba
Load an input  ·  plain-text format
Write x and y in binary (10110101) or in decimal with a d prefix (d181). n pads both to a common width; Karatsuba's n = 2k variant rounds it up to a power of two.