numクレートの大整数実装は遅いですか？

Question

私は、BigUintを使ってRustのMiller-Rabin Strong Pseudoprime Testを実装して、任意の大きな素数をサポートしました。 5と10^6の間の数字を実行するには、cargo run --releaseで約40秒かかりました。

私はJavaのBigIntegerで同じアルゴリズムを実装し、同じテストでは10秒で完了しました。錆は4倍遅く見えます。私はこれがnum::bigintの実装によって引き起こされたと仮定します。

これはちょうどnum::bigintの現在の状態ですか、それとも誰かが自分のコードで明らかな改善を見出すことができますか？ （主に私が言語をどのように使っていたかにかかわらず、私のアルゴリズムの実装が良いか悪いかに関わらず、両方の言語で全く同じように実装されているため、性能の違いはありません）。

私はそこに気付きましたRustの所有モデルのために必要とされる多くのものがclone()であり、ある程度スピードに影響を与える可能性があります。しかし、私はそれを回避する方法はないと思います、そうですか？ここで

はコードです：

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を使用する必要はありません。通常の+,-、*、>>の演算子よりも優先されます。例えば

あなたはすでに私のマシン上で良いスピードアップを与えるこの、（40から平均で24secするため）などのmight_be_primeとmod_exp書き換えることができます：私はのprintlnを移動した

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 
} 

注意を！私たちが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); 
} 

Answer 2

あなたは10^6の下の素数を見つけるためのミラー・ラビン強擬似テストを選択している理由を私は混乱していますか？それとも単なるテストサンプルですか？

あなたは任意の大きな素数を暗示しているようですが、どの程度大きかったのか、またはあなたが大規模であると考えるのかについての言及はありませんか？

あなたは素数を探しているなら、あなたは小さなずっと速くふるい分けによってそれらを見つけることができることを - Javaで私は約5秒でN下= 10^9のすべての素数を見つけるふるいを作った...

私は100万人以下の素数の結果を気にかけている理由を理解していないかもしれませんが、それは代表でさえないので、テストがふるいよりもうまくいくと思うので、なぜそれが焦点ですか？