Factorial calculated extremely slow

[mrLSD]

extern crate num;

use num::{BigInt, BigUint, Zero, One, FromPrimitive};

fn factorial(n: usize) -> BigUint {
    let mut f: BigUint = One::one();
    for i in 1..(n+1) {
        let bu: BigUint = FromPrimitive::from_usize(i).unwrap();
        f = f * bu;
    }
    f
}

fn main() {
    println!("{}", factorial(1_000_000));
}

Execute:

$ cargo build --release
$ tiem ./factorial
real    20m46.867s
user    18m15.180s
sys 2m28.616s

For example:
gcc: 2m.20s

What is wrong?

[cuviper]

Can you run it with a profiler? Also, I have no idea what your gcc version looks like.

We probably could make some optimizations for scalar multipliers though. That would let you avoid the FromPrimitive and also perform the multiplication in-place on the buffer.

(Side note, the plain From trait is preferable here, since this is an infallible conversion. But I don't think that's the performance difference, as the optimizer should see through this.)

[mrLSD]

gcc version:

// gcc -o fac-gmp-cpp fac-gmp.cpp -lgmp -O3 && time ./fac-gmp-cpp > res-fac-gmp-cpp
// gcc-v5.4.0
// gmpc-dev v11.8.16-9
#include <stdio.h>
#include <gmp.h>

static void factorial (long n, mpz_t r)
{
    mpz_init_set_si (r, 1);
    for (; n > 1; n--) {
       mpz_mul_si (r, r, n);
    }
}

int main (void)
{
    int n;
    mpz_t r;
    factorial (1000000, r);
    gmp_printf ("%Zd\n", r);
    return 0;
}

[cuviper]

OK, so mpz_mul_si (r, r, n) is multiplying a scalar instead of another mpz_t, and you're reusing the same buffer for output. These are significant differences for performance. I'd still love to see a perf profile, but my hunch is that there will be a lot of time spent in the allocator and maybe memcpy.

I think we could add scalar ops, impl Mul<u32> for BigUint etc., and we should be able to reuse the buffer in that case. (In general multiplication, we always write the result in a new buffer.)

I don't expect to achieve parity with gmp and all its hand-written asm, but we can probably reduce the gap.

[hauleth]

@mrLSD num-bignum isn't super efficient implementation of bignum. If you need speed I would suggest either:

• ramp (if you can use nightly compiler)
• gmp (if you can use C code)

[cuviper]

In current code, using (1..n + 1).fold(BigUint::one(), |f, i| f * i) takes me 2m21s, then another 8m to actually print out the 18488885-bit result. Could be we have some tricks to learn for that decimal output...

Anyway, num-bigint is migrating to its own repo, so please open a new issue if you think there are concrete improvements we can make. e.g. maybe for the decimal conversion.
https://github.com/rust-num/num-bigint/issues