锈菌中的Karatsuba增殖

Question

这是用于乘法的Karatsuba算法的实现：

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

我很想知道如何使这个更快更朴素。

Answer 1

我只能想到使用基数10的两个很好的理由：

1. 代码的目的是教书，而被教授的人(可以是你自己)或者被教导的人比第二基数更适合使用10。
2. 整数的基本表示形式为基数10。

请注意，案例2是极不可能的。既然你问的是速度，我想情况1也不适用(尽管见下文)。因此，您可能应该使用一个基数，它的幂为2。唯一不正确的情况是，分析显示瓶颈是将最终输出转换为基10以供打印，因此您选择编写一个自定义大整数实现，该实现使用的基数为10:我个人遇到过这种情况，并选择了基数1000000000，这样基将适合32位整数，并将两位数字的乘积与64位整数相匹配。

请注意，使用基数为2的幂意味着所有的电源操作都可以通过位移位来完成，或者如果您能够访问一个大整数的内部数据结构，然后通过索引调整。

还请注意上面对大整数的引用。工作(isize, isize) -> isize，除了教学目的外，没有必要使用Karatsuba。使用*会更快。