An efficient implementation of primality testing in MoonBit.

primality testing

is prime

prime number

efficient

Download zip

Author

kokic

Version

0.2.0

License

Apache-2.0

Repository

github.com/kokic/algol/tree/main/prime

Last updated

2 days ago

Downloads

#Prime

Efficient primality testing for MoonBit BigInt.

#Public API

is_prime(n):
- Uses is_small_prime for n < 10_000.
- Uses is_probable_prime_bpsw for n >= 10_000.
is_small_prime(n):
- Exact primality check for Int values in [0, 10_000).
is_probable_prime_bpsw(n):
- Baillie-Pomerance-Selfridge-Wagstaff (BPSW) probable-prime test.
- Fast in practice and has no known counterexample, but is still a probable-prime test.

#Notes

The small-number path is optimized with a precomputed prime table and a narrow lookup window.
The large-number path combines Miller-Rabin (base 2) and strong Lucas-Selfridge.

#Benchmark

$ moon bench -p kokic/prime/benchmarks --target native --release

name                            time (mean ± σ)         range (min … max)
kokic/prime BPSW aggregate       391.42 µs ±   2.54 µs   387.84 µs … 395.03 µs  in 10 ×    256 runs
core/math MR iters=1 aggregate   136.49 µs ± 968.35 ns   134.86 µs … 138.01 µs  in 10 ×    740 runs
core/math MR iters=8 aggregate   708.71 µs ±   6.47 µs   698.48 µs … 716.75 µs  in 10 ×    140 runs
core/math MR iters=64 aggregate    5.19 ms ±  45.90 µs     5.12 ms …   5.26 ms  in 10 ×     20 runs

The benchmark also reports per-case timings for primes, probable primes, perfect-square composites, and base-2 strong pseudoprimes. core/math uses Miller-Rabin with a configurable iteration count; its default-equivalent comparison here is iters=64.

SMALL_PRIMES_LENGTH

source

let SMALL_PRIMES_LENGTH : Int

abs

source

fn abs(x : @moonbitlang/core/bigint.BigInt
BigInt) -> @moonbitlang/core/bigint.BigInt
BigInt

euclid_mod

source

fn euclid_mod(a : @moonbitlang/core/bigint.BigInt
BigInt, n : @moonbitlang/core/bigint.BigInt
BigInt) -> @moonbitlang/core/bigint.BigInt
BigInt

is_even

source

fn is_even(n : @moonbitlang/core/bigint.BigInt
BigInt) -> Bool

is_odd

source

fn is_odd(n : @moonbitlang/core/bigint.BigInt
BigInt) -> Bool

is_prime

source

fn is_prime(n : @moonbitlang/core/bigint.BigInt
BigInt) -> Bool

The function calls is_small_prime (n < 10000) or is_probable_prime_bpsw (otherwise)

test "is_prime boundary regression" {
  assert_true(!is_prime(-1))
  assert_true(!is_prime(0))
  assert_true(!is_prime(1))
  assert_true(is_prime(2))
  assert_true(is_prime(3))
  assert_true(is_prime(5381))
  assert_true(is_prime(5387))
  assert_true(is_prime(9973))
  assert_true(!is_prime(9999))
  assert_true(!is_prime(10000))
  assert_true(!is_prime(10001))
  assert_true(is_prime(10007))
}

is_probable_prime_bpsw

source

fn is_probable_prime_bpsw(n : @moonbitlang/core/bigint.BigInt
BigInt) -> Bool

Also see: @math.is_probable_prime

is_small_prime

source

fn is_small_prime(n : Int) -> Bool

test "is_small_prime boundary regression" {
  assert_true(!is_small_prime(0))
  assert_true(!is_small_prime(1))
  assert_true(is_small_prime(2))
  assert_true(is_small_prime(3))
  assert_true(is_small_prime(5381))
  assert_true(is_small_prime(5387))
  assert_true(is_small_prime(5393))
  assert_true(is_small_prime(9973))
  assert_true(!is_small_prime(9999))
  assert_true(!is_small_prime(10000))
}

jacobi

source

fn jacobi(a_base : @moonbitlang/core/bigint.BigInt
BigInt, n_base : @moonbitlang/core/bigint.BigInt
BigInt) -> Int raise

Also see: https://en.wikipedia.org/wiki/Jacobi_symbol#Primality_testing

small_primes

source

let small_primes : Array[Int]

All prime numbers up to 10000

Source Files

Site source Report issue Packages Build queue Skills Statistics

prime

#Prime

#Public API

#Notes

#Benchmark

#SMALL_PRIMES_LENGTH

#abs

#euclid_mod

#is_even

#is_odd

#is_prime

#is_probable_prime_bpsw

#is_small_prime

#jacobi

#small_primes

Source Files

SMALL_PRIMES_LENGTH

abs

euclid_mod

is_even

is_odd

is_prime

is_probable_prime_bpsw

is_small_prime

jacobi

small_primes