This is an implementation of the Karatsuba algorithm, it supports multiplying positive numbers:

This is an implementation of the Karatsuba algorithm for multiplication:

use std::cmp::max;

/// Multiplies two numbers using the Karatsuba algorithm.
/// Note: Doesn't currently support multiplying negative numbers
fn karatsuba(a: isize, b: isize) -> isize {
    // Single digit multiplication: no need for Karatsuba
    if a < 10 || b < 10 {
        a * b
    } else {
        let nr_of_digits = max(get_nr_of_digits(a), get_nr_of_digits(b));

        let (p, q) = split_at(nr_of_digits / 2, a);
        let (r, s) = split_at(nr_of_digits / 2, b);

        let u = karatsuba(p, r);
        let v = karatsuba(q - p, s - r);
        let w = karatsuba(q, s);

        let raised_u = u * 10_isize.pow(nr_of_digits);
        let raised_u_w_v = (u + w - v) * 10_isize.pow(nr_of_digits / 2);

        // That's the product of a and b
        raised_u + raised_u_w_v + w
    }
}

/// Gets the number of digits in a number. For example:
/// get_nr_of_digits(12345) == 5
fn get_nr_of_digits(x: isize) -> u32 {
    let mut nr_of_digits = 1;
    let mut copy = x;
    while copy > 9 {
        copy /= 10;
        nr_of_digits += 1;
    }

    nr_of_digits
}

/// Splits a number at a position. For example:
/// split_at(2, 1234) == (12, 34)
/// Is this faster than turning the number into a string and splitting that?
fn split_at(pos: u32, x: isize) -> (isize, isize) {
    let power = 10_isize.pow(pos);
    let first = x / power;
    let last = x - first * power;

    (first, last)
}

#[test]
fn karatsuba_works() {
    assert_eq!(karatsuba(12, 34), 12 * 34);
    assert_eq!(karatsuba(3, 4), 3 * 4);
    assert_eq!(karatsuba(5678, 4321), 5678 * 4321);
    assert_eq!(karatsuba(678, 4321), 678 * 4321);
    // Multiplying negative numbers is not yet implemented
    //assert_eq!(karatsuba(-678, 432), -678 * 432);
}

#[test]
fn get_nr_of_digits_works() {
    assert_eq!(get_nr_of_digits(0), 1);
    assert_eq!(get_nr_of_digits(10), 2);
    assert_eq!(get_nr_of_digits(12345), 5);
    assert_eq!(get_nr_of_digits(87654321), 8);
}

use std::cmp::max;

/// Multiplies two numbers using the Karatsuba algorithm
fn karatsuba(a: isize, b: isize) -> isize {
    // Single digit multiplication: no need for Karatsuba
    if a < 10 && b < 10 {
        a * b
    } else {
        let nr_of_digits = max(get_nr_of_digits(a), get_nr_of_digits(b));

        let half_nr_of_digits = nr_of_digits / 2;

        let (p, q) = split_at(half_nr_of_digits, a);
        let (r, s) = split_at(half_nr_of_digits, b);

        let u = karatsuba(p, r);
        let w = karatsuba(q, s);
        let v = karatsuba(p + q, r + s);

        // Since we used integer division for half_nr_of_digits,
        // half_nr_of_digits * 2 is not always equal to nr_of_digits.
        // For example when nr_of_digits is 9.
        let raised_u = u * 10_isize.pow(half_nr_of_digits * 2); 

        let raised_v_w_u = (v - w - u) * 10_isize.pow(half_nr_of_digits);

        // That's the product of a and b
        raised_u + raised_v_w_u + w
    }
}

/// Gets the number of digits in a number. For example:
/// get_nr_of_digits(12345) == 5
fn get_nr_of_digits(x: isize) -> u32 {
    let mut nr_of_digits = 1;
    let mut copy = x;
    while copy > 9 {
        copy /= 10;
        nr_of_digits += 1;
    }

    nr_of_digits
}

/// Splits a number at a position. For example:
/// split_at(2, 1234) == (12, 34)
fn split_at(pos: u32, x: isize) -> (isize, isize) { 

    let power = 10_isize.pow(pos); 

    let high = x / power;
    let low = x % power;
    (high, low)
}

#[test]
fn split_at_works() {
    assert_eq!(split_at(2, 1234), (12, 34));
    assert_eq!(split_at(1, 67), (6, 7));
    assert_eq!(split_at(2, 67), (0, 67));
    assert_eq!(split_at(2, 674), (6,74));
    assert_eq!(split_at(2, 67461), (674, 61));
    assert_eq!(split_at(3, 674610), (674, 610));
}

#[test]
fn karatsuba_works() {
    // Positive numbers
    assert_eq!(karatsuba(12, 34), 12 * 34);
    assert_eq!(karatsuba(3, 4), 3 * 4);
    assert_eq!(karatsuba(5678, 4321), 5678 * 4321);
    assert_eq!(karatsuba(678, 4321), 678 * 4321);
    assert_eq!(karatsuba(67, 65432), 67 * 65432);
    assert_eq!(karatsuba(671, 654), 671 * 654);
    assert_eq!(karatsuba(6781001, 6542001), 6781001 * 6542001);
    assert_eq!(karatsuba(671, 654), 671 * 654);
    assert_eq!(karatsuba(67, 654321), 67 * 654321);
    assert_eq!(karatsuba(678032, 432132012), 678032 * 432132012);

    // Negative numbers
    assert_eq!(karatsuba(-678, 432), -678 * 432);
    assert_eq!(karatsuba(678032, -232132012), 678032 * -232132012);
    assert_eq!(karatsuba(571, -654), 571 * -654);
}

#[test]
fn get_nr_of_digits_works() {
    assert_eq!(get_nr_of_digits(0), 1);
    assert_eq!(get_nr_of_digits(10), 2);
    assert_eq!(get_nr_of_digits(12345), 5);
    assert_eq!(get_nr_of_digits(87654321), 8);
}