Ist die große Integer-Implementierung in der Num-Box langsam?

Question

Ich implementierte den Miller-Rabin Strong Pseudoprimientest in Rust unter Verwendung von BigUint, um beliebig große Primzahlen zu unterstützen. Um die Zahlen zwischen 5 und 10^6 zu durchlaufen, dauerte es ungefähr 40s mit cargo run --release.

Ich implementierte den gleichen Algorithmus mit Java BigInteger und der gleiche Test dauerte 10s, um zu beenden. Rust scheint 4 mal langsamer zu sein. Ich nehme an, dass dies durch die Implementierung von num::bigint verursacht wird.

Ist dies nur der aktuelle Stand von num::bigint, oder kann jemand irgendeine offensichtliche Verbesserung in meinem Code feststellen? (Hauptsächlich über, wie ich die Sprache verwendete. Unabhängig davon, ob meine Implementierung des Algorithmus gut oder schlecht ist, ist es in beiden Sprachen fast identisch implementiert - verursacht also keinen Unterschied in der Leistung.)

Ich habe es dort bemerkt sind viele clone() erforderlich, aufgrund der Eigentümer-Modell von Rust, die die Geschwindigkeit auf ein gewisses Maß beeinflussen könnte. Aber ich denke, dass es keinen Weg gibt, habe ich recht? Hier

ist der Code:

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

Sie können ziemlich leicht die meisten der Klone entfernen. BigUint hat alle Operationsmerkmale auch für Operationen mit &BigUint implementiert, nicht nur mit Werten arbeiten. Damit wird es schneller, aber immer noch etwa halb so schnell wie Java ...

auch (nicht leistungsbezogen, nur Lesbarkeit) Sie müssen nicht add verwenden, sub, mul und shr ausdrücklich; Sie überschreiben die regulären Operatoren +, -, * und >>.

Zum Beispiel könnten Sie might_be_prime und mod_exp wie folgt umschreiben, die bereits eine gute Beschleunigung auf meinem Rechner (auf avg 24sec von 40) ergibt:

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 
} 

Beachten Sie, dass ich die println bewegt! aus dem Timing heraus, so dass wir IO nicht messen.

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

Ich bin verwirrt, warum Sie den Miller-Rabin Strong Pseudoprime Test zum Finden von Primzahlen unter 10^6 wählen? Oder ist das nur eine Testprobe?

Sie scheinen willkürlich große Primzahlen zu implizieren, aber keine Erwähnung, wie groß oder was Sie für groß halten?

Wenn Sie suchen Primzahlen, dass kleine, können Sie sie viel schneller durch Sieben finden - in Java Ich habe Siebe hergestellt, die alle Primzahlen unter N finden = 10^9 in ca. 5 Sekunden ...

Obwohl ich vielleicht nicht verstehe, warum Sie sich um Ergebnisse für Primzahlen unter 1.000.000 kümmern - da das nicht repräsentativ ist, denke ich darüber nach, was der Test besser machen kann als ein Sieb - also bin ich neugierig, warum ist das der Fokus?