optimize karatsuba

Xuefeng-Zhu · Xuefeng-Zhu · commit ceefd98f8203 · 2015-05-12T22:24:36.000-05:00
diff --git a/sorting and basics/karatsuba.py b/sorting and basics/karatsuba.py
@@ -6,17 +6,17 @@ def karatsuba(x, y, b=10):
     >>> karatsuba(1234223123412323, 1234534213423333123)
     1523690672850721578619752112274729L
     """
-    nx, ny = len(str(x))/2, len(str(y))/2
-    if x < 1000 or y < 1000: return x * y
-    m = nx if nx < ny else ny
-    x1 = x / (b**m)
-    x0 = x % (x1 * (b**m))
-    y1 = y / (b**m)
-    y0 = y % (y1 * (b**m))
-    z1 = karatsuba(x1,y1,b)
-    z3 = karatsuba(x0,y0,b)
+
+    if x < 1000 or y < 1000:
+        return x * y
+    m = min(len(str(x)) / 2, len(str(y)) / 2)
+    bm = b**m
+    x1, x0 = x / bm, x % bm
+    y1, y0 = y / bm, y % bm
+    z1 = karatsuba(x1, y1, b)
+    z3 = karatsuba(x0, y0, b)
     z2 = karatsuba(x1 + x0, y1 + y0, b) - z1 - z3
-    return (b**(2*m))*z1 + (b**m)*z2 + z3
+    return (bm**2)*z1 + bm*z2 + z3
 
 if __name__ == "__main__":
     import doctest
