Sayısal değerdeki büyük tam sayı uygulaması yavaş mı?

Question

Rastgele büyük primerleri desteklemek için BigUint'u kullanarak Rust'ta Miller-Rabin Strong Pseudoprime Testini uyguladık. 5 ile 10^6 arasındaki sayılardan geçmek için, cargo run --release ile yaklaşık 40 saniye sürdü.

Aynı algoritmayı Java'nın BigInteger ile uygularım ve aynı testin tamamlanması 10 saniye sürdü. Pas 4 kat daha yavaş görünür. Bunun num::bigint'un uygulanmasından kaynaklandığını farz ediyorum.

Bu yalnızca num::bigint şu anki durumu mu, yoksa kodumda herhangi bir belirgin iyileşme olan var mı? (Esas olarak dili nasıl kullandım. Algoritma uygulamamın iyi ya da kötü olmasına bakılmaksızın, neredeyse her iki dilde de aynı şekilde uygulanıyor - bu yüzden performanstaki farklılığa neden olmaz.)

Orada fark ettim Rust'un sahip olduğu modele bağlı olarak, clone() bir çok gereklidir, bu da hızı bir seviyeye kadar etkileyebilir. Ama sanırım bunun bir yolu yok, ben haklı mıyım? Oldukça kolay klon en kaldırabilir

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

: Burada

kodudur. BigUint, &BigUint ile birlikte sadece değerlerle çalışmak yerine uygulanan tüm ops özelliklerine sahiptir. Bunun üzerine, o kadar hızlı Java gibi hızlı ama hala yaklaşık yarısı ... Ayrıca

(değil, performans sadece okunabilirliği ilgili) açıkça add, sub, mul ve shr kullanmak gerekmez olur; Düzenli olarak +, -, * ve >> işleçlerini geçersiz kılarlar. Örneğin

Zaten (ort üzerine 24sec için 40) benim makinede iyi bir hızlanma veren böyle might_be_prime ve mod_exp yazabilirsiniz:

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 
} 

Not I println taşımış! zamanlamanın dışında, yani IO'yu kıyaslamıyoruz.

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'nın altındaki primleri bulmak için neden Miller-Rabin Strong Pseudoprime Testini seçtiniz diye kafam karıştı mı? Yoksa bu sadece bir test örneği mi?

Rasgele büyük primleri ima ediyor gibi görünüyorsunuz, ancak ne kadar büyük veya büyük olarak ne düşündüğünüzden bahsetmiyorsunuz?

Eğer asal arıyorsanız, küçük çok daha hızlı eleme ile onları bulabilmesi - Java ben yaklaşık 5 saniye içinde N altında = 10^9 Tüm asal bulmak elekler yaptık ...

Belki de, neden 1.000.000'in altındaki primler için sonuçları önemsediğinizi anlamamış olmakla birlikte - bu bile bir temsilci değil çünkü testin bir elekden daha iyi ne yapabileceğini düşünüyorum - bu yüzden neden bu odak noktası merak ediyorum?