Improvement to perform the factorial in the rust language

Question

Improvement to perform the factorial in the rust language

Navigation

#1 by (3 votes)

13

I am beginning to study the language rust and, as I usually do to compare with other languages, I want to implement the factorial calculation for large numbers (aka "BigInts" ).

I use the version rust 1.9.0 (stable) , which forces me to search outside the standard library crate to use large numbers ( crate num ). On the other hand, you can not use unstable characteristics of the language such as the aggregation methods sum or product , which you have to reimplement using fold .

At the moment, I have implemented three versions:

extern crate num_bigint;
extern crate num_traits;
extern crate num_iter;

use num_bigint::BigUint;
use num_traits::{Zero, One};

use num_iter::range_inclusive;

fn fact(n: usize) -> BigUint {
    let mut res: BigUint = One::one();

    for i in 2..n + 1 {
        res = res * BigUint::from(i);
    }
    res
}

fn fact2(n: usize) -> BigUint {
    (2..n + 1).fold(One::one(), |x, y| x * BigUint::from(y))
}

fn fact3(n: usize) -> BigUint {
    range_inclusive(One::one(), BigUint::from(n)).fold(BigUint::one(), std::ops::Mul::mul)
}

I am interested, above all, in the functional orientation of the language as it appears in the last two implementations.

Although rust should be quite fast in execution, these implementations are much slower than others made in other languages (haskell, python, scala, ...). Also, the code seems inelegant to me. For that:

Is it possible to improve these implementations to be faster?
Can you rewrite this code to make it more elegant and / or functional?
Any better implementation?
Maybe with a macro you could make readable the code?

I add time estimation

Without being anything precise, I add the times obtained with different languages for the calculation of 150000! to make a better idea:

haskell  25.68 secs
python   15.20 secs
rust[1]  17.67 secs
scala     8.36 secs
scala[2]  2.32 secs
scala[3]  0.32 secs

[1] compilado en rust con optimizaciones completas
[2] usando las colecciones paralelizables de scala
[3] algoritmo paralelizable en scala (https://github.com/chemacortes/factPar)

In addition to times, memory consumption should be measured. In this aspect, yes that the rust version stands out for the little memory used.

Edit [d: 2016-07-28]: I was able to confirm that the crate num I use has some bugs that make it impossible to use the product method in iterators BigUint that would be perfect for the implementation of the factorial. You will have to be patient until ecosistema rust ripens and pull with "workarounds" , even if they are not as elegant as they should be.

rust factorial

asked by ChemaCortes 27.06.2016 в 15:09

source

1 answer

Show progress bar with values while loading subpage How to join the values of an object of a json to an array

score 3 · Answer 1

After giving it a few laps, I've come to the conclusion that the language rust is still being completed. The unstable versions allow to try some new features, but they are quite limited in application since not all the libraries implement them.

For example, focusing on the structure BigUint used for the factorial calculation, it lacks the treatments ( traits ) necessary to apply some of the new extensions such as the inclusive range ( ... ) or deal Product to be able to use the product() method with iterators of BigUint . I hope that these shortcomings will be added over time.

Finally, I have not managed to improve factorial calculation times. At the most, be sure to compile with the optimizations enabled (option --release ) and be using the 64bit versions of the rust tools if possible (for example, rustup install by default 32bit versions for windows, even if it is a 64bit windows).

Finally, a final version of factorial in rust:

extern crate num;

use num::{ One, BigUint, range_inclusive };

pub fn fact(n: usize) -> BigUint {
    range_inclusive(BigUint::one(), BigUint::from(n))
      .fold(BigUint::one(), |res, x| x * res)
}

#[test]
fn test_fact5() {
  assert_eq!(fact(5), BigUint::from(120usize));
}

#[test]
#[ignore]
fn test_factlarge {
  let s = fact(150000);
  assert_eq!(s.to_string().len(), 711273);
}

To run the first test:

cargo test --release

To run the ignored test:

cargo test --release -- --ignored

Edition: link to the github repository with the code.