Является ли реализация большого целого числа в ящике num медленным?

Question

Я реализовал прочный тест псевдотермического эффекта Миллера-Рабина в ржавчине, используя BigUint для поддержки произвольных больших простых чисел. Чтобы пробежать числа от 5 до 10^6, это заняло около 40 с cargo run --release.

Я реализовал тот же алгоритм с Java BigInteger и тот же тест занял 10 секунд. Ржавчина в 4 раза медленнее. Я предполагаю, что это вызвано реализацией num::bigint.

Это только текущее состояние num::bigint, или может ли кто-нибудь заметить какие-либо очевидные улучшения в моем коде? (В основном, о том, как я использовал этот язык. Независимо от того, хорошо ли я реализована в алгоритме, он практически реализован на обоих языках точно так же, поэтому не вызывает различий в производительности.)

Я заметил там требуется много clone(), из-за модели владения Rust, которая может сильно повлиять на скорость до некоторого уровня. Но я думаю, что это не так, я прав?

Вот код:

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 имеет все функции ops, реализованные также для операций с &BigUint, а не только для работы со значениями. С этими словами, он становится быстрее, но все равно примерно в два раза быстрее, чем Java ...

также (не связанные с производительностью, просто читаемости) вам не нужно использовать add, sub, mul и shr явно; они переопределяют обычные +, -, * и >> операторов.

Например, вы могли бы переписать might_be_prime и mod_exp, как это, который уже дает хороший прирост скорости на моей машине (от 40 до 24sec на средн):

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 
} 

Обратите внимание, что я переехал Println! вне времени, так что мы не сравниваем 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

Я смущен, почему вы выбираете Миллера-Рабина Strong псевдопростое число испытаний для нахождения простых чисел при 10^6? Или это просто образец для тестирования?

Вы, кажется, подразумеваете произвольные большие простые числа, но не упоминаете, насколько велики или что вы считаете большими?

Если вы ищете простые числа, маленькими, вы можете найти их гораздо быстрее, просеивание - в Java я сделал решето, что найти все простые числа при N = 10^9 в течение примерно 5 секунд ...

Хотя, может быть, я не понимаю, почему вы заботитесь о результатах для простых чисел до 1 000 000 - поскольку это даже не представитель, я думаю о том, что тест может сделать лучше, чем сито - так что мне любопытно, почему это в фокусе?