Crate malachite_base

Expand description

This crate contains many utilities that are used by the malachite-nz and malachite-q crates. These utilities include

Traits that wrap functions from the standard library, like CheckedAdd.
Traits that give extra functionality to primitive types, like Gcd, FloorSqrt, and BitAccess.

Iterator-producing functions that let you generate values for testing. Here’s an example of an iterator that produces all pairs of u32s:

use malachite_base::num::exhaustive::exhaustive_unsigneds;
use malachite_base::tuples::exhaustive::exhaustive_pairs_from_single;

let mut pairs = exhaustive_pairs_from_single(exhaustive_unsigneds::<u32>());
assert_eq!(
    pairs.take(20).collect::<Vec<_>>(),
    &[
        (0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 0), (2, 1),
        (3, 0), (3, 1), (2, 2), (2, 3), (3, 2), (3, 3), (0, 4), (0, 5), (1, 4), (1, 5)
    ]
);

The RoundingMode enum, which allows you to specify the rounding behavior of various functions.
The NiceFloat wrapper, which provides alternative implementations of Eq, Ord, and Display for floating-point values which are in some ways nicer than the defaults.

§Complexity conventions

Most functions in Malachite come with a “Worst-case complexity” section stating time and additional-memory bounds, like $T(n) = O(n \log n \log\log n)$ and $M(n) = O(n)$, along with a line defining each variable. The model is a word RAM: time counts operations on machine words (an operation on any primitive type up to u128 compiles to a bounded number of native instructions, so it counts as one step), and additional memory counts words allocated beyond the inputs and the output.

Since primitive-integer inputs are bounded, every function on them technically runs in constant time. The complexity sections are written to be more informative than that:

“Constant time and additional memory” means the operation count is bounded independently of the type’s width and of the inputs’ values.
Otherwise, the bound is written in terms of variables, describing how the work would scale if the same algorithm were instantiated at an arbitrarily large width. For example, mod_pow for primitive types is documented as $T(n) = O(n)$, where $n$ is exp.significant_bits(): the work scales with the exponent’s bit length. Every such variable is bounded by the type’s width, so these bounds may be read as constants; the variable form tells you what the constant depends on.

§Demos and benchmarks

This crate comes with a bin target that can be used for running demos and benchmarks.

Almost all of the public functions in this crate have an associated demo. Running a demo shows you a function’s behavior on a large number of inputs. For example, to demo the mod_pow function on u32s, you can use the following command:
```
cargo run --features bin_build --release -- -l 10000 -m exhaustive -d demo_mod_pow_u32
```
This command uses the exhaustive mode, which generates every possible input, generally starting with the simplest input and progressing to more complex ones. Another mode is random. The -l flag specifies how many inputs should be generated.
You can use a similar command to run benchmarks. The following command benchmarks various GCD algorithms for u64s:
```
cargo run --features bin_build --release -- -l 1000000 -m random -b \
    benchmark_gcd_algorithms_u64 -o gcd-bench.gp
```
This creates a file called gcd-bench.gp. You can use gnuplot to create an SVG from it like so:
```
gnuplot -e "set terminal svg; l \"gcd-bench.gp\"" > gcd-bench.svg
```

The list of available demos and benchmarks is not documented anywhere; you must find them by browsing through bin_util/demo_and_bench.

§Features

test_build: A large proportion of the code in this crate is only used for testing. For a typical user, building this code would result in an unnecessarily long compilation time and an unnecessarily large binary. Much of it is also used for testing malachite-nz and malachite-q, so it can’t just be confined to the tests directory. My solution is to only build this code when the test_build feature is enabled. If you want to run unit tests, you must enable test_build. However, doctests don’t require it, since they only test the public interface.
bin_build: This feature is used to build the code for demos and benchmarks, which also takes a long time to build. Enabling this feature also enables test_build.

Modules§

bools: Functions for working with bools.
chars: Functions for working with chars.
comparison: Macros and traits related to comparing values.
foer_sequences: FoerSequence, a type representing a sequence that is finite or eventually repeating (which is what “foer” abbreviates), just like the digits of a rational number.
iterators: Functions and adaptors for iterators.
named: The Named trait, for getting a type’s name.
nevers: Never, a type that cannot be instantiated.
num: Functions for working with primitive integers and floats.
options: Functions for working with Orderings.
orderings: Functions for working with Options.
platform
random: Functions for generating random values.
rounding_modes: RoundingMode, an enum used to specify rounding behavior.
sets: Functions for working with HashSets and BTreeSets.
slices: Functions for working with slices.
strings: Functions for working with Strings.
tuples: Functions for working with tuples.
unions: Unions (sum types). These are essentially generic enums.
vecs: Functions for working with Vecs.

Macros§

custom_tuples: Defines custom exhaustive tuple generators.
exhaustive_ordered_unique_tuples: Defines exhaustive ordered unique tuple generators.
exhaustive_tuples: Defines exhaustive tuple generators.
exhaustive_tuples_1_input: Defines exhaustive tuple generators that generate tuples from a single iterator.
exhaustive_unions: Defines exhaustive union generators.
exhaustive_unique_tuples: Defines lexicographic unique tuple generators.
exhaustive_vecs_fixed_length: Defines exhaustive fixed-length Vec generators.
fma
gmp_format: Formats values according to a GMP-style printf format string, as gmp_format does, taking the values as ordinary arguments: gmp_format!("%Zd of %d", n, k).
impl_named: Automatically implements Named for a type.
lex_custom_tuples: Defines custom lexicographic tuple generators.
lex_ordered_unique_tuples: Defines lexicographic ordered unique tuple generators.
lex_tuples: Defines lexicographic tuple generators.
lex_unique_tuples: Defines lexicographic unique tuple generators.
lex_vecs_fixed_length: Defines lexicographic fixed-length Vec generators.
max: Computes the maximum of a list of expressions.
min: Computes the minimum of a list of expressions.
random_custom_tuples: Defines custom random tuple generators.
random_ordered_unique_tuples: Defines random ordered unique tuple generators.
random_tuples: Defines random tuple generators.
random_unions: Defines random union generators.
random_unique_tuples: Defines random unique tuple generators.
random_vecs_fixed_length: Defines random fixed-length Vec generators.
round_even
split_into_chunks: Splits an immutable slice into adjacent immutable chunks.
split_into_chunks_mut: Splits a mutable slice into adjacent mutable chunks.
union_struct: Defines unions.