Clear[Karatsuba]
Karatsuba[x_, y_] := 
      Module[{a, b, c, d, n, m, amalc, bmald}, 
n = 
            Length[IntegerDigits[x]]; 
m = 
            Length[IntegerDigits[y]]; 
m = 
            Max[n, m]; 
n = 1; 
          While[n < m, n = 2*n]; 
b = 
            Mod[x, 10^(n/2)]; 
a = (x - b)/
              10^(n/2); 
d = 
            Mod[y, 10^(n/2)]; 
c = (y - d)/
              10^(n/2); 
amalc = 
            Karatsuba[a, c]; 
bmald = 
            Karatsuba[b, 
              d]; 
amalc*10^
                n + (amalc + bmald + 
                  Karatsuba[a - b, d - c])*10^(n/2) + bmald] /; 
        Min[Length[IntegerDigits[x]], Length[IntegerDigits[y]]] > 
          1
Karatsuba[x_, y_] := x*y

Flatten[
        Trace[Karatsuba[1234, 5678], Karatsuba[n_, m_] -> {n, m}]] // 
      MatrixForm

$RecursionLimit = Infinity;
Clear[Karatsuba]
Karatsuba[x_, 
          y_] := (Karatsuba[x, y] = 
              Module[{a, b, c, d, n, m, amalc, bmald}, 
n = 
                  Length[IntegerDigits[x]]; 
m = 
                  Length[IntegerDigits[y]]; 
m = 
                  Max[n, m]; 
n = 1; 
                While[n < m, n = 2*n]; 
b = 
                  Mod[x, 10^(n/2)]; 
a = (x - b)/
                    10^(n/2); 
d = 
                  Mod[y, 10^(n/2)]; 
c = (y - d)/
                    10^(n/2); 
amalc = 
                  Karatsuba[a, c]; 
bmald = 
                  Karatsuba[b, 
                    d]; 
amalc*10^
                      n + (amalc + bmald + 
                        Karatsuba[a - b, d - c])*10^(n/2) + bmald]) /; 
          Min[Length[IntegerDigits[x]], Length[IntegerDigits[y]]] > 
            1;
Karatsuba[x_, y_] := x*y

Clear[Multiply]
Multiply[x_, 
          y_] := (Multiply[x, y] = 
              Module[{a, b, c, d, n, m}, 
n = 
                  Length[IntegerDigits[x]]; 
m = 
                  Length[IntegerDigits[y]]; 
m = 
                  Max[n, m]; 
n = 1; 
                While[n < m, n = 2*n]; 
b = 
                  Mod[x, 10^(n/2)]; 
a = (x - b)/
                    10^(n/2); 
d = 
                  Mod[y, 10^(n/2)]; 
c = (y - d)/
                    10^(n/2); 
Multiply[a, c]*10^
                      n + (Multiply[a, d] + 
                        Multiply[b, c])*10^(n/2) + Multiply[b, d]]) /; 
          Min[Length[IntegerDigits[x]], Length[IntegerDigits[y]]] > 
            1;
Multiply[x_, y_] := x*y

x = Random[Integer, {(10^49), (10^50)}]; 
    y = Random[Integer, {(10^49), (10^50)}];

x = Random[Integer, {(10^99), (10^100)}]; 
    y = Random[Integer, {(10^99), (10^100)}];

Timing[z1 = x*y;]

Timing[z2 = Karatsuba[x, y];]

z2 - z1

Timing[z3 = Multiply[x, y];]

x = Random[Integer, {(10^999999), (10^1000000)}]; 
    y = Random[Integer, {(10^999999), (10^1000000)}];

Timing[x*y;]