Addition for arbitrarily large integers

help
1

I wrote this algorithm for adding two numbers with unlimited length:

fn add(self, rhs: Self) -> Self::Output {
        let mut data = self.data;
        let mut other_data = rhs.data;
        let mut error = 0;

        if data.len() > other_data.len() {
            error = data.len() - other_data.len();
            other_data.append(&mut vec![0; error]);
        } else if data.len() < other_data.len() {
            error = other_data.len() - data.len();
            data.append(&mut vec![0; error]);
        }

        assert!(data.len() == other_data.len());
        let mut carry_flag: u16 = 0;
        let mut set_on_last = false;

        for (idx, other_data) in other_data.iter().enumerate() {
            let add_res = *other_data as u16 + data[idx] as u16 + carry_flag;
            if add_res > u8::MAX as u16 {
                carry_flag = add_res / u8::MAX as u16;
                data[idx] = (add_res as u16 % u8::MAX as u16) as u8;
                set_on_last = true;
            } else {
                data[idx] = add_res as u8;
                set_on_last = false;
            }
        }

        if set_on_last {
            for (idx, data_) in data.clone().iter().rev().enumerate() {
                if data_ == &0 {
                    data.remove(idx);                    
                }
            }
            data.push(carry_flag as u8);
        }
        
        Self {data, polarity: true}
    }

However, when I try and add two numbers (45986093450806083945+938650409348560983), I get 1334440654591915589918089391908436672 back from the program. The function takes in two Vec<u8> and tries to add them together. What is the issue with the algorithm? is there a simpler way to do this?

2

You should not be dividing by u8::MAX but instead by 256, since that's your basis. In the same way in the normal decimal system the biggest digit you can have is 9, but you divide instead by 10 to get the number of tens.

2 Likes
3

I made that change, but now it comes back as 1334440654591915589918088292380031424. The answer has become slightly more accurate, but there are still a few issues. The last 7 elements of the array are all ones, when they should be zeros. Here is the number result array compared to the correct answer:

[192, 186, 181, 66,  236, 47, 54,  140, 3, 1, 1, 1, 1, 1, 1, 1]
[192, 185, 181, 64,  236, 45, 54,  139, 2, 0, 0, 0, 0, 0, 0, 0]

What is causing the one to appear?

4

Turns out the solution is to reset the carry flag every time you hit the second branch.

5

Could I ask you to try out these nightly functions?

(I linked u8, but they're on all the unsigned integers, so use whichever digit type you prefer.)

They exist in the hopes of making it easier to write arbitrary width integers (Tracking Issue for bigint helper methods · Issue #85532 · rust-lang/rust · GitHub) so it'd be really useful information towards helping them get stabilized if you could report what went well with them, or how you might wish they'd work differently to be more helpful.

If nothing else, hopefully they can save you a bunch of the back-and-forth as casting.

1 Like
6

Interesting. I might look in to implementing carrying_mul in multiplication, but the entire reason iI am doing this is to learn, so i might just implement it my self. I also want to implement faster multiplication as well. Here is the github, if you wish to contribute.