This repository contains the code for an experimental implementation of the Karatsuba multiplication algorithm in C that uses the divide-and-conquer algorithm.

• GCC (GNU Compiler Collection)
• Make

Clone the repository and change into the directory:

git clone https://github.com/drifter1/karatsuba-c.git
cd karatsuba-c

To build the binary simply type make in this directory.

Launch the command-line interface using ./bin/karatsuba. Example usage and output below.

Karatsuba Parameters: B = 10, K = 9, M = 3
X: 12345
Y: 6789
-----Karatsuba Recursion for 12345 • 06789-----
X = 12345 = X1 • 10^3 + X0 = 12 • 10^3 + 345
Y = 06789 = Y1 • 10^3 + Y0 = 06 • 10^3 + 789
  -----Direct Calculation of 345 • 789-----
Z0 = X0 • Y0 = 345 • 789 = 272205
  -----Direct Calculation of 12 • 06-----
Z2 = X1 • Y1 = 12 • 06 = 72
  -----Direct Calculation of 357 • 795-----
Z1 = (12 + 345) • (06 + 789) = 357 • 795 = 283815
12345 • 06789 = 72 • 10^6 + (283815 - 72 - 272205) • 10^3 + 272205 = 72 • 10^6 + 11538 • 10^3 + 272205 = 83810205
Z: 83810205

To clean the binary executable, you just have to type make clean.

Published under the GPL-3.0 license - see LICENSE file for details.

This is an experimental implementation that will not work with all inputs. It has been uploaded purely out of goodwill. Please keep this in mind when using it. Thank you!