Docs are broken

[AaronKutch]

When I try to go to https://docs.rs/apint/0.1.0/apint/, it says that they do not exist

[AaronKutch]

Also, I am running into_checked_shl on a 256 bit ApInt with a shift amount of 256 and it panics with invalid shift amount. I would expect that it would accept any positive shift amount. Also, can you message me whenever you have an implementation for multiplying and dividing large ApInts? I tried making a very inefficient workaround, but I don't think it is a good use of my time if it will be implemented in a month

[Robbepop]

Hi, yeah docs are broken for version 0.1.0 since the nightly rust compiler version at docs.rs is slightly too outdated and thus results in compilation-error while generating docs. I can fix this easily if you need it badly. For a temporary workaround you can download the crate and do cargo doc --open.

Shifting is only valid (also in C - otherwise you get undefined behaviour) for shift amounts that are at most as large as the bit-width of the respective integer value. This is expected behaviour. But since you receive a Result type back you can track this situation and perform error handling procedures in this case. :)

[AaronKutch]

That makes sense. I am not sure why I asked you to message me, I can look myself. I need to get more sleep

[Robbepop]

I can try to implement an okayish-efficient way to handle multiplication, division and remainder for large ApInt instances within the next few weeks.

[AaronKutch]

I haven't seen you committing anything in the past two weeks, so I hope you are busy implementing the mul and div functions. Next week I will probably run out of other things to do before I absolutely need the mul and div functions to advance my crate further. If you have troubles you can't get past I might be able to help you.

[Robbepop]

I haven't put a lot of work into apint the last 2 weeks since I have other projects and not enough spare time. Help is very welcome! I can create an issue around the implementation of mul and div operations tomorrow where we can discuss the strategy and the concrete implementation we want for apint.

For now, I would implement the entire operations similar to how LLVM did with their very similar support library, named APInt. Here are the sources of its division and remainder.

[AaronKutch]

I am making implementations for mul and udiv, here is a rough draft (not building yet) for mul. I am confused about the implementation of ApInt, about how to access the digits. Wherever I index an ApInt, I really mean to access the Digits as if they were an array. Wherever in the comments there is an uninitialized variable I mean for you to put some code there that produces what that comment says. This is just the first round, and I will take what you fix and put it through edge case testing on my fork and whatever you say it needs. Also, the part with the Vec is just an example and probably needs to be replaced with some different construct

    //long multiplication, in the future we could have karatsuba multiplication for larger ints (wikipedia says 320-640 bits is about where karatsuba multiplication algorithms become faster)

//NOTE: currently this performs wrapping or modular multiplication, I will need to add overflow checks.

//during setting up the following two vars, if one of them is all zeros just do an early return of lhs = 0
let lhs_first_zero: usize = //the first most significant digit that is zero
let rhs_first_zero: usize = //the first most significant digit that is zero

//the first iterations of both nested loops below are unrolled to the front, for having something to initialize the carries and stuff with, and just in case the compiler cannot unroll it.

let temp0: DoubleDigit = lhs[0].dd() * rhs[0].dd();
lhs[lhs_i] = temp0.lo(); //throughout, we try to get the final digits for lhs as soon as we can instead of something like lhs = sum at the very end, and there are potential optimizations the compiler can do with this.
let mut horz_carry: Digit = temp0.hi(); //the horizontal carry seen across the top of the multiplication
let mut sum = Vec::with_capacity(/*width in digits here, minus 1*/);
//the goal here with `sum` is to allocate and initialize it only once.
//We could start sum as a zeroed ApInt and then let the loop below overwrite the zeroes,
//but I am not sure if the compiler is smart enough know that all the zeros will be
//eventually be overwritten and not have to intitialize it out first. Note also that
//sum has one less Digit than what lhs has, because the first digit is already taken
//care of above. This is why sum is addressed by sum[lhs_i - 1]. I am pretty sure that
//any cost of decrementing lhs_i is offset by other optimizations below
for rhs_i in 1..rhs_first_zero {
    let temp0: DoubleDigit = (lhs[0].dd() * rhs[rhs_i].dd()) + horz_carry.dd();
    horz_carry = temp0.hi();
    sum.push(temp0.lo());
}
let sum = //redefine sum as an ApInt without doing any more allocations or initializations
for lhs_i in 1..lhs_first_zero {
    let temp0: DoubleDigit = lhs[lhs_i].dd() * rhs[0].dd();
    let mut horz_carry = temp0.hi();
    let temp1: DoubleDigit = sum[lhs_i - 1].dd() + temp0.lo().dd();
    lhs[lhs_i] = temp1.lo();
    let mut add_carry: Digit = temp1.hi();
    for rhs_i in 1..(rhs_first_zero - lhs_i) {
        let temp0: DoubleDigit = (lhs[lhs_i].dd() * rhs[rhs_i].dd()) + horz_carry;
        horz_carry = temp0.hi();
        let temp1: DoubleDigit = sum[lhs_i - 1].dd() + temp0.lo().dd() + add_carry.dd(); //this can overflow but it takes more than 2^30 digit width ApInts.
        sum[lhs_i - 1] = temp1.lo();
        add_carry = temp1.hi();
    }
}
//if the width of lhs is something like 250, do the last 6 bits need to be zeroed out?

[AaronKutch]

I realized I should have started a new issue but lets just get this one close to compiling

[Robbepop]

Thank you really much for your thought and scratch implementation of the multiplication!

Accessing Digits

How accessing digits for small and large ApInt data structures work can be seen by the example of the implementation of ApInt::checked_add_assign:

pub fn checked_add_assign(&mut self, rhs: &ApInt) -> Result<()> {
    match self.zip_access_data_mut(rhs)? {
        Inl(lhs, rhs) => {
            let lval = lhs.repr();
            let rval = rhs.repr();
            let result = lval.wrapping_add(rval);
            *lhs = Digit(result);
        }
        Ext(lhs, rhs) => {
            let mut carry = Digit::zero();
            for (l, r) in lhs.into_iter().zip(rhs) {
                *l = ll::carry_add(*l, *r, &mut carry);
            }
        }
    }
    self.clear_unused_bits();
    // Maybe we should return a recoverable error upon carry != 0 at this point.
    Ok(())
}

The self.zip_access_data_mut is a utility method to split program logic into parts to operate differently on small and large ApInt instances. The Inl(lhs, rhs) side provides digit access for small ApInt instances up to 64-bits width and Ext(lhs, rhs) provides access to large ApInt instances above 64-bit width. In the case of Inl lhs and rhs are just single Digit instances whereas in the case of Ext they are digits slices ([&Digit] or [&mut Digit]). The advantage of zip_access_data_* is that it checks for equal width and thus we need the additional ? operator at its end - this ensures that both lhs and rhs in Ext are of the same length. As can be seen in the example you can use them to iterate over all digits of lhs and rhs and do other stuff that can be done with slices.

Code Review

Do you want to create a Pull Request provided with additional unit tests to test your initial implementation of the multiplication when it is done? I will review your current implementation later when I have more time. :)

Cya!

[Robbepop]

Could you please open a new issue for the multiplication implementation and another issue for the division and remainder implementation once available? :)

[Robbepop]

I think we can close this since due to version 0.2.0 the problem has been resolved.