Algorithms Coursera Programming Assignment 1.js

// 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);