L'implementazione del numero intero nella cella num è lenta?

Question

Ho implementato il test Pseudoprime Strong di Miller-Rabin in Rust utilizzando BigUint per supportare primi grandi arbitrari. Per eseguire i numeri compresi tra 5 e 10^6, sono stati necessari circa 40 secondi con cargo run --release.

Ho implementato lo stesso algoritmo con Java BigInteger e lo stesso test ha richiesto 10 secondi. La ruggine sembra essere 4 volte più lenta. Presumo che ciò sia causato dall'implementazione di num::bigint.

Questo è solo lo stato corrente di num::bigint oppure qualcuno può notare miglioramenti evidenti nel mio codice? (Principalmente su come ho usato il linguaggio. Indipendentemente dal fatto che la mia implementazione dell'algoritmo sia buona o cattiva, è quasi implementata esattamente nello stesso modo in entrambe le lingue - quindi non fa la differenza nelle prestazioni.)

Ho notato lì sono necessari molti clone(), a causa del modello proprietario di Rust, che potrebbe influire sulla velocità a un certo livello. Ma immagino che non ci sia modo di aggirare questo, ho ragione?

Ecco il codice:

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

È possibile rimuovere la maggior parte dei cloni abbastanza facilmente. BigUint ha tutti i tratti operativi implementati anche per le operazioni con &BigUint, non solo con i valori. Con questo, si diventa più veloce, ma ancora circa la metà veloce come Java ...

anche (non legati alla performance, solo la leggibilità) non è necessario utilizzare add, sub, mul e shr esplicitamente; sostituiscono gli operatori regolari +, -, * e >>.

Per esempio si potrebbe riscrivere might_be_prime e mod_exp come questo, che dà già un buon aumento di velocità sulla mia macchina (da 40 a 24sec su 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 
} 

Si noti che ho spostato il println! fuori dai tempi, in modo che non ci sia un benchmarking 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

Sono confuso perché si sceglie il test pseudoprimo forte Miller-Rabin per la ricerca di numeri primi in 10^6? O è solo un campione di prova?

Sembra che implichi numeri primi arbitrari di grandi dimensioni, ma nessuna menzione di quanto grande o di quello che consideri grande?

Se siete alla ricerca di numeri primi che le piccole, è possibile trovarli molto più veloce mediante setacciatura - in Java che ho fatto setacci che trovano tutti i primi sotto N = 10^9 in circa 5 secondi ...

Anche se, forse, non capisco perché ti preoccupi dei risultati per i numeri primi sotto 1.000.000 - poiché non è nemmeno rappresentativo, penso a cosa il test può fare meglio di un setaccio - quindi sono curioso perché è questo l'obiettivo?