package core:math/big

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 (319)
Procedure Groups (187)

Types

Category ¶

Category :: enum int {
	itoa, 
	atoi, 
	factorial, 
	factorial_bin, 
	choose, 
	lsb, 
	ctz, 
	sqr, 
	bitfield_extract, 
	rm_trials, 
	is_prime, 
	random_prime, 
}

DIGIT ¶

DIGIT :: distinct u64
 

We can use u128 as an intermediary.

Endianness ¶

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

Error ¶

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.

Event ¶

Event :: struct {
	ticks:  time.Duration,
	count:  int,
	cycles: u64,
}

Flag ¶

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

Flags ¶

Flags :: bit_set[Flag; u8]

Int ¶

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

Order ¶

Order :: enum i8 {
	LSB_First = -1, 
	MSB_First = 1, 
}

Primality_Flag ¶

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 ¶

Primality_Flags :: bit_set[Primality_Flag; u8]

Rat ¶

Rat :: struct {
	a,
	b: Int,
}

Sign ¶

Sign :: enum u8 {
	Zero_or_Positive = 0, 
	Negative         = 1, 
}

Constants

Error_String ¶

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 ¶

MATH_BIG_FORCE_32_BIT :: #config(MATH_BIG_FORCE_32_BIT, false)

MATH_BIG_FORCE_64_BIT ¶

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 ¶

MATH_BIG_USE_FROBENIUS_TEST :: !MATH_BIG_USE_LUCAS_SELFRIDGE_TEST

MATH_BIG_USE_LUCAS_SELFRIDGE_TEST ¶

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 ¶

RADIX_TABLE_REVERSE_SIZE :: 80

Variables

FACTORIAL_BINARY_SPLIT_CUTOFF ¶

FACTORIAL_BINARY_SPLIT_CUTOFF: int = …
 

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

FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS ¶

FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS: int = …

FACTORIAL_MAX_N ¶

FACTORIAL_MAX_N: int = …
 

Largest N for which we'll compute N!

INT_INF ¶

INT_INF: ^Int = …
 

Initialize constants.

INT_MINUS_INF ¶

INT_MINUS_INF: ^Int = …
 

Initialize constants.

INT_MINUS_ONE ¶

INT_MINUS_ONE: ^Int = …
 

Initialize constants.

INT_NAN ¶

INT_NAN: ^Int = …
 

Initialize constants.

INT_ONE ¶

INT_ONE: ^Int = …
 

Initialize constants.

INT_ZERO ¶

INT_ZERO: ^Int = …
 

Initialize constants.

MAX_ITERATIONS_RANDOM_PRIME ¶

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 ¶

MAX_ITERATIONS_ROOT_N: int = …

MUL_KARATSUBA_CUTOFF ¶

MUL_KARATSUBA_CUTOFF: int = …

MUL_TOOM_CUTOFF ¶

MUL_TOOM_CUTOFF: int = …

RADIX_TABLE ¶

RADIX_TABLE: string = …
 

Characters used in radix conversions.

RADIX_TABLE_REVERSE ¶

RADIX_TABLE_REVERSE: [80]u8 = …

RANDOM_PRIME_ITERATIONS_USED ¶

@(thread_local)
RANDOM_PRIME_ITERATIONS_USED: int

SQR_KARATSUBA_CUTOFF ¶

SQR_KARATSUBA_CUTOFF: int = …

SQR_TOOM_CUTOFF ¶

SQR_TOOM_CUTOFF: int = …

Timings ¶

Timings: [Category]Event = …

USE_MILLER_RABIN_ONLY ¶

USE_MILLER_RABIN_ONLY: bool = …
 

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

Procedures

SCOPED_COUNT_ADD ¶

SCOPED_COUNT_ADD :: proc "odin" (c: Category, count: int) {…}

SCOPED_TIMING ¶

SCOPED_TIMING :: proc "odin" (c: Category) -> (ticks: time.Tick, cycles: u64) {…}

assert_if_nil_int ¶

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

assert_if_nil_rat ¶

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

assert_initialized ¶

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

Internal helpers.

clamp ¶

