1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
//! This crate defines [`Rational`]s. The name of this crate refers to the mathematical symbol for
//! rational numbers, ℚ.
//! - There are many functions defined on [`Rational`]s.
//! These include
//! - All the ones you'd expect, like addition, subtraction, multiplication, and division;
//! - Functions related to conversion between [`Rational`]s and other kinds of numbers, including
//! primitive floats;
//! - Functions for Diophantine approximation.
//! - The numerators and denominators of [`Rational`]s are stored as
//! [`Natural`](malachite_nz::natural::Natural)s, so [`Rational`]s with small numerators and
//! denominators can be stored entirely on the stack.
//! - Most arithmetic involving [`Rational`]s requires (automatically) reducing the numerator and
//! denominator. This is done very efficiently by using the high performance GCD and exact
//! division algorithms implemented by [`Natural`](malachite_nz::natural::Natural)s.
//!
//! # 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:
//! ```text
//! 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:
//! ```text
//! 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:
//! ```text
//! 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:
//! ```text
//! 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`](malachite_nz#limbs) to [`u32`] instead of the
//! default, [`u64`].
//! - `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`.
#![allow(
unstable_name_collisions,
clippy::assertions_on_constants,
clippy::cognitive_complexity,
clippy::many_single_char_names,
clippy::range_plus_one,
clippy::suspicious_arithmetic_impl,
clippy::suspicious_op_assign_impl,
clippy::too_many_arguments,
clippy::type_complexity,
clippy::upper_case_acronyms
)]
#![warn(
clippy::cast_lossless,
clippy::explicit_into_iter_loop,
clippy::explicit_iter_loop,
clippy::filter_map_next,
clippy::large_digit_groups,
clippy::manual_filter_map,
clippy::manual_find_map,
clippy::map_flatten,
clippy::map_unwrap_or,
clippy::match_same_arms,
clippy::missing_const_for_fn,
clippy::mut_mut,
clippy::needless_borrow,
clippy::needless_continue,
clippy::needless_pass_by_value,
clippy::print_stdout,
clippy::redundant_closure_for_method_calls,
clippy::single_match_else,
clippy::trait_duplication_in_bounds,
clippy::type_repetition_in_bounds,
clippy::unused_self
)]
#[macro_use]
extern crate malachite_base;
extern crate malachite_nz;
#[cfg(feature = "serde")]
#[macro_use]
extern crate serde;
#[cfg(feature = "test_build")]
extern crate itertools;
#[cfg(feature = "test_build")]
extern crate num;
#[cfg(feature = "test_build")]
extern crate rug;
use malachite_base::named::Named;
#[cfg(feature = "test_build")]
use malachite_base::num::arithmetic::traits::CoprimeWith;
use malachite_base::num::basic::traits::{NegativeOne, One, OneHalf, Two, Zero};
use malachite_base::num::logic::traits::SignificantBits;
use malachite_nz::natural::Natural;
/// A rational number.
#[derive(Clone, Hash, Eq, PartialEq)]
#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
pub struct Rational {
// whether the `Rational` is non-negative
#[cfg_attr(feature = "serde", serde(rename = "s"))]
pub(crate) sign: bool,
#[cfg_attr(feature = "serde", serde(rename = "n"))]
pub(crate) numerator: Natural,
#[cfg_attr(feature = "serde", serde(rename = "d"))]
pub(crate) denominator: Natural,
}
impl Rational {
// Returns true iff `self` is valid.
//
// To be valid, its denominator must be nonzero, its numerator and denominator must be
// relatively prime, and if its numerator is zero, then `sign` must be `true`. All `Rational`s
// must be valid.
#[cfg(feature = "test_build")]
pub fn is_valid(&self) -> bool {
self.denominator != 0
&& (self.sign || self.numerator != 0)
&& (&self.numerator).coprime_with(&self.denominator)
}
}
impl<'a> SignificantBits for &'a Rational {
/// Returns the sum of the bits needed to represent the numerator and denominator.
///
/// # Worst-case complexity
/// Constant time and additional memory.
///
/// # Examples
/// ```
/// extern crate malachite_base;
///
/// use malachite_base::num::logic::traits::SignificantBits;
/// use malachite_base::num::basic::traits::Zero;
/// use malachite_q::Rational;
/// use std::str::FromStr;
///
/// assert_eq!(Rational::ZERO.significant_bits(), 1);
/// assert_eq!(Rational::from_str("-100/101").unwrap().significant_bits(), 14);
/// ```
fn significant_bits(self) -> u64 {
self.numerator.significant_bits() + self.denominator.significant_bits()
}
}
/// The constant 0.
impl Zero for Rational {
const ZERO: Rational = Rational {
sign: true,
numerator: Natural::ZERO,
denominator: Natural::ONE,
};
}
/// The constant 1.
impl One for Rational {
const ONE: Rational = Rational {
sign: true,
numerator: Natural::ONE,
denominator: Natural::ONE,
};
}
/// The constant 2.
impl Two for Rational {
const TWO: Rational = Rational {
sign: true,
numerator: Natural::TWO,
denominator: Natural::ONE,
};
}
/// The constant -1.
impl NegativeOne for Rational {
const NEGATIVE_ONE: Rational = Rational {
sign: false,
numerator: Natural::ONE,
denominator: Natural::ONE,
};
}
/// The constant 1/2.
impl OneHalf for Rational {
const ONE_HALF: Rational = Rational {
sign: true,
numerator: Natural::ONE,
denominator: Natural::TWO,
};
}
impl Default for Rational {
/// The default value of a [`Rational`], 0.
fn default() -> Rational {
Rational::ZERO
}
}
// Implements `Named` for `Rational`.
impl_named!(Rational);
/// Traits for arithmetic.
pub mod arithmetic;
/// Traits for comparing [`Rational`]s for equality or order.
pub mod comparison;
/// Traits for converting to and from [`Rational`]s, converting to and from strings, and extracting
/// digits and continued fractions.
pub mod conversion;
/// Iterators that generate [`Rational`]s without repetition.
pub mod exhaustive;
/// Iterators that generate [`Rational`]s randomly.
pub mod random;
#[cfg(feature = "test_build")]
pub mod test_util;