apn_mojo.integer¶

The integer family provides exact signed integers, three division conventions, roots, number theory, combinatorics, and modular arithmetic. See the Integer tutorial for construction and basic use.

Exact Integers and their functions, one declaration per name.

Every function is scalar and exact; apply one to batches with vmap, as in vmap[apn_mojo.integer.gcd]()(values, 12). Arguments accept Integers, native integers of up to 64 bits and integer literals of any width. Functions raise on a domain error, naming the problem and a remedy.

Summary¶

Functions¶

abs¶

Source: apn_mojo/integer/math.mojo

def abs(value: Integer) raises -> Integer

The absolute value.

Arguments

• value (Integer): The integer.

Returns

Integer: The nonnegative magnitude.

Raises

Error: Only on a checked size error.

add¶

Source: apn_mojo/integer/math.mojo

def add(left: Integer, right: Integer) raises -> Integer

The exact sum; the same as left + right.

Arguments

• left (Integer): The first operand.
• right (Integer): The second operand.

Returns

Integer: left + right.

Raises

Error: Only on a checked size error.

ceil¶

Source: apn_mojo/integer/math.mojo

def ceil(value: Integer) raises -> Integer

An Integer is its own ceil (numpy's ceil).

Arguments

• value (Integer): The operand.

Returns

Integer: The value.

Raises

Error: Only on a checked size error.

clip¶

Source: apn_mojo/integer/math.mojo

def clip(value: Integer, a_min: Integer, a_max: Integer) raises -> Integer

value limited to [a_min, a_max]: minimum(maximum(value, a_min), a_max) (numpy's clip), so a_max when a_min > a_max.

Arguments

• value (Integer): The operand.
• a_min (Integer): The lower limit.
• a_max (Integer): The upper limit.

Returns

Integer: The limited value.

Raises

Error: Only on a checked size error.

comb¶

Source: apn_mojo/integer/math.mojo

def comb(N: Integer, k: Integer) raises -> Integer

The number of combinations of N things taken k at a time, exactly (scipy's comb with exact=True); apn_mojo.comb adds repetition.

As in scipy, the result is 0 when k > N, N < 0 or k < 0.

Arguments

• N (Integer): The number of things.
• k (Integer): The number taken.

Returns

Integer: The exact count.

Raises

Error: When the result exceeds the addressable size.

div_exact¶

Source: apn_mojo/integer/math.mojo

def div_exact(a: Integer, b: Integer) raises -> Integer

The quotient of an exact division, checked.

Arguments

• a (Integer): The dividend.
• b (Integer): The nonzero divisor.

Returns

Integer: a / b when b divides a.

Raises

Error: When b is zero or the remainder is not zero.

div_rem_euclid¶

Source: apn_mojo/integer/value.mojo

def div_rem_euclid(a: Integer, b: Integer) raises -> Tuple[Integer, Integer]

Euclidean division and its remainder, together.

The quotient is chosen so that 0 <= r < abs(b).

Arguments

• a (Integer): The dividend.
• b (Integer): The divisor.

Returns

Tuple[Integer, Integer]: (q, r) with a == q * b + r.

Raises

Error: When b is zero.

div_rem_floor¶

Source: apn_mojo/integer/value.mojo

def div_rem_floor(a: Integer, b: Integer) raises -> Tuple[Integer, Integer]

Floor division and its remainder, together.

The quotient rounds toward negative infinity, so the remainder is zero or has the divisor's sign; this is the rule of // and %.

Arguments

• a (Integer): The dividend.
• b (Integer): The divisor.

Returns

Tuple[Integer, Integer]: (q, r) with a == q * b + r.

Raises

Error: When b is zero.

div_rem_trunc¶

Source: apn_mojo/integer/value.mojo

def div_rem_trunc(a: Integer, b: Integer) raises -> Tuple[Integer, Integer]

Truncating division and its remainder, together.

The quotient rounds toward zero, so the remainder is zero or has the dividend's sign.

Arguments

• a (Integer): The dividend.
• b (Integer): The divisor.

Returns

Tuple[Integer, Integer]: (q, r) with a == q * b + r.

Raises

Error: When b is zero.

divide¶

Source: apn_mojo/integer/math.mojo

def divide(left: Integer, right: Integer) raises -> Rational

The exact quotient as a Rational; the same as left / right.

Arguments

• left (Integer): The dividend.
• right (Integer): The divisor.

Returns

Rational: left / right in lowest terms, even when integral.

Raises

Error: When right is zero.

factor¶

Source: apn_mojo/integer/factorization.mojo

def factor(
    n: Integer,
    *,
    budget: FactorBudget = FactorBudget(),
) raises -> Factorization

The prime factorization of n, as far as the budget allows.

Trial division by the primes below budget.trial_bound, then perfect-power reduction, then Pollard-Brent rho on what remains. A part the budget did not split is reported with is_prime = False, and the factorization is then incomplete; composites are never reported as prime. factor(2**64 + 1) is 274177 * 67280421310721.

Arguments

• n (Integer): A nonzero integer.
• budget (FactorBudget): The trial bound and the rho iterations.

Returns

Factorization: The sign and the parts, ascending by base.

Raises

Error: For n = 0, a trial bound below 2, negative rho iterations, or elliptic-curve trials, which are not available.

factorial¶

Source: apn_mojo/integer/math.mojo

def factorial(n: Integer) raises -> Integer

n!, exactly.

Arguments

• n (Integer): A nonnegative integer.

Returns

Integer: The product 1 * 2 * ... * n; factorial(0) is one.

Raises

Error: When n is negative or the result exceeds the addressable size.

factorial2¶

Source: apn_mojo/integer/math.mojo

def factorial2(n: Integer) raises -> Integer

n!!, exactly: n * (n - 2) * ....

Arguments

• n (Integer): A nonnegative integer.

Returns

Integer: The product of the integers down to 1 or 2 with the parity of n; zero and one both give one.

Raises

Error: When n is negative or the result exceeds the addressable size.

floor¶

Source: apn_mojo/integer/math.mojo

def floor(value: Integer) raises -> Integer

An Integer is its own floor (numpy's floor).

Arguments

• value (Integer): The operand.

Returns

Integer: The value.

Raises

Error: Only on a checked size error.

gcd¶

Source: apn_mojo/integer/number_theory.mojo

def gcd(a: Integer, b: Integer) raises -> Integer

The greatest common divisor.

Arguments

• a (Integer): The first integer.
• b (Integer): The second integer.

Returns

Integer: The nonnegative gcd; gcd(0, 0) is zero.

Raises

Error: Only on a checked size error.

inverse_mod¶

Source: apn_mojo/integer/math.mojo

def inverse_mod(x: Integer, modulus: Integer) raises -> Integer

The multiplicative inverse of x modulo modulus.

Arguments

• x (Integer): The value to invert.
• modulus (Integer): The nonzero modulus.

Returns

Integer: y in 0 <= y < abs(modulus) with x * y congruent to 1.

Raises

Error: When the modulus is zero or gcd(x, modulus) != 1.

iroot¶

Source: apn_mojo/integer/math.mojo

def iroot(x: Integer, n: Integer) raises -> Integer

The integer n-th root, truncated toward zero.

iroot(-1001, 3) is -10: negative roots truncate toward zero, while nonnegative roots round down.

Arguments

• x (Integer): The radicand.
• n (Integer): The degree, positive.

Returns

Integer: The root; degree one returns x.

Raises

Error: When n is not positive, or x is negative and n even.

iroot_exact¶

Source: apn_mojo/integer/powers.mojo

def iroot_exact(x: Integer, n: Integer) raises -> Optional[Integer]

The exact n-th root of x, when x is a perfect n-th power.

iroot_exact(-27, 3) is -3; iroot_exact(2, 2) and iroot_exact(-4, 2) are None. Cheap tests reject most inputs before any root is taken: the trailing zero bits must be a multiple of n, and residues modulo a few small numbers must be n-th power residues. Through vmap it gives the roots, 0 where there is none, and a Mask of where there is one.

Arguments

• x (Integer): The radicand; a negative one has a root only for odd n.
• n (Integer): The degree, positive.

Returns

Optional[Integer]: The integer r with r**n == x, or None when there is none.

Raises

Error: When n is not positive.

is_prime¶

Source: apn_mojo/integer/primality.mojo

def is_prime(n: Integer) raises -> Bool

Whether n is prime.

Below 264 the answer is proven: Miller-Rabin with the first twelve prime bases has no false positive below about 3.2 * 1023 (Sorenson and Webster 2017). Above, the test is Baillie-PSW: trial division by the primes below 1000, a strong probable-prime test to base 2, a perfect-square check, and a strong Lucas test with Selfridge's parameters. No composite is known to pass it, but that is not a proof.

Arguments

• n (Integer): Any integer; negative numbers, 0 and 1 are not prime.

Returns

Bool: True for a prime.

Raises

Error: Only on a checked size error.

isqrt¶

Source: apn_mojo/integer/number_theory.mojo

def isqrt(a: Integer) raises -> Integer

The integer square root, floor(sqrt(a)).

Arguments

• a (Integer): A nonnegative integer.

Returns

Integer: The largest r with r * r <= a.

Raises

Error: When a is negative.

jacobi¶

Source: apn_mojo/integer/number_theory.mojo

def jacobi(a: Integer, n: Integer) raises -> Integer

The Jacobi symbol (a/n).

For a prime n it is the Legendre symbol: 1 when a is a nonzero square modulo n, -1 when it is not a square, and 0 when n divides a.

Arguments

• a (Integer): Any integer.
• n (Integer): An odd positive modulus.

Returns

Integer: -1, 0 or 1.

Raises

Error: When n is even or not positive.

lcm¶

Source: apn_mojo/integer/number_theory.mojo

def lcm(a: Integer, b: Integer) raises -> Integer

The least common multiple.

Arguments

• a (Integer): The first integer.
• b (Integer): The second integer.

Returns

Integer: The nonnegative lcm; zero when either input is zero.

Raises

Error: Only on a checked size error.

maximum¶

Source: apn_mojo/integer/math.mojo

def maximum(left: Integer, right: Integer) raises -> Integer

The larger of two Integers, the first when they are equal (numpy's maximum).

Arguments

• left (Integer): The first operand.
• right (Integer): The second operand.

Returns

Integer: left if left >= right, else right.

Raises

Error: Only on a checked size error.

minimum¶

Source: apn_mojo/integer/math.mojo

def minimum(left: Integer, right: Integer) raises -> Integer

The smaller of two Integers, the first when they are equal (numpy's minimum).

Arguments

• left (Integer): The first operand.
• right (Integer): The second operand.

Returns

Integer: left if left <= right, else right.

Raises

Error: Only on a checked size error.

multiply¶

Source: apn_mojo/integer/math.mojo

def multiply(left: Integer, right: Integer) raises -> Integer

The exact product; the same as left * right.

Arguments

• left (Integer): The first operand.
• right (Integer): The second operand.

Returns

Integer: left * right.

Raises

Error: Only on a checked size error.

next_prime¶

Source: apn_mojo/integer/factorization.mojo

def next_prime(n: Integer) raises -> Integer

The least prime above n, testing a wheel of 30 with is_prime.

Arguments

• n (Integer): Any integer.

Returns

Integer: The next prime; 2 for every n < 2.

Raises

Error: Only on a checked size error.

perfect_power¶

Source: apn_mojo/integer/powers.mojo

def perfect_power(x: Integer) raises -> Tuple[Integer, Integer]

x as b**e with the largest exponent e.

perfect_power(1000) is (10, 3) and perfect_power(-512) is (-2, 9); perfect_power(12) is (12, 1). The search tries each prime exponent up to the bit length of x, odd ones only for negative x, and continues on every root it finds, which builds composite exponents.

Arguments

• x (Integer): Any integer.

Returns

Tuple[Integer, Integer]: (b, e) with b**e == x and e maximal; (x, 1) when x is not a perfect power, and for -1, 0 and 1.

Raises

Error: Only on a checked size error.

pow_mod¶

Source: apn_mojo/integer/math.mojo

def pow_mod(
    base: Integer,
    exponent: Integer,
    modulus: Integer,
) raises -> Integer

base ** exponent modulo modulus, without forming the full power.

A negative exponent first takes the modular inverse of base. Not constant time: do not use it on secret operands.

Arguments

• base (Integer): The base.
• exponent (Integer): The exponent; negative requires an inverse.
• modulus (Integer): The nonzero modulus.

Returns

Integer: The result in 0 <= r < abs(modulus); modulus 1 or -1 gives zero.

Raises

Error: When the modulus is zero, or the exponent is negative and base has no inverse.

primes_below¶

Source: apn_mojo/integer/factorization.mojo

def primes_below(bound: Int) raises -> List[Int]

Every prime below bound, by a segmented sieve of Eratosthenes.

Arguments

• bound (Int): The exclusive limit.

Returns

List[Int]: The primes, ascending.

Raises

Error: Only on a checked size error.

reciprocal¶

Source: apn_mojo/integer/math.mojo

def reciprocal(value: Integer) raises -> Rational

1 / value, exactly (numpy's reciprocal).

Arguments

• value (Integer): A nonzero Integer.

Returns

Rational: The exact Rational reciprocal.

Raises

Error: When value is zero.

remove_factor¶

Source: apn_mojo/integer/number_theory.mojo

def remove_factor(n: Integer, p: Integer) raises -> Tuple[Integer, Integer]

Divide n by the highest power of p that divides it.

remove_factor(-72, 2) is (-9, 3), since -72 is -9 * 23. The search divides by p, p2, p**4, ... and then back down through the same powers, so a multiplicity k costs about 2 log2(k) divisions rather than k. Factors of 2 are counted from trailing zero bits instead.

Arguments

• n (Integer): A nonzero integer.
• p (Integer): The factor, at least 2; it need not be prime.

Returns

Tuple[Integer, Integer]: (n / p**k, k) with k as large as possible; the cofactor keeps the sign of n.

Raises

Error: When p is below 2, or n is zero, which every power divides.

round¶

Source: apn_mojo/integer/math.mojo

def round(value: Integer) raises -> Integer

An Integer is its own round (numpy's round).

Arguments

• value (Integer): The operand.

Returns

Integer: The value.

Raises

Error: Only on a checked size error.

stable_hash¶

Source: apn_mojo/integer/math.mojo

def stable_hash(x: Integer) -> UInt64

A 64-bit hash of the value, stable across processes and releases.

The algorithm is APNH-64: tag 1, then the sign, the number of 64-bit magnitude words and the words. Unlike Mojo's Hasher, its output never changes, so stored hashes stay valid. Equal Integers hash equal.

Arguments

• x (Integer): The integer.

Returns

UInt64: The hash.

subtract¶

Source: apn_mojo/integer/math.mojo

def subtract(left: Integer, right: Integer) raises -> Integer

The exact difference; the same as left - right.

Arguments

• left (Integer): The first operand.
• right (Integer): The second operand.

Returns

Integer: left - right.

Raises

Error: Only on a checked size error.

trial_division¶

Source: apn_mojo/integer/number_theory.mojo

def trial_division(n: Integer, bound: Integer) raises -> TrialDivision

The prime factors of n below bound, found by trial division.

trial_division(360, 4) finds 23 and 32 and leaves 5. The candidates are 2, 3, 5 and the numbers coprime to 30; a composite candidate never divides, because its prime factors were divided out before it. The search stops once a candidate's square exceeds what remains, which is then 1 or a prime, and that prime counts as a factor when it is below bound. A batch cannot hold its result, so apply it to one value at a time rather than through vmap.

Arguments

• n (Integer): A nonzero integer.
• bound (Integer): Only primes below it are tried; below 3, none are.

Returns

TrialDivision: The factors and the cofactor; see TrialDivision.

Raises

Error: When n is zero, which every prime divides.

trunc¶

Source: apn_mojo/integer/math.mojo

def trunc(value: Integer) raises -> Integer

An Integer is its own trunc (numpy's trunc).

Arguments

• value (Integer): The operand.

Returns

Integer: The value.

Raises

Error: Only on a checked size error.

Structs¶

FactorBudget¶

Source: apn_mojo/integer/factorization.mojo

struct FactorBudget(ImplicitlyCopyable, Writable)

How much work factor may spend: the trial-division bound and the total number of rho iterations over all parts.

Implements

Copyable, ImplicitlyCopyable, Writable

Fields

• trial_bound (Int)
• rho_iterations (Int)
• ecm_curves (Int)

FactorBudget.__init__ { #FactorBudget.init .api-name }¶

def __init__(
    out self,
    *,
    trial_bound: Int = 1 << 16,
    rho_iterations: Int = 1 << 24,
    ecm_curves: Int = 0,
)

A budget; every argument is optional. factor checks it.

Arguments

• trial_bound (Int): Divide out every prime below this bound, at least 2.
• rho_iterations (Int): The rho steps shared by all parts, at least 0; 2**24 by default, enough for products of four 40-bit primes, while a composite rho cannot split gives up after about 8 s at 256 bits.
• ecm_curves (Int): Elliptic-curve trials; only 0 is available.

FactorBudget.write_to¶

def write_to(self, mut writer: Some[Writer])

Write the settings, as print does.

Arguments

• writer (mut Some[Writer]): The destination.

FactorTerm¶

Source: apn_mojo/integer/factorization.mojo

struct FactorTerm(ImplicitlyCopyable, Writable)

One part of a factorization: base**multiplicity, with whether the base is prime (proven below 2**64, Baillie-PSW above).

Implements

Copyable, ImplicitlyCopyable, Writable

Fields

• base (Integer)
• multiplicity (Int)
• is_prime (Bool)

FactorTerm.write_to¶

def write_to(self, mut writer: Some[Writer])

Write base^multiplicity, marked ? when the base may be composite.

Arguments

• writer (mut Some[Writer]): The destination.

Factorization¶

Source: apn_mojo/integer/factorization.mojo

struct Factorization(ImplicitlyCopyable, Writable)

The sign and the parts of an integer, ascending by base.

Implements

Copyable, ImplicitlyCopyable, Writable

Factorization.is_complete¶

def is_complete(self) -> Bool

Whether every base is prime.

Returns

Bool: False when the budget left a composite part.

Factorization.sign¶

def sign(self) -> Int

The sign of the factored integer.

Returns

Int: -1, 0 or 1.

Factorization.terms¶

def terms(self) -> List[FactorTerm]

The parts, ascending by base, equal bases merged.

Returns

List[FactorTerm]: The terms.

Factorization.write_to¶

def write_to(self, mut writer: Some[Writer])

Write the factorization as -1 * 2^3 * 5, ? marking parts that may be composite.

Arguments

• writer (mut Some[Writer]): The destination.

Integer¶

Source: apn_mojo/integer/value.mojo

struct Integer(
    Absable,
    Comparable,
    Hashable,
    ImplicitlyCopyable,
    IntableRaising,
    Writable,
    _IntegerOperand,
    _BatchElement,
)

An exact signed integer of any size.

Arithmetic grows the value instead of wrapping, and a copy keeps its value when the original changes. Values that fit 64 bits are stored inline; larger ones share immutable words, so copies are cheap.

All eleven compound forms (+= through **=) leave the destination unchanged when they raise. Arithmetic with a native integer or an integer literal is exact in either order; with a Rational it returns Rational, and with a Float or native float it returns Float. Integer is Hashable: equal values hash equally whatever their construction, so it works as a Dict or Set key.

Implements

Absable, Comparable, Copyable, Equatable, Hashable, ImplicitlyCopyable, IntableRaising, Writable, _BatchElement, _IntegerOperand, _MapArgument

Integer.__init__ { #Integer.init .api-name }¶

def __init__(out self, value: Int = 0)

An Integer from a native Int; Integer() is zero.

Arguments

• value (Int): The value.

def __init__(
    out self,
    text: String,
    base: Int = 10,
    *,
    allow_prefix: Bool = False,
    allow_whitespace: Bool = False,
    allow_underscores: Bool = False,
    limits: Optional[ConversionLimits] = None,
) raises

Parse an Integer from text.

Text is decimal by default. Bases 2 through 36 use case-insensitive digits, and base=0 detects a 0b, 0o or 0x prefix.

Arguments

• text (String): The digits, with an optional sign.
• base (Int): The radix, from 2 to 36, or 0 to read a prefix.
• allow_prefix (Bool): Accept a prefix that matches base.
• allow_whitespace (Bool): Accept surrounding ASCII whitespace.
• allow_underscores (Bool): Accept single underscores between digits.
• limits (Optional[ConversionLimits]): Optional per-call conversion limits; see ConversionLimits.

Raises

Error: When the text is not a valid integer in the base, naming the byte offset, or when it exceeds limits.

def __init__(out self, value: Int64)

def __init__(out self, value: UInt64)

def __init__[dtype: DType](out self, value: SIMD[dtype, 1])

def __init__(out self, value: IntLiteral)

Integer.from_bytes¶

def from_bytes(
    data: Span[UInt8, _],
    *,
    negative: Bool = False,
    big_endian: Bool = False,
) -> Self

The Integer whose magnitude has these bytes in base 256, with a sign.

Leading zero bytes are allowed. No bytes, or only zero bytes, give zero, whatever negative says. Time is linear in the number of bytes.

Arguments

• data (Span[UInt8, _]): The magnitude's bytes.
• negative (Bool): Whether the result is negative.
• big_endian (Bool): The most significant byte comes first; by default the least significant byte comes first.

Returns

Self: The Integer.

Integer.from_json¶

def from_json(
    text: String,
    *,
    limits: Optional[ConversionLimits] = None,
) raises -> Self

Read an Integer from its version-1 JSON record.

Arguments

• text (String): A record such as {"version":1,"family":"integer","value":"-7"}.
• limits (Optional[ConversionLimits]): Optional per-call conversion limits; see ConversionLimits.

Returns

Self: The Integer the record holds.

Raises

Error: When the text is not exactly that schema, naming the byte offset.

Integer.magnitude_bit_length¶

def magnitude_bit_length(self) -> Int

The number of bits in the absolute value.

Returns

Int: The bit length of abs(self); zero has length 0.

Integer.parse¶

def parse(
    text: String,
    base: Int = 10,
    *,
    allow_prefix: Bool = False,
    allow_whitespace: Bool = False,
    allow_underscores: Bool = False,
    limits: Optional[ConversionLimits] = None,
) raises -> Self

Parse an Integer from text; the same contract as the text constructor.

Arguments

• text (String): The digits, with an optional sign.
• base (Int): The radix, from 2 to 36, or 0 to read a prefix.
• allow_prefix (Bool): Accept a prefix that matches base.
• allow_whitespace (Bool): Accept surrounding ASCII whitespace.
• allow_underscores (Bool): Accept single underscores between digits.
• limits (Optional[ConversionLimits]): Optional per-call conversion limits; see ConversionLimits.

Returns

Self: The parsed Integer.

Raises

Error: When the text is not a valid integer in the base, or exceeds limits.

Integer.sign¶

def sign(self) -> Int

The sign: -1, 0 or 1.

Returns

Int: -1 for a negative value, 0 for zero, 1 for a positive value.

Integer.to_bytes¶

def to_bytes(self, *, big_endian: Bool = False) -> List[UInt8]

The magnitude in base 256, without leading zero bytes.

Zero gives no bytes. The sign is not included: sign() gives it, and Integer.from_bytes(x.to_bytes(), negative=x.sign() < 0) is x. The bytes are read directly from the magnitude, in time linear in its length.

Arguments

• big_endian (Bool): Put the most significant byte first; by default the least significant byte comes first.

Returns

List[UInt8]: (magnitude_bit_length() + 7) // 8 bytes.

Integer.to_json¶

def to_json(self, *, limits: Optional[ConversionLimits] = None) raises -> String

Write the version-1 JSON record of this Integer.

Arguments

• limits (Optional[ConversionLimits]): Optional per-call conversion limits; see ConversionLimits.

Returns

String: Compact canonical JSON, with the value as a decimal string.

Raises

Error: When the output exceeds limits.

Integer.to_native_exact¶

def to_native_exact[dtype: DType](self) raises -> SIMD[dtype, 1]

Convert to a native integer type, exactly.

Parameters

• dtype (DType): The target: DType.int or a signed or unsigned 8- to 64-bit integer.

Returns

SIMD[dtype, 1]: The same value in the native type.

Raises

Error: When the value does not fit the type; nothing is clamped or wrapped.

Integer.to_string¶

def to_string(
    self,
    base: Int = 10,
    *,
    prefix: Bool = False,
    uppercase: Bool = False,
    limits: Optional[ConversionLimits] = None,
) raises -> String

Write the exact digits in a base.

Arguments

• base (Int): The radix, from 2 to 36.
• prefix (Bool): Write 0b, 0o or 0x for bases 2, 8 and 16, after the sign.
• uppercase (Bool): Use uppercase letter digits and prefix.
• limits (Optional[ConversionLimits]): Optional per-call conversion limits; see ConversionLimits.

Returns

String: The exact digits; String(x) is the decimal form.

Raises

Error: When the base is out of range or the output exceeds limits.

Integer.write_to¶

def write_to(self, mut writer: Some[Writer])

Write the canonical decimal form, as print does.

Arguments

• writer (mut Some[Writer]): The destination.

TrialDivision¶

Source: apn_mojo/integer/number_theory.mojo

struct TrialDivision(ImplicitlyCopyable, Writable)

The prime factors of an integer below a bound, and what remains.

trial_division returns it. Copies share one immutable list of factors.

Implements

Copyable, ImplicitlyCopyable, Writable

TrialDivision.cofactor¶

def cofactor(self) -> Integer

What remains after dividing out the factors.

Returns

Integer: n divided by every prime power found. It keeps the sign of n, and is 1 or -1 when the factorization is complete.

TrialDivision.factors¶

def factors(self) -> List[Tuple[Integer, Integer]]

The primes found, ascending, each with its multiplicity.

Returns

List[Tuple[Integer, Integer]]: (prime, multiplicity) pairs.

TrialDivision.write_to¶

def write_to(self, mut writer: Some[Writer])

Write the factors and the cofactor, as print does.

Arguments

• writer (mut Some[Writer]): The destination.

Mixing families¶

Arithmetic with native integers up to 64 bits and arbitrary-width integer literals stays exact. An integer combined with a Rational produces a Rational; with a Float or typed native float, it produces a rounded Float. Result types follow the operation, not the size of the answer.

Comparisons between library values use their exact mathematical values. Put the library value on the left of a comparison with a typed native value, or explicitly construct a suitable library value first. Native integer constructors are limited to 64 bits; use text or integer literals for wider initial values.

An Integer variable keeps its type. /= cannot store a fraction in it, and += cannot silently replace it with a Rational. Use a rational destination when results may be fractional, or call to_integer_exact() on a fraction that must be integral.

Integer ** requires nonnegative exponents. Use pow_rational for reciprocal powers. For a quotient and remainder, choose div_rem_floor, div_rem_trunc, or div_rem_euclid; standard divmod is not supported. Checked size guards reject results that exceed addressable storage.

Text and bytes¶

to_string(base) and Integer(text, base=...) accept bases 2 through 36. Power-of-two bases convert in time linear in the length; other bases in quadratic time, many digits per pass (see Exact text). For binary interchange, to_bytes() returns the magnitude in base 256, least significant byte first unless big_endian=True, and Integer.from_bytes(bytes, negative=...) rebuilds the value; the sign is sign(), and zero has no bytes.

Functions on batches¶

Use vmap to apply a scalar function to batch elements. For example, vmap[gcd]()(values, 12) shares the scalar divisor, and vmap[div_rem_floor]()(a, b) returns quotient and remainder batches. Mapped axes must have equal extents; a one-element batch is not a scalar. An element failure discards partial results and reports its logical index.

"""Exact integer functions such as gcd, lcm and isqrt, on scalars and batches."""

from apn_mojo import Batch, Integer, Mask, gcd, lcm, isqrt, integer, vmap
from apn_mojo import sum, prod, min, max, dot, axpy
from apn_mojo import iroot, pow_mod, inverse_mod, div_exact


def main() raises:
    print("number theory:", gcd(-36, 48), lcm(-36, 48), isqrt(145))
    print("roots:", iroot(1000, 3), iroot(-1001, 3))
    print(
        "modular:",
        pow_mod(7, 100, 1000),
        inverse_mod(3, 11),
        pow_mod(7, -5, 1000),
    )
    print("exact division:", div_exact(-84, 7))
    var exponents = Batch[Integer].from_native([-1, 0, 1, 2])
    print("modular powers:", vmap[pow_mod]()(3, exponents, 11))
    var values = Batch[Integer].from_native([1, 2, 3, 4])
    print(
        "reductions:",
        sum(values),
        prod(values),
        min(values),
        max(values),
    )
    print("dot:", dot(values, values[::-1]))
    var shifted = axpy(3, values, values[::-1])
    print("axpy:", shifted[0], shifted[1], shifted[2], shifted[3])
    print("empty:", sum(Batch[Integer]()), prod(Batch[Integer]()))
    var signs = Batch[Integer].from_native([-1, 0, 1])
    print("unary:", vmap[integer.abs]()(signs)[0], (-signs)[2])
    var mask = Mask([True, False, True])
    print("mask:", mask.count(), mask.all(), mask.any(), (~mask).count())

number theory: 12 144 12
roots: 10 -10
modular: 1 4 943
exact division: -12
modular powers: [4, 1, 3, 9]
reductions: 10 24 1 4
dot: 20
axpy: 7 9 11 13
empty: 0 1
unary: 1 -1
mask: 2 False True 1

See Exact combinatorics and Counters and weighted totals for applications. Arithmetic is not constant-time and makes no cryptographic guarantee.

Number theory¶

The API includes factor removal, trial division, exact roots, perfect powers, primality tests, and the Jacobi symbol. is_prime is deterministic below 2**64 and uses the Baillie–PSW probable-prime test above that range. See Integer architecture for the algorithms. Rational gcd, lcm, and root_exact live in apn_mojo.rational.

factor(n) returns the sign and prime powers of n in ascending order. It tries division below FactorBudget.trial_bound, perfect-power reduction, and then Pollard and Brent's rho method. Rho shares at most rho_iterations steps across all parts, with a default budget of 2**24. In the recorded tests, that budget handled products of four 40-bit primes; a 256-bit composite that rho could not split took about 8 seconds to exhaust it.

An unsplit part is reported with is_prime = False, making is_complete() false; a composite is never reported as prime. For example, factor(2**64 + 1) is 274177 * 67280421310721. primes_below(n) lists the primes below n by a segmented sieve, and next_prime(n) returns the least prime above n.

"""Factors, exact roots, perfect powers and primes, on scalars and batches."""

from apn_mojo import Batch, Integer, Rational, integer, rational, vmap
from apn_mojo import remove_factor, trial_division, iroot_exact, perfect_power
from apn_mojo import is_prime, jacobi, root_exact


def main() raises:
    var cofactor, count = remove_factor(-72, 2)
    print("-72 without 2s:", cofactor, "times 2 **", count)
    print(trial_division(360, 4))
    var division = trial_division(Integer.parse("123456789012345678901234567890"), 1000)
    print("primes below 1000:", len(division.factors()), "cofactor:", division.cofactor())
    print("cube root of -27:", iroot_exact(-27, 3).value())
    print("2 is a square:", Bool(iroot_exact(2, 2)))
    var base, exponent = perfect_power(-512)
    print("-512 =", base, "**", exponent)
    print("2**127 - 1 is prime:", is_prime((Integer(1) << 127) - 1))
    print("primes:", vmap[integer.is_prime]()(Batch[Integer].from_native([97, 561, 7919])))
    print("jacobi(2, 15):", jacobi(2, 15))
    print("root of 9/4:", root_exact(Rational(9, 4), 2).value())
    print("gcd(1/2, 1/3):", rational.gcd(Rational(1, 2), Rational(1, 3)))
    print("5/2 rounds to", Rational(5, 2).round())

-72 without 2s: -9 times 2 ** 3
TrialDivision(factors=[(2, 3), (3, 2)], cofactor=5)
primes below 1000: 9 cofactor: 86148338324417741
cube root of -27: -3
2 is a square: False
-512 = -2 ** 9
2**127 - 1 is prime: True
primes: [True, False, True]
jacobi(2, 15): 1
root of 9/4: 3/2
gcd(1/2, 1/3): 1/6
5/2 rounds to 2

A tour of Integer¶

This example covers text and JSON, conversion limits, division rules, number-theoretic functions, and batch updates.

"""A tour of Integer: text, bytes, JSON, division conventions, functions and batch updates."""

from apn_mojo import (
    Batch,
    Integer,
    div_rem_floor,
    div_rem_trunc,
    div_rem_euclid,
    gcd,
    lcm,
    isqrt,
    ConversionLimits,
    sum,
    prod,
    min,
    max,
    dot,
    axpy,
    integer,
    vmap,
)


def main() raises:
    var value = Integer("340282366920938463463374607431768211455")
    var saved = value
    value += value
    print("original:", saved)
    print("doubled: ", value)
    var restored = Integer.from_json(value.to_json())
    var labels = Dict[Integer, String]()
    labels[value] = "exact value"
    print("restored key:", labels[restored])
    var limits = ConversionLimits(
        max_input_bytes=4096,
        max_output_bytes=4096,
        max_digits=1000,
        max_values=100,
    )
    print(
        "bounded round trip:",
        Integer.from_json(saved.to_json(limits=limits), limits=limits),
    )
    var code = Integer(
        " -0xFF_FF ", base=0, allow_whitespace=True, allow_underscores=True
    )
    print("hexadecimal:", code.to_string(16, prefix=True, uppercase=True))
    var magnitude = code.to_bytes(big_endian=True)
    print(
        "bytes:",
        len(magnitude),
        Integer.from_bytes(Span(magnitude), negative=code.sign() < 0, big_endian=True),
    )

    var quotient, remainder = div_rem_floor(-7, 3)
    print("floor:", quotient, remainder)
    quotient, remainder = div_rem_trunc(-7, 3)
    print("truncating:", quotient, remainder)
    quotient, remainder = div_rem_euclid(-7, -3)
    print("Euclidean:", quotient, remainder)
    print("native:", Int(quotient))
    print("unsigned:", Integer(UInt64.MAX).to_native_exact[DType.uint64]())
    print("power:", Integer(3) ** 100)
    print("gcd, lcm, square root:", gcd(-36, 48), lcm(-36, 48), isqrt(145))
    print("signed bits:", Integer(-7) >> 1, ~Integer(7))
    print(
        "sign and magnitude bits:", value.sign(), value.magnitude_bit_length()
    )
    try:
        value //= 0
    except error:
        print(error)

    var values: List[Integer] = [saved, value, Integer(-7)]
    var batch = Batch[Integer](values)
    print(
        "negation and absolute value:",
        (-batch)[2],
        vmap[integer.abs]()(batch[::-1])[0],
    )
    var results = (batch + 3) * batch
    for result in results:
        print(result)
    var sequence = Batch[Integer].from_iterable(range(5))
    print("sum and product:", sum(sequence), prod(sequence[1:]))
    print("minimum and maximum:", min(sequence), max(sequence[::-1]))
    print("dot product:", dot(sequence, sequence[::-1]))
    print("scaled addition:", axpy(2, sequence, sequence[::-1]).to_json())
    for value in sequence:
        print("from range:", value)

    var batch_q, batch_r = vmap[div_rem_euclid]()(batch, -7)
    print("batch division:", batch_q[0], batch_r[0])
    var preserved = batch[:]
    var divisors = Batch[Integer].from_native([3, 5, 0])
    try:
        batch //= divisors
    except error:
        print(error)
    print("unchanged after error:", (batch == preserved).all())
    batch //= 3
    batch %= -7
    batch **= 2
    print(
        "batch square root and gcd:",
        vmap[isqrt]()(batch)[0],
        vmap[gcd]()(batch, 12)[0],
    )
    print(
        "batch sign and magnitude bits:",
        batch.sign()[0],
        batch.magnitude_bit_length()[0],
    )

    var positive = batch > 0
    print("positive values:", positive.count())
    print("all positive:", positive.all())
    var snapshot = batch[:]
    batch[1:] = batch[:-1]
    batch[::2] = -1
    print("updated:", batch[0], batch[1], batch[2])
    print("original snapshot:", snapshot[0], snapshot[1], snapshot[2])
    var negative = batch < 0
    var selected = batch[negative]
    batch[negative] = 0
    print("selected snapshot:", selected.to_json())
    print("negative values replaced:", batch.to_json())
    var document = snapshot[::-1].to_json()
    var restored_batch = Batch[Integer].from_json(document)
    print("saved reversed snapshot:", document)
    print("restored first value:", restored_batch[0])

    try:
        _ = Integer("12x")
    except error:
        print(error)

original: 340282366920938463463374607431768211455
doubled:  680564733841876926926749214863536422910
restored key: exact value
bounded round trip: 340282366920938463463374607431768211455
hexadecimal: -0XFFFF
bytes: 2 -65535
floor: -3 2
truncating: -2 -1
Euclidean: 3 2
native: 3
unsigned: 18446744073709551615
power: 515377520732011331036461129765621272702107522001
gcd, lcm, square root: 12 144 12
signed bits: -4 -8
sign and magnitude bits: 1 129
Cannot divide Integer: divisor is 0; use a nonzero divisor. The destination is unchanged.
negation and absolute value: 7 7
115792089237316195423570985008687907853610267032561502502920958615344897851390
463168356949264781694283940034751631412399373928720379230903586816788982136830
28
sum and product: 10 24
minimum and maximum: 0 4
dot product: 10
scaled addition: {"version":1,"family":"integer-batch","values":["4","5","6","7","8"]}
from range: 0
from range: 1
from range: 2
from range: 3
from range: 4
batch division: -48611766702991209066196372490252601636 3
Cannot divide batch: divisor is 0 at logical element 2 (zero-based); use a nonzero divisor. The destination is unchanged.
unchanged after error: True
batch square root and gcd: 6 12
batch sign and magnitude bits: 1 6
positive values: 3
all positive: True
updated: -1 36 -1
original snapshot: 36 25 9
selected snapshot: {"version":1,"family":"integer-batch","values":["-1","-1"]}
negative values replaced: {"version":1,"family":"integer-batch","values":["0","36","0"]}
saved reversed snapshot: {"version":1,"family":"integer-batch","values":["9","25","36"]}
restored first value: 9
Cannot parse Integer: invalid digit at byte 2 for base 10; use valid digits, base=0 for prefixes, allow_whitespace=True for surrounding ASCII spaces, or allow_underscores=True for underscores between digits.