Fermat Factorisation Benchmark, Rust

bench.rs

use fermat_bench as bench;
use criterion::{black_box, criterion_group, criterion_main, Criterion};

pub fn criterion_benchmark(c: &mut Criterion) {
    // Smaller number
    c.bench_function("fermat0 47368008965429", |b| {
        b.iter(|| bench::fermat0(black_box(47368008965429)))
    });

    c.bench_function("fermat1 47368008965429", |b| {
        b.iter(|| bench::fermat1(black_box(47368008965429)))
    });

    c.bench_function("fermat2 47368008965429", |b| {
        b.iter(|| bench::fermat2(black_box(47368008965429)))
    });

    c.bench_function("fermat3 47368008965429", |b| {
        b.iter(|| bench::fermat3(black_box(47368008965429)))
    });

    c.bench_function("fermat4 47368008965429", |b| {
        b.iter(|| bench::fermat4(black_box(47368008965429)))
    });

    // Bigger number
    c.bench_function("fermat0 4736791755876611", |b| {
        b.iter(|| bench::fermat0(black_box(4736791755876611)))
    });

    c.bench_function("fermat1 4736791755876611", |b| {
        b.iter(|| bench::fermat1(black_box(4736791755876611)))
    });

    c.bench_function("fermat2 4736791755876611", |b| {
        b.iter(|| bench::fermat2(black_box(4736791755876611)))
    });

    c.bench_function("fermat3 4736791755876611", |b| {
        b.iter(|| bench::fermat3(black_box(4736791755876611)))
    });

    c.bench_function("fermat4 4736791755876611", |b| {
        b.iter(|| bench::fermat4(black_box(4736791755876611)))
    });
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

Cargo.toml

[package]
name = "fermat-bench"
version = "0.1.0"
edition = "2021"

[dev-dependencies]
criterion = "0.5"

[[bench]]
name = "bench"
harness = false

lib.rs

fn isqrtc(n: i64) -> i64 {
    (n as f64).sqrt().ceil() as i64
}

pub fn fermat0(n: i64) -> (i64, i64) {
    let mut a = isqrtc(n);
    loop {
        let d = a*a - n;
        let b = isqrtc(d);

        if b.pow(2) == d {
            return (a - b, a + b)
        }

        a += 1
    }
}

pub fn fermat1(n: i64) -> (i64, i64) {
    let mut a = isqrtc(n);
    let mut b = isqrtc(a.pow(2) - n);

    while a.pow(2) - b.pow(2) != n {
        while a.pow(2) - b.pow(2) < n { a += 1 }
        while a.pow(2) - b.pow(2) > n { b += 1 }
    }

    (a - b, a + b)
}

pub fn fermat2(n: i64) -> (i64, i64) {
    let mut a = isqrtc(n);
    let mut a2 = a.pow(2);
    let mut b = isqrtc(a.pow(2) - n);
    let mut b2 = b.pow(2);

    while a2 - b2 != n {
        while a2 - b2 < n { (a2, a) = (a2 + a + a + 1, a + 1) }
        while a2 - b2 > n { (b2, b) = (b2 + b + b + 1, b + 1) }
    }

    (a - b, a + b)
}

pub fn fermat3(n: i64) -> (i64, i64) {
    let a = isqrtc(n);
    let mut a2 = a.pow(2);
    let mut c = 2 * a + 1;

    let b = isqrtc(a.pow(2) - n);
    let mut b2 = b.pow(2);
    let mut d = 2 * b + 1;

    while a2 - b2 != n {
        while a2 - b2 < n { (a2, c) = (a2 + c, c + 2) }
        while a2 - b2 > n { (b2, d) = (b2 + d, d + 2) }
    }

    ((c - d) / 2, (c + d) / 2 - 1)
}

pub fn fermat4(n: i64) -> (i64, i64) {
    let a = isqrtc(n);
    let mut a2 = a.pow(2);
    let mut c = 2 * a + 1;

    let b = isqrtc(a.pow(2) - n);
    let mut b2 = b.pow(2);
    let mut d = 2 * b + 1;

    while a2 - b2 != n {
        while a2 - b2 < n {
            a2 += c;
            c += 2;
        }
        while a2 - b2 > n {
            b2 += d;
            d += 2;
        }
    }

    ((c - d) / 2, (c + d) / 2 - 1)
}

Results.txt

     Running benches/bench.rs (target/release/deps/bench-568c60cc9537d831)
Gnuplot not found, using plotters backend
fermat0 47368008965429  time:   [704.00 µs 705.98 µs 708.41 µs]
                        change: [-0.4049% -0.0289% +0.3505%] (p = 0.88 > 0.05)
                        No change in performance detected.
Found 17 outliers among 100 measurements (17.00%)
  2 (2.00%) high mild
  15 (15.00%) high severe

fermat1 47368008965429  time:   [3.6045 ms 3.6146 ms 3.6259 ms]
                        change: [-0.1035% +0.2346% +0.6118%] (p = 0.19 > 0.05)
                        No change in performance detected.
Found 18 outliers among 100 measurements (18.00%)
  3 (3.00%) high mild
  15 (15.00%) high severe

fermat2 47368008965429  time:   [3.2758 ms 3.2851 ms 3.2951 ms]
                        change: [+0.0980% +0.4433% +0.7790%] (p = 0.02 < 0.05)
                        Change within noise threshold.
Found 16 outliers among 100 measurements (16.00%)
  6 (6.00%) high mild
  10 (10.00%) high severe

fermat3 47368008965429  time:   [2.8620 ms 2.8676 ms 2.8740 ms]
                        change: [-0.4545% -0.1259% +0.2029%] (p = 0.46 > 0.05)
                        No change in performance detected.
Found 14 outliers among 100 measurements (14.00%)
  1 (1.00%) high mild
  13 (13.00%) high severe

fermat4 47368008965429  time:   [2.8654 ms 2.8726 ms 2.8808 ms]
                        change: [-1.7519% -1.1322% -0.5216%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 19 outliers among 100 measurements (19.00%)
  3 (3.00%) high mild
  16 (16.00%) high severe

fermat0 4736791755876611
                        time:   [7.0380 ms 7.0549 ms 7.0741 ms]
                        change: [-0.3640% -0.0139% +0.3399%] (p = 0.94 > 0.05)
                        No change in performance detected.
Found 19 outliers among 100 measurements (19.00%)
  5 (5.00%) high mild
  14 (14.00%) high severe

fermat1 4736791755876611
                        time:   [35.774 ms 35.842 ms 35.920 ms]
                        change: [-0.4050% -0.1066% +0.1825%] (p = 0.49 > 0.05)
                        No change in performance detected.
Found 11 outliers among 100 measurements (11.00%)
  2 (2.00%) high mild
  9 (9.00%) high severe

fermat2 4736791755876611
                        time:   [32.578 ms 32.652 ms 32.735 ms]
                        change: [-0.2806% +0.0633% +0.3776%] (p = 0.72 > 0.05)
                        No change in performance detected.
Found 13 outliers among 100 measurements (13.00%)
  2 (2.00%) high mild
  11 (11.00%) high severe

fermat3 4736791755876611
                        time:   [28.384 ms 28.441 ms 28.507 ms]
                        change: [-0.1940% +0.1054% +0.4258%] (p = 0.49 > 0.05)
                        No change in performance detected.
Found 19 outliers among 100 measurements (19.00%)
  7 (7.00%) high mild
  12 (12.00%) high severe

fermat4 4736791755876611
                        time:   [28.400 ms 28.471 ms 28.558 ms]
                        change: [-0.4726% -0.1083% +0.3000%] (p = 0.59 > 0.05)
                        No change in performance detected.
Found 9 outliers among 100 measurements (9.00%)
  1 (1.00%) high mild
  8 (8.00%) high severe

rust-toolchain.toml

[toolchain]
channel = "1.75"