num crate 中的大整数实现是否很慢？

Question

我使用 BigUint 在 Rust 中实现了 Miller-Rabin 强伪素数测试以支持任意大素数。到运行通过5到10^6之间的数字，用了40s左右cargo run --release.

我用 Java 的 BigInteger 实现了相同的算法，同样的测试用了 10 秒才完成。 Rust 似乎慢了 4 倍。我假设这是由 num::bigint 的实施引起的。

这只是 num::bigint 的当前状态，还是有人能发现我的代码有任何明显的改进？（主要是关于我如何使用这门语言的。无论我的算法实现是好是坏，它在两种语言中的实现几乎完全相同 - 所以不会造成性能差异。）

我注意到有很多 clone() 需要，由于 Rust 的所有权模型，这可能会在某种程度上影响速度。但我想没有办法解决这个问题，对吗？

代码如下：

extern crate rand;
extern crate num;
extern crate core;
extern crate time;

use std::time::{Duration};
use time::{now, Tm};

use rand::Rng;
use num::{Zero, One};
use num::bigint::{RandBigInt, BigUint, ToBigUint};
use num::traits::{ToPrimitive};
use num::integer::Integer;
use core::ops::{Add, Sub, Mul, Div, Rem, Shr};

fn find_r_and_d(i: BigUint) -> (u64, BigUint) {
    let mut d = i;
    let mut r = 0;
    loop {
        if d.clone().rem(&2u64.to_biguint().unwrap()) == Zero::zero() {
            d = d.shr(1usize);
            r = r + 1;
        } else {
            break;
        }
    }
    return (r, d);
}

fn might_be_prime(n: &BigUint) -> bool {
    let nsub1 = n.sub(1u64.to_biguint().unwrap());
    let two = 2u64.to_biguint().unwrap();

    let (r, d) = find_r_and_d(nsub1.clone());
    'WitnessLoop: for kk in 0..6u64 {
        let a = rand::thread_rng().gen_biguint_range(&two, &nsub1);
        let mut x = mod_exp(&a, &d, &n);
        if x == 1u64.to_biguint().unwrap() || x == nsub1 {
            continue;
        }
        for rr in 1..r {
            x = x.clone().mul(x.clone()).rem(n);
            if x == 1u64.to_biguint().unwrap() {
                return false;
            } else if x == nsub1 {
                continue 'WitnessLoop;
            } 
        }
        return false;
    }
    return true;
}

fn mod_exp(base: &BigUint, exponent: &BigUint, modulus: &BigUint) -> BigUint {
    let one = 1u64.to_biguint().unwrap();
    let mut result = one.clone();
    let mut base_clone = base.clone();
    let mut exponent_clone = exponent.clone();

    while exponent_clone > 0u64.to_biguint().unwrap() {
        if exponent_clone.clone() & one.clone() == one {
            result = result.mul(&base_clone).rem(modulus);
        } 
        base_clone = base_clone.clone().mul(base_clone).rem(modulus);
        exponent_clone = exponent_clone.shr(1usize);
    }
    return result;
}

fn main() {  
    let now1 = now();

    for n in 5u64..1_000_000u64 {
        let b = n.to_biguint().unwrap();
        if might_be_prime(&b) {
            println!("{}", n);
        }
    }

    let now2 = now();
    println!("{}", now2.to_timespec().sec - now1.to_timespec().sec);
}

Answer 1

您可以很容易地删除大部分克隆。 BigUint 还为使用 &BigUint 的操作实现了所有操作特征，而不仅仅是使用值。这样，它变得更快，但仍然是 Java...

的一半左右

此外（与性能无关，只是可读性）您不需要明确使用 add、sub、mul 和 shr；它们会覆盖常规的 +、-、* 和 >> 运算符。

例如，您可以像这样重写 might_be_prime 和 mod_exp，这已经在我的机器上提供了很好的加速（平均从 40 秒到 24 秒）：

fn might_be_prime(n: &BigUint) -> bool {
    let one = BigUint::one();
    let nsub1 = n - &one;
    let two = BigUint::new(vec![2]);
    let mut rng = rand::thread_rng();

    let (r, mut d) = find_r_and_d(nsub1.clone());
    let mut x;
    let mut a: BigUint;
    'WitnessLoop: for kk in 0..6u64 {
        a = rng.gen_biguint_range(&two, &nsub1);
        x = mod_exp(&mut a, &mut d, &n);
        if &x == &one || x == nsub1 {
            continue;
        }
        for rr in 1..r {
            x = (&x * &x) % n;
            if &x == &one {
                return false;
            } else if x == nsub1 {
                continue 'WitnessLoop;
            } 
        }
        return false;
    }
    true
}

fn mod_exp(base: &mut BigUint, exponent: &mut BigUint, modulus: &BigUint) -> BigUint {
    let one = BigUint::one();
    let zero = BigUint::zero();
    let mut result = BigUint::one();

    while &*exponent > &zero {
        if &*exponent & &one == one {
           result = (result * &*base) % modulus;
        }
        *base = (&*base * &*base) % modulus;
        *exponent = &*exponent >> 1usize;
    }
    result
}

请注意，我已经移动了 println！时间不对，所以我们没有对 IO 进行基准测试。

fn main() {  
    let now1 = now();

    let v = (5u64..1_000_000u64)
        .filter_map(|n| n.to_biguint())
        .filter(|n| might_be_prime(&n))
        .collect::<Vec<BigUint>>();

    let now2 = now();
    for n in v {
        println!("{}", n);
    }
    println!("time spent seconds: {}", now2.to_timespec().sec - now1.to_timespec().sec);
}

num crate 中的大整数实现是否很慢？

Is the big integer implementation in the num crate slow?

performance

biginteger

performance-testing

rust