#mathematics #math #numerics #bignum

bin+lib malachite-q

The arbitrary-precision type Rational, with efficient algorithms partially derived from GMP

7 releases

Uses new Rust 2021

0.3.0 Oct 18, 2022
0.2.6 Aug 18, 2022
0.2.5 Jul 18, 2022
0.2.4 Jun 24, 2022

#697 in Math

Download history 16/week @ 2022-08-19 6/week @ 2022-08-26 2/week @ 2022-09-02 7/week @ 2022-09-09 1/week @ 2022-09-16 1/week @ 2022-09-23 3/week @ 2022-09-30 2/week @ 2022-10-07 22/week @ 2022-10-14 47/week @ 2022-10-21 17/week @ 2022-10-28 35/week @ 2022-11-04 30/week @ 2022-11-11 29/week @ 2022-11-18 13/week @ 2022-11-25 6/week @ 2022-12-02

84 downloads per month
Used in malachite

LGPL-3.0-only

11MB
213K SLoC

Rather than using this crate directly, use the malachite meta-crate. It re-exports all of this crate's public members.

In malachite-q's doctests you will frequently see import paths beginning with malachite_q::. When using the malachite crate, replace this part of the paths with malachite::.

The import path of the Rational type is shortened further, to malachite::Rational.

malachite-q

This crate defines Rationals. The name of this crate refers to the mathematical symbol for rational numbers, $$\mathbb{Q}$$.

  • There are many functions defined on Rationals. These include
    • All the ones you'd expect, like addition, subtraction, multiplication, and division;
    • Functions related to conversion between Rationals and other kinds of numbers, including primitive floats;
    • Functions for Diophantine approximation;
    • Functions for expressing Rationals in scientific notation.
  • The numerators and denominators of Rationals are stored as Naturals, so Rationals with small numerators and denominators can be stored entirely on the stack.
  • Most arithmetic involving Rationals requires (automatically) reducing the numerator and denominator. This is done very efficiently by using the high performance GCD and exact division algorithms implemented by Naturals.

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 Rational addition, you can use the following command:
    cargo run --features bin_build --release -- -l 10000 -m exhaustive -d demo_rational_add
    
    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 addition algorithms:
    cargo run --features bin_build --release -- -l 1000000 -m random -b \
        benchmark_rational_add_algorithms -o gcd-bench.gp
    
    or GCD implementations of other libraries:
    cargo run --features bin_build --release -- -l 1000000 -m random -b \
        benchmark_rational_add_assign_library_comparison -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

  • 32_bit_limbs: Sets the type of Limb to u32 instead of the default, u64.
  • 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. 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.

Dependencies

~2.3–6MB
~120K SLoC