Karatsuba algorithm: Difference between revisions

Content deleted Content added
Basic step: clarification
m Example: gr: demands a conjunction (as) rather than a preposition (like).
Line 91:
: ''z''<sub>1</sub> = ('''12''' + '''345''') '''×''' ('''6''' + '''789''') − ''z''<sub>2</sub> − ''z''<sub>0</sub> = 357 '''×''' 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538
 
We get the result by just adding these three partial results, shifted accordingly (and then taking carries into account by decomposing these three inputs in base ''1000'' likeas for the input operands):
: result = ''z''<sub>2</sub> · (''B''<sup>''m''</sup>)<sup>''2''</sup> + ''z''<sub>1</sub> · (''B''<sup>''m''</sup>)<sup>''1''</sup> + ''z''<sub>0</sub> · (''B''<sup>''m''</sup>)<sup>''0''</sup>, i.e.
: result = 72 · ''1000''<sup>2</sup> + 11538 · ''1000'' + 272205 = '''83810205'''.