package core:math/big
Overview
Arbitrary precision integers and rationals.
Index
Types (10)
Constants (16)
Procedures (320)
assert_… (3)
- bit_length
- clamp
- clear_if_uninitialized_multi
- clear_if_uninitialized_single
- combinations_with_repetition
- combinations_without_repetition
- copy_digits
- count_bits
- digit_log
- error_if_immutable_multi
- error_if_immutable_single
int_… (113)
- int_abs
- int_add
- int_add_digit
- int_add_rat
- int_addmod
- int_atoi
- int_bit_and
- int_bit_complement
- int_bit_or
- int_bit_xor
- int_bitfield_extract
- int_bitfield_extract_single
- int_choose_digit
- int_clear
- int_cmp
- int_cmp_digit
- int_cmp_mag
- int_compare
- int_compare_digit
- int_compare_magnitude
- int_copy
- int_count_lsb
- int_destroy
- int_div
- int_div_digit
- int_div_rat
- int_divmod
- int_divmod_digit
- int_double
- int_equals
- int_equals_abs
- int_equals_digit
- int_factorial
- int_from_bytes_big
- int_from_bytes_big_python
- int_from_bytes_little
- int_from_bytes_little_python
- int_gcd
- int_gcd_lcm
- int_get
- int_get_float
- int_get_i128
- int_get_i32
- int_get_i64
- int_get_u128
- int_get_u32
- int_get_u64
- int_greater_than
- int_greater_than_abs
- int_greater_than_digit
- int_greater_than_or_equal
- int_greater_than_or_equal_abs
- int_greater_than_or_equal_digit
- int_grow
- int_halve
- int_inf
- int_init_multi
- int_is_even
- int_is_initialized
- int_is_negative
- int_is_odd
- int_is_positive
- int_is_power_of_two
- int_is_square
- int_is_zero
- int_itoa_cstring
- int_itoa_raw
- int_itoa_string
- int_lcm
- int_less_than
- int_less_than_abs
- int_less_than_digit
- int_less_than_or_equal
- int_less_than_or_equal_abs
- int_less_than_or_equal_digit
- int_log
- int_minus_inf
- int_minus_one
- int_mod
- int_mod_bits
- int_mod_digit
- int_mul
- int_mul_digit
- int_mul_rat
- int_mulmod
- int_nan
- int_neg
- int_one
- int_pow
- int_pow_int
- int_random
- int_random_digit
- int_root_n
- int_set_from_integer
- int_shl
- int_shr
- int_shr_signed
- int_shrmod
- int_sqr
- int_sqrmod
- int_sqrt
- int_sub
- int_sub_digit
- int_sub_rat
- int_submod
- int_swap
- int_to_bytes_big
- int_to_bytes_big_python
- int_to_bytes_little
- int_to_bytes_little_python
- int_to_bytes_size
- int_to_cstring
- int_to_string
internal_… (148)
- internal_assert_initialized
- internal_clamp
- internal_clear_if_uninitialized_multi
- internal_clear_if_uninitialized_single
- internal_clear_non_finite_multi
- internal_clear_non_finite_single
- internal_copy_digits
- internal_count_bits
- internal_digit_log
- internal_error_if_immutable_multi
- internal_error_if_immutable_single
- internal_error_if_non_finite_multi
- internal_error_if_non_finite_single
- internal_get_low_u32
- internal_get_low_u64
- internal_int_abs
- internal_int_add_digit
- internal_int_add_signed
- internal_int_add_unsigned
- internal_int_addmod
- internal_int_allocated_cap
- internal_int_and
- internal_int_bitfield_extract
- internal_int_bitfield_extract_bool
- internal_int_bitfield_extract_single
- internal_int_bitfield_set_single
- internal_int_bitfield_toggle_single
- internal_int_bitfield_unset_single
- internal_int_clear
- internal_int_compare
- internal_int_compare_digit
- internal_int_compare_magnitude
- internal_int_complement
- internal_int_copy
- internal_int_count_lsb
- internal_int_decr
- internal_int_destroy
- internal_int_div
- internal_int_divmod
- internal_int_divmod_digit
- internal_int_equals
- internal_int_equals_abs
- internal_int_equals_digit
- internal_int_exponent_mod
- internal_int_extended_euclidean
- internal_int_factorial
- internal_int_gcd
- internal_int_gcd_lcm
- internal_int_get
- internal_int_get_float
- internal_int_get_i128
- internal_int_get_i32
- internal_int_get_i64
- internal_int_get_u128
- internal_int_get_u32
- internal_int_get_u64
- internal_int_greater_than
- internal_int_greater_than_abs
- internal_int_greater_than_digit
- internal_int_greater_than_or_equal
- internal_int_greater_than_or_equal_abs
- internal_int_greater_than_or_equal_digit
- internal_int_grow
- internal_int_incr
- internal_int_inf
- internal_int_init_multi
- internal_int_inverse_modulo
- internal_int_invmod
- internal_int_is_even
- internal_int_is_initialized
- internal_int_is_negative
- internal_int_is_odd
- internal_int_is_positive
- internal_int_is_power_of_two
- internal_int_is_prime
- internal_int_is_square
- internal_int_is_zero
- internal_int_kronecker
- internal_int_lcm
- internal_int_legendre
- internal_int_less_than
- internal_int_less_than_abs
- internal_int_less_than_digit
- internal_int_less_than_or_equal
- internal_int_less_than_or_equal_abs
- internal_int_less_than_or_equal_digit
- internal_int_log
- internal_int_minus_inf
- internal_int_minus_one
- internal_int_mod
- internal_int_mod_bits
- internal_int_mod_digit
- internal_int_mul
- internal_int_mul_denom
- internal_int_mul_digit
- internal_int_mul_integer
- internal_int_mulmod
- internal_int_nan
- internal_int_neg
- internal_int_one
- internal_int_or
- internal_int_pack
- internal_int_pack_count
- internal_int_pow
- internal_int_pow_int
- internal_int_power_modulo
- internal_int_power_of_two
- internal_int_powmod
- internal_int_prime_frobenius_underwood
- internal_int_prime_is_divisible
- internal_int_prime_miller_rabin
- internal_int_prime_next_prime
- internal_int_prime_strong_lucas_selfridge
- internal_int_random
- internal_int_random_digit
- internal_int_read_from_ascii_file
- internal_int_root_n
- internal_int_scale_denom
- internal_int_set_from_integer
- internal_int_shl
- internal_int_shl1
- internal_int_shr
- internal_int_shr1
- internal_int_shr_signed
- internal_int_shrink
- internal_int_shrmod
- internal_int_sqrmod
- internal_int_sqrt
- internal_int_sqrtmod_prime
- internal_int_sub_digit
- internal_int_sub_signed
- internal_int_sub_unsigned
- internal_int_submod
- internal_int_swap
- internal_int_unpack
- internal_int_write_to_ascii_file
- internal_int_xor
- internal_int_zero_unused
- internal_platform_abs
- internal_platform_count_lsb
- internal_prime_fermat
- internal_random_prime
- internal_rat_destroy
- internal_rat_is_zero
- internal_rat_norm
- internal_rat_swap
- internal_rat_to_float
- internal_sqr
- number_of_rabin_miller_trials
- permutations_with_repetition
- permutations_without_repetition
platform_… (3)
- power_of_two
- radix_size
rat_… (34)
- rat_abs
- rat_add_int
- rat_add_rat
- rat_compare
- rat_copy
- rat_div_int
- rat_div_rat
- rat_is_even
- rat_is_int
- rat_is_negative
- rat_is_odd
- rat_is_positive
- rat_is_zero
- rat_mul_int
- rat_mul_rat
- rat_neg
- rat_set_digit
- rat_set_f16
- rat_set_f32
- rat_set_f64
- rat_set_frac_digit
- rat_set_frac_int
- rat_set_i64
- rat_set_int
- rat_set_rat
- rat_set_u64
- rat_sign
- rat_sqr
- rat_sub_int
- rat_sub_rat
- rat_swap
- rat_to_f16
- rat_to_f32
- rat_to_f64
- shrink
- string_to_int
- zero_unused
Procedure Groups (188)
- abs
- add
- addmod
- assert_if_nil
- atoi
bit_… (4)
- choose
- clear
- clear_if_uninitialized
- cmp
- cmp_mag
- compare
- compare_magnitude
- copy
- count_lsb
- destroy
- div
- divmod
- double
- eq
- eq_abs
- equals
- equals_abs
- error_if_immutable
- factorial
- gcd
- gcd_lcm
- get
- grow
- gt
- gt_abs
- gteq
- gteq_abs
- halve
- inf
- init_multi
internal_… (92)
- internal_abs
- internal_add
- internal_add_signed
- internal_add_unsigned
- internal_addmod
- internal_and
- internal_clear
- internal_clear_if_uninitialized
- internal_clear_non_finite
- internal_cmp
- internal_cmp_digit
- internal_cmp_mag
- internal_compare
- internal_compare_digit
- internal_compare_magnitude
- internal_complement
- internal_copy
- internal_count_lsb
- internal_decr
- internal_destroy
- internal_div
- internal_divmod
- internal_eq
- internal_eq_abs
- internal_equals
- internal_equals_abs
- internal_error_if_immutable
- internal_error_if_non_finite
- internal_get
- internal_get_i128
- internal_get_i32
- internal_get_i64
- internal_get_u128
- internal_get_u32
- internal_get_u64
- internal_greater_than
- internal_greater_than_abs
- internal_greater_than_or_equal
- internal_greater_than_or_equal_abs
- internal_grow
- internal_gt
- internal_gt_abs
- internal_gte
- internal_gte_abs
- internal_incr
- internal_inf
- internal_init_multi
- internal_invmod
- internal_is_even
- internal_is_initialized
- internal_is_negative
- internal_is_odd
- internal_is_positive
- internal_is_power_of_two
- internal_is_zero
- internal_less_than
- internal_less_than_abs
- internal_less_than_or_equal
- internal_less_than_or_equal_abs
- internal_log
- internal_lt
- internal_lt_abs
- internal_lte
- internal_lte_abs
- internal_minus_inf
- internal_minus_one
- internal_mod
- internal_mul
- internal_mulmod
- internal_nan
- internal_neg
- internal_one
- internal_or
- internal_pow
- internal_powmod
- internal_random
- internal_root_n
- internal_set
- internal_shl
- internal_shr
- internal_shr_signed
- internal_shrink
- internal_shrmod
- internal_sqrmod
- internal_sqrt
- internal_sub
- internal_sub_unsigned
- internal_submod
- internal_swap
- internal_xor
- internal_zero
- internal_zero_unused
- itoa
- lcm
- log
- lt
- lt_abs
- lteq
- lteq_abs
- minus_inf
- minus_one
- mod
- mod_bits
- mul
- mulmod
- nan
- neg
- one
- pow
- random
- rat_set_frac
- root_n
- set
- shl
- shl1
- shr
- shr1
- shr_signed
- shrmod
- sqr
- sqrmod
- sqrt
- sub
- submod
- swap
- zero
Types
DIGIT ¶
DIGIT :: distinct u64
We use u128 as an intermediary.
Related Procedures With Parameters
- digit_log
- int_add_digit
- int_compare_digit
- int_div_digit
- int_divmod_digit
- int_equals_digit
- int_greater_than_digit
- int_greater_than_or_equal_digit
- int_less_than_digit
- int_less_than_or_equal_digit
- int_log
- int_mod_digit
- int_mul_digit
- int_sub_digit
- internal_digit_log
- internal_int_add_digit
- internal_int_compare_digit
- internal_int_divmod_digit
- internal_int_equals_digit
- internal_int_greater_than_digit
- internal_int_greater_than_or_equal_digit
- internal_int_less_than_digit
- internal_int_less_than_or_equal_digit
- internal_int_log
- internal_int_mod_digit
- internal_int_mul_digit
- internal_int_sub_digit
- rat_set_digit
- rat_set_frac_digit
- add (procedure groups)
- cmp (procedure groups)
- compare (procedure groups)
- div (procedure groups)
- divmod (procedure groups)
- eq (procedure groups)
- equals (procedure groups)
- greater_than (procedure groups)
- greater_than_or_equal (procedure groups)
- gt (procedure groups)
- gteq (procedure groups)
- internal_add (procedure groups)
- internal_cmp (procedure groups)
- internal_cmp_digit (procedure groups)
- internal_compare (procedure groups)
- internal_compare_digit (procedure groups)
- internal_divmod (procedure groups)
- internal_eq (procedure groups)
- internal_equals (procedure groups)
- internal_greater_than (procedure groups)
- internal_greater_than_or_equal (procedure groups)
- internal_gt (procedure groups)
- internal_gte (procedure groups)
- internal_less_than (procedure groups)
- internal_less_than_or_equal (procedure groups)
- internal_log (procedure groups)
- internal_lt (procedure groups)
- internal_lte (procedure groups)
- internal_mod (procedure groups)
- internal_mul (procedure groups)
- internal_sub (procedure groups)
- less_than (procedure groups)
- less_than_or_equal (procedure groups)
- log (procedure groups)
- lt (procedure groups)
- lteq (procedure groups)
- mod (procedure groups)
- mul (procedure groups)
- rat_set_frac (procedure groups)
- set (procedure groups)
- sub (procedure groups)
Related Constants
Error ¶
Error :: enum u8 { None = 0, Out_Of_Memory = 1, Invalid_Pointer = 2, Invalid_Argument = 3, Mode_Not_Implemented = 4, // Allocation Assignment_To_Immutable = 10, Max_Iterations_Reached = 11, Buffer_Overflow = 12, Integer_Overflow = 13, Integer_Underflow = 14, Empty_Input = 20, Invalid_Character = 21, Trailing_Whitespace = 22, Division_by_Zero = 30, Math_Domain_Error = 31, Cannot_Open_File = 50, Cannot_Read_File = 51, Cannot_Write_File = 52, Unimplemented = 127, Okay = None, }
Errors are a strict superset of runtime.Allocation_Error.
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 ¶
A rational number a/b.
Results are canonical: b > 0, gcd(a, b) == 1, and zero is 0/1.
The zero value Rat{} is 0. A zero b with a nonzero a is invalid: procedures return .Division_by_Zero.
Operations expect canonical operands. internal_rat_norm makes a Rat canonical after setting a or b directly.
rat_set_f64 stores +/-Inf and NaN as +/-1/1 with .Inf or .NaN in a.flags. rat_to_f* returns them as inexact +/-Inf or NaN, rat_copy, rat_set_rat, rat_abs and rat_neg keep them, and rat_is_int is false for them. Arithmetic, rat_compare and rat_is_positive, rat_is_negative, rat_is_even and rat_is_odd return .Invalid_Argument for them.
Related Procedures With Parameters
- int_add_rat
- int_div_rat
- int_mul_rat
- int_sub_rat
- internal_rat_is_zero
- internal_rat_norm
- internal_rat_swap
- internal_rat_to_float
- rat_abs
- rat_add_int
- rat_add_rat
- rat_compare
- rat_copy
- rat_div_int
- rat_div_rat
- rat_is_even
- rat_is_int
- rat_is_negative
- rat_is_odd
- rat_is_positive
- rat_is_zero
- rat_mul_int
- rat_mul_rat
- rat_neg
- rat_set_digit
- rat_set_f16
- rat_set_f32
- rat_set_f64
- rat_set_frac_digit
- rat_set_frac_int
- rat_set_i64
- rat_set_int
- rat_set_rat
- rat_set_u64
- rat_sign
- rat_sqr
- rat_sub_int
- rat_sub_rat
- rat_swap
- rat_to_f16
- rat_to_f32
- rat_to_f64
- abs (procedure groups)
- add (procedure groups)
- copy (procedure groups)
- div (procedure groups)
- internal_is_zero (procedure groups)
- internal_swap (procedure groups)
- is_even (procedure groups)
- is_neg (procedure groups)
- is_negative (procedure groups)
- is_odd (procedure groups)
- is_pos (procedure groups)
- is_positive (procedure groups)
- is_zero (procedure groups)
- mul (procedure groups)
- neg (procedure groups)
- rat_set_frac (procedure groups)
- set (procedure groups)
- sqr (procedure groups)
- sub (procedure groups)
- swap (procedure groups)
Constants
Error_String ¶
Error_String: [Error]string : #sparse[Error]string{.None = "None", .Out_Of_Memory = "Out of memory", .Invalid_Pointer = "Invalid pointer", .Invalid_Argument = "Invalid argument", .Mode_Not_Implemented = "Allocation mode not implemented", .Assignment_To_Immutable = "Assignment to immutable", .Max_Iterations_Reached = "Max iterations reached", .Buffer_Overflow = "Buffer overflow", .Integer_Overflow = "Integer overflow", .Integer_Underflow = "Integer underflow", .Empty_Input = "Empty input", .Invalid_Character = "Invalid character", .Trailing_Whitespace = "Trailing whitespace", .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"}
FACTORIAL_BINARY_SPLIT_CUTOFF ¶
FACTORIAL_BINARY_SPLIT_CUTOFF :: #config(MATH_BIG_FACTORIAL_BINARY_SPLIT_CUTOFF, 6100)
-define:MATH_BIG_FACTORIAL_BINARY_SPLIT_CUTOFF=6100
Cutoff to switch to int_factorial_binary_split, and its max recursion level.
FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS ¶
FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS :: #config(MATH_BIG_FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS, 100)
-define:MATH_BIG_FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS=100
FACTORIAL_MAX_N ¶
FACTORIAL_MAX_N :: #config(MATH_BIG_FACTORIAL_MAX_N, 1_000_000)
-define:MATH_BIG_FACTORIAL_MAX_N=1_000_000
Largest N for which we'll compute N!
ITOA_COUNT ¶
ITOA_COUNT :: 18
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)
-define:MATH_BIG_USE_LUCAS_SELFRIDGE_TEST=false
internal_int_is_prime switchables.
Use Frobenius-Underwood for primality testing (default), or Lucas-Selfridge with -define:MATH_BIG_USE_LUCAS_SELFRIDGE_TEST=true.
MAX_ITERATIONS_RANDOM_PRIME ¶
MAX_ITERATIONS_RANDOM_PRIME :: #config(MATH_BIG_MAX_ITERATIONS_RANDOM_PRIME, 1_000_000)
-define:MATH_BIG_MAX_ITERATIONS_RANDOM_PRIME=1_000_000
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 :: #config(MATH_BIG_MAX_ITERATIONS_ROOT_N, 500)
-define:MATH_BIG_MAX_ITERATIONS_ROOT_N=500
MUL_KARATSUBA_CUTOFF ¶
MUL_KARATSUBA_CUTOFF :: #config(MATH_BIG_MUL_KARATSUBA_CUTOFF, 80)
-define:MATH_BIG_MUL_KARATSUBA_CUTOFF=80
MUL_TOOM_CUTOFF ¶
MUL_TOOM_CUTOFF :: #config(MATH_BIG_MUL_TOOM_CUTOFF, 350)
-define:MATH_BIG_MUL_TOOM_CUTOFF=350
RADIX_TABLE_REVERSE_SIZE ¶
RADIX_TABLE_REVERSE_SIZE :: 80
SQR_KARATSUBA_CUTOFF ¶
SQR_KARATSUBA_CUTOFF :: #config(MATH_BIG_SQR_KARATSUBA_CUTOFF, 120)
-define:MATH_BIG_SQR_KARATSUBA_CUTOFF=120
SQR_TOOM_CUTOFF ¶
SQR_TOOM_CUTOFF :: #config(MATH_BIG_SQR_TOOM_CUTOFF, 400)
-define:MATH_BIG_SQR_TOOM_CUTOFF=400
USE_MILLER_RABIN_ONLY ¶
USE_MILLER_RABIN_ONLY :: #config(MATH_BIG_USE_MILLER_RABIN_ONLY, false)
-define:MATH_BIG_USE_MILLER_RABIN_ONLY=false
Default for internal_int_is_prime's miller_rabin_only: use Miller-Rabin primality testing only and skip the above.
Variables
RADIX_TABLE ¶
@(rodata) RADIX_TABLE: string = …
Characters used in radix conversions: digit n is written as RADIX_TABLE[n], i.e. 0-9, A-Z, a-z, + and / for 0..=63.
That is not RFC 4648 base64, which starts with A-Z. atoi also accepts a-z as A-Z in radix 2..=36.
RADIX_TABLE_REVERSE ¶
@(rodata) RADIX_TABLE_REVERSE: [80]u8 = …
RANDOM_PRIME_ITERATIONS_USED ¶
@(thread_local) RANDOM_PRIME_ITERATIONS_USED: int
How many iterations we used for the last random prime.
Procedures
assert_if_nil_int ¶
assert_if_nil_int :: proc(integers: ..^Int, loc := #caller_location) {…}
assert_if_nil_rat ¶
assert_if_nil_rat :: proc(rationals: ..^Rat, loc := #caller_location) {…}
assert_initialized ¶
assert_initialized :: proc(a: ^Int, loc := #caller_location) {…}
Internal helpers.
bit_length ¶
bit_length :: proc(value: $T) -> (bits: T) {…}
Bits needed for a non-negative value, 0 for 0. Used by internal_int_is_prime and _private_int_factorial_binary_split.
clamp ¶
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 ¶
clear_if_uninitialized_multi :: proc( args: ..^Int, allocator := context.allocator, ) -> (err: Error) {…}
clear_if_uninitialized_single ¶
clear_if_uninitialized_single :: proc( arg: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
combinations_with_repetition ¶
With n items, calculate how many ways that r of them can be chosen.
Also known as the multiset coefficient or (n multichoose k).
combinations_without_repetition ¶
With n items, calculate how many ways that r of them can be chosen without any repeats.
Also known as the binomial coefficient or (n choose k).
copy_digits ¶
copy_digits :: proc( dest, src: ^Int, digits: int, offset: int = int(0), allocator := context.allocator, ) -> (err: Error) {…}
count_bits ¶
count_bits :: proc(a: ^Int, allocator := context.allocator) -> (count: int, err: Error) {…}
Count bits in an Int.
int_abs ¶
int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
Set dest to |src|.
int_add ¶
int_add :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
High-level addition. Handles sign.
int_add_digit ¶
int_add_digit :: proc( dest, a: ^Int, digit: DIGIT, allocator := context.allocator, ) -> (err: Error) {…}
int_add_rat ¶
int_add_rat :: proc( dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator, ) -> (err: Error) {…}
int_addmod ¶
int_addmod :: proc( remainder, number, addend, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number + addend) % modulus.
int_atoi ¶
int_atoi :: proc( res: ^Int, input: string, radix: i8 = i8(10), n: ^int = nil, allocator := context.allocator, ) -> (err: Error) {…}
Read a string [ASCII] in a given radix.
If n isn't nil, it's set to the number of characters read, the same as strconv's n: the
digits, and a leading '-' if anything follows it. So input[n:] is whatever comes after them.
In radix 2..=23, input may also start with "+Inf", "-Inf" or "NaN", which set res to +/-Inf or NaN and count as the number below.
In radix 24..=64 they get no special treatment and are read like any other input, e.g. "NaN" is 30191 in radix 36.
Returns:
nilifinputis just the number..Trailing_Whitespaceif only whitespace (' ','\t','\n','\v','\f','\r') or NUL follows the number.resholds the number, so callers that don't mind trailing whitespace can treat this as success. Other callers can triminputfirst..Invalid_Characterif anything else follows the number, orinputdoesn't start with one, e.g."12x","x"or"- \n".resholds whatever was read before that character..Empty_Inputifinputis"","-"or only whitespace.resis zero..Invalid_Argumentifradixisn't in 2..=64.
Related Procedure Groups
int_bit_and ¶
int_bit_and :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
2's complement and, returns dest = a & b;
int_bit_complement ¶
int_bit_complement :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
dest = ~src
int_bit_or ¶
int_bit_or :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
2's complement or, returns dest = a | b;
int_bit_xor ¶
int_bit_xor :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
2's complement xor, returns dest = a ^ b;
int_bitfield_extract ¶
int_bitfield_extract :: proc( a: ^Int, offset, count: int, allocator := context.allocator, ) -> (res: _WORD, err: Error) {…}
int_bitfield_extract_single ¶
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 ¶
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 ¶
int_clear :: proc( a: ^Int, minimize: bool = false, allocator := context.allocator, ) -> (err: Error) {…}
Clear Int and resize it to the default size.
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.
Related Procedure Groups
int_compare ¶
int_compare :: proc( a, b: ^Int, allocator := context.allocator, ) -> (comparison: int, err: Error) {…}
Compare two Ints, signed.
int_compare_digit ¶
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 ¶
int_compare_magnitude :: proc( a, b: ^Int, allocator := context.allocator, ) -> (res: int, err: Error) {…}
Compare the magnitude of two Ints, unsigned.
Related Procedure Groups
int_copy ¶
int_copy :: proc( dest, src: ^Int, minimize: bool = false, allocator := context.allocator, ) -> (err: Error) {…}
Copy one Int to another.
int_count_lsb ¶
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 ¶
int_destroy :: proc(integers: ..^Int) {…}
int_div ¶
int_div :: proc( quotient, numerator, denominator: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
int_div_digit ¶
int_div_digit :: proc( quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator, ) -> (err: Error) {…}
int_div_rat ¶
int_div_rat :: proc( dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator, ) -> (err: Error) {…}
int_divmod ¶
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 ¶
int_divmod_digit :: proc( quotient, numerator: ^Int, denominator: DIGIT, allocator := context.allocator, ) -> (remainder: DIGIT, err: Error) {…}
int_double ¶
int_double :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
dest = src * 2 dest = src << 1
int_equals ¶
int_equals :: proc(a, b: ^Int, allocator := context.allocator) -> (equals: bool, err: Error) {…}
bool := a == b
int_equals_abs ¶
int_equals_abs :: proc( a, b: ^Int, allocator := context.allocator, ) -> (equals: bool, err: Error) {…}
bool := |a| == |b|
Compares the magnitudes only, ignores the sign.
Related Procedure Groups
int_equals_digit ¶
int_equals_digit :: proc( a: ^Int, b: DIGIT, allocator := context.allocator, ) -> (equals: bool, err: Error) {…}
bool := a == b
int_factorial ¶
int_factorial :: proc(res: ^Int, n: int, allocator := context.allocator) -> (err: Error) {…}
int_from_bytes_big ¶
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 ¶
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 ¶
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 ¶
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 top bit of the last byte if signed is true.
int_gcd ¶
int_gcd :: proc(res, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
Greatest Common Divisor.
int_gcd_lcm ¶
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 ¶
int_get :: proc(a: ^Int, $T: typeid, allocator := context.allocator) -> (res: T, 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(a: ^Int, allocator := context.allocator) -> (res: f64, err: Error) {…}
int_get_i128 ¶
int_get_i128 :: proc(a: ^Int, allocator := context.allocator) -> (res: i128, err: Error) {…}
int_get_i32 ¶
int_get_i32 :: proc(a: ^Int, allocator := context.allocator) -> (res: i32, err: Error) {…}
int_get_i64 ¶
int_get_i64 :: proc(a: ^Int, allocator := context.allocator) -> (res: i64, err: Error) {…}
int_get_u128 ¶
int_get_u128 :: proc(a: ^Int, allocator := context.allocator) -> (res: u128, err: Error) {…}
int_get_u32 ¶
int_get_u32 :: proc(a: ^Int, allocator := context.allocator) -> (res: u32, err: Error) {…}
int_get_u64 ¶
int_get_u64 :: proc(a: ^Int, allocator := context.allocator) -> (res: u64, err: Error) {…}
int_greater_than ¶
int_greater_than :: proc( a, b: ^Int, allocator := context.allocator, ) -> (greater_than: bool, err: Error) {…}
bool := a > b
Related Procedure Groups
int_greater_than_abs ¶
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.
Related Procedure Groups
int_greater_than_digit ¶
int_greater_than_digit :: proc( a: ^Int, b: DIGIT, allocator := context.allocator, ) -> (greater_than: bool, err: Error) {…}
bool := a > b
Related Procedure Groups
int_greater_than_or_equal ¶
int_greater_than_or_equal :: proc( a, b: ^Int, allocator := context.allocator, ) -> (greater_than_or_equal: bool, err: Error) {…}
bool := a >= b
Related Procedure Groups
int_greater_than_or_equal_abs ¶
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.
Related Procedure Groups
int_greater_than_or_equal_digit ¶
int_greater_than_or_equal_digit :: proc( a: ^Int, b: DIGIT, allocator := context.allocator, ) -> (greater_than_or_equal: bool, err: Error) {…}
bool := a >= b
Related Procedure Groups
int_grow ¶
int_grow :: proc( a: ^Int, digits: int, allow_shrink: bool = false, allocator := context.allocator, ) -> (err: Error) {…}
int_halve ¶
int_halve :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
dest = src / 2 dest = src >> 1
int_inf ¶
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 ¶
int_init_multi :: proc(integers: ..^Int, allocator := context.allocator) -> (err: Error) {…}
Allocates several Ints at once.
int_is_even ¶
int_is_even :: proc(a: ^Int, allocator := context.allocator) -> (even: bool, err: Error) {…}
int_is_negative ¶
int_is_negative :: proc( a: ^Int, allocator := context.allocator, ) -> (negative: bool, err: Error) {…}
Related Procedure Groups
int_is_odd ¶
int_is_odd :: proc(a: ^Int, allocator := context.allocator) -> (odd: bool, err: Error) {…}
int_is_positive ¶
int_is_positive :: proc( a: ^Int, allocator := context.allocator, ) -> (positive: bool, err: Error) {…}
Related Procedure Groups
int_is_power_of_two ¶
int_is_power_of_two :: proc( a: ^Int, allocator := context.allocator, ) -> (res: bool, err: Error) {…}
int_is_square ¶
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 ¶
int_is_zero :: proc(a: ^Int, allocator := context.allocator) -> (zero: bool, err: Error) {…}
int_itoa_cstring ¶
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 ¶
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 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.
The digits are written backwards from the end of buffer and then moved to the front,
so the result is always buffer[:written], however much larger than size the buffer is.
size only saves the radix_size call. A buffer too small for the result gives .Buffer_Overflow.
NaN and +/-Inf are written as "NaN", "+Inf" and "-Inf" in radix 2..=23. Radix 24..=64 gives .Invalid_Argument.
int_itoa_string ¶
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 ¶
int_lcm :: proc(res, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
Least Common Multiple.
int_less_than ¶
int_less_than :: proc( a, b: ^Int, allocator := context.allocator, ) -> (less_than: bool, err: Error) {…}
bool := a < b
int_less_than_abs ¶
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.
Related Procedure Groups
int_less_than_digit ¶
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 ¶
int_less_than_or_equal :: proc( a, b: ^Int, allocator := context.allocator, ) -> (less_than_or_equal: bool, err: Error) {…}
bool := a <= b
Related Procedure Groups
int_less_than_or_equal_abs ¶
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.
Related Procedure Groups
int_less_than_or_equal_digit ¶
int_less_than_or_equal_digit :: proc( a: ^Int, b: DIGIT, allocator := context.allocator, ) -> (less_than_or_equal: bool, err: Error) {…}
bool := a <= b
Related Procedure Groups
int_log ¶
int_log :: proc( a: ^Int, base: DIGIT, allocator := context.allocator, ) -> (res: int, err: Error) {…}
Logs and roots and such.
int_minus_inf ¶
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 ¶
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 ¶
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 ¶
int_mod_bits :: proc( remainder, numerator: ^Int, bits: int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = numerator % (1 << bits)
int_mod_digit ¶
int_mod_digit :: proc( numerator: ^Int, denominator: DIGIT, allocator := context.allocator, ) -> (remainder: DIGIT, err: Error) {…}
int_mul ¶
int_mul :: proc(dest, src, multiplier: ^Int, allocator := context.allocator) -> (err: Error) {…}
High level multiplication (handles sign).
int_mul_digit ¶
int_mul_digit :: proc( dest, src: ^Int, multiplier: DIGIT, allocator := context.allocator, ) -> (err: Error) {…}
Multiply by a DIGIT.
int_mul_rat ¶
int_mul_rat :: proc( dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator, ) -> (err: Error) {…}
int_mulmod ¶
int_mulmod :: proc( remainder, number, multiplicand, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number * multiplicand) % modulus.
int_nan ¶
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 ¶
int_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
Set dest to -src.
int_one ¶
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 ¶
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 ¶
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 ¶
int_random :: proc(dest: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
int_random_digit ¶
int_random_digit :: internal_int_random_digit
int_root_n ¶
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 ¶
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 ¶
int_shl :: proc(dest, src: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
Shift left by a certain bit count.
int_shr ¶
int_shr :: proc(dest, source: ^Int, bits: int, allocator := context.allocator) -> (err: Error) {…}
int_shr_signed ¶
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 ¶
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_sqrmod ¶
int_sqrmod :: proc( remainder, number, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number * number) % modulus.
int_sqrt ¶
int_sqrt :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
This function is less generic than root_n, simpler and faster.
int_sub ¶
int_sub :: proc(dest, number, decrease: ^Int, allocator := context.allocator) -> (err: Error) {…}
High-level subtraction, dest = number - decrease. Handles signs.
int_sub_digit ¶
int_sub_digit :: proc( dest, a: ^Int, digit: DIGIT, allocator := context.allocator, ) -> (err: Error) {…}
int_sub_rat ¶
int_sub_rat :: proc( dst: ^Rat, x: ^Int, y: ^Rat, allocator := context.allocator, ) -> (err: Error) {…}
int_submod ¶
int_submod :: proc( remainder, number, decrease, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number - decrease) % modulus.
int_swap ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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.
internal_assert_initialized ¶
internal_assert_initialized :: proc(a: ^Int, loc := #caller_location) {…}
Internal helpers.
internal_clamp ¶
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( args: ..^Int, allocator := context.allocator, ) -> (err: Error) {…}
internal_clear_if_uninitialized_single ¶
internal_clear_if_uninitialized_single :: proc( arg: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
internal_clear_non_finite_multi ¶
internal_clear_non_finite_multi :: proc "contextless" (args: ..^Int) {…}
internal_clear_non_finite_single ¶
internal_clear_non_finite_single :: proc "contextless" (arg: ^Int) {…}
internal_count_bits ¶
Count bits in an Int.
Assumes a not to be nil and to have been initialized.
internal_digit_log ¶
Returns log_base(a), where a is a DIGIT.
internal_int_abs ¶
internal_int_abs :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
Set dest to |src|.
internal_int_add_digit ¶
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 ¶
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.
Related Procedure Groups
internal_int_add_unsigned ¶
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 ¶
internal_int_addmod :: proc( remainder, number, addend, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number + addend) % modulus.
internal_int_allocated_cap ¶
This procedure returns the allocated capacity of an Int.
Assumes a not to be nil.
internal_int_and ¶
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_bool ¶
Helpers to extract values from the Int.
Offset is zero indexed.
internal_int_bitfield_set_single ¶
Helpers to (un)set a bit in an Int. Offset is zero indexed.
internal_int_clear ¶
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.
Related Procedure Groups
internal_int_compare ¶
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 Ints, i.e. initialized and not nil.
Related Procedure Groups
internal_int_compare_digit ¶
Compare an Int to an unsigned DIGIT, which may use all of its bits.
Returns -1 if a < b, 0 if a == b and 1 if a > b.
Expects: a to be a valid Int, i.e. initialized and not nil.
Related Procedure Groups
internal_int_compare_magnitude ¶
Compare the magnitude of two Ints, unsigned.
Related Procedure Groups
internal_int_complement ¶
internal_int_complement :: proc( dest, src: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
dest = ~src
internal_int_copy ¶
internal_int_copy :: proc( dest, src: ^Int, minimize: bool = false, allocator := context.allocator, ) -> (err: Error) {…}
Copy one Int to another.
Related Procedure Groups
internal_int_count_lsb ¶
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(dest: ^Int, allocator := context.allocator) -> (err: Error) {…}
internal_int_destroy ¶
internal_int_destroy :: proc(integers: ..^Int) {…}
internal_int_div ¶
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 ¶
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 ¶
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_abs ¶
bool := |a| == |b|
Compares the magnitudes only, ignores the sign.
Related Procedure Groups
internal_int_exponent_mod ¶
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 ¶
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 ¶
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 ¶
internal_int_gcd :: proc(res_gcd, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
internal_int_gcd_lcm ¶
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 ¶
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_greater_than_abs ¶
bool := |a| > |b|
Compares the magnitudes only, ignores the sign.
Related Procedure Groups
internal_int_greater_than_or_equal_abs ¶
bool := |a| >= |b|
Compares the magnitudes only, ignores the sign.
Related Procedure Groups
internal_int_greater_than_or_equal_digit ¶
internal_int_greater_than_or_equal_digit :: proc( a: ^Int, b: DIGIT, ) -> (greater_than_or_equal: bool) {…}
bool := a >= b
Related Procedure Groups
internal_int_grow ¶
internal_int_grow :: proc( a: ^Int, digits: int, allow_shrink: bool = false, allocator := context.allocator, ) -> (err: Error) {…}
internal_int_incr ¶
internal_int_incr :: proc(dest: ^Int, allocator := context.allocator) -> (err: Error) {…}
internal_int_inf ¶
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 ¶
internal_int_init_multi :: proc( integers: ..^Int, allocator := context.allocator, ) -> (err: Error) {…}
Allocates several Ints at once.
internal_int_inverse_modulo ¶
internal_int_inverse_modulo :: proc( dest, a, b: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
hac 14.61, pp608.
internal_int_is_even ¶
This procedure will return true if the Int is even, false if not.
Assumes a not to be nil.
internal_int_is_initialized ¶
This procedure will return true if the Int is initialized, false if not.
Assumes a not to be nil.
internal_int_is_negative ¶
This procedure will return true if the Int is negative, false if not.
Assumes a not to be nil.
internal_int_is_odd ¶
This procedure will return true if the Int is even, false if not.
Assumes a not to be nil.
internal_int_is_positive ¶
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 ¶
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( a: ^Int, miller_rabin_trials: int = int(-1), miller_rabin_only: bool = USE_MILLER_RABIN_ONLY, 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( 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 ¶
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( 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(res_lcm, 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_abs ¶
bool := |a| < |b|
Compares the magnitudes only, ignores the sign.
Related Procedure Groups
internal_int_less_than_or_equal_abs ¶
bool := |a| <= |b|
Compares the magnitudes only, ignores the sign.
Related Procedure Groups
internal_int_log ¶
Returns log_base(a).
Assumes a to not be nil and have been iniialized.
internal_int_minus_inf ¶
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 ¶
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 ¶
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 ¶
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 ¶
internal_int_mod_digit :: proc( numerator: ^Int, denominator: DIGIT, allocator := context.allocator, ) -> (remainder: DIGIT, err: Error) {…}
internal_int_mul ¶
internal_int_mul :: proc( dest, src, multiplier: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
High level multiplication (handles sign).
internal_int_mul_denom ¶
internal_int_mul_denom :: proc( dst, x, y: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
internal_int_mul_digit ¶
internal_int_mul_digit :: proc( dest, src: ^Int, multiplier: DIGIT, allocator := context.allocator, ) -> (err: Error) {…}
Multiply by a DIGIT.
internal_int_mul_integer ¶
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 ¶
internal_int_mulmod :: proc( remainder, number, multiplicand, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number * multiplicand) % modulus.
internal_int_nan ¶
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 ¶
internal_int_neg :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
Set dest to -src.
internal_int_one ¶
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 ¶
internal_int_or :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
2's complement or, returns dest = a | b;
internal_int_pack ¶
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 ¶
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( 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 ¶
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 ¶
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 ¶
internal_int_power_of_two :: proc( a: ^Int, power: int, allocator := context.allocator, ) -> (err: Error) {…}
internal_int_powmod ¶
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 ¶
internal_int_prime_frobenius_underwood :: proc( N: ^Int, allocator := context.allocator, ) -> (result: bool, err: Error) {…}
internal_int_prime_is_divisible ¶
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 ¶
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 ¶
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 ¶
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 ¶
internal_int_random :: proc( dest: ^Int, bits: int, allocator := context.allocator, ) -> (err: Error) {…}
internal_int_random_digit ¶
internal_int_random_digit :: proc() -> (res: DIGIT) {…}
internal_int_read_from_ascii_file ¶
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 ¶
internal_int_root_n :: proc( dest, src: ^Int, n: int, allocator := context.allocator, ) -> (err: Error) {…}
Find the nth root of an Integer, truncated towards zero.
Result found such that dest**n <= |src| < (dest+1)**n, with the sign of src.
The top bits of the root are found one at a time, which puts the estimate just above
the root, within a factor of 1 + 1/(2n). From there Newton's iteration
x[i+1] = ((n - 1) * x[i] + |src| / x[i]**(n - 1)) / n converges quadratically
down to the root, stopping as soon as x no longer decreases.
n must be at least 1, and odd if src is negative.
Assumes dest and src not to be nil and have been initialized.
internal_int_scale_denom ¶
internal_int_scale_denom :: proc( dst, x, y: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
internal_int_set_from_integer ¶
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 ¶
internal_int_shl :: proc( dest, src: ^Int, bits: int, allocator := context.allocator, ) -> (err: Error) {…}
Shift left by a certain bit count.
internal_int_shl1 ¶
internal_int_shl1 :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
dest = src * 2 dest = src << 1
internal_int_shr ¶
internal_int_shr :: proc( dest, source: ^Int, bits: int, allocator := context.allocator, ) -> (err: Error) {…}
internal_int_shr1 ¶
internal_int_shr1 :: proc(dest, src: ^Int, allocator := context.allocator) -> (err: Error) {…}
dest = src / 2 dest = src >> 1
Assumes dest and src not to be nil and have been initialized.
Grows dest to src.used digits if it is shorter.
internal_int_shr_signed ¶
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 ¶
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( 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( remainder, number, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number * number) % modulus.
internal_int_sqrt ¶
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 ¶
internal_int_sqrtmod_prime :: proc( res, n, prime: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
internal_int_sub_digit ¶
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 ¶
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 ¶
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 ¶
internal_int_submod :: proc( remainder, number, decrease, modulus: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
remainder = (number - decrease) % modulus.
internal_int_swap ¶
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 ¶
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 ¶
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 ¶
internal_int_xor :: proc(dest, a, b: ^Int, allocator := context.allocator) -> (err: Error) {…}
2's complement xor, returns dest = a ~ b;
internal_platform_abs ¶
internal_platform_abs :: proc(n: $T) -> T {…}
internal_platform_count_lsb ¶
internal_platform_count_lsb :: proc(a: $T) -> (count: int) {…}
internal_prime_fermat ¶
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 ¶
internal_random_prime :: proc( a: ^Int, size_in_bits: int, trials: int, flags: bit_set[Primality_Flag; u8] = Primality_Flags{}, 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_norm ¶
internal_rat_norm :: proc(z: ^Rat, allocator := context.allocator) -> (err: Error) {…}
internal_rat_swap ¶
internal_rat_swap :: proc(a, b: ^Rat) {…}
internal_rat_to_float ¶
internal_rat_to_float :: proc( $T: typeid, z: ^Rat, allocator := context.allocator, ) -> (f: T, exact: bool, err: Error) {…}
internal_sqr ¶
internal_sqr :: proc(dest, src: ^Int, allocator := context.allocator) -> (res: Error) {…}
number_of_rabin_miller_trials ¶
Returns the number of Rabin-Miller trials needed for a given bit size.
permutations_with_repetition ¶
permutations_with_repetition :: proc( dest: ^Int, n, r: int, allocator := context.allocator, ) -> (error: Error) {…}
With n items, calculate how many ways that r of them can be ordered.
permutations_without_repetition ¶
With n items, calculate how many ways that r of them can be ordered without any repeats.
platform_abs ¶
platform_abs :: proc(n: $T) -> T {…}
platform_count_lsb ¶
platform_count_lsb :: proc(a: $T) -> (count: int) {…}
power_of_two ¶
power_of_two :: proc(a: ^Int, power: int, allocator := context.allocator) -> (err: Error) {…}
radix_size ¶
radix_size :: proc( a: ^Int, radix: i8, zero_terminate: bool = false, allocator := context.allocator, ) -> (size: int, err: Error) {…}
We size for string by default.
rat_abs ¶
rat_abs :: proc(dst, x: ^Rat, allocator := context.allocator) -> (err: Error) {…}
rat_add_int ¶
rat_add_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}
rat_add_rat ¶
rat_add_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}
rat_compare ¶
rat_compare :: proc( x, y: ^Rat, allocator := context.allocator, ) -> (comparison: int, error: Error) {…}
rat_copy ¶
rat_copy :: proc( dst, src: ^Rat, minimize: bool = false, allocator := context.allocator, ) -> (err: Error) {…}
rat_div_int ¶
rat_div_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}
rat_div_rat ¶
rat_div_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}
rat_is_even ¶
rat_is_even :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}
rat_is_negative ¶
rat_is_negative :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}
Related Procedure Groups
rat_is_odd ¶
rat_is_odd :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}
rat_is_positive ¶
rat_is_positive :: proc(z: ^Rat, allocator := context.allocator) -> (ok: bool, err: Error) {…}
Related Procedure Groups
rat_mul_int ¶
rat_mul_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}
rat_mul_rat ¶
rat_mul_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}
rat_neg ¶
rat_neg :: proc(dst, x: ^Rat, allocator := context.allocator) -> (err: Error) {…}
rat_set_digit ¶
rat_set_digit :: proc(dst: ^Rat, a: DIGIT, allocator := context.allocator) -> (err: Error) {…}
rat_set_f16 ¶
rat_set_f16 :: proc(dst: ^Rat, f: f16, allocator := context.allocator) -> (err: Error) {…}
rat_set_f32 ¶
rat_set_f32 :: proc(dst: ^Rat, f: f32, allocator := context.allocator) -> (err: Error) {…}
rat_set_f64 ¶
rat_set_f64 :: proc(dst: ^Rat, f: f64, allocator := context.allocator) -> (err: Error) {…}
rat_set_frac_digit ¶
rat_set_frac_digit :: proc( dst: ^Rat, a, b: DIGIT, allocator := context.allocator, ) -> (err: Error) {…}
rat_set_frac_int ¶
rat_set_frac_int :: proc( dst: ^Rat, a, b: ^Int, allocator := context.allocator, ) -> (err: Error) {…}
rat_set_i64 ¶
rat_set_i64 :: proc(dst: ^Rat, x: i64, allocator := context.allocator) -> (err: Error) {…}
rat_set_int ¶
rat_set_int :: proc(dst: ^Rat, a: ^Int, allocator := context.allocator) -> (err: Error) {…}
rat_set_rat ¶
rat_set_rat :: proc(dst, x: ^Rat, allocator := context.allocator) -> (err: Error) {…}
rat_set_u64 ¶
rat_set_u64 :: proc(dst: ^Rat, x: u64, allocator := context.allocator) -> (err: Error) {…}
rat_sub_int ¶
rat_sub_int :: proc(dst, x: ^Rat, y: ^Int, allocator := context.allocator) -> (err: Error) {…}
rat_sub_rat ¶
rat_sub_rat :: proc(dst, x, y: ^Rat, allocator := context.allocator) -> (err: Error) {…}
rat_swap ¶
rat_swap :: proc(a, b: ^Rat) {…}
rat_to_f16 ¶
rat_to_f16 :: proc( z: ^Rat, allocator := context.allocator, ) -> (f: f16, exact: bool, err: Error) {…}
rat_to_f32 ¶
rat_to_f32 :: proc( z: ^Rat, allocator := context.allocator, ) -> (f: f32, exact: bool, err: Error) {…}
rat_to_f64 ¶
rat_to_f64 :: proc( z: ^Rat, allocator := context.allocator, ) -> (f: f64, exact: bool, err: Error) {…}
shrink ¶
shrink :: proc(a: ^Int, allocator := context.allocator) -> (err: Error) {…}
Resize backing store.
string_to_int ¶
string_to_int :: int_atoi
Read a string [ASCII] in a given radix.
If n isn't nil, it's set to the number of characters read, the same as strconv's n: the
digits, and a leading '-' if anything follows it. So input[n:] is whatever comes after them.
In radix 2..=23, input may also start with "+Inf", "-Inf" or "NaN", which set res to +/-Inf or NaN and count as the number below.
In radix 24..=64 they get no special treatment and are read like any other input, e.g. "NaN" is 30191 in radix 36.
Returns:
nilifinputis just the number..Trailing_Whitespaceif only whitespace (' ','\t','\n','\v','\f','\r') or NUL follows the number.resholds the number, so callers that don't mind trailing whitespace can treat this as success. Other callers can triminputfirst..Invalid_Characterif anything else follows the number, orinputdoesn't start with one, e.g."12x","x"or"- \n".resholds whatever was read before that character..Empty_Inputifinputis"","-"or only whitespace.resis zero..Invalid_Argumentifradixisn't in 2..=64.
Related Procedure Groups
Procedure Groups
abs ¶
abs :: proc{ int_abs, platform_abs, rat_abs, }
add ¶
add :: proc{ int_add, int_add_digit, rat_add_rat, rat_add_int, int_add_rat, }
High-level addition. Handles sign.
addmod ¶
addmod :: proc{ int_addmod, }
assert_if_nil ¶
assert_if_nil :: proc{ assert_if_nil_int, assert_if_nil_rat, }
bit_and ¶
bit_and :: proc{ int_bit_and, }
bit_complement ¶
bit_complement :: proc{ int_bit_complement, }
bit_or ¶
bit_or :: proc{ int_bit_or, }
bit_xor ¶
bit_xor :: proc{ int_bit_xor, }
choose ¶
choose :: proc{ int_choose_digit, }
clear_if_uninitialized ¶
clear_if_uninitialized :: proc{ clear_if_uninitialized_single, clear_if_uninitialized_multi, }
cmp ¶
cmp :: proc{ int_compare, int_compare_digit, }
cmp_mag ¶
cmp_mag :: proc{ int_compare_magnitude, }
compare ¶
compare :: proc{ int_compare, int_compare_digit, }
compare_magnitude ¶
compare_magnitude :: proc{ int_compare_magnitude, }
count_lsb ¶
count_lsb :: proc{ int_count_lsb, platform_count_lsb, }
destroy ¶
destroy :: proc{ int_destroy, internal_rat_destroy, }
div ¶
div :: proc{ int_div, int_div_digit, rat_div_rat, rat_div_int, int_div_rat, }
divmod ¶
divmod :: proc{ int_divmod, int_divmod_digit, }
double ¶
double :: proc{ int_double, }
eq ¶
eq :: proc{ int_equals, int_equals_digit, }
eq_abs ¶
eq_abs :: proc{ int_equals_abs, }
equals ¶
equals :: proc{ int_equals, int_equals_digit, }
equals_abs ¶
equals_abs :: proc{ int_equals_abs, }
error_if_immutable ¶
error_if_immutable :: proc{ error_if_immutable_single, error_if_immutable_multi, }
factorial ¶
factorial :: proc{ int_factorial, }
gcd_lcm ¶
gcd_lcm :: proc{ int_gcd_lcm, }
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 ¶
greater_than :: proc{ int_greater_than, int_greater_than_digit, }
greater_than_abs ¶
greater_than_abs :: proc{ int_greater_than_abs, }
greater_than_or_equal ¶
greater_than_or_equal :: proc{ int_greater_than_or_equal, int_greater_than_or_equal_digit, }
greater_than_or_equal_abs ¶
greater_than_or_equal_abs :: proc{ int_greater_than_or_equal_abs, }
gt ¶
gt :: proc{ int_greater_than, int_greater_than_digit, }
gt_abs ¶
gt_abs :: proc{ int_greater_than_abs, }
gteq ¶
gteq :: proc{ int_greater_than_or_equal, int_greater_than_or_equal_digit, }
gteq_abs ¶
gteq_abs :: proc{ int_greater_than_or_equal_abs, }
init_multi ¶
init_multi :: proc{ int_init_multi, }
internal_abs ¶
internal_abs :: proc{ internal_int_abs, internal_platform_abs, }
internal_add ¶
internal_add :: proc{ internal_int_add_signed, internal_int_add_digit, }
internal_add_signed ¶
internal_add_signed :: proc{ internal_int_add_signed, }
internal_add_unsigned ¶
internal_add_unsigned :: proc{ internal_int_add_unsigned, }
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_clear_if_uninitialized ¶
internal_clear_if_uninitialized :: proc{ internal_clear_if_uninitialized_single, internal_clear_if_uninitialized_multi, }
internal_clear_non_finite ¶
internal_clear_non_finite :: proc{ internal_clear_non_finite_single, internal_clear_non_finite_multi, }
internal_cmp ¶
internal_cmp :: proc{ internal_int_compare, internal_int_compare_digit, }
internal_cmp_digit ¶
internal_cmp_digit :: proc{ internal_int_compare_digit, }
internal_cmp_mag ¶
internal_cmp_mag :: proc{ internal_int_compare_magnitude, }
internal_compare ¶
internal_compare :: proc{ internal_int_compare, internal_int_compare_digit, }
internal_compare_digit ¶
internal_compare_digit :: proc{ internal_int_compare_digit, }
internal_compare_magnitude ¶
internal_compare_magnitude :: proc{ internal_int_compare_magnitude, }
internal_complement ¶
internal_complement :: proc{ internal_int_complement, }
internal_copy ¶
internal_copy :: proc{ internal_int_copy, }
internal_count_lsb ¶
internal_count_lsb :: proc{ internal_int_count_lsb, internal_platform_count_lsb, }
internal_decr ¶
internal_decr :: proc{ internal_int_decr, }
internal_destroy ¶
internal_destroy :: proc{ internal_int_destroy, internal_rat_destroy, }
internal_div ¶
internal_div :: proc{ internal_int_div, }
internal_divmod ¶
internal_divmod :: proc{ internal_int_divmod, internal_int_divmod_digit, }
internal_eq ¶
internal_eq :: proc{ internal_int_equals, internal_int_equals_digit, }
internal_eq_abs ¶
internal_eq_abs :: proc{ internal_int_equals_abs, }
internal_equals ¶
internal_equals :: proc{ internal_int_equals, internal_int_equals_digit, }
internal_equals_abs ¶
internal_equals_abs :: proc{ internal_int_equals_abs, }
internal_error_if_immutable ¶
internal_error_if_immutable :: proc{ internal_error_if_immutable_single, internal_error_if_immutable_multi, }
internal_error_if_non_finite ¶
internal_error_if_non_finite :: proc{ internal_error_if_non_finite_single, internal_error_if_non_finite_multi, }
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_greater_than ¶
internal_greater_than :: proc{ internal_int_greater_than, internal_int_greater_than_digit, }
internal_greater_than_abs ¶
internal_greater_than_abs :: proc{ internal_int_greater_than_abs, }
internal_greater_than_or_equal ¶
internal_greater_than_or_equal :: proc{ internal_int_greater_than_or_equal, internal_int_greater_than_or_equal_digit, }
internal_greater_than_or_equal_abs ¶
internal_greater_than_or_equal_abs :: proc{ internal_int_greater_than_or_equal_abs, }
internal_grow ¶
internal_grow :: proc{ internal_int_grow, }
internal_gt ¶
internal_gt :: proc{ internal_int_greater_than, internal_int_greater_than_digit, }
internal_gt_abs ¶
internal_gt_abs :: proc{ internal_int_greater_than_abs, }
internal_gte ¶
internal_gte :: proc{ internal_int_greater_than_or_equal, internal_int_greater_than_or_equal_digit, }
internal_gte_abs ¶
internal_gte_abs :: proc{ internal_int_greater_than_or_equal_abs, }
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_invmod ¶
internal_invmod :: proc{ internal_int_inverse_modulo, }
internal_is_even ¶
internal_is_even :: proc{ internal_int_is_even, }
internal_is_initialized ¶
internal_is_initialized :: proc{ internal_int_is_initialized, }
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_is_power_of_two ¶
internal_is_power_of_two :: proc{ internal_int_is_power_of_two, }
internal_is_zero ¶
internal_is_zero :: proc{ internal_rat_is_zero, internal_int_is_zero, }
internal_less_than ¶
internal_less_than :: proc{ internal_int_less_than, internal_int_less_than_digit, }
internal_less_than_abs ¶
internal_less_than_abs :: proc{ internal_int_less_than_abs, }
internal_less_than_or_equal ¶
internal_less_than_or_equal :: proc{ internal_int_less_than_or_equal, internal_int_less_than_or_equal_digit, }
internal_less_than_or_equal_abs ¶
internal_less_than_or_equal_abs :: proc{ internal_int_less_than_or_equal_abs, }
internal_log ¶
internal_log :: proc{ internal_int_log, internal_digit_log, }
internal_lt ¶
internal_lt :: proc{ internal_int_less_than, internal_int_less_than_digit, }
internal_lt_abs ¶
internal_lt_abs :: proc{ internal_int_less_than_abs, }
internal_lte ¶
internal_lte :: proc{ internal_int_less_than_or_equal, internal_int_less_than_or_equal_digit, }
internal_lte_abs ¶
internal_lte_abs :: proc{ internal_int_less_than_or_equal_abs, }
internal_minus_inf ¶
internal_minus_inf :: proc{ internal_int_minus_inf, }
internal_minus_one ¶
internal_minus_one :: proc{ internal_int_minus_one, }
internal_mod ¶
internal_mod :: proc{ internal_int_mod, internal_int_mod_digit, }
internal_mul ¶
internal_mul :: proc{ internal_int_mul, internal_int_mul_digit, internal_int_mul_integer, }
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_pow ¶
internal_pow :: proc{ internal_int_pow, internal_int_pow_int, }
internal_powmod ¶
internal_powmod :: proc{ internal_int_power_modulo, }
internal_random ¶
internal_random :: proc{ internal_int_random, }
internal_root_n ¶
internal_root_n :: proc{ internal_int_root_n, }
internal_set ¶
internal_set :: proc{ internal_int_set_from_integer, internal_int_copy, int_atoi, }
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_sub ¶
internal_sub :: proc{ internal_int_sub_signed, internal_int_sub_digit, }
internal_sub_unsigned ¶
internal_sub_unsigned :: proc{ internal_int_sub_unsigned, }
internal_submod ¶
internal_submod :: proc{ internal_int_submod, }
internal_swap ¶
internal_swap :: proc{ internal_int_swap, internal_rat_swap, }
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_even ¶
is_even :: proc{ int_is_even, rat_is_even, }
is_initialized ¶
is_initialized :: proc{ int_is_initialized, }
is_neg ¶
is_neg :: proc{ int_is_negative, rat_is_negative, }
is_negative ¶
is_negative :: proc{ int_is_negative, rat_is_negative, }
is_odd ¶
is_odd :: proc{ int_is_odd, rat_is_odd, }
is_pos ¶
is_pos :: proc{ int_is_positive, rat_is_positive, }
is_positive ¶
is_positive :: proc{ int_is_positive, rat_is_positive, }
is_power_of_two ¶
is_power_of_two :: proc{ platform_int_is_power_of_two, int_is_power_of_two, }
is_zero ¶
is_zero :: proc{ int_is_zero, rat_is_zero, }
itoa ¶
itoa :: proc{ int_itoa_string, int_itoa_raw, }
less_than ¶
less_than :: proc{ int_less_than, int_less_than_digit, }
less_than_abs ¶
less_than_abs :: proc{ int_less_than_abs, }
less_than_or_equal ¶
less_than_or_equal :: proc{ int_less_than_or_equal, int_less_than_or_equal_digit, }
less_than_or_equal_abs ¶
less_than_or_equal_abs :: proc{ int_less_than_or_equal_abs, }
lt ¶
lt :: proc{ int_less_than, int_less_than_digit, }
lt_abs ¶
lt_abs :: proc{ int_less_than_abs, }
lteq ¶
lteq :: proc{ int_less_than_or_equal, int_less_than_or_equal_digit, }
lteq_abs ¶
lteq_abs :: proc{ int_less_than_or_equal_abs, }
minus_inf ¶
minus_inf :: proc{ int_minus_inf, }
minus_one ¶
minus_one :: proc{ int_minus_one, }
mod ¶
mod :: proc{ int_mod, int_mod_digit, }
mod_bits ¶
mod_bits :: proc{ int_mod_bits, }
mul ¶
mul :: proc{ int_mul, int_mul_digit, rat_mul_rat, rat_mul_int, int_mul_rat, }
mulmod ¶
mulmod :: proc{ int_mulmod, }
pow ¶
pow :: proc{ int_pow, int_pow_int, }
random ¶
random :: proc{ int_random, }
rat_set_frac ¶
rat_set_frac :: proc{ rat_set_frac_digit, rat_set_frac_int, }
root_n ¶
root_n :: proc{ int_root_n, }
set ¶
set :: proc{ int_set_from_integer, int_copy, int_atoi, rat_set_f64, rat_set_f32, rat_set_f16, rat_set_u64, rat_set_i64, rat_set_int, rat_set_digit, rat_set_rat, }
shl1 ¶
shl1 :: proc{ int_double, }
shr_signed ¶
shr_signed :: proc{ int_shr_signed, }
shrmod ¶
shrmod :: proc{ int_shrmod, }
sqrmod ¶
sqrmod :: proc{ int_sqrmod, }
sub ¶
sub :: proc{ int_sub, int_sub_digit, rat_sub_rat, rat_sub_int, int_sub_rat, }
err = sub(dest, a, b);
submod ¶
submod :: proc{ int_submod, }
`#config` values
- FACTORIAL_BINARY_SPLIT_CUTOFF
-define:MATH_BIG_FACTORIAL_BINARY_SPLIT_CUTOFF=6100 - FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS
-define:MATH_BIG_FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS=100 - FACTORIAL_MAX_N
-define:MATH_BIG_FACTORIAL_MAX_N=1_000_000 - MATH_BIG_USE_LUCAS_SELFRIDGE_TEST
-define:MATH_BIG_USE_LUCAS_SELFRIDGE_TEST=false - MAX_ITERATIONS_RANDOM_PRIME
-define:MATH_BIG_MAX_ITERATIONS_RANDOM_PRIME=1_000_000 - MAX_ITERATIONS_ROOT_N
-define:MATH_BIG_MAX_ITERATIONS_ROOT_N=500 - MUL_KARATSUBA_CUTOFF
-define:MATH_BIG_MUL_KARATSUBA_CUTOFF=80 - MUL_TOOM_CUTOFF
-define:MATH_BIG_MUL_TOOM_CUTOFF=350 - SQR_KARATSUBA_CUTOFF
-define:MATH_BIG_SQR_KARATSUBA_CUTOFF=120 - SQR_TOOM_CUTOFF
-define:MATH_BIG_SQR_TOOM_CUTOFF=400 - USE_MILLER_RABIN_ONLY
-define:MATH_BIG_USE_MILLER_RABIN_ONLY=false
Source Files
- api.odin
- combinatorics.odin
- common.odin
- helpers.odin
- internal.odin
- logical.odin
- prime.odin
- private.odin
- public.odin
- radix.odin
- radix_os.odin
- rat.odin
Generation Information
Generated with odin version dev-2026-11 (vendor "odin") Windows_amd64 @ 2026-11-18 21:05:19.828955300 +0000 UTC