Trait Base

pub trait Base: Copy + Debug {
    const NUMBER: u16;

    // Required methods
    fn new() -> Self;
    fn exp_range(&self) -> ExpRange;
    fn sig_range(&self) -> SigRange;

    // Provided methods
    fn pow(exp: u32) -> u64 { ... }
    fn pow_u128(exp: u32) -> u128 { ... }
    fn calculate_ranges() -> (ExpRange, SigRange) { ... }
    fn lshift(lhs: u64, exp: u32) -> u64 { ... }
    fn rshift(lhs: u64, exp: u32) -> u64 { ... }
    fn lshift_u128(lhs: u128, exp: u32) -> u128 { ... }
    fn rshift_u128(lhs: u128, exp: u32) -> u128 { ... }
    fn get_mag(sig: u64) -> u32 { ... }
    fn get_mag_u128(sig: u128) -> u32 { ... }
    fn as_number(&self) -> u16 { ... }
}

If performance isn’t critical I’d highly recommend the create_default_base macro which creates a base with sensible defaults. The only reason to create a custom implementation is if you find the default implementations’ operations to be a bottleneck. In this case I’d recommend looking at my implementation of the Decimal base as a guide.

This trait is used to indicate that a type is a valid base for a BigNumBase. It contains metadata and functions that can be used to efficiently handle arbitrary bases. Importantly you must ensure all of the following:

• base.exp_range().max() = base.exp_range().min() + 1
• base.exp_range().min() > 0
• base.sig_range().min() = base.pow(exp_range().min())
• base.sig_range().max() = base.pow(exp_range().max()) - 1
• B::pow(n) = NUMBER.pow(n) for all n < base.exp_range().max()
• B::rshift(lhs, exp) = lhs / B::NUMBER.pow(n) for all n <= base.exp_range().max()
• B::lshift(lhs, exp) = lhs * B::NUMBER.exp(n) for all n <= base.exp_range().max()
• B::get_mag(n) should return the highest exponent x such that n >= B::pow(x), for all n <= exp_range().max()
• base.sig_range().min() * B::NUMBER > u64::MAX
  • This restriction allows us to conveniently handle some construction cases

The above requirements also hold for the u128 versions of lshift, rshift, get_mag, pow which are used for multiplication and division (since those calculations involve projecting values to u128 to preserve information)

Some of these calculations have the potential to overflow a u64 so you may need to think of other ways to compute them if you plan to verify them manually.

Additionally, the implementers will be copied on every math operation and in some other contexts, so ensure that they are lightweight. E.g. even though

#[derive(Clone, Copy, Debug)]
pub struct CustomBase {
    metadata: [u8; 10000000000],
}

is valid, it’s ill-advised here. If you need a table of powers I would recommend a global const array that you reference in the pow method.

The recommended format for a non-performance critical simple Base definition and implementation is:

use bignumbe_rs::{ExpRange, SigRange, Base};

#[derive(Clone, Copy, Debug)]
pub struct Base13 {
    exp_range: ExpRange,
    sig_range: SigRange
}

impl Base for Base13{
    const NUMBER: u16 = 13;

    fn new() -> Self {
        let (exp_range, sig_range) = Self::calculate_ranges();
        Self {exp_range, sig_range}
    }

    fn exp_range(&self) -> ExpRange {
        self.exp_range
    }

    fn sig_range(&self) -> SigRange {
        self.sig_range
    }
}

Required Associated Constants

const NUMBER: u16

This contains the numeric value of the type. E.g. for binary 2, for decimal 10, etc.

Required Methods

fn new() -> Self

Function that can create an instance of this Base. Users should never have to manually create instances of this type. This is called implicitly on every call to BigNumBase<Self>::new() so it should be as lightweight as possible. Note that it is not called when creating a BigNumBase from another, like when performing an addition. In this case the base is simply copied over.

fn exp_range(&self) -> ExpRange

Function that fetches the non-inclusive range of the exponent for the significand in the BigNum with this base. E.g. the range for binary is [63, 64), since the range of the significand is [2^63, 2^64)

fn sig_range(&self) -> SigRange

Function that fetches the inclusive range for the significand in the BigNum with this base. E.g. for binary the range of the significand is [2^63, 2^64 - 1]

Provided Methods

fn pow(exp: u32) -> u64

This is a function that computes Self::NUMBER ^ exp. It has a default implementation that computes the value directly. It is recommended to override this behavior if there is a trick to the exponentiation (like how for binary 2^n = (1 << n)). You can also create a gloabl const lookup table and reference that.

fn pow_u128(exp: u32) -> u128

This is a function that computes the same value as pow but in a u128 value. Mostly useful to help with multiplication/division, and as such it’s probably unnecessary to override it unless multiplication/division performance is critical

fn calculate_ranges() -> (ExpRange, SigRange)

This function calculates the ranges for the exponent and the significand. It is not particularly efficient so if performance is a concern you should not use it. It mainly exists to facilitate the create_default_base! macro. It is recommended to store the ranges in a const and return them directly in the exp_range and sig_range methods if convenient.

fn lshift(lhs: u64, exp: u32) -> u64

This is a function that computes lhs * (Self::NUMBER ^ exp). There is a default implementation that obtains the value of Self::NUMBER ^ exp via the pow method for this type, and does a division. It is recommended to override this method if there is a trick for the division (like how in binary, lhs * (2 ^ exp) = lhs >> exp, or in octal lhs * (8 ^ exp) = lhs >> (3 * exp)

fn rshift(lhs: u64, exp: u32) -> u64

This is a function that computes lhs / (Self::NUMBER ^ exp). There is a default implementation that obtains the value of Self::NUMBER ^ exp via the pow method for this type, and does a multiplication. It is recommended to override this method if there is a trick for the division (like how in binary, lhs / (2 ^ exp) = lhs << exp, or in octal lhs / (8 ^ exp) = lhs << (3 * exp)

fn lshift_u128(lhs: u128, exp: u32) -> u128

This is a function that computes the same thing as lshift but in a u128 value. Mostly useful to help with multiplication/division, and as such it’s probably unnecessary to override it unless multiplication/division performance is critical

fn rshift_u128(lhs: u128, exp: u32) -> u128

This is a function that computes the same thing as rshift but in a u128 value. Mostly useful to help with multiplication/division, and as such it’s probably unnecessary to override it unless multiplication/division performance is critical

fn get_mag(sig: u64) -> u32

This is a function that computes the highest power x such that sig >= (Self::NUMBER ^ x). There is a default implementation that uses ilog, and it is recommended to use this unless there is a special way to find the magnitude (e.g. binary and decimal have specialized ilog implementations). As a special case, bases that are powers of 2 or 10 can use log arithmetic to convert. I tried this with octal and hexadecimal but it had no noticeable impact.

fn get_mag_u128(sig: u128) -> u32

This is a function that computes the same thing as get_mag but in a u128 value. Mostly useful to help with multiplication/division, and as such it’s probably unnecessary to override it unless multiplication/division performance is critical

fn as_number(&self) -> u16

This method just fetches Self::NUMBER but is provided as an instance method for convenience. Overriding it is undefined behavior

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl Base for Binary

const NUMBER: u16 = 2u16

impl Base for Decimal

const NUMBER: u16 = 10u16

impl Base for Hexadecimal

const NUMBER: u16 = 16u16

impl Base for Octal

const NUMBER: u16 = 8u16