# Karatsuba multiplication in Rust

This is an implementation of the Karatsuba algorithm for multiplication:

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);
}


I'd love to know how to make this faster and rustier.

Note also the reference to big integers above. Working (isize, isize) -> isize, there's no point using Karatsuba except for teaching purposes. It would be faster to use *.