[libre-riscv-dev] algebraic numbers library

[Jacob Lifshay]

I've been writing an algebraic numbers library for a while with the
intention that it could be used to create a reference by which we
could test our IEEE 754 operations, since the numbers it represents
are exact instead of approximated.

The main API is using RealAlgebraicNumber in
https://salsa.debian.org/Kazan-team/algebraics/blob/master/src/algebraic_numbers.rs

the RealAlgebraicNumber type supports add, sub, mul, div (but not by
zero), comparisons, raising to rational powers, floor, ceil, trunc,
fract, conversion to rational numbers and integers (returning None if
the number is not rational or integer), and conversions from rational
numbers and integers.

It is based on polynomials over bigints, so the only restrictions are
execution time and memory usage.

I specifically don't support conversions to floating point (though may
add them anyway for other users), since that should be implemented by
the library implementing ieee754 on top of the algebraic numbers
library.

I just got it to pass it's tests a few minutes ago, so it's probably
correctly implemented (or at least won't silently fail), but is quite
slow since I have not optimized it much yet.

I'm planning on publishing it on crates.io (Rust's package repository)
under the name algebraics (where I currently have a place-holder
crate) after a little more testing and un-`pub`-ifying
partially-implemented parts.

Comments appreciated.

Sample ieee mantissa rounding algorithm using the library (not tested):

fn round_to_nearest(mut value: RealAlgebraicNumber,
mantissa_fraction_bits: usize) -> BigInt {
    // notice how the code is quite straight forward
    value *= BigInt::one() << mantissa_fraction_bits;
    let mut retval = value.to_integer_floor(); // gets floor as BigInt
    value -= &retval;
    let one_half = Ratio::new(1, 2).into();
    match value.cmp(&one_half) {
        Ordering::Less => {}
        Ordering::Equal => if retval.is_odd() {
            retval += 1i32;
        },
        Ordering::Greater => retval += 1i32,
    }
    retval
}

Jacob Lifshay