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

Question

我在Rust中实现了Miller-Rabin Strong Pseudoprime测试,BigUint用于支持任意大质数.要通过5到10 ^ 6之间的数字,它需要大约40秒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);
}