clamp :: proc "odin" (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 ¶

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

clear_if_uninitialized_single ¶

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

copy_digits ¶

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

count_bits ¶

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

Count bits in an Int.

destroy_constants ¶

destroy_constants :: proc "odin" () {…}
 

Destroy constants.

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

digit_log ¶

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

error_if_immutable_multi ¶

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

error_if_immutable_single ¶

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

ilog2 ¶

ilog2 :: proc "odin" (value: $) -> $ {…}

initialize_constants ¶

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

int_abs ¶

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

Set dest to |src|.

int_add ¶

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

High-level addition. Handles sign.

int_add_digit ¶

int_add_digit :: proc "odin" (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 ¶

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

int_addmod ¶

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

remainder = (number + addend) % modulus.

int_and ¶

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

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

int_atoi ¶

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

Read a string [ASCII] in a given radix.

int_bitfield_extract ¶

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

int_bitfield_extract_single ¶

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

Helpers to extract values from the Int.

int_choose_digit ¶

int_choose_digit :: proc "odin" (dest: ^Int, base, power: 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 ¶

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

Clear Int and resize it to the default size.

int_cmp ¶

int_cmp :: int_compare
 

Compare two Ints, signed.

int_cmp_digit ¶

int_cmp_digit :: int_compare_digit
 

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

int_cmp_mag ¶

int_cmp_mag :: int_compare_magnitude
 

Compare the magnitude of two Ints, unsigned.

int_compare ¶

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

Compare two Ints, signed.

int_compare_digit ¶

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

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

int_compare_magnitude ¶

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

Compare the magnitude of two Ints, unsigned.

int_complement ¶

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

dest = ~src

int_copy ¶

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

Copy one Int to another.

int_count_lsb ¶

int_count_lsb :: proc "odin" (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 ¶

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

Deallocates the backing memory of one or more Ints.

int_div ¶

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

int_div_digit ¶

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

int_div_rat ¶

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

int_divmod ¶

int_divmod :: proc "odin" (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 ¶

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

int_double ¶

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

dest = src * 2

dest = src << 1

int_equals ¶

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

bool := a == b

int_equals_abs ¶

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

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

int_equals_digit ¶

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

bool := a == b

int_factorial ¶

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

int_from_bytes_big ¶

int_from_bytes_big :: proc "odin" (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 ¶

int_from_bytes_big_python :: proc "odin" (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 ¶

int_from_bytes_little :: proc "odin" (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 ¶

int_from_bytes_little_python :: proc "odin" (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 ¶

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

Greatest Common Divisor.

int_gcd_lcm ¶

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

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

int_get ¶

int_get :: proc "odin" (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 ¶

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

int_get_i128 ¶

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

int_get_i32 ¶

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

int_get_i64 ¶

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

int_get_u128 ¶

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

int_get_u32 ¶

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

int_get_u64 ¶

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

int_greater_than ¶

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

bool := a > b

int_greater_than_abs ¶

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

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

int_greater_than_digit ¶

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

bool := a > b

int_greater_than_or_equal ¶

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

bool := a >= b

int_greater_than_or_equal_abs ¶

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

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

int_greater_than_or_equal_digit ¶

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

bool := a >= b

int_grow ¶

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

int_halve ¶

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

dest = src / 2

dest = src >> 1

int_inf ¶

int_inf :: proc "odin" (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 ¶

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

Allocates several Ints at once.

int_is_even ¶

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

int_is_initialized ¶

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

int_is_negative ¶

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

int_is_odd ¶

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

int_is_positive ¶

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

int_is_power_of_two ¶

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

int_is_square ¶

int_is_square :: proc "odin" (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 ¶

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

int_itoa_cstring ¶

int_itoa_cstring :: proc "odin" (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 ¶

int_itoa_raw :: proc "odin" (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 ¶

int_itoa_string :: proc "odin" (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 ¶

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

Least Common Multiple.

int_less_than ¶

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

bool := a < b

int_less_than_abs ¶

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

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

int_less_than_digit ¶

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

bool := a < b

int_less_than_or_equal ¶

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

bool := a <= b

int_less_than_or_equal_abs ¶

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

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

int_less_than_or_equal_digit ¶

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

bool := a <= b

int_log ¶

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

Logs and roots and such.

int_minus_inf ¶

int_minus_inf :: proc "odin" (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 ¶

int_minus_one :: proc "odin" (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 ¶

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

remainder = numerator % denominator.

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

int_mod_bits ¶

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

remainder = numerator % (1 << bits)

int_mod_digit ¶

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

int_mul ¶

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

High level multiplication (handles sign).

int_mul_digit ¶

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

Multiply by a DIGIT.

int_mul_rat ¶

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

int_mulmod ¶

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

remainder = (number * multiplicand) % modulus.

int_nan ¶

int_nan :: proc "odin" (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 ¶

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

Set dest to -src.

int_one ¶

int_one :: proc "odin" (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_or ¶

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

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

int_pow ¶

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

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

int_pow_int ¶

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

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

int_random ¶

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

int_random_digit ¶

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

int_root_n ¶

int_root_n :: proc "odin" (remainder, numerator: ^Int, bits: 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 ¶

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

Helpers to set an Int to a specific value.

int_shl ¶

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

Shift left by a certain bit count.

int_shr ¶

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

int_shr_signed ¶

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

Shift right by a certain bit count with sign extension.

int_shrmod ¶

int_shrmod :: proc "odin" (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 ¶

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

int_sqrmod ¶

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

remainder = (number * number) % modulus.

int_sqrt ¶

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

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

int_sub ¶

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

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

int_sub_digit ¶

int_sub_digit :: proc "odin" (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 ¶

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

int_submod ¶

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

remainder = (number - decrease) % modulus.

int_swap ¶

int_swap :: proc "odin" (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 ¶

int_to_bytes_big :: proc "odin" (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 ¶

int_to_bytes_big_python :: proc "odin" (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 ¶

int_to_bytes_little :: proc "odin" (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 ¶

int_to_bytes_little_python :: proc "odin" (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 ¶

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

Size binary representation

int_to_cstring ¶

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 ¶

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.

int_xor ¶

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

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

internal_assert_initialized ¶

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

Internal helpers.

internal_clamp ¶

internal_clamp :: proc "odin" (arg: ^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 ¶

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

internal_clear_if_uninitialized_single ¶

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

internal_copy_digits ¶

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

internal_count_bits ¶

internal_count_bits :: proc "odin" (a: ^Int) -> (cap: int) {…}
 

Count bits in an Int.

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

internal_digit_log ¶

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

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

internal_error_if_immutable_multi ¶

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

internal_error_if_immutable_single ¶

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

internal_get_low_u32 ¶

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

internal_get_low_u64 ¶

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

internal_int_abs ¶

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

Set dest to |src|.

internal_int_add_digit ¶

internal_int_add_digit :: proc "odin" (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 ¶

internal_int_add_signed :: proc "odin" (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 ¶

internal_int_add_unsigned :: proc "odin" (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 ¶

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

remainder = (number + addend) % modulus.

internal_int_allocated_cap ¶

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

This procedure returns the allocated capacity of an Int.

Assumes `a` not to be `nil`.

internal_int_and ¶

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

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

internal_int_bitfield_extract ¶

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

internal_int_bitfield_extract_bool ¶

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

Helpers to extract values from the Int.

Offset is zero indexed.

internal_int_bitfield_extract_single ¶

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

internal_int_bitfield_set_single ¶

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

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

Offset is zero indexed.

internal_int_bitfield_toggle_single ¶

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

internal_int_bitfield_unset_single ¶

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

internal_int_clear ¶

internal_int_clear :: proc "odin" (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 ¶

internal_int_compare :: proc "odin" (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 ¶

internal_int_compare_digit :: proc "odin" (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 ¶

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

Compare the magnitude of two Ints, unsigned.

internal_int_complement ¶

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

dest = ~src

internal_int_copy ¶

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

Copy one Int to another.

internal_int_count_lsb ¶

internal_int_count_lsb :: proc "odin" (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 ¶

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

internal_int_destroy ¶

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

Deallocates the backing memory of one or more Ints.

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

internal_int_div ¶

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

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

internal_int_divmod ¶

internal_int_divmod :: proc "odin" (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 ¶

internal_int_divmod_digit :: proc "odin" (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 ¶

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

bool := a == b

internal_int_equals_abs ¶

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

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

internal_int_equals_digit ¶

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

bool := a == b

internal_int_exponent_mod ¶

internal_int_exponent_mod :: proc "odin" (quotient, remainder, numerator, denominator: ^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_extended_euclidean ¶

internal_int_extended_euclidean :: proc "odin" (
	a, b, U1, U2, U3: ^Int, 
) -> (err: Error) {…}
 

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

internal_int_factorial ¶

internal_int_factorial :: proc "odin" (a: ^Int, power: 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 ¶

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

internal_int_gcd_lcm ¶

internal_int_gcd_lcm :: proc "odin" (quotient, remainder, numerator, denominator: ^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 ¶

internal_int_get :: proc "odin" (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 ¶

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

internal_int_get_i128 ¶

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

internal_int_get_i32 ¶

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

internal_int_get_i64 ¶

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

internal_int_get_u128 ¶

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

internal_int_get_u32 ¶

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

internal_int_get_u64 ¶

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

internal_int_greater_than ¶

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

bool := a > b

internal_int_greater_than_abs ¶

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

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

internal_int_greater_than_digit ¶

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

bool := a > b

internal_int_greater_than_or_equal ¶

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

bool := a >= b

internal_int_greater_than_or_equal_abs ¶

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

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

internal_int_greater_than_or_equal_digit ¶

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

bool := a >= b

internal_int_grow ¶

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

internal_int_incr ¶

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

internal_int_inf ¶

internal_int_inf :: proc "odin" (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 ¶

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

Allocates several Ints at once.

internal_int_inverse_modulo ¶

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

hac 14.61, pp608.

internal_int_is_even ¶

internal_int_is_even :: proc "odin" (a: ^Int) -> (initialized: bool) {…}
 

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

Assumes `a` not to be `nil`.

internal_int_is_initialized ¶

internal_int_is_initialized :: proc "odin" (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 ¶

internal_int_is_negative :: proc "odin" (a: ^Int) -> (initialized: bool) {…}
 

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

Assumes `a` not to be `nil`.

internal_int_is_odd ¶

internal_int_is_odd :: proc "odin" (a: ^Int) -> (initialized: bool) {…}
 

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

Assumes `a` not to be `nil`.

internal_int_is_positive ¶

internal_int_is_positive :: proc "odin" (a: ^Int) -> (initialized: 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 ¶

internal_int_is_power_of_two :: proc "odin" (a: ^Int) -> (initialized: 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 ¶

internal_int_is_prime :: proc "odin" (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 ¶

internal_int_is_square :: proc "odin" (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 ¶

internal_int_is_zero :: proc "odin" (a: ^Int) -> (initialized: bool) {…}
 

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

Assumes `a` not to be `nil`.

internal_int_kronecker ¶

internal_int_kronecker :: proc "odin" (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 ¶

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

internal_int_legendre ¶

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 ¶

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

bool := a < b

internal_int_less_than_abs ¶

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

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

internal_int_less_than_digit ¶

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

bool := a < b

internal_int_less_than_or_equal ¶

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

bool := a <= b

internal_int_less_than_or_equal_abs ¶

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

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

internal_int_less_than_or_equal_digit ¶

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

bool := a <= b

internal_int_log ¶

internal_int_log :: proc "odin" (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 ¶

internal_int_minus_inf :: proc "odin" (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 ¶

internal_int_minus_one :: proc "odin" (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 ¶

internal_int_mod :: proc "odin" (dest, a, b: ^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 ¶

internal_int_mod_bits :: proc "odin" (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 ¶

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

internal_int_mul ¶

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

High level multiplication (handles sign).

internal_int_mul_denom ¶

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

internal_int_mul_digit ¶

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

Multiply by a DIGIT.

internal_int_mul_integer ¶

internal_int_mul_integer :: proc "odin" (dest, a: ^Int, b: $, 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 ¶

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

remainder = (number * multiplicand) % modulus.

internal_int_nan ¶

internal_int_nan :: proc "odin" (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 ¶

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

Set dest to -src.

internal_int_one ¶

internal_int_one :: proc "odin" (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 ¶

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

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

internal_int_pack ¶

internal_int_pack :: proc "odin" (a: ^Int, buf: []$, 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 ¶

internal_int_pack_count :: proc "odin" (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 ¶

internal_int_pow :: proc "odin" (remainder, numerator: ^Int, bits: 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 ¶

internal_int_pow_int :: proc "odin" (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_of_two ¶

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

internal_int_prime_frobenius_underwood ¶

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

internal_int_prime_is_divisible ¶

internal_int_prime_is_divisible :: proc "odin" (a: ^Int, allocator := context.allocator) -> (square: 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 ¶

internal_int_prime_miller_rabin :: proc "odin" (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 ¶

internal_int_prime_next_prime :: proc "odin" (a: ^Int, digits: int, allow_shrink: bool = false, 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 ¶

internal_int_prime_strong_lucas_selfridge :: proc "odin" (a: ^Int, allocator := context.allocator) -> (square: 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 .
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 ¶

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

internal_int_random_digit ¶

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

internal_int_read_from_ascii_file ¶

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

Read an Int from an ASCII file.

internal_int_root_n ¶

internal_int_root_n :: proc "odin" (remainder, numerator: ^Int, bits: 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 ¶

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

internal_int_set_from_integer ¶

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

Helpers to set an Int to a specific value.

internal_int_shl ¶

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

Shift left by a certain bit count.

internal_int_shl1 ¶

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

dest = src * 2

dest = src << 1

internal_int_shr ¶

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

internal_int_shr1 ¶

internal_int_shr1 :: proc "odin" (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 ¶

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

Shift right by a certain bit count with sign extension.

internal_int_shrink ¶

internal_int_shrink :: proc "odin" (arg: ^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 ¶

internal_int_shrmod :: proc "odin" (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 ¶

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

remainder = (number * number) % modulus.

internal_int_sqrt ¶

internal_int_sqrt :: proc "odin" (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 ¶

internal_int_sqrtmod_prime :: proc "odin" (dest, a, b: ^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 ¶

internal_int_sub_digit :: proc "odin" (dest, a: ^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 ¶

internal_int_sub_signed :: proc "odin" (dest, a, b: ^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 ¶

internal_int_sub_unsigned :: proc "odin" (dest, a, b: ^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 ¶

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

remainder = (number - decrease) % modulus.

internal_int_swap ¶

internal_int_swap :: proc "odin" (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 ¶

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

internal_int_write_to_ascii_file ¶

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

Write an Int to an ASCII file.

internal_int_xor ¶

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

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

internal_int_zero_unused ¶

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

internal_platform_abs ¶

internal_platform_abs :: proc "odin" (value: $) -> $ {…}

internal_platform_count_lsb ¶

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

internal_prime_fermat ¶

internal_prime_fermat :: proc "odin" (a, b: ^Int, allocator := context.allocator) -> (probably_prime: 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 ¶

internal_random_prime :: proc "odin" (
	a:            ^Int, 
	size_in_bits: int, 
	trials:       int, 
	flags:        bit_set[Primality_Flag; u8] = Primality_Flags{}, 
	r:            ^rand.Rand = nil, 
) -> (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 ¶

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

internal_rat_is_zero ¶

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

internal_rat_norm ¶

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

internal_rat_swap ¶

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

internal_rat_to_float ¶

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

internal_small_pow ¶

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

internal_sqr ¶

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

number_of_rabin_miller_trials ¶

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

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

platform_abs ¶

platform_abs :: proc "odin" (value: $) -> $ {…}

platform_count_lsb ¶

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

platform_int_is_power_of_two ¶

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

power_of_two ¶

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

print ¶

print :: proc "odin" (
	name:       string, 
	a:          ^Int, 
	base:       i8 = i8(10), 
	print_name: bool = true, 
	newline:    bool = true, 
) {…}
print_bool :: proc "odin" (name: string, value: bool) {…}
print_configation :: proc "odin" () {…}
print_timings :: proc "odin" () {…}
print_value :: proc "odin" (name: string, value: i64) {…}

radix_size ¶

radix_size :: proc "odin" (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 ¶

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

rat_add_int ¶

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

rat_add_rat ¶

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

rat_compare ¶

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

rat_copy ¶

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

rat_div_int ¶

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

rat_div_rat ¶

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

rat_is_even ¶

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

rat_is_int ¶

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

rat_is_negative ¶

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

rat_is_odd ¶

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

rat_is_positive ¶

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

rat_is_zero ¶

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

rat_mul_int ¶

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

rat_mul_rat ¶

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

rat_neg ¶

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

rat_set_digit ¶

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

rat_set_f16 ¶

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

rat_set_f32 ¶

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

rat_set_f64 ¶

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

rat_set_frac_digit ¶

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

rat_set_frac_int ¶

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

rat_set_i64 ¶

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

rat_set_int ¶

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

rat_set_rat ¶

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

rat_set_u64 ¶

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

rat_sign ¶

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

rat_sqr ¶

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

rat_sub_int ¶

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

rat_sub_rat ¶

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

rat_swap ¶

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

rat_to_f16 ¶

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

rat_to_f32 ¶

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

rat_to_f64 ¶

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

shrink ¶

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

Resize backing store.

small_pow ¶

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

zero_unused ¶

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

Procedure Groups

add ¶

 

High-level addition. Handles sign.

addmod ¶

addmod :: proc{
	int_addmod,
}

and ¶

and :: proc{
	int_and,
}

atoi ¶

atoi :: proc{
	int_atoi,
}

choose ¶

choose :: proc{
	int_choose_digit,
}

clear ¶

clear :: proc{
	int_clear,
}

compare_magnitude ¶

compare_magnitude :: proc{
	int_compare_magnitude,
}

complement ¶

complement :: proc{
	int_complement,
}

copy ¶

copy :: proc{
	int_copy,
	rat_copy,
}

destroy ¶

destroy :: proc{
	int_destroy,
}

double ¶

double :: proc{
	int_double,
}

eq_abs ¶

eq_abs :: proc{
	int_equals_abs,
}

equals_abs ¶

equals_abs :: proc{
	int_equals_abs,
}

factorial ¶

factorial :: proc{
	int_factorial,
}

gcd ¶

gcd :: proc{
	int_gcd,
}

gcd_lcm ¶

gcd_lcm :: proc{
	int_gcd_lcm,
}

get ¶

get :: proc{
	int_get,
}

get_i128 ¶

get_i128 :: proc{
	int_get_i128,
}

get_i32 ¶

get_i32 :: proc{
	int_get_i32,
}

get_i64 ¶

get_i64 :: proc{
	int_get_i64,
}

get_u128 ¶

get_u128 :: proc{
	int_get_u128,
}

get_u32 ¶

get_u32 :: proc{
	int_get_u32,
}

get_u64 ¶

get_u64 :: proc{
	int_get_u64,
}

greater_than_abs ¶

greater_than_abs :: proc{
	int_greater_than_abs,
}

grow ¶

grow :: proc{
	int_grow,
}

halve ¶

halve :: proc{
	int_halve,
}

inf ¶

inf :: proc{
	int_inf,
}

init_multi ¶

init_multi :: proc{
	int_init_multi,
}

internal_add_signed ¶

internal_add_signed :: proc{
	internal_int_add_signed,
}

internal_addmod ¶

internal_addmod :: proc{
	internal_int_addmod,
}

internal_and ¶

internal_and :: proc{
	internal_int_and,
}

internal_clear ¶

internal_clear :: proc{
	internal_int_clear,
}

internal_complement ¶

internal_complement :: proc{
	internal_int_complement,
}

internal_copy ¶

internal_copy :: proc{
	internal_int_copy,
}

internal_decr ¶

internal_decr :: proc{
	internal_int_decr,
}

internal_div ¶

internal_div :: proc{
	internal_int_div,
}

internal_equals_abs ¶

internal_equals_abs :: proc{
	internal_int_equals_abs,
}

internal_get ¶

internal_get :: proc{
	internal_int_get,
}

internal_get_i128 ¶

internal_get_i128 :: proc{
	internal_int_get_i128,
}

internal_get_i32 ¶

internal_get_i32 :: proc{
	internal_int_get_i32,
}

internal_get_i64 ¶

internal_get_i64 :: proc{
	internal_int_get_i64,
}

internal_get_u128 ¶

internal_get_u128 :: proc{
	internal_int_get_u128,
}

internal_get_u32 ¶

internal_get_u32 :: proc{
	internal_int_get_u32,
}

internal_get_u64 ¶

internal_get_u64 :: proc{
	internal_int_get_u64,
}

internal_grow ¶

internal_grow :: proc{
	internal_int_grow,
}

internal_incr ¶

internal_incr :: proc{
	internal_int_incr,
}

internal_inf ¶

internal_inf :: proc{
	internal_int_inf,
}

internal_init_multi ¶

internal_init_multi :: proc{
	internal_int_init_multi,
}

internal_is_even ¶

internal_is_even :: proc{
	internal_int_is_even,
}

internal_is_negative ¶

internal_is_negative :: proc{
	internal_int_is_negative,
}

internal_is_odd ¶

internal_is_odd :: proc{
	internal_int_is_odd,
}

internal_is_positive ¶

internal_is_positive :: proc{
	internal_int_is_positive,
}

internal_minus_inf ¶

internal_minus_inf :: proc{
	internal_int_inf,
}

internal_minus_one ¶

internal_minus_one :: proc{
	internal_int_minus_one,
}

internal_mulmod ¶

internal_mulmod :: proc{
	internal_int_mulmod,
}

internal_nan ¶

internal_nan :: proc{
	internal_int_nan,
}

internal_neg ¶

internal_neg :: proc{
	internal_int_neg,
}

internal_one ¶

internal_one :: proc{
	internal_int_one,
}

internal_or ¶

internal_or :: proc{
	internal_int_or,
}

internal_random ¶

internal_random :: proc{
	internal_int_random,
}

internal_root_n ¶

internal_root_n :: proc{
	internal_int_root_n,
}

internal_shl ¶

internal_shl :: proc{
	internal_int_shl,
}

internal_shr ¶

internal_shr :: proc{
	internal_int_shr,
}

internal_shr_signed ¶

internal_shr_signed :: proc{
	internal_int_shr_signed,
}

internal_shrink ¶

internal_shrink :: proc{
	internal_int_shrink,
}

internal_shrmod ¶

internal_shrmod :: proc{
	internal_int_shrmod,
}

internal_sqrmod ¶

internal_sqrmod :: proc{
	internal_int_sqrmod,
}

internal_sqrt ¶

internal_sqrt :: proc{
	internal_int_sqrt,
}

internal_submod ¶

internal_submod :: proc{
	internal_int_submod,
}

internal_xor ¶

internal_xor :: proc{
	internal_int_xor,
}

internal_zero ¶

internal_zero :: proc{
	internal_int_clear,
}

internal_zero_unused ¶

internal_zero_unused :: proc{
	internal_int_zero_unused,
}

is_initialized ¶

is_initialized :: proc{
	int_is_initialized,
}

is_odd ¶

is_odd :: proc{
	int_is_odd,
	rat_is_odd,
}

lcm ¶

lcm :: proc{
	int_lcm,
}

less_than_abs ¶

less_than_abs :: proc{
	int_less_than_abs,
}

log ¶

log :: proc{
	int_log,
	digit_log,
}

lt_abs ¶

lt_abs :: proc{
	int_less_than_abs,
}

minus_inf ¶

minus_inf :: proc{
	int_inf,
}

minus_one ¶

minus_one :: proc{
	int_minus_one,
}

mod_bits ¶

mod_bits :: proc{
	int_mod_bits,
}

mulmod ¶

mulmod :: proc{
	int_mulmod,
}

nan ¶

nan :: proc{
	int_nan,
}

neg ¶

neg :: proc{
	int_neg,
	rat_neg,
}

one ¶

one :: proc{
	int_one,
}

or ¶

or :: proc{
	int_or,
}

random ¶

random :: proc{
	int_random,
}

root_n ¶

root_n :: proc{
	int_root_n,
}

shl ¶

shl :: proc{
	int_shl,
}

shl1 ¶

shl1 :: proc{
	int_double,
}

shr ¶

shr :: proc{
	int_shr,
}

shr1 ¶

shr1 :: proc{
	int_halve,
}

shr_signed ¶

shr_signed :: proc{
	int_shr_signed,
}

shrmod ¶

shrmod :: proc{
	int_shrmod,
}

sqr ¶

sqr :: proc{
	int_sqr,
	rat_sqr,
}

sqrmod ¶

sqrmod :: proc{
	int_sqrmod,
}

sqrt ¶

sqrt :: proc{
	int_sqrt,
}

sub ¶

 

err = sub(dest, a, b);

submod ¶

submod :: proc{
	int_submod,
}

swap ¶

swap :: proc{
	int_swap,
	rat_swap,
}

xor ¶

xor :: proc{
	int_xor,
}

zero ¶

zero :: proc{
	int_clear,
}

Source Files

Generation Information

Generated with odin version dev-2022-10 (vendor "odin") Windows_amd64 @ 2022-10-05 21:11:47.414296100 +0000 UTC