Czy duża liczba całkowita w powolnej skrzynce num?

Question

Zaimplementowałem Miller-Rabin Strong Pseudoprime Test w Rust przy użyciu BigUint do obsługi dowolnych dużych liczb pierwszych. Aby przejść przez liczby od 5 do 10^6, zajęło to około 40 sekund z cargo run --release.

Zaimplementowałam ten sam algorytm z Javą BigInteger i ten sam test trwał 10 sekund. Rdza wydaje się 4 razy wolniejsza. Zakładam, że jest to spowodowane wdrożeniem num::bigint.

Czy to tylko obecny stan num::bigint, czy ktoś może zauważyć jakąkolwiek oczywistą poprawę w moim kodzie? (Głównie o tym, jak użyłem tego języka, bez względu na to, czy moja implementacja algorytmu jest dobra czy zła, jest prawie zaimplementowana dokładnie tak samo w obu językach - tak więc nie powoduje to różnicy w wydajności.)

Zauważyłem tam jest wiele wymaganych clone(), ze względu na model własności Rusta, który może mieć wpływ na prędkość do pewnego poziomu. Ale myślę, że nie da się tego obejść, mam rację?

Oto kod:

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

Można usunąć większość klonów dość łatwo. BigUint ma wszystkie cechy ops zaimplementowane również dla operacji z &BigUint, a nie tylko z wartościami. Z tym, że staje się szybsze, ale nadal o połowę tak szybko jak Java ...

także (nie związane z wydajnością, tylko czytelność) nie trzeba używać add, sub, mul i shr jawnie; zastępują one zwykłe operatory +, -, * i .

Na przykład można przepisać might_be_prime i mod_exp takiego, który już daje dobre przyspieszenie na moim komputerze (od 40 do 24sec na AVG):

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 
} 

Zauważ, że mam przeniósł println! poza czasem, tak, że nie porównujemy 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

Jestem zdezorientowany, dlaczego wybieracie Miller-Rabin Strong Pseudoprime Test na znalezienie liczb pierwszych poniżej 10^6? Czy to tylko próbka testowa?

Wydajesz się sugerować dowolne duże liczby pierwsze, ale bez wzmianki o tym, jak duże lub co uważasz za duże?

Jeśli szukasz liczb pierwszych, że małe, można je znaleźć o wiele szybciej przez przesiewanie - w Javie Zrobiłem sit że Znajdź wszystkie liczby pierwsze pod n = 10^9 w około 5 sekund ...

Chociaż, być może nie rozumiem, dlaczego dbasz o wyniki dla liczb pierwszych poniżej 1 000 000 - ponieważ nie jest to nawet przedstawiciel, myślę o tym, co test może zrobić lepiej niż sito - więc jestem ciekawy, dlaczego to się koncentruje?