from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import math


def karatsuba_multiplication(x, y):
    """Multiply 2 n-bits integers by Karatsuba's algorithm.

    This is a divide-and-conquer algorithm.
  
    We would like to multiply two long n-bits integers, where
      x = x_L * 10^(n/2) + x_R
      y = y_L * 10^(n/2) + y_R
    Since
      xy = 2^n x_L y_L + 2^(n/2) (x_L y_R + x_R y_L) + x_R y_R
         = 2^n x_L y_L 
           + 2^(n/2) [(x_L + x_R)((y_L + y_R) - x_L y_L - x_R y_R] 
           + x_R y_R

    Time complexity: O((n+n)^log3) = O(n^1.59), much faster than 
    the naive one with O(n^2).
    """
    x_n = int(math.log10(x)) + 1
    y_n = int(math.log10(y)) + 1
    if x_n != y_n:
        raise ValueError('The 2 integers are not of equal length.')
    else:
        n = x_n
    x_L, x_R = divmod(x, 10 ** (n // 2))
    y_L, y_R = divmod(y, 10 ** (n // 2))
    mul_L = x_L * y_L
    mul_R = x_R * y_R
    sum_mul = (x_L + x_R) * (y_L + y_R)
    mul = (
        mul_L * (10 ** ((n // 2) * 2))
        + (sum_mul - mul_L - mul_R) * (10 ** (n // 2))
        + mul_R)
    return mul


def main():
    x = 1234
    y = 1234
    print('(x, y): ({}, {})'.format(x, y))
    print('Multiply: {}'.format(karatsuba_multiplication(x, y)))

    x = 12345
    y = 12345
    print('(x, y): ({}, {})'.format(x, y))
    print('Multiply: {}'.format(karatsuba_multiplication(x, y)))

if __name__ == '__main__':
    main()

@@ -597,17 +597,19 @@
 ty: O((n
-+
+ + 
 n)%5Elog3)
@@ -622,16 +622,21 @@
 %5E1.59), 
+%0A    
 much fas
@@ -644,21 +644,16 @@
 er than 
-%0A    
 the naiv

Revise docstring: complexity