Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save biancadanforth/c2f741e7103505e5a40e589c75bf9742 to your computer and use it in GitHub Desktop.
Save biancadanforth/c2f741e7103505e5a40e589c75bf9742 to your computer and use it in GitHub Desktop.
// From https://www.coursera.org/learn/algorithms-divide-conquer/home/welcome
// Assignment: https://www.coursera.org/learn/algorithms-divide-conquer/exam/srsxO/programming-assignment-1
/**
* Assignment: Implement a recursive integer multiplication and/or Karatsuba's
* algorithm to compute the product of the following two 64-digit numbers:
* - 3141592653589793238462643383279502884197169399375105820974944592
* - 2718281828459045235360287471352662497757247093699959574966967627
* Constraints:
* - Multiply only pairs of single digit numbers
* Test Cases:
* 1. What if n is odd (&& n !== 1, which is covered)?
* 2. What if n is not a power of 2? (the only explicit assumption for Karatsuba)
* 3. What if nY !== nX?
* - If both are a power of 2, it works.
* - ...
* Base Case:
* - How to know when to stop the recursion? When the length of the input
* numbers is 1.
*/
/**
* Pseudocode:
* 1. Compute a * c
* 2. Compute b * d
* 3. Compute (a + b) * (c + d)
* 4. Compute 3) - 2) - 1)
* 5. Sum [10^n](ac) + [10^(n/2)](ad + bc) + bd
*/
// original x: 3141592653589793238462643383279502884197169399375105820974944592
// original y: 2718281828459045235360287471352662497757247093699959574966967627
const x = 3141592653589793238462643383279502884197169399375105820974944592;
const y = 2718281828459045235360287471352662497757247093699959574966967627;
const product = x * y;
const karatsubaProduct = karatsubaV3(x,y);
console.log(`Product: ${product}
Karatsuba Product: ${karatsubaProduct}`);
console.log(product === karatsubaProduct);
// ~~~~~~~~~~~~~~~~~~ ATTEPMT 3 (BELOW) ~~~~~~~~~~~~~~~~~~~~~~
// TODO: THIS IS CURRENTLY A COPY OF ATTEMPT 2
/**
* Assumptions:
* - Can we eliminate the assumptions we have to make in Attempt 2?
* Put another way, can we "massage" the inputs so that the assumptions
* still hold? See Algorithms Illuminated textbook, pg. 9 footnote for
* a hint.
*
* TODO: Consider edge cases in Attempt 3, as Attempt 2 does not.
* See Test Cases enumerated above. There could be more I haven't
* thought of.
*/
function karatsubaV3(x,y) {
// TODO: Find better, more flexible way to get n
let n = parseInt(Math.log10(x)) + 1 || 1; // Math.log10(0) = -Infinity...
// Base case
if (n === 1) {
return x * y;
}
const a = Math.floor(x/(Math.pow(10, n/2)));
const b = x - (a * Math.pow(10, n/2));
const c = Math.floor(y/(Math.pow(10, n/2)));
const d = y - (c * Math.pow(10, n/2));
// Step 1: Compute a * c
const ac = karatsubaV3(a, c);
// Step 2: Compute b * d
const bd = karatsubaV3(b, d);
// Step 3: Compute (a + b) * (c + d)
const abcd = karatsubaV3(a + b, c + d);
// Step 4: Compute 3) - 2) - 1) (yields ad + bc)
const adbc = abcd - bd - ac;
// Step 5: Sum [10^n](ac) + [10^(n/2)](ad + bc) + bd
return Math.pow(10, n) * ac + Math.pow(10, n/2) * adbc + bd;
}
// ~~~~~~~~~~~~~~~~~~ ATTEPMT 2 (BELOW) ~~~~~~~~~~~~~~~~~~~~~~
/**
* Assumptions:
* - x.length = y.length = n
* - n is a power of 2
*
* Does not currently handle any Test Cases. Improves on Attempt 1
* because it only makes 3 recursive calls. In fact, since Attempt 1
* makes more than 3 recursive calls, it is not the Karatsuba
* implementation (see S.1.3.3 in Algorithms Illuminated textbook).
*/
function karatsubaV2(x,y) {
// TODO: Find better, more flexible way to get n
let n = parseInt(Math.log10(x)) + 1 || 1; // Math.log10(0) = -Infinity...
// Base case
if (n === 1) {
return x * y;
}
const a = Math.floor(x/(Math.pow(10, n/2)));
const b = x - (a * Math.pow(10, n/2));
const c = Math.floor(y/(Math.pow(10, n/2)));
const d = y - (c * Math.pow(10, n/2));
// Step 1: Compute a * c
const ac = karatsubaV2(a, c);
// Step 2: Compute b * d
const bd = karatsubaV2(b, d);
// Step 3: Compute (a + b) * (c + d)
const abcd = karatsubaV2(a + b, c + d);
// Step 4: Compute 3) - 2) - 1) (yields ad + bc)
const adbc = abcd - bd - ac;
// Step 5: Sum [10^n](ac) + [10^(n/2)](ad + bc) + bd
return Math.pow(10, n) * ac + Math.pow(10, n/2) * adbc + bd;
}
// ~~~~~~~~~~~~~~~~~~ ATTEPMT 1 (BELOW) ~~~~~~~~~~~~~~~~~~~~~~
/**
* Takes input strings x and y, parses them into integers, and computes the product.
* TODO: Shouldn't rely on JS coercing integers into a number?
*/
// function karatsubaV1(x, y) {
// if (x.length === 1) {
// return x*y;
// }
// const nX = x.length;
// const nY = y.length;
// const n = Math.max(nX, nY);
// // TODO: Need to handle the case that nX or nY is odd; can't pass a fraction to substring...
// const a = x.substring(0, nX/2);
// const b = x.substring(nX/2, nX);
// const c = y.substring(0, nY/2);
// const d = y.substring(nY/2, nY);
// return (
// Math.pow(10, n)*karatsubaV1(a, c) + Math.pow(10, n/2)*(karatsubaV1(a, d) +
// karatsubaV1(b, c)) + karatsubaV1(b, d)
// );
// }
// karatsuba(x, y);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment