mooncakes.io

All the tools you need for integers and rational numbers.

Download zip

Author

kokic

Version

0.1.0

License

Apache-2.0

Repository

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

Last updated

20 hours ago

Downloads

Dependencies

kokic/prime0.2.0
moonbitlang/x0.5.4

kokic/pythagoras does not have a README file

Factorization

source

type Factorization[N, P] = (N) -> @moonbitlang/core/hashmap.HashMap
HashMap[N, P] raise InvokeError

Abs

source

pub trait Abs : HasNil + Neg + Compare {
}

impl Abs for Int

impl Abs for BigInt

HasNil

source

pub trait HasNil {
  fn nil() -> Self
}

impl HasNil for Int

impl HasNil for BigInt

HasOne

source

pub trait HasOne {
  fn one() -> Self
}

impl HasOne for Int

impl HasOne for BigInt

Signum

source

pub trait Signum : HasNil + HasOne + Neg + Eq + Compare {
}

impl Signum for Int

impl Signum for BigInt

InvokeError

source

pub suberror InvokeError {
  InvalidInput(msg~ : String)
  FactorizationFailed(remaining~ : @moonbitlang/core/bigint.BigInt
BigInt)
}

abs

source

fn[N : Abs + HasNil + Neg + Compare + Eq] abs(x : N) -> N

cauchy_bound

source

fn cauchy_bound(coeffs : Array[@moonbitlang/core/bigint.BigInt
BigInt]) -> @moonbitlang/core/bigint.BigInt
BigInt raise InvokeError

Parameters

coeffs : [a_0, a_1, ..., a_n] Raises InvalidInput for degree below one or a zero leading coefficient.

divisors

source

fn[E : Abs + HasOne + Mul + HasNil + Neg + Compare + Eq, P : HasOne + Compare + Add + Eq] divisors(n : E, f : (E) -> @moonbitlang/core/hashmap.HashMap
HashMap[E, P] raise InvokeError) -> Array[E] raise InvokeError

All positive m such that m | n

factor

source

fn factor(n : @moonbitlang/core/bigint.BigInt
BigInt) -> @moonbitlang/core/hashmap.HashMap
HashMap[@moonbitlang/core/bigint.BigInt
BigInt, Int] raise InvokeError

Returns a complete prime factorization, or raises if factor search fails.

factor9973

source

fn factor9973(n : Int) -> @moonbitlang/core/hashmap.HashMap
HashMap[Int, Int] raise InvokeError

This function assumes that n has no prime factors greater than 9973 (i.e., n ≤ 9973² = 99460729). The returned result does not contain 1.

Time complexity: (O(π(√n)) = O(√n/log n)), assuming arithmetic operations are (O(1)). Given the fixed input bound (n ≤ 9973²), the actual running time is bounded by a constant.

factorial_naive

source

fn[N : HasOne + Compare + Add + Mul + Eq] factorial_naive(n : N) -> N raise InvokeError

gcd

source

fn[N : Signum + Mod + HasNil + HasOne + Neg + Eq + Compare] gcd(a : N, b : N) -> N

generate_divisors_bounded

source

fn generate_divisors_bounded(n : @moonbitlang/core/bigint.BigInt
BigInt, bound : @moonbitlang/core/bigint.BigInt
BigInt) -> Array[@moonbitlang/core/bigint.BigInt
BigInt] raise InvokeError

generate_time_based_seed

source

fn generate_time_based_seed() -> Bytes

is_root

source

fn is_root(coeffs : Array[@moonbitlang/core/bigint.BigInt
BigInt], r : @moonbitlang/x/rational.Rational
Rational[@moonbitlang/core/bigint.BigInt
BigInt]) -> Bool

Parameters

coeffs : [a_0, a_1, ..., a_n]

min

source

fn[N : Compare + Eq] min(a : N, b : N) -> N

pollard_rho_brent

source

fn pollard_rho_brent(n : @moonbitlang/core/bigint.BigInt
BigInt, k? : Int, c? : (@moonbitlang/core/random.Rand
Rand) -> @moonbitlang/core/bigint.BigInt
BigInt, f? : (@moonbitlang/core/bigint.BigInt
BigInt, @moonbitlang/core/bigint.BigInt
BigInt, @moonbitlang/core/bigint.BigInt
BigInt) -> @moonbitlang/core/bigint.BigInt
BigInt, rand? : @moonbitlang/core/random.Rand
Rand, retry? : Int) -> @moonbitlang/core/bigint.BigInt
BigInt

Pollard's Rho algorithm for integer factorization with Brent's cycle detection.

Parameters

