19 releases
new 0.4.9  May 22, 2024 

0.4.7  Apr 12, 2024 
0.4.5  Feb 12, 2024 
0.4.4  Oct 29, 2023 
0.2.5  Jul 18, 2022 
#658 in Math
31,532 downloads per month
Used in 57 crates
(5 directly)
11MB
209K
SLoC
Rather than using this crate directly, use the
malachite
metacrate. It reexports all of this crate's
public members.
In malachitenz
's doctests you will frequently see import paths beginning with
malachite_nz::
. When using the malachite
crate, replace this part of the paths with
malachite::
.
The import paths of the Natural
and Integer
types are shortened further, to
malachite::Natural
and malachite::Integer
.
malachitenz
This crate defines
Natural
s
(nonnegative integers) and
Integer
s. Unlike
primitive integers (u32
,
i32
, and so on), these may be
arbitrarily large. The name of this crate refers to the mathematical symbols for natural numbers
and integers, ℕ and ℤ.

There are many functions defined on
Natural
s andInteger
s. These include All the ones you'd expect, like addition, subtraction, multiplication, and integer division;
 Implementations of
DivRound
, which provides division that rounds according to a specifiedRoundingMode
;  Various mathematical functions, like implementations of
FloorSqrt
andGcd
;  Modular arithmetic functions, like implementations of
ModAdd
andModPow
, and of traits for arithmetic modulo a power of 2, likeModPowerOf2Add
andModPowerOf2Pow
;  Various functions for logic and bit manipulation, like
BitAnd
andBitAccess
.

The implementations of these functions use highperformance algorithms that work efficiently for large numbers. For example, multiplication uses the naive quadratic algorithm, or one of 13 variants of ToomCook multiplication, or SchönhageStrassen (FFT) multiplication, depending on the input size.

Small numbers are also handled efficiently. Any
Natural
smaller than 2^{64} does not use any allocated memory, and working with such numbers is almost as fast as working with primitive integers. As a result, Malachite does not provide implementations for e.g. adding aNatural
to au64
, since theu64
can be converted to aNatural
very cheaply. 
Malachite handles memory intelligently. Consider the problem of adding a 1000bit
Natural
and a 500bitNatural
. If we only have references to theNatural
s, then we must allocate new memory for the result, and this is what the&Natural + &Natural
implementation does. However, if we can take the first (larger)Natural
by value, then we do not need to allocate any memory (except in the unlikely case of a carry): we can reuse the memory of the firstNatural
to store the result, and this is what theNatural + &Natural
implementation does. On the other hand, if we can only take the second (smaller)Natural
by value, then we only have 500 bits of memory available, which is not enough to store the sum. In this case, theVec
containing the smallerNatural
's data can be extended to hold 1000 bits, in hopes that this will be more efficient than allocating 1000 bits in a completely newVec
. Finally, if bothNatural
s are taken by value, then theNatural + Natural
implementation chooses to reuse the memory of the larger one.Now consider what happens when evaluating the expression
&x + &y + &z
, where eachNatural
has n bits. Malachite must allocate about n bits for the result, but what about the intermediate sum&x + &y
? Does Malachite need to allocate another n bits for that, for a total of 2 n bits? No! Malachite first allocates n bits for&x + &y
, but then that partial sum is taken by value using theNatural + &Natural
implementation described above; so those n bits are reused for the final sum.
Limbs
Large Natural
s
and Integer
s
store their data as Vec
s of some
primitive type. The elements of these
Vec
s are called "limbs" in GMP
terminology, since they're large digits. By default, the type of a Limb
is
u64
, but you can set it to
u32
using the 32_bit_limbs
feature.
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 onNatural
s, you can use the following command:
This command uses thecargo run features bin_build release  l 10000 m exhaustive d demo_natural_mod_pow
exhaustive
mode, which generates every possible input, generally starting with the simplest input and progressing to more complex ones. Another mode israndom
. Thel
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
u64
s:
or GCD implementations of other libraries:cargo run features bin_build release  l 1000000 m random b \ benchmark_natural_gcd_algorithms o gcdbench.gp
This creates a file called gcdbench.gp. You can use gnuplot to create an SVG from it like so:cargo run features bin_build release  l 1000000 m random b \ benchmark_natural_gcd_library_comparison o gcdbench.gp
gnuplot e "set terminal svg; l \"gcdbench.gp\"" > gcdbench.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
32_bit_limbs
: Sets the type ofLimb
tou32
instead of the default,u64
.random
: This feature provides some functions for randomly generating values. It is off by default to avoid pulling in some extra dependencies.enable_serde
: Enables serialization and deserialization using serde.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. Some of it is also used for testingmalachiteq
, so it can't just be confined to thetests
directory. My solution is to only build this code when thetest_build
feature is enabled. If you want to run unit tests, you must enabletest_build
. However, doctests don't require it, since they only test the public interface. Enabling this feature also enablesrandom
.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 enablestest_build
andrandom
.
Copyright © 2024 Mikhail Hogrefe
Dependencies
~2–12MB
~151K SLoC