Karatsuba multiplication in Rust

Question

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.

Answer 1

I can only think of two good reasons for using base 10:

1. The purpose of the code is to teach, and the person (could be yourself) or people being taught are more comfortable with base 10 than base 2.
2. The underlying representation of the integers is in base 10.

Note that case 2 is extremely unlikely. And since you're asking about speed, I assume that case 1 doesn't apply either (although see below). Therefore you should probably be using a base which is a power of 2. The only case in which this isn't true is where profiling showed that the bottleneck was converting your final output to base 10 for printing and so you chose to write a custom big integer implementation which uses a base which is a power of 10: I have personally encountered this situation, and chose to work base 1000000000 so that the base would fit in a 32-bit integer and the product of two digits fit within a 64-bit integer.

Note that working with a base which is a power of 2 means that all of the power operations can be done with bitshifts, or if you're able to access the internal data structure of a big integer then by index adjustments.

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 *.