Simple Rust BigInt

#1

I know Rust has a BigInt crate, but is there any/has someone make simple Rust BigInt that fit for competitive programming like?

#2

Is there something about the num-bigint crate that keeps it from being useful in your situation?

#3

What are your requirements for competitive programming? The num-bigint readme also lists a few alternatives.

#4

I think the usual requirement for competitive programming is to be able to copy-and-paste without external Cargo dependency.

2 Likes
#5

Exactly. Most of the online judge are not supporting Rust external Cargo dependency.

#6

A u128 is already pretty big. Isn’t that enough? ^^

2 Likes
#7

No, u128 often isn’t enough.

#8

Would 256 bits be enough? You could do this:

struct u256 {
    high: u128,
    low: u128,
}

impl u256 {
    // overload operator + -- I don't know how
    fn add(a: &u256 , b: &u256 ) -> Result<u256, OverflowError> {
        let mut ans = u256 { a.high + b.high, a.low + b.low };
        // if overflow occurred, ans.low will be smaller than both a.low 
        // and b.low, we only need to check for one of a or b to know.
        if ans.low < a.low {
            // Because it is binary, overflow means that we should add
            // 1 to the next column, which is the lowest bit of our high field
            ans.high += 1u128;
        }
        if ans.high < a.high {
            return OverflowError;
        }
        ans
    }
}

I didn’t check any of this, but this is the basic idea. I think it is simple and quick enough to do yourself. You can even extend it to have three or more u128 members. For signed, you will have to do a little more work, though.

1 Like
#9

I think it might be a good idea to try to get that changed to support a handful, the same way that the playground supports some crates. An online interview system I used recently also had a list of about 6 that it included.

I agree that arbitrary crates won’t happen, but things like regex seem like must-haves.

1 Like
#10

https://doc.rust-lang.org/std/ops/trait.Add.html

use std::ops::Add;
impl Add for u256 {
  type Output = Point;
  fn add(self, other: u256) -> u256 {
    // ...
  }
}
#11

256 bits isn’t enough. It should be able to calculate more than

-1 * 10^100000 to 10^100000

This is one of the problems if you want to know it: Addition of Big Integers

And so, looks like I need to make it myself then.

#12

Woah! That’s a 41KB number you’re going to be manipulating there. At that point manipulating numbers should be done with a library, or a Vec<u8>

#13

Given that “addition of big integers” is the entire problem, it would seem to be cheating to use something like num-bigint – although other languages like Python do have this built in.

At least addition is straightforward to implement. Parsing will be harder if you want to represent it in full binary, since you need multiplication by 10 as you accumulate, and then division by 10 when you print it. You can keep it simple if you use unpacked BCD instead, one decimal digit per byte.

#14

Or if memory usage becomes a problem, an unpacked radix-100 representation (two decimal digits per u8 byte) can be used for addition and subtraction, with straightforward conversion between internal and external representations. However, I wouldn’t recommend radix-100 for more complex math.