I implemented Lucas-Lehmer Mersenne testing algorithm with num-bigint and ramp crates. TLDR; version is that ramp is about 8 times faster, the time taken/time complexity rises roughly with n^3 as mentioned in a prior post.
Bellow are both source codes with times.
num-bigint, v0.2.6 , compiled with rustc 1.43.0 - current stable version
extern crate num_bigint;
use num_bigint::BigUint;
use std::env;
use std::time::Instant;
fn main() {
// reading argument
let args: Vec<String> = env::args().collect();
let p: u32 = args[1].parse().unwrap();
let start = Instant::now();
let val: BigUint = mersenne(p);
let duration = start.elapsed();
println!("mersenne({}) = {}", p, val);
println!("duration: {:?}", duration);
}
fn mersenne(p: u32) -> BigUint {
// Lucas-Lehmer test
// check if (p-1)-th place LL sequence member (mod 2^p - 1) is divisible by 2^p - 1
let mut ll: BigUint = BigUint::from(4_u8);
let two: BigUint = BigUint::from(2_u8);
let mut m: BigUint = BigUint::from(1_u8);
for _ in 0..p {
m *= &two;
}
m = &m - BigUint::from(1_u8);
//println!("m = {}", m);
//println!("ll[{}] = {}", 1, ll);
for i in 2..p {
if i % 1000 < 1 { println!("Logging {}/{} - {:.2} %", i, p, ((i as f64) * 100.)/(p as f64)); }
ll = &ll * &ll - &two;
ll %= &m;
//println!("ll[{}] = {}", i, ll);
}
return ll;
}
ramp, v0.5.7 , compiled with rustc 1.45.0-nightly (7ced01a73 2020-04-30) - current nightly version
NOTE There was an issue with ramp v0.5.6 and some std::ptr interface changes in latest nightyl version - in v0.5.7 it was fixed.
extern crate ramp;
use ramp::Int;
use std::env;
use std::time::Instant;
fn main() {
// reading argument
let args: Vec<String> = env::args().collect();
let p: u32 = args[1].parse().unwrap();
let start = Instant::now();
let val: Int = mersenne(p);
let duration = start.elapsed();
println!("mersenne({}) = {}", p, val);
println!("duration: {:?}", duration);
}
fn mersenne(p: u32) -> Int {
// Lucas-Lehmer test
// check if (p-1)-th place LL sequence member (mod 2^p - 1) is divisible by 2^p - 1
let mut ll: Int = Int::from(4_u8);
let two: Int = Int::from(2_u8);
let mut m: Int = Int::from(1_u8);
for _ in 0..p {
m *= &two;
}
m = &m - Int::from(1_u8);
//println!("m = {}", m);
//println!("ll[{}] = {}", 1, ll);
for i in 2..p {
if i % 1000 < 1 { println!("Logging {}/{} - {:.2} %", i, p, ((i as f64) * 100.)/(p as f64)); }
ll = &ll * &ll - &two;
ll %= &m;
//println!("ll[{}] = {}", i, ll);
}
return ll;
}
The measured times are - M = 2^p - 1, p - num-bigint - ramp
9686 - 5.30 - 0.73
9941 - 5.61 - 0.81
11213 - 8.72 - 1.05
19937 - 44.45 - 5.35
21701 - 56.19 - 6.69
23209 - 70.73 - 8.11
44 497 - 469.96 - 53.09
86243 - 3162.42 - 417.78
110503 - 6599.85 - didn't do
132049 - 11257.44 - didn't do
. The 
