package core:math/big
Source

⌘K
Ctrl+K
or
/

    Overview

    A BigInt implementation in Odin. For the theoretical underpinnings, see Knuth's The Art of Computer Programming, Volume 2, section 4.3. The code started out as an idiomatic source port of libTomMath, which is in the public domain, with thanks.

    Index

    Procedures (315)
    Procedure Groups (188)

    Types

    DIGIT ¶
    Source

    DIGIT :: distinct u64
     

    We can use u128 as an intermediary.

    Related Procedures With Parameters
    Related Procedures With Returns

    Endianness ¶
    Source

    Endianness :: enum i8 {
	Little   = -1, 
	Platform = 0, 
	Big      = 1, 
}

    Error ¶
    Source

    Error :: enum int {
	Okay                    = 0, 
	Out_Of_Memory           = 1, 
	Invalid_Pointer         = 2, 
	Invalid_Argument        = 3, 
	Assignment_To_Immutable = 10, 
	Max_Iterations_Reached  = 11, 
	Buffer_Overflow         = 12, 
	Integer_Overflow        = 13, 
	Integer_Underflow       = 14, 
	Division_by_Zero        = 30, 
	Math_Domain_Error       = 31, 
	Cannot_Open_File        = 50, 
	Cannot_Read_File        = 51, 
	Cannot_Write_File       = 52, 
	Unimplemented           = 127, 
}
     

    Errors are a strict superset of runtime.Allocation_Error.

    Related Procedures With Returns

    Flag ¶
    Source

    Flag :: enum u8 {
	NaN, 
	Inf, 
	Immutable, 
}

    Flags ¶
    Source

    Flags :: bit_set[Flag; u8]

    Int ¶
    Source

    Int :: struct {
	used:  int,
	digit: [dynamic]DIGIT,
	sign:  Sign,
	flags: bit_set[Flag; u8],
}
    Related Procedures With Parameters

    Order ¶
    Source

    Order :: enum i8 {
	LSB_First = -1, 
	MSB_First = 1, 
}
    Related Procedures With Parameters

    Primality_Flag ¶
    Source

    Primality_Flag :: enum u8 {
	Blum_Blum_Shub = 0, // Make prime congruent to 3 mod 4
	Safe           = 1, // Make sure (p-1)/2 is prime as well (implies .Blum_Blum_Shub)
	Second_MSB_On  = 3, // Make the 2nd highest bit one
}

    Primality_Flags ¶
    Source

    Primality_Flags :: bit_set[Primality_Flag; u8]

    Rat ¶
    Source

    Rat :: struct {
	a: Int,
	b: Int,
}
    Related Procedures With Parameters

    Sign ¶
    Source

    Sign :: enum u8 {
	Zero_or_Positive = 0, 
	Negative         = 1, 
}
    Related Procedures With Returns

    Constants

    Error_String ¶
    Source

    Error_String: [Error]string : [Error]string{.Okay = "Okay", .Out_Of_Memory = "Out of memory", .Invalid_Pointer = "Invalid pointer", .Invalid_Argument = "Invalid argument", .Assignment_To_Immutable = "Assignment to immutable", .Max_Iterations_Reached = "Max iterations reached", .Buffer_Overflow = "Buffer overflow", .Integer_Overflow = "Integer overflow", .Integer_Underflow = "Integer underflow", .Division_by_Zero = "Division by zero", .Math_Domain_Error = "Math domain error", .Cannot_Open_File = "Cannot_Open_File", .Cannot_Read_File = "Cannot_Read_File", .Cannot_Write_File = "Cannot_Write_File", .Unimplemented = "Unimplemented"}

    MATH_BIG_FORCE_32_BIT ¶
    Source

    MATH_BIG_FORCE_32_BIT :: #config(MATH_BIG_FORCE_32_BIT, false)

    MATH_BIG_FORCE_64_BIT ¶
    Source

    MATH_BIG_FORCE_64_BIT :: #config(MATH_BIG_FORCE_64_BIT, false)
     

    We don't allow these to be switched at runtime for two reasons:

    1) 32-bit and 64-bit versions of procedures use different types for their storage,
	so we'd have to double the number of procedures, and they couldn't interact.

2) Optimizations thanks to precomputed masks wouldn't work.

    MATH_BIG_USE_FROBENIUS_TEST ¶
    Source

    MATH_BIG_USE_FROBENIUS_TEST :: !MATH_BIG_USE_LUCAS_SELFRIDGE_TEST

    MATH_BIG_USE_LUCAS_SELFRIDGE_TEST ¶
    Source

    MATH_BIG_USE_LUCAS_SELFRIDGE_TEST :: #config(MATH_BIG_USE_LUCAS_SELFRIDGE_TEST, false)
     

    internal_int_is_prime switchables.

    Use Frobenius-Underwood for primality testing, or use Lucas-Selfridge (default).

    RADIX_TABLE_REVERSE_SIZE ¶
    Source

    RADIX_TABLE_REVERSE_SIZE :: 80

    Variables

    FACTORIAL_BINARY_SPLIT_CUTOFF ¶
    Source

    FACTORIAL_BINARY_SPLIT_CUTOFF: int = …
     

    Cutoff to switch to int_factorial_binary_split, and its max recursion level.

    FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS ¶
    Source

    FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS: int = …

    FACTORIAL_MAX_N ¶
    Source

    FACTORIAL_MAX_N: int = …
     

    Largest N for which we'll compute N!

    INT_INF ¶
    Source

    INT_INF: ^Int = …
     

    Initialize constants.

    INT_MINUS_INF ¶
    Source

    INT_MINUS_INF: ^Int = …
     

    Initialize constants.

    INT_MINUS_ONE ¶
    Source

    INT_MINUS_ONE: ^Int = …
     

    Initialize constants.

    INT_NAN ¶
    Source

    INT_NAN: ^Int = …
     

    Initialize constants.

    INT_ONE ¶
    Source

    INT_ONE: ^Int = …
     

    Initialize constants.

    INT_ZERO ¶
    Source

    INT_ZERO: ^Int = …
     

    Initialize constants.

    MAX_ITERATIONS_RANDOM_PRIME ¶
    Source

    MAX_ITERATIONS_RANDOM_PRIME: int = …
     

    How many times we'll call internal_int_random during random prime generation before we bail out.

    Set to 0 or less to try indefinitely.

    MAX_ITERATIONS_ROOT_N ¶
    Source

    MAX_ITERATIONS_ROOT_N: int = …

    MUL_KARATSUBA_CUTOFF ¶
    Source

    MUL_KARATSUBA_CUTOFF: int = …

    MUL_TOOM_CUTOFF ¶
    Source

    MUL_TOOM_CUTOFF: int = …

    RADIX_TABLE ¶
    Source

    RADIX_TABLE: string = …
     

    Characters used in radix conversions.

    RADIX_TABLE_REVERSE ¶
    Source

    RADIX_TABLE_REVERSE: [80]u8 = …

    RANDOM_PRIME_ITERATIONS_USED ¶
    Source

    @(thread_local)
