Working with Rust's num-bigint

May 24, 2020 4 minutes reading time Development rust go

Why Rust

A couple of years ago, I started learning Go. It’s a nice little language that I like very much, but some things still bother me. Go has no generics, no adequate support for functional style, and no tail call optimization. In my view, most other things the language got right. I know that some of these topics are the subject of heated debates, but the views presented here are mine. What I love most is that it’s a simple and mostly clean language, has a superb standard library, excellent support for templating, and “implicit” interface implementation.

I stumbled across Rust at the same time, but from what I can remember, people were having difficulties due to a steep learning curve, and a standard library that was missing a few bits and pieces. So I went with Go. Rust was still on my radar. I found some time recently and started learning it.

The problem to solve

Whenever I learn a new language, I try to solve some problems with a limited scope. Only after I have successfully solved some of them, I try to use my skills in a little project. This time I went with HackerRank’s Marc’s Cakewalk problem. Because it’s too simple, I added some extra difficulty. The original problem is solvable by using the u64 data type, because it restricts the size n of the input vector. So I removed this restriction, which was 40 elements. Now I needed an arbitrary-sized integer type. Rust has no arbitrary-sized integer type, and there’s no ready-to-use solution in the standard library.

The crate num-bigint

For my additional difficulty to work, I had to calculate e.g. 42 * 2^100000 as a term and add it together with other terms of the same structure. I found out that the crate num-bigint could solve my problem, because it is able to handle arbitrary-sized integers. I wasn’t able to find helpful examples on the Internet. All I found was the source code and the documentation of the crate itself. So I had to use this. Remember, I’m still trying to learn Rust and I’m not familiar with all of its concepts and conventions, let alone the standard library and the crate ecosystem.

I figured it out eventually. Big-integer multiplication, addition, and the power function with a fixed-sized integer as exponent was all I needed. Addition and multiplication is really easy, because it’s done by operator-overloading. The power function was the most challenging, because I didn’t know how to properly read the crate’s documentation. Once I learned that, it was easy, too - just use the pow-trait.

Solution with Rust

So here is the Rust source code for the problem. You cannot use it as part of a HackerRank submission, because it uses an external crate, which HackerRank does not allow. The solution partly has a functional style, except that sort and reverse are having side effects.

extern crate num_bigint;
extern crate num_traits;

use num_bigint::BigInt;
use num_traits::pow;

fn main() {
    let mut cs: Vec<usize> = vec![7, 4, 9, 6]; // example
    let miles = marcs_cakewalk(&mut cs);
    println!("{}", miles.to_str_radix(10));
}

fn marcs_cakewalk(cs: &mut Vec<usize>) -> BigInt {
    cs.sort();
    cs.reverse();
    cs.iter()
        .enumerate() // zip index and value into tuple
        .map(|(i, &v)| BigInt::from(v) * pow(BigInt::from(2), i))
        .fold(
            BigInt::from(0),
            |sum, value| sum + value,
        )
}

Solution with Go

Go has an arbitrary-sized integer type in the standard library called big.Int. A solution with this type, even though it is not written in a functional style, could use the following function. HackerRank would even allow it as part of a solution, because it only uses the standard library.

func marcsCakewalk(cs []int64) *big.Int {
	sort.SliceStable(cs, func(a, b int) bool { return cs[a] > cs[b] })
	sum := big.NewInt(0)
	for i := range cs {
		b2 := big.NewInt(2)
		f1 := big.NewInt(cs[i])
		f2 := b2.Exp(b2, big.NewInt(int64(i)), nil) // 2 ** i
		sum = sum.Add(sum, f1.Mul(f1, f2))
	}
	return sum
}

Conclusion

If you are learning Rust, and you need the crate num-bigint, and you do not find information on how to use it in a limited scenario similar to the one mentioned above, this article might help you. At least it will help me sometime in the future when I need functionality from this crate again and have forgotten how to use it.