title: Is the big integer implementation in the num crate slow?
body: <p>I implemented the Miller-Rabin Strong Pseudoprime Test in Rust using <code>BigUint</code> to support arbitrary large primes. To run through the numbers between 5 and 10^6, it took about 40s with <code>cargo run --release</code>.</p>
  
  <p>I implemented the same algorithm with Java's <code>BigInteger</code> and the same test took 10s to finish. Rust appears to be 4 times slower. I assume this is caused by the implementation of <code>num::bigint</code>. </p>
  
  <p>Is this just the current state of <code>num::bigint</code>, or can anyone spot any obvious improvement in my code? (Mainly about how I used the language. Regardless whether my implementation of the algorithm is good or bad, it is almost implemented exactly the same in both languages - so does not cause the difference in performance.) </p>
  
  <p>I did notice there are lots of <code>clone()</code> required, due to Rust's ownership model, that could well impact the speed to some level. But I guess there is no way around that, am I right? </p>
  
  <p>Here is the code:</p>
  
  <pre><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) -&gt; (u64, BigUint) {
      let mut d = i;
      let mut r = 0;
      loop {
          if d.clone().rem(&amp;2u64.to_biguint().unwrap()) == Zero::zero() {
              d = d.shr(1usize);
              r = r + 1;
          } else {
              break;
          }
      }
      return (r, d);
  }
  
  fn might_be_prime(n: &amp;BigUint) -&gt; 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(&amp;two, &amp;nsub1);
          let mut x = mod_exp(&amp;a, &amp;d, &amp;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: &amp;BigUint, exponent: &amp;BigUint, modulus: &amp;BigUint) -&gt; 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 &gt; 0u64.to_biguint().unwrap() {
          if exponent_clone.clone() &amp; one.clone() == one {
              result = result.mul(&amp;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(&amp;b) {
              println!("{}", n);
          }
      }
  
      let now2 = now();
      println!("{}", now2.to_timespec().sec - now1.to_timespec().sec);
  }  
  </code></pre>