RANDOM_PRIME_ITERATIONS_USED: int
     

    How many iterations we used for the last random prime.

    SQR_KARATSUBA_CUTOFF ¶
    Source

    SQR_KARATSUBA_CUTOFF: int = …

    SQR_TOOM_CUTOFF ¶
    Source

    SQR_TOOM_CUTOFF: int = …

    USE_MILLER_RABIN_ONLY ¶
    Source

    USE_MILLER_RABIN_ONLY: bool = …
     

    Runtime tunable to use Miller-Rabin primality testing only and skip the above.

    Procedures

    assert_if_nil_int ¶
    Source

    assert_if_nil_int :: proc(.. integers: ..^Int, loc := #caller_location) {…}

    assert_if_nil_rat ¶
    Source

    assert_if_nil_rat :: proc(.. rationals: ..^Rat, loc := #caller_location) {…}

    assert_initialized ¶
    Source

    assert_initialized :: proc(a: ^Int, loc := #caller_location) {…}
     

    Internal helpers.

    clamp ¶
    Source

    clamp :: proc(a: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Trim unused digits.

    This is used to ensure that leading zero digits are trimmed and the leading "used" digit will be non-zero.
Typically very fast.  Also fixes the sign if there are no more leading digits.

    clear_if_uninitialized_multi ¶
    Source

    clear_if_uninitialized_multi :: proc(.. args: ..^Int, allocator := context.allocator) -> (err: Error) {…}

    clear_if_uninitialized_single ¶
    Source

    clear_if_uninitialized_single :: proc(arg: ^Int, allocator := context.allocator) -> (err: Error) {…}

    copy_digits ¶
    Source

    copy_digits :: proc(dest, src: ^Int, digits: int, offset: int = int(0), allocator := context.allocator) -> (err: Error) {…}

    count_bits ¶
    Source

    count_bits :: proc(a: ^Int, allocator := context.allocator) -> (count: int, err: Error) {…}
     

    Count bits in an Int.

    destroy_constants ¶
    Source

    destroy_constants :: proc() {…}
     

    Destroy constants.

    Optional for an EXE, as this would be called at the very end of a process.

    digit_log ¶
    Source

    digit_log :: proc(a: DIGIT, base: DIGIT) -> (log: int, err: Error) {…}

    error_if_immutable_multi ¶
    Source

    error_if_immutable_multi :: proc(.. args: ..^Int) -> (err: Error) {…}

    error_if_immutable_single ¶
    Source

    error_if_immutable_single :: proc(arg: ^Int) -> (err: Error) {…}

    ilog2 ¶
    Source

    ilog2 :: proc(value: $T) -> (log2: $T) {…}

    initialize_constants ¶
    Source

    initialize_constants :: proc() -> (res: int) {…}

    int_abs ¶
    Source

    int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Set dest to |src|.

    int_add ¶
    Source

    int_add :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    High-level addition. Handles sign.

    int_add_digit ¶
    Source

    int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {…}
     

    Adds the unsigned DIGIT immediate to an Int,

    such that the `DIGIT` doesn't have to be turned into an `Int` first.

dest = a + digit;

    int_add_rat ¶
    Source

    int_add_rat :: proc(dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    int_addmod ¶
    Source

    int_addmod :: proc(remainder, number, addend, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number + addend) % modulus.

    int_atoi ¶
    Source

    int_atoi :: proc(res: ^Int, input: string, radix: i8 = i8(10), allocator := context.allocator) -> (err: Error) {…}
     

    Read a string [ASCII] in a given radix.

    int_bit_and ¶
    Source

    int_bit_and :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    2's complement and, returns dest = a & b;

    int_bit_complement ¶
    Source

    int_bit_complement :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    dest = ~src

    int_bit_or ¶
    Source

    int_bit_or :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    2's complement or, returns dest = a | b;

    int_bit_xor ¶
    Source

    int_bit_xor :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    2's complement xor, returns dest = a ^ b;

    int_bitfield_extract ¶
    Source

    int_bitfield_extract :: proc(a: ^Int, offset, count: int, allocator := context.allocator) -> (res: _WORD, err: Error) {…}

    int_bitfield_extract_single ¶
    Source

    int_bitfield_extract_single :: proc(a: ^Int, offset: int, allocator := context.allocator) -> (bit: _WORD, err: Error) {…}
     

    Helpers to extract values from the Int.

    int_choose_digit ¶
    Source

    int_choose_digit :: proc(res: ^Int, n, k: int, allocator := context.allocator) -> (err: Error) {…}
     

    Number of ways to choose k items from n items.

    Also known as the binomial coefficient.

TODO: Speed up.

Could be done faster by reusing code from factorial and reusing the common "prefix" results for n!, k! and n-k!
We know that n >= k, otherwise we early out with res = 0.

So:
	n-k, keep result
	n, start from previous result
	k, start from previous result

    int_clear ¶
    Source

    int_clear :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Clear Int and resize it to the default size.

    int_cmp ¶
    Source

    int_cmp :: int_compare
     

    Compare two Ints, signed.

    int_cmp_digit ¶
    Source

    int_cmp_digit :: int_compare_digit
     

    Compare an Int to an unsigned number upto the size of the backing type.

    int_cmp_mag ¶
    Source

    int_cmp_mag :: int_compare_magnitude
     

    Compare the magnitude of two Ints, unsigned.

    int_compare ¶
    Source

    int_compare :: proc(a, b: ^Int, allocator := context.allocator) -> (comparison: int, err: Error) {…}
     

    Compare two Ints, signed.

    int_compare_digit ¶
    Source

    int_compare_digit :: proc(a: ^Int, b: DIGIT, allocator := context.allocator) -> (comparison: int, err: Error) {…}
     

    Compare an Int to an unsigned number upto the size of the backing type.

    int_compare_magnitude ¶
    Source

    int_compare_magnitude :: proc(a, b: ^Int, allocator := context.allocator) -> (res: int, err: Error) {…}
     

    Compare the magnitude of two Ints, unsigned.

    int_copy ¶
    Source

    int_copy :: proc(dest, src: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Copy one Int to another.

    int_count_lsb ¶
    Source

    int_count_lsb :: proc(a: ^Int, allocator := context.allocator) -> (count: int, err: Error) {…}
     

    Returns the number of trailing zeroes before the first one.

    Differs from regular `ctz` in that 0 returns 0.

    int_destroy ¶
    Source

    int_destroy :: proc(.. integers: ..^Int) {…}
     

    Deallocates the backing memory of one or more Ints.

    int_div ¶
    Source

    int_div :: proc(quotient, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {…}

    int_div_digit ¶
    Source

    int_div_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (err: Error) {…}

    int_div_rat ¶
    Source

    int_div_rat :: proc(dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    int_divmod ¶
    Source

    int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    divmod.

    Both the quotient and remainder are optional and may be passed a nil.

    int_divmod_digit ¶
    Source

    int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {…}

    int_double ¶
    Source

    int_double :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    dest = src * 2

    dest = src << 1

    int_equals ¶
    Source

    int_equals :: proc(a, b: ^Int, allocator := context.allocator) -> (equals: bool, err: Error) {…}
     

    bool := a == b

    int_equals_abs ¶
    Source

    int_equals_abs :: proc(a, b: ^Int, allocator := context.allocator) -> (equals: bool, err: Error) {…}
     

    bool := |a| == |b| Compares the magnitudes only, ignores the sign.

    int_equals_digit ¶
    Source

    int_equals_digit :: proc(a: ^Int, b: DIGIT, allocator := context.allocator) -> (equals: bool, err: Error) {…}
     

    bool := a == b

    int_factorial ¶
    Source

    int_factorial :: proc(res: ^Int, n: int, allocator := context.allocator) -> (err: Error) {…}

    int_from_bytes_big ¶
    Source

    int_from_bytes_big :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Read Int from a Big Endian binary representation.

    Sign is detected from the first byte if `signed` is true.

    int_from_bytes_big_python ¶
    Source

    int_from_bytes_big_python :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Read Int from a Big Endian Python binary representation.

    Sign is detected from the first byte if `signed` is true.

    int_from_bytes_little ¶
    Source

    int_from_bytes_little :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Read Int from a Little Endian binary representation.

    Sign is detected from the last byte if `signed` is true.

    int_from_bytes_little_python ¶
    Source

    int_from_bytes_little_python :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Read Int from a Little Endian Python binary representation.

    Sign is detected from the first byte if `signed` is true.

    int_gcd ¶
    Source

    int_gcd :: proc(res, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Greatest Common Divisor.

    int_gcd_lcm ¶
    Source

    int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Function computing both GCD and (if target isn't nil) also LCM.

    int_get ¶
    Source

    int_get :: proc(a: ^Int, $T: typeid, allocator := context.allocator) -> (res: typeid, err: Error) {…}
     

    TODO: Think about using count_bits to check if the value could be returned completely,

    and maybe return max(T), .Integer_Overflow if not?

    int_get_float ¶
    Source

    int_get_float :: proc(a: ^Int, allocator := context.allocator) -> (res: f64, err: Error) {…}

    int_get_i128 ¶
    Source

    int_get_i128 :: proc(a: ^Int, allocator := context.allocator) -> (res: i128, err: Error) {…}

    int_get_i32 ¶
    Source

    int_get_i32 :: proc(a: ^Int, allocator := context.allocator) -> (res: i32, err: Error) {…}

    int_get_i64 ¶
    Source

    int_get_i64 :: proc(a: ^Int, allocator := context.allocator) -> (res: i64, err: Error) {…}

    int_get_u128 ¶
    Source

    int_get_u128 :: proc(a: ^Int, allocator := context.allocator) -> (res: u128, err: Error) {…}

    int_get_u32 ¶
    Source

    int_get_u32 :: proc(a: ^Int, allocator := context.allocator) -> (res: u32, err: Error) {…}

    int_get_u64 ¶
    Source

    int_get_u64 :: proc(a: ^Int, allocator := context.allocator) -> (res: u64, err: Error) {…}

    int_greater_than ¶
    Source

    int_greater_than :: proc(a, b: ^Int, allocator := context.allocator) -> (greater_than: bool, err: Error) {…}
     

    bool := a > b

    int_greater_than_abs ¶
    Source

    int_greater_than_abs :: proc(a, b: ^Int, allocator := context.allocator) -> (greater_than: bool, err: Error) {…}
     

    bool := |a| > |b| Compares the magnitudes only, ignores the sign.

    int_greater_than_digit ¶
    Source

    int_greater_than_digit :: proc(a: ^Int, b: DIGIT, allocator := context.allocator) -> (greater_than: bool, err: Error) {…}
     

    bool := a > b

    int_greater_than_or_equal ¶
    Source

    int_greater_than_or_equal :: proc(a, b: ^Int, allocator := context.allocator) -> (greater_than_or_equal: bool, err: Error) {…}
     

    bool := a >= b

    int_greater_than_or_equal_abs ¶
    Source

    int_greater_than_or_equal_abs :: proc(a, b: ^Int, allocator := context.allocator) -> (greater_than_or_equal: bool, err: Error) {…}
     

    bool := |a| >= |b| Compares the magnitudes only, ignores the sign.

    int_greater_than_or_equal_digit ¶
    Source

    int_greater_than_or_equal_digit :: proc(a: ^Int, b: DIGIT, allocator := context.allocator) -> (greater_than_or_equal: bool, err: Error) {…}
     

    bool := a >= b

    int_grow ¶
    Source

    int_grow :: proc(a: ^Int, digits: int, allow_shrink: bool = false, allocator := context.allocator) -> (err: Error) {…}

    int_halve ¶
    Source

    int_halve :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    dest = src / 2

    dest = src >> 1

    int_inf ¶
    Source

    int_inf :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to Inf and optionally shrink it to the minimum backing size.

    int_init_multi ¶
    Source

    int_init_multi :: proc(.. integers: ..^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Allocates several Ints at once.

    int_is_even ¶
    Source

    int_is_even :: proc(a: ^Int, allocator := context.allocator) -> (even: bool, err: Error) {…}

    int_is_initialized ¶
    Source

    int_is_initialized :: proc(a: ^Int) -> bool {…}

    int_is_negative ¶
    Source

    int_is_negative :: proc(a: ^Int, allocator := context.allocator) -> (negative: bool, err: Error) {…}

    int_is_odd ¶
    Source

    int_is_odd :: proc(a: ^Int, allocator := context.allocator) -> (odd: bool, err: Error) {…}

    int_is_positive ¶
    Source

    int_is_positive :: proc(a: ^Int, allocator := context.allocator) -> (positive: bool, err: Error) {…}

    int_is_power_of_two ¶
    Source

    int_is_power_of_two :: proc(a: ^Int, allocator := context.allocator) -> (res: bool, err: Error) {…}

    int_is_square ¶
    Source

    int_is_square :: proc(a: ^Int, allocator := context.allocator) -> (square: bool, err: Error) {…}
     

    Check if remainders are possible squares - fast exclude non-squares.

    Returns `true` if `a` is a square, `false` if not.
Assumes `a` not to be `nil` and to have been initialized.

    int_is_zero ¶
    Source

    int_is_zero :: proc(a: ^Int, allocator := context.allocator) -> (zero: bool, err: Error) {…}

    int_itoa_cstring ¶
    Source

    int_itoa_cstring :: proc(a: ^Int, radix: i8 = i8(10), allocator := context.allocator) -> (res: cstring, err: Error) {…}
     

    This version of itoa allocates on behalf of the caller. The caller must free the string.

    The radix defaults to 10.

    int_itoa_raw ¶
    Source

    int_itoa_raw :: proc(a: ^Int, radix: i8, buffer: []u8, size: int = int(-1), zero_terminate: bool = false) -> (written: int, err: Error) {…}
     

    A low-level itoa using a caller-provided buffer. itoa_string and itoa_cstring use this.

    You can use also use it if you want to pre-allocate a buffer and optionally reuse it.

Use `radix_size` or `radix_size_estimate` to determine a buffer size big enough.

You can pass the output of `radix_size` to `size` if you've previously called it to size
the output buffer. If you haven't, this routine will call it. This way it knows if the buffer
is the appropriate size, and we can write directly in place without a reverse step at the end.

				=== === === IMPORTANT === === ===

If you determined the buffer size using `radix_size_estimate`, or have a buffer
that you reuse that you know is large enough, don't pass this size unless you know what you are doing,
because we will always write backwards starting at last byte of the buffer.

Keep in mind that if you set `size` yourself and it's smaller than the buffer,
it'll result in buffer overflows, as we use it to avoid reversing at the end
and having to perform a buffer overflow check each character.

    int_itoa_string ¶
    Source

    int_itoa_string :: proc(a: ^Int, radix: i8 = i8(10), zero_terminate: bool = false, allocator := context.allocator) -> (res: string, err: Error) {…}
     

    This version of itoa allocates on behalf of the caller. The caller must free the string.

    The radix defaults to 10.

    int_lcm ¶
    Source

    int_lcm :: proc(res, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Least Common Multiple.

    int_less_than ¶
    Source

    int_less_than :: proc(a, b: ^Int, allocator := context.allocator) -> (less_than: bool, err: Error) {…}
     

    bool := a < b

    int_less_than_abs ¶
    Source

    int_less_than_abs :: proc(a, b: ^Int, allocator := context.allocator) -> (less_than: bool, err: Error) {…}
     

    bool := |a| < |b| Compares the magnitudes only, ignores the sign.

    int_less_than_digit ¶
    Source

    int_less_than_digit :: proc(a: ^Int, b: DIGIT, allocator := context.allocator) -> (less_than: bool, err: Error) {…}
     

    bool := a < b

    int_less_than_or_equal ¶
    Source

    int_less_than_or_equal :: proc(a, b: ^Int, allocator := context.allocator) -> (less_than_or_equal: bool, err: Error) {…}
     

    bool := a <= b

    int_less_than_or_equal_abs ¶
    Source

    int_less_than_or_equal_abs :: proc(a, b: ^Int, allocator := context.allocator) -> (less_than_or_equal: bool, err: Error) {…}
     

    bool := |a| <= |b| Compares the magnitudes only, ignores the sign.

    int_less_than_or_equal_digit ¶
    Source

    int_less_than_or_equal_digit :: proc(a: ^Int, b: DIGIT, allocator := context.allocator) -> (less_than_or_equal: bool, err: Error) {…}
     

    bool := a <= b

    int_log ¶
    Source

    int_log :: proc(a: ^Int, base: DIGIT, allocator := context.allocator) -> (res: int, err: Error) {…}
     

    Logs and roots and such.

    int_minus_inf ¶
    Source

    int_minus_inf :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to -Inf and optionally shrink it to the minimum backing size.

    int_minus_one ¶
    Source

    int_minus_one :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to -1 and optionally shrink it to the minimum backing size.

    int_mod ¶
    Source

    int_mod :: proc(remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = numerator % denominator.

    0 <= remainder < denominator if denominator > 0
denominator < remainder <= 0 if denominator < 0

    int_mod_bits ¶
    Source

    int_mod_bits :: proc(remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = numerator % (1 << bits)

    int_mod_digit ¶
    Source

    int_mod_digit :: proc(numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {…}

    int_mul ¶
    Source

    int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    High level multiplication (handles sign).

    int_mul_digit ¶
    Source

    int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := context.allocator) -> (err: Error) {…}
     

    Multiply by a DIGIT.

    int_mul_rat ¶
    Source

    int_mul_rat :: proc(dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    int_mulmod ¶
    Source

    int_mulmod :: proc(remainder, number, multiplicand, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number * multiplicand) % modulus.

    int_nan ¶
    Source

    int_nan :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to NaN and optionally shrink it to the minimum backing size.

    int_neg ¶
    Source

    int_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Set dest to -src.

    int_one ¶
    Source

    int_one :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to 1 and optionally shrink it to the minimum backing size.

    int_pow ¶
    Source

    int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allocator) -> (err: Error) {…}
     

    Calculate dest = base^power using a square-multiply algorithm.

    int_pow_int ¶
    Source

    int_pow_int :: proc(dest: ^Int, base, power: int, allocator := context.allocator) -> (err: Error) {…}
     

    Calculate dest = base^power using a square-multiply algorithm.

    int_random ¶
    Source

    int_random :: proc(dest: ^Int, bits: int, r: ^rand.Rand = nil, allocator := context.allocator) -> (err: Error) {…}

    int_random_digit ¶
    Source

    int_random_digit :: proc(r: ^rand.Rand = nil) -> (res: DIGIT) {…}

    int_root_n ¶
    Source

    int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.allocator) -> (err: Error) {…}
     

    Find the nth root of an Integer.

    Result found such that `(dest)**n <= src` and `(dest+1)**n > src`

This algorithm uses Newton's approximation `x[i+1] = x[i] - f(x[i])/f'(x[i])`,
which will find the root in `log(n)` time where each step involves a fair bit.

    int_set_from_integer ¶
    Source

    int_set_from_integer :: proc(dest: ^Int, src: $T, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Helpers to set an Int to a specific value.

    int_shl ¶
    Source

    int_shl :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    Shift left by a certain bit count.

    int_shr ¶
    Source

    int_shr :: proc(dest, source: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}

    int_shr_signed ¶
    Source

    int_shr_signed :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    Shift right by a certain bit count with sign extension.

    int_shrmod ¶
    Source

    int_shrmod :: proc(quotient, remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    quotient, remainder := numerator >> bits;

    `remainder` is allowed to be passed a `nil`, in which case `mod` won't be computed.

    int_sqr ¶
    Source

    int_sqr :: proc(dest, src: ^Int) -> (err: Error) {…}

    int_sqrmod ¶
    Source

    int_sqrmod :: proc(remainder, number, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number * number) % modulus.

    int_sqrt ¶
    Source

    int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    This function is less generic than root_n, simpler and faster.

    int_sub ¶
    Source

    int_sub :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    High-level subtraction, dest = number - decrease. Handles signs.

    int_sub_digit ¶
    Source

    int_sub_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {…}
     

    Adds the unsigned DIGIT immediate to an Int,

    such that the `DIGIT` doesn't have to be turned into an `Int` first.

dest = a - digit;

    int_sub_rat ¶
    Source

    int_sub_rat :: proc(dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    int_submod ¶
    Source

    int_submod :: proc(remainder, number, decrease, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number - decrease) % modulus.

    int_swap ¶
    Source

    int_swap :: proc(a, b: ^Int) {…}
     

    In normal code, you can also write a, b = b, a.

    However, that only swaps within the current scope.
This helper swaps completely.

    int_to_bytes_big ¶
    Source

    int_to_bytes_big :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Return Big Endian binary representation of a, either signed or unsigned.

    If `a` is negative and we ask for the default unsigned representation, we return abs(a).

    int_to_bytes_big_python ¶
    Source

    int_to_bytes_big_python :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Return Python 3.x compatible Big Endian binary representation of a, either signed or unsigned.

    If `a` is negative when asking for an unsigned number, we return an error like Python does.

    int_to_bytes_little ¶
    Source

    int_to_bytes_little :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Return Little Endian binary representation of a, either signed or unsigned.

    If `a` is negative and we ask for the default unsigned representation, we return abs(a).

    int_to_bytes_little_python ¶
    Source

    int_to_bytes_little_python :: proc(a: ^Int, buf: []u8, signed: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Return Python 3.x compatible Little Endian binary representation of a, either signed or unsigned.

    If `a` is negative when asking for an unsigned number, we return an error like Python does.

    int_to_bytes_size ¶
    Source

    int_to_bytes_size :: proc(a: ^Int, signed: bool = false, allocator := context.allocator) -> (size_in_bytes: int, err: Error) {…}
     

    Size binary representation

    int_to_cstring ¶
    Source

    int_to_cstring :: int_itoa_cstring
     

    This version of itoa allocates on behalf of the caller. The caller must free the string.

    The radix defaults to 10.

    int_to_string ¶
    Source

    int_to_string :: int_itoa_string
     

    This version of itoa allocates on behalf of the caller. The caller must free the string.

    The radix defaults to 10.

    internal_assert_initialized ¶
    Source

    internal_assert_initialized :: proc(a: ^Int, loc := #caller_location) {…}
     

    Internal helpers.

    internal_clamp ¶
    Source

    internal_clamp :: proc(a: ^Int) -> (err: Error) {…}
     

    Trim unused digits.

    This is used to ensure that leading zero digits are trimmed and the leading "used" digit will be non-zero.
Typically very fast.  Also fixes the sign if there are no more leading digits.

    internal_clear_if_uninitialized_multi ¶
    Source

    internal_clear_if_uninitialized_multi :: proc(.. args: ..^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_clear_if_uninitialized_single ¶
    Source

    internal_clear_if_uninitialized_single :: proc(arg: ^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_copy_digits ¶
    Source

    internal_copy_digits :: proc(dest, src: ^Int, digits: int, offset: int = int(0)) -> (err: Error) {…}

    internal_count_bits ¶
    Source

    internal_count_bits :: proc(a: ^Int) -> (count: int) {…}
     

    Count bits in an Int.

    Assumes `a` not to be `nil` and to have been initialized.

    internal_digit_log ¶
    Source

    internal_digit_log :: proc(a: DIGIT, base: DIGIT) -> (log: int, err: Error) {…}
     

    Returns log_base(a), where a is a DIGIT.

    internal_error_if_immutable_multi ¶
    Source

    internal_error_if_immutable_multi :: proc(.. args: ..^Int) -> (err: Error) {…}

    internal_error_if_immutable_single ¶
    Source

    internal_error_if_immutable_single :: proc(arg: ^Int) -> (err: Error) {…}

    internal_get_low_u32 ¶
    Source

    internal_get_low_u32 :: proc(a: ^Int) -> u32 {…}

    internal_get_low_u64 ¶
    Source

    internal_get_low_u64 :: proc(a: ^Int) -> u64 {…}

    internal_int_abs ¶
    Source

    internal_int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Set dest to |src|.

    internal_int_add_digit ¶
    Source

    internal_int_add_digit :: proc(dest, a: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {…}
     

    Low-level addition Int+DIGIT, signed. Handbook of Applied Cryptography, algorithm 14.7.

    Assumptions:
	`dest` and `a` != `nil` and have been initalized.
	`dest` is large enough (a.used + 1) to fit result.

    internal_int_add_signed ¶
    Source

    internal_int_add_signed :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Low-level addition, signed. Handbook of Applied Cryptography, algorithm 14.7.

    Assumptions:
	`dest`, `a` and `b` != `nil` and have been initalized.

    internal_int_add_unsigned ¶
    Source

    internal_int_add_unsigned :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Low-level addition, unsigned. Handbook of Applied Cryptography, algorithm 14.7.

    Assumptions:
	`dest`, `a` and `b` != `nil` and have been initalized.

    internal_int_addmod ¶
    Source

    internal_int_addmod :: proc(remainder, number, addend, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number + addend) % modulus.

    internal_int_allocated_cap ¶
    Source

    internal_int_allocated_cap :: proc(a: ^Int) -> (cap: int) {…}
     

    This procedure returns the allocated capacity of an Int.

    Assumes `a` not to be `nil`.

    internal_int_and ¶
    Source

    internal_int_and :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    2's complement and, returns dest = a & b;

    internal_int_bitfield_extract ¶
    Source

    internal_int_bitfield_extract :: proc(a: ^Int, offset, count: int) -> (res: _WORD, err: Error) {…}

    internal_int_bitfield_extract_bool ¶
    Source

    internal_int_bitfield_extract_bool :: proc(a: ^Int, offset: int) -> (val: bool, err: Error) {…}
     

    Helpers to extract values from the Int.

    Offset is zero indexed.

    internal_int_bitfield_extract_single ¶
    Source

    internal_int_bitfield_extract_single :: proc(a: ^Int, offset: int) -> (bit: _WORD, err: Error) {…}

    internal_int_bitfield_set_single ¶
    Source

    internal_int_bitfield_set_single :: proc(a: ^Int, offset: int) -> (err: Error) {…}
     

    Helpers to (un)set a bit in an Int.

    Offset is zero indexed.

    internal_int_bitfield_toggle_single ¶
    Source

    internal_int_bitfield_toggle_single :: proc(a: ^Int, offset: int) -> (err: Error) {…}

    internal_int_bitfield_unset_single ¶
    Source

    internal_int_bitfield_unset_single :: proc(a: ^Int, offset: int) -> (err: Error) {…}

    internal_int_clear ¶
    Source

    internal_int_clear :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Clear Int and resize it to the default size.

    Assumes `a` not to be `nil`.

    internal_int_compare ¶
    Source

    internal_int_compare :: proc(a, b: ^Int) -> (comparison: int) {…}
     

    Compare two Ints, signed.

    Returns -1 if `a` < `b`, 0 if `a` == `b` and 1 if `b` > `a`.

Expects `a` and `b` both to be valid `Int`s, i.e. initialized and not `nil`.

    internal_int_compare_digit ¶
    Source

    internal_int_compare_digit :: proc(a: ^Int, b: DIGIT) -> (comparison: int) {…}
     

    Compare an Int to an unsigned number upto DIGIT & _MASK.

    Returns -1 if `a` < `b`, 0 if `a` == `b` and 1 if `b` > `a`.

Expects: `a` and `b` both to be valid `Int`s, i.e. initialized and not `nil`.

    internal_int_compare_magnitude ¶
    Source

    internal_int_compare_magnitude :: proc(a, b: ^Int) -> (comparison: int) {…}
     

    Compare the magnitude of two Ints, unsigned.

    internal_int_complement ¶
    Source

    internal_int_complement :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    dest = ~src

    internal_int_copy ¶
    Source

    internal_int_copy :: proc(dest, src: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Copy one Int to another.

    internal_int_count_lsb ¶
    Source

    internal_int_count_lsb :: proc(a: ^Int) -> (count: int, err: Error) {…}
     

    Returns the number of trailing zeroes before the first one.

    Differs from regular `ctz` in that 0 returns 0.

Assumes `a` not to be `nil` and have been initialized.

    internal_int_decr ¶
    Source

    internal_int_decr :: proc(dest: ^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_destroy ¶
    Source

    internal_int_destroy :: proc(.. integers: ..^Int) {…}
     

    Deallocates the backing memory of one or more Ints.

    Asssumes none of the `integers` to be a `nil`.

    internal_int_div ¶
    Source

    internal_int_div :: proc(quotient, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Asssumes quotient, numerator and denominator to have been initialized and not to be nil.

    internal_int_divmod ¶
    Source

    internal_int_divmod :: proc(quotient, remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    divmod.

    Both the quotient and remainder are optional and may be passed a nil.
`numerator` and `denominator` are expected not to be `nil` and have been initialized.

    internal_int_divmod_digit ¶
    Source

    internal_int_divmod_digit :: proc(quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {…}
     

    Single digit division (based on routine from MPI).

    The quotient is optional and may be passed a nil.

    internal_int_equals ¶
    Source

    internal_int_equals :: proc(a, b: ^Int) -> (equals: bool) {…}
     

    bool := a == b

    internal_int_equals_abs ¶
    Source

    internal_int_equals_abs :: proc(a, b: ^Int) -> (equals: bool) {…}
     

    bool := |a| == |b| Compares the magnitudes only, ignores the sign.

    internal_int_equals_digit ¶
    Source

    internal_int_equals_digit :: proc(a: ^Int, b: DIGIT) -> (equals: bool) {…}
     

    bool := a == b

    internal_int_exponent_mod ¶
    Source

    internal_int_exponent_mod :: internal_int_power_modulo
     

    This is a shell function that calls either the normal or Montgomery exptmod functions.

    Originally the call to the Montgomery code was embedded in the normal function but that
wasted alot of stack space for nothing (since 99% of the time the Montgomery code would be called).

Computes res == G**X mod P.
Assumes `res`, `G`, `X` and `P` to not be `nil` and for `G`, `X` and `P` to have been initialized.

    internal_int_extended_euclidean ¶
    Source

    internal_int_extended_euclidean :: proc(
	a, b, U1, U2, U3: ^Int, 
	allocator := context.allocator, 
) -> (err: Error) {…}
     

    Extended Euclidean algorithm of (a, b) produces a * u1 + b * u2 = u3.

    internal_int_factorial ¶
    Source

    internal_int_factorial :: proc(res: ^Int, n: int, allocator := context.allocator) -> (err: Error) {…}
     

    TODO: Use Sterling's Approximation to estimate log2(N!) to size the result.

    This way we'll have to reallocate less, possibly not at all.

    internal_int_gcd ¶
    Source

    internal_int_gcd :: proc(res_gcd, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_gcd_lcm ¶
    Source

    internal_int_gcd_lcm :: proc(res_gcd, res_lcm, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Returns GCD, LCM or both.

    Assumes `a` and `b` to have been initialized.
`res_gcd` and `res_lcm` can be nil or ^Int depending on which results are desired.

    internal_int_get ¶
    Source

    internal_int_get :: proc(a: ^Int, $T: typeid) -> (res: typeid, err: Error) {…}
     

    TODO: Think about using count_bits to check if the value could be returned completely,

    and maybe return max(T), .Integer_Overflow if not?

    internal_int_get_float ¶
    Source

    internal_int_get_float :: proc(a: ^Int) -> (res: f64, err: Error) {…}

    internal_int_get_i128 ¶
    Source

    internal_int_get_i128 :: proc(a: ^Int) -> (res: i128, err: Error) {…}

    internal_int_get_i32 ¶
    Source

    internal_int_get_i32 :: proc(a: ^Int) -> (res: i32, err: Error) {…}

    internal_int_get_i64 ¶
    Source

    internal_int_get_i64 :: proc(a: ^Int) -> (res: i64, err: Error) {…}

    internal_int_get_u128 ¶
    Source

    internal_int_get_u128 :: proc(a: ^Int) -> (res: u128, err: Error) {…}

    internal_int_get_u32 ¶
    Source

    internal_int_get_u32 :: proc(a: ^Int) -> (res: u32, err: Error) {…}

    internal_int_get_u64 ¶
    Source

    internal_int_get_u64 :: proc(a: ^Int) -> (res: u64, err: Error) {…}

    internal_int_greater_than ¶
    Source

    internal_int_greater_than :: proc(a, b: ^Int) -> (greater_than: bool) {…}
     

    bool := a > b

    internal_int_greater_than_abs ¶
    Source

    internal_int_greater_than_abs :: proc(a, b: ^Int) -> (greater_than: bool) {…}
     

    bool := |a| > |b| Compares the magnitudes only, ignores the sign.

    internal_int_greater_than_digit ¶
    Source

    internal_int_greater_than_digit :: proc(a: ^Int, b: DIGIT) -> (greater_than: bool) {…}
     

    bool := a > b

    internal_int_greater_than_or_equal ¶
    Source

    internal_int_greater_than_or_equal :: proc(a, b: ^Int) -> (greater_than_or_equal: bool) {…}
     

    bool := a >= b

    internal_int_greater_than_or_equal_abs ¶
    Source

    internal_int_greater_than_or_equal_abs :: proc(a, b: ^Int) -> (greater_than_or_equal: bool) {…}
     

    bool := |a| >= |b| Compares the magnitudes only, ignores the sign.

    internal_int_greater_than_or_equal_digit ¶
    Source

    internal_int_greater_than_or_equal_digit :: proc(a: ^Int, b: DIGIT) -> (greater_than_or_equal: bool) {…}
     

    bool := a >= b

    internal_int_grow ¶
    Source

    internal_int_grow :: proc(a: ^Int, digits: int, allow_shrink: bool = false, allocator := context.allocator) -> (err: Error) {…}

    internal_int_incr ¶
    Source

    internal_int_incr :: proc(dest: ^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_inf ¶
    Source

    internal_int_inf :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to Inf and optionally shrink it to the minimum backing size.

    internal_int_init_multi ¶
    Source

    internal_int_init_multi :: proc(.. integers: ..^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Allocates several Ints at once.

    internal_int_inverse_modulo ¶
    Source

    internal_int_inverse_modulo :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    hac 14.61, pp608.

    internal_int_invmod ¶
    Source

    internal_int_invmod :: internal_int_inverse_modulo
     

    hac 14.61, pp608.

    internal_int_is_even ¶
    Source

    internal_int_is_even :: proc(a: ^Int) -> (even: bool) {…}
     

    This procedure will return true if the Int is even, false if not.

    Assumes `a` not to be `nil`.

    internal_int_is_initialized ¶
    Source

    internal_int_is_initialized :: proc(a: ^Int) -> (initialized: bool) {…}
     

    This procedure will return true if the Int is initialized, false if not.

    Assumes `a` not to be `nil`.

    internal_int_is_negative ¶
    Source

    internal_int_is_negative :: proc(a: ^Int) -> (negative: bool) {…}
     

    This procedure will return true if the Int is negative, false if not.

    Assumes `a` not to be `nil`.

    internal_int_is_odd ¶
    Source

    internal_int_is_odd :: proc(a: ^Int) -> (odd: bool) {…}
     

    This procedure will return true if the Int is even, false if not.

    Assumes `a` not to be `nil`.

    internal_int_is_positive ¶
    Source

    internal_int_is_positive :: proc(a: ^Int) -> (positive: bool) {…}
     

    This procedure will return true if the Int is positive, false if not.

    Assumes `a` not to be `nil`.

    internal_int_is_power_of_two ¶
    Source

    internal_int_is_power_of_two :: proc(a: ^Int) -> (power_of_two: bool) {…}
     

    This procedure will return true if the Int is a power of two, false if not.

    Assumes `a` not to be `nil`.

    internal_int_is_prime ¶
    Source

    internal_int_is_prime :: proc(a: ^Int, miller_rabin_trials: int = int(-1), miller_rabin_only: bool = USE_MILLER_RABIN_ONLY, r: ^rand.Rand = nil, allocator := context.allocator) -> (is_prime: bool, err: Error) {…}
     

    a is the big Int to test for primality.

    `miller_rabin_trials` can be one of the following:
	`< 0`:	For `a` up to 3_317_044_064_679_887_385_961_981, set `miller_rabin_trials` to negative to run a predetermined
			number of trials for a deterministic answer.
	`= 0`:	Run Miller-Rabin with bases 2, 3 and one random base < `a`. Non-deterministic.
	`> 0`:	Run Miller-Rabin with bases 2, 3 and `miller_rabin_trials` number of random bases. Non-deterministic.

`miller_rabin_only`:
	`false`	Also use either Frobenius-Underwood or Lucas-Selfridge, depending on the compile-time `MATH_BIG_USE_FROBENIUS_TEST` choice.
	`true`	Run Rabin-Miller trials but skip Frobenius-Underwood / Lucas-Selfridge.

`r` takes a pointer to an instance of `core:math/rand`'s `Rand` and may be `nil` to use the global one.

Returns `is_prime` (bool), where:
	`false`	Definitively composite.
	`true`	Probably prime if `miller_rabin_trials` >= 0, with increasing certainty with more trials.
			Deterministically prime if `miller_rabin_trials` = 0 for `a` up to 3_317_044_064_679_887_385_961_981.

Assumes `a` not to be `nil` and to have been initialized.

    internal_int_is_square ¶
    Source

    internal_int_is_square :: proc(a: ^Int, allocator := context.allocator) -> (square: bool, err: Error) {…}
     

    Check if remainders are possible squares - fast exclude non-squares.

    Returns `true` if `a` is a square, `false` if not.
Assumes `a` not to be `nil` and to have been initialized.

    internal_int_is_zero ¶
    Source

    internal_int_is_zero :: proc(a: ^Int) -> (zero: bool) {…}
     

    This procedure will return true if the Int is zero, false if not.

    Assumes `a` not to be `nil`.

    internal_int_kronecker ¶
    Source

    internal_int_kronecker :: proc(a, p: ^Int, allocator := context.allocator) -> (kronecker: int, err: Error) {…}
     

    Kronecker/Legendre symbol (a|p)

    Straightforward implementation of algorithm 1.4.10 in
Henri Cohen: "A Course in Computational Algebraic Number Theory"

@book{cohen2013course,
	title={A course in computational algebraic number theory},
	author={Cohen, Henri},
	volume={138},
	year={2013},
	publisher={Springer Science \& Business Media}
}

Assumes `a` and `p` to not be `nil` and to have been initialized.

    internal_int_lcm ¶
    Source

    internal_int_lcm :: proc(res_lcm, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_legendre ¶
    Source

    internal_int_legendre :: internal_int_kronecker
     

    Kronecker/Legendre symbol (a|p)

    Straightforward implementation of algorithm 1.4.10 in
Henri Cohen: "A Course in Computational Algebraic Number Theory"

@book{cohen2013course,
	title={A course in computational algebraic number theory},
	author={Cohen, Henri},
	volume={138},
	year={2013},
	publisher={Springer Science \& Business Media}
}

Assumes `a` and `p` to not be `nil` and to have been initialized.

    internal_int_less_than ¶
    Source

    internal_int_less_than :: proc(a, b: ^Int) -> (less_than: bool) {…}
     

    bool := a < b

    internal_int_less_than_abs ¶
    Source

    internal_int_less_than_abs :: proc(a, b: ^Int) -> (less_than: bool) {…}
     

    bool := |a| < |b| Compares the magnitudes only, ignores the sign.

    internal_int_less_than_digit ¶
    Source

    internal_int_less_than_digit :: proc(a: ^Int, b: DIGIT) -> (less_than: bool) {…}
     

    bool := a < b

    internal_int_less_than_or_equal ¶
    Source

    internal_int_less_than_or_equal :: proc(a, b: ^Int) -> (less_than_or_equal: bool) {…}
     

    bool := a <= b

    internal_int_less_than_or_equal_abs ¶
    Source

    internal_int_less_than_or_equal_abs :: proc(a, b: ^Int) -> (less_than_or_equal: bool) {…}
     

    bool := |a| <= |b| Compares the magnitudes only, ignores the sign.

    internal_int_less_than_or_equal_digit ¶
    Source

    internal_int_less_than_or_equal_digit :: proc(a: ^Int, b: DIGIT) -> (less_than_or_equal: bool) {…}
     

    bool := a <= b

    internal_int_log ¶
    Source

    internal_int_log :: proc(a: ^Int, base: DIGIT) -> (res: int, err: Error) {…}
     

    Returns log_base(a).

    Assumes `a` to not be `nil` and have been iniialized.

    internal_int_minus_inf ¶
    Source

    internal_int_minus_inf :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to -Inf and optionally shrink it to the minimum backing size.

    internal_int_minus_one ¶
    Source

    internal_int_minus_one :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to -1 and optionally shrink it to the minimum backing size.

    internal_int_mod ¶
    Source

    internal_int_mod :: proc(remainder, numerator, denominator: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = numerator % denominator.

    0 <= remainder < denominator if denominator > 0
denominator < remainder <= 0 if denominator < 0

Asssumes quotient, numerator and denominator to have been initialized and not to be nil.

    internal_int_mod_bits ¶
    Source

    internal_int_mod_bits :: proc(remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = numerator % (1 << bits)

    Assumes `remainder` and `numerator` both not to be `nil` and `bits` to be >= 0.

    internal_int_mod_digit ¶
    Source

    internal_int_mod_digit :: proc(numerator: ^Int, denominator: DIGIT, allocator := context.allocator) -> (remainder: DIGIT, err: Error) {…}

    internal_int_mul ¶
    Source

    internal_int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    High level multiplication (handles sign).

    internal_int_mul_denom ¶
    Source

    internal_int_mul_denom :: proc(dst, x, y: ^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_mul_digit ¶
    Source

    internal_int_mul_digit :: proc(dest, src: ^Int, multiplier: DIGIT, allocator := context.allocator) -> (err: Error) {…}
     

    Multiply by a DIGIT.

    internal_int_mul_integer ¶
    Source

    internal_int_mul_integer :: proc(dest, a: ^Int, b: $T, allocator := context.allocator) -> (err: Error) {…}
     

    Multiply bigint a with int d and put the result in dest. Like internal_int_mul_digit but with an integer as the small input.

    internal_int_mulmod ¶
    Source

    internal_int_mulmod :: proc(remainder, number, multiplicand, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number * multiplicand) % modulus.

    internal_int_nan ¶
    Source

    internal_int_nan :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to NaN and optionally shrink it to the minimum backing size.

    internal_int_neg ¶
    Source

    internal_int_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Set dest to -src.

    internal_int_one ¶
    Source

    internal_int_one :: proc(a: ^Int, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Set the Int to 1 and optionally shrink it to the minimum backing size.

    internal_int_or ¶
    Source

    internal_int_or :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    2's complement or, returns dest = a | b;

    internal_int_pack ¶
    Source

    internal_int_pack :: proc(a: ^Int, buf: []$T, nails: int = 0, order: Order = Order.LSB_First) -> (written: int, err: Error) {…}
     

    Based on gmp's mpz_export.

    See https://gmplib.org/manual/Integer-Import-and-Export.html

`buf` is a pre-allocated slice of type `T` "words", which must be an unsigned integer of some description.
	Use `internal_int_pack_count(a, T, nails)` to calculate the necessary size.
	The library internally uses `DIGIT` as the type, which is u64 or u32 depending on the platform.
	You are of course welcome to export to []u8, []u32be, and so forth.
	After this you can use `mem.slice_data_cast` to interpret the buffer as bytes if you so choose.

`nails` are the number of top bits the output "word" reserves.
	To mimic the internals of this library, this would be 4.

To use the minimum amount of output bytes, set `nails` to 0 and pass a `[]u8`.
IMPORTANT: `pack` serializes the magnitude of an Int, that is, the output is unsigned.

Assumes `a` not to be `nil` and to have been initialized.

    internal_int_pack_count ¶
    Source

    internal_int_pack_count :: proc(a: ^Int, $T: typeid, nails: int = 0) -> (size_needed: int) {…}
     

    Calculate the size needed for internal_int_pack.

    See https://gmplib.org/manual/Integer-Import-and-Export.html

    internal_int_pow ¶
    Source

    internal_int_pow :: proc(dest, base: ^Int, power: int, allocator := context.allocator) -> (err: Error) {…}
     

    Calculate dest = base^power using a square-multiply algorithm.

    Assumes `dest` and `base` not to be `nil` and to have been initialized.

    internal_int_pow_int ¶
    Source

    internal_int_pow_int :: proc(dest: ^Int, base, power: int, allocator := context.allocator) -> (err: Error) {…}
     

    Calculate dest = base^power.

    Assumes `dest` not to be `nil` and to have been initialized.

    internal_int_power_modulo ¶
    Source

    internal_int_power_modulo :: proc(res, G, X, P: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    This is a shell function that calls either the normal or Montgomery exptmod functions.

    Originally the call to the Montgomery code was embedded in the normal function but that
wasted alot of stack space for nothing (since 99% of the time the Montgomery code would be called).

Computes res == G**X mod P.
Assumes `res`, `G`, `X` and `P` to not be `nil` and for `G`, `X` and `P` to have been initialized.

    internal_int_power_of_two ¶
    Source

    internal_int_power_of_two :: proc(a: ^Int, power: int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_powmod ¶
    Source

    internal_int_powmod :: internal_int_power_modulo
     

    This is a shell function that calls either the normal or Montgomery exptmod functions.

    Originally the call to the Montgomery code was embedded in the normal function but that
wasted alot of stack space for nothing (since 99% of the time the Montgomery code would be called).

Computes res == G**X mod P.
Assumes `res`, `G`, `X` and `P` to not be `nil` and for `G`, `X` and `P` to have been initialized.

    internal_int_prime_frobenius_underwood ¶
    Source

    internal_int_prime_frobenius_underwood :: proc(N: ^Int, allocator := context.allocator) -> (result: bool, err: Error) {…}

    internal_int_prime_is_divisible ¶
    Source

    internal_int_prime_is_divisible :: proc(a: ^Int, allocator := context.allocator) -> (res: bool, err: Error) {…}
     

    Determines if an Integer is divisible by one of the _PRIME_TABLE primes.

    Returns true if it is, false if not.

    internal_int_prime_miller_rabin ¶
    Source

    internal_int_prime_miller_rabin :: proc(a, b: ^Int, allocator := context.allocator) -> (probably_prime: bool, err: Error) {…}
     

    Miller-Rabin test of "a" to the base of "b" as described in HAC pp. 139 Algorithm 4.24.

    Sets result to `false` if definitely composite or `true` if probably prime.
Randomly the chance of error is no more than 1/4 and often very much lower.

Assumes `a` and `b` not to be `nil` and to have been initialized.

    internal_int_prime_next_prime ¶
    Source

    internal_int_prime_next_prime :: proc(a: ^Int, trials: int, bbs_style: bool, allocator := context.allocator) -> (err: Error) {…}
     

    Finds the next prime after the number a using t trials of Miller-Rabin,

    in place: It sets `a` to the prime found.
`bbs_style` = true means the prime must be congruent to 3 mod 4

    internal_int_prime_strong_lucas_selfridge ¶
    Source

    internal_int_prime_strong_lucas_selfridge :: proc(a: ^Int, allocator := context.allocator) -> (lucas_selfridge: bool, err: Error) {…}
     

    Strong Lucas-Selfridge test.

    returns true if it is a strong L-S prime, false if it is composite

Code ported from Thomas Ray Nicely's implementation of the BPSW test at http://www.trnicely.net/misc/bpsw.html

Freeware copyright (C) 2016 Thomas R. Nicely <http://www.trnicely.net>.
Released into the public domain by the author, who disclaims any legal liability arising from its use.

The multi-line comments are made by Thomas R. Nicely and are copied verbatim.
(If that name sounds familiar, he is the guy who found the fdiv bug in the Pentium CPU.)

    internal_int_random ¶
    Source

    internal_int_random :: proc(dest: ^Int, bits: int, r: ^rand.Rand = nil, allocator := context.allocator) -> (err: Error) {…}

    internal_int_random_digit ¶
    Source

    internal_int_random_digit :: proc(r: ^rand.Rand = nil) -> (res: DIGIT) {…}

    internal_int_read_from_ascii_file ¶
    Source

    internal_int_read_from_ascii_file :: proc(a: ^Int, filename: string, radix: i8 = i8(10), allocator := context.allocator) -> (err: Error) {…}
     

    Read an Int from an ASCII file.

    internal_int_root_n ¶
    Source

    internal_int_root_n :: proc(dest, src: ^Int, n: int, allocator := context.allocator) -> (err: Error) {…}
     

    Find the nth root of an Integer.

    Result found such that `(dest)**n <= src` and `(dest+1)**n > src`

This algorithm uses Newton's approximation `x[i+1] = x[i] - f(x[i])/f'(x[i])`,
which will find the root in `log(n)` time where each step involves a fair bit.

Assumes `dest` and `src` not to be `nil` and have been initialized.

    internal_int_scale_denom ¶
    Source

    internal_int_scale_denom :: proc(dst, x, y: ^Int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_set_from_integer ¶
    Source

    internal_int_set_from_integer :: proc(dest: ^Int, src: $T, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}
     

    Helpers to set an Int to a specific value.

    internal_int_shl ¶
    Source

    internal_int_shl :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    Shift left by a certain bit count.

    internal_int_shl1 ¶
    Source

    internal_int_shl1 :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    dest = src * 2

    dest = src << 1

    internal_int_shr ¶
    Source

    internal_int_shr :: proc(dest, source: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}

    internal_int_shr1 ¶
    Source

    internal_int_shr1 :: proc(dest, src: ^Int) -> (err: Error) {…}
     

    dest = src / 2

    dest = src >> 1

Assumes `dest` and `src` not to be `nil` and have been initialized.
We make no allocations here.

    internal_int_shr_signed ¶
    Source

    internal_int_shr_signed :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    Shift right by a certain bit count with sign extension.

    internal_int_shrink ¶
    Source

    internal_int_shrink :: proc(a: ^Int) -> (err: Error) {…}
     

    Resize backing store.

    We don't need to pass the allocator, because the storage itself stores it.

Assumes `a` not to be `nil`, and to have already been initialized.

    internal_int_shrmod ¶
    Source

    internal_int_shrmod :: proc(quotient, remainder, numerator: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
     

    quotient, remainder := numerator >> bits;

    `remainder` is allowed to be passed a `nil`, in which case `mod` won't be computed.

    internal_int_sqrmod ¶
    Source

    internal_int_sqrmod :: proc(remainder, number, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number * number) % modulus.

    internal_int_sqrt ¶
    Source

    internal_int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    This function is less generic than root_n, simpler and faster.

    Assumes `dest` and `src` not to be `nil` and to have been initialized.

    internal_int_sqrtmod_prime ¶
    Source

    internal_int_sqrtmod_prime :: proc(res, n, prime: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Tonelli-Shanks algorithm

    https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
https://gmplib.org/list-archives/gmp-discuss/2013-April/005300.html

    internal_int_sub_digit ¶
    Source

    internal_int_sub_digit :: proc(dest, number: ^Int, digit: DIGIT, allocator := context.allocator) -> (err: Error) {…}
     

    Low-level subtraction, signed. Handbook of Applied Cryptography, algorithm 14.9.

    dest = number - decrease. Assumes |number| > |decrease|.

Assumptions:
	`dest`, `number` != `nil` and have been initalized.
	`dest` is large enough (number.used + 1) to fit result.

    internal_int_sub_signed ¶
    Source

    internal_int_sub_signed :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Low-level subtraction, signed. Handbook of Applied Cryptography, algorithm 14.9.

    dest = number - decrease. Assumes |number| > |decrease|.

Assumptions:
	`dest`, `number` and `decrease` != `nil` and have been initalized.

    internal_int_sub_unsigned ¶
    Source

    internal_int_sub_unsigned :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Low-level subtraction, dest = number - decrease. Assumes |number| > |decrease|.

    Handbook of Applied Cryptography, algorithm 14.9.

Assumptions:
	`dest`, `number` and `decrease` != `nil` and have been initalized.

    internal_int_submod ¶
    Source

    internal_int_submod :: proc(remainder, number, decrease, modulus: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    remainder = (number - decrease) % modulus.

    internal_int_swap ¶
    Source

    internal_int_swap :: proc(a, b: ^Int) {…}
     

    In normal code, you can also write a, b = b, a.

    However, that only swaps within the current scope.
This helper swaps completely.

    internal_int_unpack ¶
    Source

    internal_int_unpack :: proc(a: ^Int, buf: []$T, nails: int = 0, order: Order = Order.LSB_First, allocator := context.allocator) -> (err: Error) {…}

    internal_int_write_to_ascii_file ¶
    Source

    internal_int_write_to_ascii_file :: proc(a: ^Int, filename: string, radix: i8 = i8(10), allocator := context.allocator) -> (err: Error) {…}
     

    Write an Int to an ASCII file.

    internal_int_xor ¶
    Source

    internal_int_xor :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    2's complement xor, returns dest = a ~ b;

    internal_int_zero_unused ¶
    Source

    internal_int_zero_unused :: proc(dest: ^Int, old_used: int = -1) {…}

    internal_platform_abs ¶
    Source

    internal_platform_abs :: proc(n: $T) -> $T {…}

    internal_platform_count_lsb ¶
    Source

    internal_platform_count_lsb :: proc(a: $T) -> (count: int) {…}

    internal_prime_fermat ¶
    Source

    internal_prime_fermat :: proc(a, b: ^Int, allocator := context.allocator) -> (fermat: bool, err: Error) {…}
     

    Performs one Fermat test.

    If "a" were prime then b**a == b (mod a) since the order of
the multiplicative sub-group would be phi(a) = a-1.  That means
it would be the same as b**(a mod (a-1)) == b**1 == b (mod a).

Returns `true` if the congruence holds, or `false` otherwise.

Assumes `a` and `b` not to be `nil` and to have been initialized.

    internal_random_prime ¶
    Source

    internal_random_prime :: proc(
	a:            ^Int, 
	size_in_bits: int, 
	trials:       int, 
	flags:        bit_set[Primality_Flag; u8] = Primality_Flags{}, 
	r:            ^rand.Rand = nil, 
	allocator := context.allocator, 
) -> (err: Error) {…}
     

    Makes a truly random prime of a given size (bits),

    Flags are as follows:
 	Blum_Blum_Shub    - Make prime congruent to 3 mod 4
	Safe              - Make sure (p-1)/2 is prime as well (implies .Blum_Blum_Shub)
	Second_MSB_On     - Make the 2nd highest bit one

This is possibly the mother of all prime generation functions, muahahahahaha!

    internal_rat_destroy ¶
    Source

    internal_rat_destroy :: proc(.. rationals: ..^Rat) {…}

    internal_rat_is_zero ¶
    Source

    internal_rat_is_zero :: proc(z: ^Rat) -> bool {…}

    internal_rat_norm ¶
    Source

    internal_rat_norm :: proc(z: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    internal_rat_swap ¶
    Source

    internal_rat_swap :: proc(a, b: ^Rat) {…}

    internal_rat_to_float ¶
    Source

    internal_rat_to_float :: proc($T: typeid, z: ^Rat, allocator := context.allocator) -> (f: typeid, exact: bool, err: Error) {…}

    internal_small_pow ¶
    Source

    internal_small_pow :: proc(base: _WORD, exponent: _WORD) -> (result: _WORD) {…}

    internal_sqr ¶
    Source

    internal_sqr :: proc(dest, src: ^Int, allocator := context.allocator) -> (res: Error) {…}

    number_of_rabin_miller_trials ¶
    Source

    number_of_rabin_miller_trials :: proc(bit_size: int) -> (number_of_trials: int) {…}
     

    Returns the number of Rabin-Miller trials needed for a given bit size.

    platform_abs ¶
    Source

    platform_abs :: proc(n: $T) -> $T {…}

    platform_count_lsb ¶
    Source

    platform_count_lsb :: proc(a: $T) -> (count: int) {…}

    platform_int_is_power_of_two ¶
    Source

    platform_int_is_power_of_two :: proc(a: int) -> bool {…}

    power_of_two ¶
    Source

    power_of_two :: proc(a: ^Int, power: int, allocator := context.allocator) -> (err: Error) {…}

    radix_size ¶
    Source

    radix_size :: proc(a: ^Int, radix: i8 = i8(10), zero_terminate: bool = false, allocator := context.allocator) -> (size: int, err: Error) {…}
     

    We size for string by default.

    rat_abs ¶
    Source

    rat_abs :: proc(dst, x: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    rat_add_int ¶
    Source

    rat_add_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}

    rat_add_rat ¶
    Source

    rat_add_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    rat_compare ¶
    Source

    rat_compare :: proc(x, y: ^Rat, allocator := context.allocator) -> (comparison: int, error: Error) {…}

    rat_copy ¶
    Source

    rat_copy :: proc(dst, src: ^Rat, minimize: bool = false, allocator := context.allocator) -> (err: Error) {…}

    rat_div_int ¶
    Source

    rat_div_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}

    rat_div_rat ¶
    Source

    rat_div_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    rat_is_even ¶
    Source

    rat_is_even :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}

    rat_is_int ¶
    Source

    rat_is_int :: proc(z: ^Rat) -> bool {…}

    rat_is_negative ¶
    Source

    rat_is_negative :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}

    rat_is_odd ¶
    Source

    rat_is_odd :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}

    rat_is_positive ¶
    Source

    rat_is_positive :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}

    rat_is_zero ¶
    Source

    rat_is_zero :: proc(z: ^Rat) -> bool {…}

    rat_mul_int ¶
    Source

    rat_mul_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}

    rat_mul_rat ¶
    Source

    rat_mul_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    rat_neg ¶
    Source

    rat_neg :: proc(dst, x: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    rat_set_digit ¶
    Source

    rat_set_digit :: proc(dst: ^Rat, a: DIGIT, allocator := context.allocator) -> (err: Error) {…}

    rat_set_f16 ¶
    Source

    rat_set_f16 :: proc(dst: ^Rat, f: f16, allocator := context.allocator) -> (err: Error) {…}

    rat_set_f32 ¶
    Source

    rat_set_f32 :: proc(dst: ^Rat, f: f32, allocator := context.allocator) -> (err: Error) {…}

    rat_set_f64 ¶
    Source

    rat_set_f64 :: proc(dst: ^Rat, f: f64, allocator := context.allocator) -> (err: Error) {…}

    rat_set_frac_digit ¶
    Source

    rat_set_frac_digit :: proc(dst: ^Rat, a, b: DIGIT, allocator := context.allocator) -> (err: Error) {…}

    rat_set_frac_int ¶
    Source

    rat_set_frac_int :: proc(dst: ^Rat, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}

    rat_set_i64 ¶
    Source

    rat_set_i64 :: proc(dst: ^Rat, x: i64, allocator := context.allocator) -> (err: Error) {…}

    rat_set_int ¶
    Source

    rat_set_int :: proc(dst: ^Rat, a: ^Int, allocator := context.allocator) -> (err: Error) {…}

    rat_set_rat ¶
    Source

    rat_set_rat :: proc(dst, x: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    rat_set_u64 ¶
    Source

    rat_set_u64 :: proc(dst: ^Rat, x: u64, allocator := context.allocator) -> (err: Error) {…}

    rat_sign ¶
    Source

    rat_sign :: proc(z: ^Rat) -> Sign {…}

    rat_sqr ¶
    Source

    rat_sqr :: proc(dest, src: ^Rat) -> (err: Error) {…}

    rat_sub_int ¶
    Source

    rat_sub_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}

    rat_sub_rat ¶
    Source

    rat_sub_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}

    rat_swap ¶
    Source

    rat_swap :: proc(a, b: ^Rat) {…}

    rat_to_f16 ¶
    Source

    rat_to_f16 :: proc(z: ^Rat, allocator := context.allocator) -> (f: f16, exact: bool, err: Error) {…}

    rat_to_f32 ¶
    Source

    rat_to_f32 :: proc(z: ^Rat, allocator := context.allocator) -> (f: f32, exact: bool, err: Error) {…}

    rat_to_f64 ¶
    Source

    rat_to_f64 :: proc(z: ^Rat, allocator := context.allocator) -> (f: f64, exact: bool, err: Error) {…}

    shrink ¶
    Source

    shrink :: proc(a: ^Int, allocator := context.allocator) -> (err: Error) {…}
     

    Resize backing store.

    small_pow ¶
    Source

    small_pow :: proc(base: _WORD, exponent: _WORD) -> (result: _WORD) {…}

    zero_unused ¶
    Source

    zero_unused :: proc(dest: ^Int, old_used: int = -1) {…}

    Procedure Groups

    abs ¶
    Source

    abs :: proc{
	int_abs,
	platform_abs,
	rat_abs,
}

    add ¶
    Source

     

    High-level addition. Handles sign.

    addmod ¶
    Source

    addmod :: proc{
	int_addmod,
}

    assert_if_nil ¶
    Source

    assert_if_nil :: proc{
	assert_if_nil_int,
	assert_if_nil_rat,
}

    atoi ¶
    Source

    atoi :: proc{
	int_atoi,
}

    bit_and ¶
    Source

    bit_and :: proc{
	int_bit_and,
}

    bit_complement ¶
    Source

    bit_complement :: proc{
	int_bit_complement,
}

    bit_or ¶
    Source

    bit_or :: proc{
	int_bit_or,
}

    bit_xor ¶
    Source

    bit_xor :: proc{
	int_bit_xor,
}

    choose ¶
    Source

    choose :: proc{
	int_choose_digit,
}

    clear ¶
    Source

    clear :: proc{
	int_clear,
}

    clear_if_uninitialized ¶
    Source

    clear_if_uninitialized :: proc{
	clear_if_uninitialized_single,
	clear_if_uninitialized_multi,
}

    cmp ¶
    Source

    cmp :: proc{
	int_compare,
	int_compare_digit,
}

    cmp_mag ¶
    Source

    cmp_mag :: proc{
	int_compare_magnitude,
}

    compare ¶
    Source

    compare :: proc{
	int_compare,
	int_compare_digit,
}

    compare_magnitude ¶
    Source

    compare_magnitude :: proc{
	int_compare_magnitude,
}

    copy ¶
    Source

    copy :: proc{
	int_copy,
	rat_copy,
}

    count_lsb ¶
    Source

    count_lsb :: proc{
	int_count_lsb,
	platform_count_lsb,
}

    destroy ¶
    Source

    destroy :: proc{
	int_destroy,
}

    div ¶
    Source

    divmod ¶
    Source

    divmod :: proc{
	int_divmod,
	int_divmod_digit,
}

    double ¶
    Source

    double :: proc{
	int_double,
}

    eq ¶
    Source

    eq :: proc{
	int_equals,
	int_equals_digit,
}

    eq_abs ¶
    Source

    eq_abs :: proc{
	int_equals_abs,
}

    equals ¶
    Source

    equals :: proc{
	int_equals,
	int_equals_digit,
}

    equals_abs ¶
    Source

    equals_abs :: proc{
	int_equals_abs,
}

    error_if_immutable ¶
    Source

    error_if_immutable :: proc{
	error_if_immutable_single,
	error_if_immutable_multi,
}

    exp ¶
    Source

    exp :: proc{
	int_pow,
	int_pow_int,
	small_pow,
}

    factorial ¶
    Source

    factorial :: proc{
	int_factorial,
}

    gcd ¶
    Source

    gcd :: proc{
	int_gcd,
}

    gcd_lcm ¶
    Source

    gcd_lcm :: proc{
	int_gcd_lcm,
}

    get ¶
    Source

    get :: proc{
	int_get,
}

    get_i128 ¶
    Source

    get_i128 :: proc{
	int_get_i128,
}

    get_i32 ¶
    Source

    get_i32 :: proc{
	int_get_i32,
}

    get_i64 ¶
    Source

    get_i64 :: proc{
	int_get_i64,
}

    get_u128 ¶
    Source

    get_u128 :: proc{
	int_get_u128,
}

    get_u32 ¶
    Source

    get_u32 :: proc{
	int_get_u32,
}

    get_u64 ¶
    Source

    get_u64 :: proc{
	int_get_u64,
}

    greater_than ¶
    Source

    greater_than :: proc{
	int_greater_than,
	int_greater_than_digit,
}

    greater_than_abs ¶
    Source

    greater_than_abs :: proc{
	int_greater_than_abs,
}

    greater_than_or_equal ¶
    Source

    greater_than_or_equal :: proc{
	int_greater_than_or_equal,
	int_greater_than_or_equal_digit,
}

    greater_than_or_equal_abs ¶
    Source

    greater_than_or_equal_abs :: proc{
	int_greater_than_or_equal_abs,
}

    grow ¶
    Source

    grow :: proc{
	int_grow,
}

    gt ¶
    Source

    gt_abs ¶
    Source

    gt_abs :: proc{
	int_greater_than_abs,
}

    gteq ¶
    Source

    gteq_abs ¶
    Source

    gteq_abs :: proc{
	int_greater_than_or_equal_abs,
}

    halve ¶
    Source

    halve :: proc{
	int_halve,
}

    inf ¶
    Source

    inf :: proc{
	int_inf,
}

    init_multi ¶
    Source

    init_multi :: proc{
	int_init_multi,
}

    internal_abs ¶
    Source

    internal_abs :: proc{
	internal_int_abs,
	internal_platform_abs,
}

    internal_add ¶
    Source

    internal_add_signed ¶
    Source

    internal_add_signed :: proc{
	internal_int_add_signed,
}

    internal_add_unsigned ¶
    Source

    internal_add_unsigned :: proc{
	internal_int_add_unsigned,
}

    internal_addmod ¶
    Source

    internal_addmod :: proc{
	internal_int_addmod,
}

    internal_and ¶
    Source

    internal_and :: proc{
	internal_int_and,
}

    internal_clear ¶
    Source

    internal_clear :: proc{
	internal_int_clear,
}

    internal_clear_if_uninitialized ¶
    Source

    internal_cmp ¶
    Source

    internal_cmp_digit ¶
    Source

    internal_cmp_digit :: proc{
	internal_int_compare_digit,
}

    internal_cmp_mag ¶
    Source

    internal_cmp_mag :: proc{
	internal_int_compare_magnitude,
}

    internal_compare ¶
    Source

    internal_compare :: proc{
	internal_int_compare,
	internal_int_compare_digit,
}

    internal_compare_digit ¶
    Source

    internal_compare_digit :: proc{
	internal_int_compare_digit,
}

    internal_compare_magnitude ¶
    Source

    internal_compare_magnitude :: proc{
	internal_int_compare_magnitude,
}

    internal_complement ¶
    Source

    internal_complement :: proc{
	internal_int_complement,
}

    internal_copy ¶
    Source

    internal_copy :: proc{
	internal_int_copy,
}

    internal_count_lsb ¶
    Source

    internal_count_lsb :: proc{
	internal_int_count_lsb,
	internal_platform_count_lsb,
}

    internal_decr ¶
    Source

    internal_decr :: proc{
	internal_int_decr,
}

    internal_destroy ¶
    Source

    internal_destroy :: proc{
	internal_int_destroy,
	internal_rat_destroy,
}

    internal_div ¶
    Source

    internal_div :: proc{
	internal_int_div,
}

    internal_divmod ¶
    Source

    internal_divmod :: proc{
	internal_int_divmod,
	internal_int_divmod_digit,
}

    internal_eq ¶
    Source

    internal_eq_abs ¶
    Source

    internal_eq_abs :: proc{
	internal_int_equals_abs,
}

    internal_equals ¶
    Source

    internal_equals :: proc{
	internal_int_equals,
	internal_int_equals_digit,
}

    internal_equals_abs ¶
    Source

    internal_equals_abs :: proc{
	internal_int_equals_abs,
}

    internal_error_if_immutable ¶
    Source

    internal_exp ¶
    Source

    internal_exp :: proc{
	int_pow,
	int_pow_int,
	small_pow,
}

    internal_get ¶
    Source

    internal_get :: proc{
	internal_int_get,
}

    internal_get_i128 ¶
    Source

    internal_get_i128 :: proc{
	internal_int_get_i128,
}

    internal_get_i32 ¶
    Source

    internal_get_i32 :: proc{
	internal_int_get_i32,
}

    internal_get_i64 ¶
    Source

    internal_get_i64 :: proc{
	internal_int_get_i64,
}

    internal_get_u128 ¶
    Source

    internal_get_u128 :: proc{
	internal_int_get_u128,
}

    internal_get_u32 ¶
    Source

    internal_get_u32 :: proc{
	internal_int_get_u32,
}

    internal_get_u64 ¶
    Source

    internal_get_u64 :: proc{
	internal_int_get_u64,
}

    internal_greater_than ¶
    Source

    internal_greater_than :: proc{
	internal_int_greater_than,
	internal_int_greater_than_digit,
}

    internal_greater_than_abs ¶
    Source

    internal_greater_than_abs :: proc{
	internal_int_greater_than_abs,
}

    internal_greater_than_or_equal ¶
    Source

    internal_greater_than_or_equal_abs ¶
    Source

    internal_greater_than_or_equal_abs :: proc{
	internal_int_greater_than_or_equal_abs,
}

    internal_grow ¶
    Source

    internal_grow :: proc{
	internal_int_grow,
}

    internal_gt ¶
    Source

    internal_gt_abs ¶
    Source

    internal_gt_abs :: proc{
	internal_int_greater_than_abs,
}

    internal_gte ¶
    Source

    internal_gte_abs ¶
    Source

    internal_gte_abs :: proc{
	internal_int_greater_than_or_equal_abs,
}

    internal_incr ¶
    Source

    internal_incr :: proc{
	internal_int_incr,
}

    internal_inf ¶
    Source

    internal_inf :: proc{
	internal_int_inf,
}

    internal_init_multi ¶
    Source

    internal_init_multi :: proc{
	internal_int_init_multi,
}

    internal_invmod ¶
    Source

    internal_invmod :: proc{
	internal_int_inverse_modulo,
}

    internal_is_even ¶
    Source

    internal_is_even :: proc{
	internal_int_is_even,
}

    internal_is_initialized ¶
    Source

    internal_is_initialized :: proc{
	internal_int_is_initialized,
}

    internal_is_negative ¶
    Source

    internal_is_negative :: proc{
	internal_int_is_negative,
}

    internal_is_odd ¶
    Source

    internal_is_odd :: proc{
	internal_int_is_odd,
}

    internal_is_positive ¶
    Source

    internal_is_positive :: proc{
	internal_int_is_positive,
}

    internal_is_power_of_two ¶
    Source

    internal_is_power_of_two :: proc{
	internal_int_is_power_of_two,
}

    internal_is_zero ¶
    Source

    internal_is_zero :: proc{
	internal_rat_is_zero,
	internal_int_is_zero,
}

    internal_less_than ¶
    Source

    internal_less_than :: proc{
	internal_int_less_than,
	internal_int_less_than_digit,
}

    internal_less_than_abs ¶
    Source

    internal_less_than_abs :: proc{
	internal_int_less_than_abs,
}

    internal_less_than_or_equal ¶
    Source

    internal_less_than_or_equal_abs ¶
    Source

    internal_less_than_or_equal_abs :: proc{
	internal_int_less_than_or_equal_abs,
}

    internal_log ¶
    Source

    internal_log :: proc{
	internal_int_log,
	internal_digit_log,
}

    internal_lt ¶
    Source

    internal_lt_abs ¶
    Source

    internal_lt_abs :: proc{
	internal_int_less_than_abs,
}

    internal_lte ¶
    Source

    internal_lte_abs ¶
    Source

    internal_lte_abs :: proc{
	internal_int_less_than_or_equal_abs,
}

    internal_minus_inf ¶
    Source

    internal_minus_inf :: proc{
	internal_int_inf,
}

    internal_minus_one ¶
    Source

    internal_minus_one :: proc{
	internal_int_minus_one,
}

    internal_mod ¶
    Source

    internal_mod :: proc{
	internal_int_mod,
	internal_int_mod_digit,
}

    internal_mul ¶
    Source

    internal_mulmod ¶
    Source

    internal_mulmod :: proc{
	internal_int_mulmod,
}

    internal_nan ¶
    Source

    internal_nan :: proc{
	internal_int_nan,
}

    internal_neg ¶
    Source

    internal_neg :: proc{
	internal_int_neg,
}

    internal_one ¶
    Source

    internal_one :: proc{
	internal_int_one,
}

    internal_or ¶
    Source

    internal_or :: proc{
	internal_int_or,
}

    internal_pow ¶
    Source

    internal_pow :: proc{
	internal_int_pow,
	internal_int_pow_int,
}

    internal_powmod ¶
    Source

    internal_powmod :: proc{
	internal_int_power_modulo,
}

    internal_random ¶
    Source

    internal_random :: proc{
	internal_int_random,
}

    internal_root_n ¶
    Source

    internal_root_n :: proc{
	internal_int_root_n,
}

    internal_set ¶
    Source

    internal_shl ¶
    Source

    internal_shl :: proc{
	internal_int_shl,
}

    internal_shr ¶
    Source

    internal_shr :: proc{
	internal_int_shr,
}

    internal_shr_signed ¶
    Source

    internal_shr_signed :: proc{
	internal_int_shr_signed,
}

    internal_shrink ¶
    Source

    internal_shrink :: proc{
	internal_int_shrink,
}

    internal_shrmod ¶
    Source

    internal_shrmod :: proc{
	internal_int_shrmod,
}

    internal_sqrmod ¶
    Source

    internal_sqrmod :: proc{
	internal_int_sqrmod,
}

    internal_sqrt ¶
    Source

    internal_sqrt :: proc{
	internal_int_sqrt,
}

    internal_sub ¶
    Source

    internal_sub_unsigned ¶
    Source

    internal_sub_unsigned :: proc{
	internal_int_sub_unsigned,
}

    internal_submod ¶
    Source

    internal_submod :: proc{
	internal_int_submod,
}

    internal_swap ¶
    Source

    internal_swap :: proc{
	internal_int_swap,
	internal_rat_swap,
}

    internal_xor ¶
    Source

    internal_xor :: proc{
	internal_int_xor,
}

    internal_zero ¶
    Source

    internal_zero :: proc{
	internal_int_clear,
}

    internal_zero_unused ¶
    Source

    internal_zero_unused :: proc{
	internal_int_zero_unused,
}

    is_even ¶
    Source

    is_even :: proc{
	int_is_even,
	rat_is_even,
}

    is_initialized ¶
    Source

    is_initialized :: proc{
	int_is_initialized,
}

    is_neg ¶
    Source

    is_neg :: proc{
	int_is_negative,
	rat_is_negative,
}

    is_negative ¶
    Source

    is_negative :: proc{
	int_is_negative,
	rat_is_negative,
}

    is_odd ¶
    Source

    is_odd :: proc{
	int_is_odd,
	rat_is_odd,
}

    is_pos ¶
    Source

    is_pos :: proc{
	int_is_positive,
	rat_is_positive,
}

    is_positive ¶
    Source

    is_positive :: proc{
	int_is_positive,
	rat_is_positive,
}

    is_power_of_two ¶
    Source

    is_power_of_two :: proc{
	platform_int_is_power_of_two,
	int_is_power_of_two,
}

    is_zero ¶
    Source

    is_zero :: proc{
	int_is_zero,
	rat_is_zero,
}

    itoa ¶
    Source

    itoa :: proc{
	int_itoa_string,
	int_itoa_raw,
}

    lcm ¶
    Source

    lcm :: proc{
	int_lcm,
}

    less_than ¶
    Source

    less_than :: proc{
	int_less_than,
	int_less_than_digit,
}

    less_than_abs ¶
    Source

    less_than_abs :: proc{
	int_less_than_abs,
}

    less_than_or_equal ¶
    Source

    less_than_or_equal :: proc{
	int_less_than_or_equal,
	int_less_than_or_equal_digit,
}

    less_than_or_equal_abs ¶
    Source

    less_than_or_equal_abs :: proc{
	int_less_than_or_equal_abs,
}

    log ¶
    Source

    log :: proc{
	int_log,
	digit_log,
}

    lt ¶
    Source

    lt_abs ¶
    Source

    lt_abs :: proc{
	int_less_than_abs,
}

    lteq ¶
    Source

    lteq_abs ¶
    Source

    lteq_abs :: proc{
	int_less_than_or_equal_abs,
}

    minus_inf ¶
    Source

    minus_inf :: proc{
	int_inf,
}

    minus_one ¶
    Source

    minus_one :: proc{
	int_minus_one,
}

    mod ¶
    Source

    mod :: proc{
	int_mod,
	int_mod_digit,
}

    mod_bits ¶
    Source

    mod_bits :: proc{
	int_mod_bits,
}

    mul ¶
    Source

    mulmod ¶
    Source

    mulmod :: proc{
	int_mulmod,
}

    nan ¶
    Source

    nan :: proc{
	int_nan,
}

    neg ¶
    Source

    neg :: proc{
	int_neg,
	rat_neg,
}

    one ¶
    Source

    one :: proc{
	int_one,
}

    pow ¶
    Source

    pow :: proc{
	int_pow,
	int_pow_int,
	small_pow,
}

    random ¶
    Source

    random :: proc{
	int_random,
}

    rat_set_frac ¶
    Source

    rat_set_frac :: proc{
	rat_set_frac_digit,
	rat_set_frac_int,
}

    root_n ¶
    Source

    root_n :: proc{
	int_root_n,
}

    set ¶
    Source

    shl ¶
    Source

    shl :: proc{
	int_shl,
}

    shl1 ¶
    Source

    shl1 :: proc{
	int_double,
}

    shr ¶
    Source

    shr :: proc{
	int_shr,
}

    shr1 ¶
    Source

    shr1 :: proc{
	int_halve,
}

    shr_signed ¶
    Source

    shr_signed :: proc{
	int_shr_signed,
}

    shrmod ¶
    Source

    shrmod :: proc{
	int_shrmod,
}

    sqr ¶
    Source

    sqr :: proc{
	int_sqr,
	rat_sqr,
}

    sqrmod ¶
    Source

    sqrmod :: proc{
	int_sqrmod,
}

    sqrt ¶
    Source

    sqrt :: proc{
	int_sqrt,
}

    sub ¶
    Source

     

    err = sub(dest, a, b);

    submod ¶
    Source

    submod :: proc{
	int_submod,
}

    swap ¶
    Source

    swap :: proc{
	int_swap,
	rat_swap,
}

    zero ¶
    Source

    zero :: proc{
	int_clear,
}

    Source Files

    Generation Information

    Generated with odin version dev-2024-04 (vendor "odin") Windows_amd64 @ 2024-04-25 21:10:21.762554700 +0000 UTC