architecture - Why are multiplication algorithms needed if hardware already does it? -

i learning karatsuba algorithm fast integer multiplication , wondered, since computers have dedicated hardware built cpus multiplication why algorithm necessary?

is large numbers hard multiply, algorithm breaks down simpler steps easier hardware handle, because hardware @ multiplying smaller numbers?

1. all cpu has fixed bit width alu/fpu.

   for example on i80x86 (pc) alu limited to:

   i8086+   16 bit i80386+  32 bit x64 arch 64 bit 

   allowing compute 16/32/64 bit numbers operands. i80x87 fpu use 80 bit number representations converted from/to ieee float(32bit)/double(64bit) limiting precision.

2. if need compute numbers bigger bit width hw limit

   then need break down chunks computable on alu/fpu (and handle them digits of number) , combine results final value. alu counting , why cpu's have carry flag , alu support adding , substracting carry. if doing simple +/- add/subs digits lowest (lsw) highest (msw) propagating carry. see:

   • cant make value propagate through carry

   the multiplication , division more complex , need use long algorithms (like computing on paper) o(n^2). n number of "digits". 1 digit 8/16/32/64 bit number or biggest 10^m base number. while computing small numbers (up few 100x bits) there no gain more advanced algorithms because have overhead. bigger numbers situation turns in favor of them. see:

   • fast bignum sqr

   computing big floating point numbers tricky , faster done on integer arithmetics alu instead in fpu in general. still in occasions can benefit fpu if break values more variables example enhance accuracy while summing/integrating see:

   • is possible make realistic n-body solar system simulation in matter of size , mass? last edit