n: Composite number to be factored.
k: Frequency of GCD computations.
c: Constant used in the polynomial function.
f: Polynomial function (default is f(t) = (t^2 + c) mod n).
rand: Random number generator (default is a time-based seed).
retry: Number of attempts to find a non-trivial factor.

pollard_rho_brent_loop

source

fn pollard_rho_brent_loop(n : @moonbitlang/core/bigint.BigInt
BigInt, k? : Int, c? : (@moonbitlang/core/random.Rand
Rand) -> @moonbitlang/core/bigint.BigInt
BigInt, f? : (@moonbitlang/core/bigint.BigInt
BigInt, @moonbitlang/core/bigint.BigInt
BigInt, @moonbitlang/core/bigint.BigInt
BigInt) -> @moonbitlang/core/bigint.BigInt
BigInt, rand? : @moonbitlang/core/random.Rand
Rand) -> @moonbitlang/core/bigint.BigInt
BigInt

Parameters

n: Composite number to be factored.
k: Frequency of GCD computations.
c: Constant used in the polynomial function.
f: Polynomial function (default is f(t) = (t^2 + c) mod n).
rand: Random number generator (default is a time-based seed).

prime_factor_descent

source

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

n ← min(a, n/a) where a is a non-trivial factor of n found via Pollard's rho.

random

source

fn random(rand : @moonbitlang/core/random.Rand
Rand, limit : @moonbitlang/core/bigint.BigInt
BigInt) -> @moonbitlang/core/bigint.BigInt
BigInt

random_range

source

fn random_range(rand : @moonbitlang/core/random.Rand
Rand, inclusive : @moonbitlang/core/bigint.BigInt
BigInt, exclusive : @moonbitlang/core/bigint.BigInt
BigInt) -> @moonbitlang/core/bigint.BigInt
BigInt

random_time_based

source

fn random_time_based() -> @moonbitlang/core/random.Rand
Rand

rat_neg_one

source

let rat_neg_one : @moonbitlang/x/rational.Rational
Rational[@moonbitlang/core/bigint.BigInt
BigInt]

rat_one

source

let rat_one : @moonbitlang/x/rational.Rational
Rational[@moonbitlang/core/bigint.BigInt
BigInt]

rat_two

source

let rat_two : @moonbitlang/x/rational.Rational
Rational[@moonbitlang/core/bigint.BigInt
BigInt]

rat_zero

source

let rat_zero : @moonbitlang/x/rational.Rational
Rational[@moonbitlang/core/bigint.BigInt
BigInt]

rational_root_candidates

source

fn rational_root_candidates(coeffs : Array[@moonbitlang/core/bigint.BigInt
BigInt]) -> Array[@moonbitlang/x/rational.Rational
Rational[@moonbitlang/core/bigint.BigInt
BigInt]] raise InvokeError

Parameters

coeffs : [a_0, a_1, ..., a_n] High-degree zero coefficients are ignored. Nonzero constants have no candidates. Empty or all-zero coefficients raise InvalidInput, since the zero polynomial has infinitely many rational roots. Factor search failure is propagated rather than returning incomplete candidates.

signum

source

fn[N : Signum + HasNil + HasOne + Neg + Eq + Compare, S : HasNil + HasOne + Neg] signum(a : N) -> S

sorted_factors

source

fn[E : Compare + Eq, P : Compare + Eq] sorted_factors(n : E, f : (E) -> @moonbitlang/core/hashmap.HashMap
HashMap[E, P] raise InvokeError) -> Array[(E, P)] raise InvokeError

uint64_array_to_bytes

source

fn uint64_array_to_bytes(values : Array[UInt64]) -> Bytes

Source Files

Site source Report issue Packages Build queue Skills Statistics

pythagoras

#Factorization

#Abs

#HasNil

#HasOne

#Signum

#InvokeError

#abs

#cauchy_bound

Parameters

#divisors

#factor

#factor9973

#factorial_naive

#gcd

#generate_divisors_bounded

#generate_time_based_seed

#is_root

Parameters

#min

#pollard_rho_brent

Parameters

#pollard_rho_brent_loop

Parameters

#prime_factor_descent

#random

#random_range

#random_time_based

#rat_neg_one

#rat_one

#rat_two

#rat_zero

#rational_root_candidates

Parameters

#signum

#sorted_factors

#uint64_array_to_bytes

Source Files

Factorization

Abs

HasNil

HasOne

Signum

InvokeError

abs

cauchy_bound

divisors

factor

factor9973

factorial_naive

gcd

generate_divisors_bounded

generate_time_based_seed

is_root

min

pollard_rho_brent

pollard_rho_brent_loop

prime_factor_descent

random

random_range

random_time_based

rat_neg_one

rat_one

rat_two

rat_zero

rational_root_candidates

signum

sorted_factors

uint64_array_to_bytes