Advanced Algorithms: Dynamic Programming - Karatsuba Multiplication [WIP]

karatsuba.dart

import 'dart:math' as math;

int karatsubaProductOf(int x, int y) {
  print("x is $x");
  print("y is $y");
  int N = math.max(x.bitLength, y.bitLength);

  if (N <= 10) {
    return x * y;
  }

  // Number of bits halved and rounded up
  N = (N / 2).ceil();

  // Gets the right half of the digits
  int x2 = x >> N;
  print("x2 is $x2");
  int y2 = y >> N;
  print("y2 is $y2");

  // Gets the left half of the digits
  int x1 = x - (x2 << N);
  print("x1 is $x1");
  
  int y1 = y - (y2 << N);
  print("y1 is $y1");

  int x1_y1 = karatsubaProductOf(x1, y1);
  print("x1_y1 is $x1_y1");
  
  int x2_y2 = karatsubaProductOf(x2, y2);
  print("x2_y2 is $x2_y2");
  
  int x1_x2_y1_y2 = karatsubaProductOf(x1 + x2, y1 + y2);
  print("x1_x2_y1_y2 is $x1_x2_y1_y2");
  
  
  int z = x1_x2_y1_y2 - x1_y1 - x2_y2;

  return math.pow(10, N) * x1_y1 + math.pow(10, N / 2) * z + x2_y2;
}

void main() {
  print(karatsubaProductOf(0, 0));
  print("---------------------------------");
  
  print(karatsubaProductOf(12, 3456));
  assert(karatsubaProductOf(12, 3456) == 41472, true);
  print("---------------------------------");
//   print(karatsubaProductOf(1234, 5678));
//   assert(karatsubaProductOf(1234, 5678) == 7006652);
//   print("---------------------------------");
//   print(karatsubaProductOf(-1234, -5678));
//   print("---------------------------------");
//   print(karatsubaProductOf(1234, -5678));
//   print("---------------------------------");
//   print(karatsubaProductOf(-1234, 5678));
//   print("---------------------------------");
}