🥮 mooncakes.io

/

prime

An efficient implementation of primality testing in MoonBit.

primality testing

is prime

prime number

efficient

moon add kokic/prime@0.1.8

Author

Version

0.1.8

License

Apache-2.0

Repository

github.com/kokic/prime

Last updated

last month

Downloads

30

README

#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

name                        time (mean ± σ)         range (min … max) 
kokic/prime BPSW               1.36 ms ±   9.23 µs     1.35 ms …   1.37 ms  in 10 ×     74 runs
core/math is_probable_prime   17.80 ms ± 200.94 µs    17.50 ms …  17.98 ms  in 10 ×      6 runs

#
abs

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

#
euclid_mod

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

#
is_even

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

#
is_odd

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

#
is_prime

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

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

Also see: @math.is_probable_prime

#
is_small_prime

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

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

Source Files

Powered by MoonBit

Site source Report issue Packages Build queue Skills Statistics

© 2026 mooncakes.io