search

Aatch / ramp

RAMP - Rust Arithmetic in Multiple Precision
Apache License 2.0
261 stars 38 forks source link

(2**64 - 1) * 2**64 + 2**64 == 1 #45

Closed huonw closed 9 years ago

huonw commented 9 years ago

This test fails:

#[test]
fn foo() {
    let mut ar = ((Int::from(1) << 64) - 1) << 64_usize;
    let br = Int::from(1) << 64;
    assert_eq!(ar + br, Int::from(1) << 128);
}

(I'm debugging it now.)

Aatch commented 9 years ago

That is some edge case there. I'm guessing it's something to do with the shift-left implementation.

huonw commented 9 years ago

Seems like ar and br are computed correctly, but the number is normalised after doing the elementwise addition (i.e. ll::add), but before pushing the carry, so, in this case, the raw addition entirely overflows and leaves every limb 0 meaning normalization trims everything off. #46