Skip to content

Instantly share code, notes, and snippets.

@burdiuz
Created November 13, 2021 17:25
Show Gist options
  • Save burdiuz/74912a8f78bd80dd07aa884e6ab9c940 to your computer and use it in GitHub Desktop.
Save burdiuz/74912a8f78bd80dd07aa884e6ab9c940 to your computer and use it in GitHub Desktop.
Karatsuba multiplication in JS
const karatsuba = (x, y, l) => {
if (l <= 2) {
return x * y;
}
const l_2 = l / 2n;
const half = 10n ** l_2;
const a = x / half;
const b = x % half;
const c = y / half;
const d = y % half;
return (
10n ** l * karatsuba(a, c, l_2) +
half * (karatsuba(a, d, l_2) + karatsuba(b, c, l_2)) +
karatsuba(d, b, l_2)
);
};
const traditionalMultiplication =
BigInt("6745896724546734658950865974635261545768459589748632415463257657") *
BigInt("9345872469823451516517615876937639745346369324563458754923465349");
const karatsubaMultiplication = karatsuba(
BigInt("6745896724546734658950865974635261545768459589748632415463257657"),
BigInt("9345872469823451516517615876937639745346369324563458754923465349"),
64n
);
console.log(karatsubaMultiplication);
console.log(traditionalMultiplication === karatsubaMultiplication);
/*
63046290482213522841036229052622386403907374545967197641214085642152283525360434286859603802055738768753469016012669606898427293n
true
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment