Rust 纪元第 382 周最佳 crate：ibig 的实践，以及和 num crate 的比较

niqin.com

发布于 2022-06-30 16:38:57

5230

Rust 纪元第 382 周，评出的周最佳 crate 是大数计算相关的 ibig。目前在 github 星星数量不足 50，还处于开发初期。

虽然以前的 Rust 开发中，大数计算方面使用的是 num crate 的 BigInt 和 BigUint，完全满足需求。但是查阅到 ibig 提供的基准测试，性能挺不错。所以本文结合目前使用较广的大数计算 crate num，采用 2 种阶乘的不同实现方式，进行实践。尝试一下，看是否进行 crate 替换。

大数计算的概念，就不赘述。我们设想一个 1000000000 甚至更大的阶乘，不使用大数计算相关 crate，显然是跑不起来的。下面，我们使用 num 和 ibig 进行测试和比较。

准备

为了仅测试 num 和 ibig，我们创建一个单独的工程，并引入 chrono 进行时间的简单计算。执行如下命令：

cargo new bigint
cd ./bigint
cargo add num ibig chrono

阶乘测试和比较

第一种阶乘实现方式

如上一步所示，我们使用的都是最新版本。下面，我们进行阶乘编码的实现，采用两种方式编写。先看第一种：

use chrono::prelude::*;
use ibig::prelude::*;
use num::bigint::{BigInt, ToBigInt};

fn factorial_num1(x: u32) -> BigInt {
    if let Some(mut factorial) = 1.to_bigint() {
        for i in 1..(x + 1) {
            factorial = factorial * i;
        }
        factorial
    } else {
        panic!("阶乘计算失败");
    }
}

fn factorial_ibig1(x: u32) -> UBig {
    if let Some(mut factorial) = Some(UBig::from(1 as u16)) {
        for i in 1..(x + 1) {
            factorial = factorial * UBig::from(i);
        }
        factorial
    } else {
        panic!("阶乘计算失败");
    }
}

fn main() {
    let n: u32 = 100;

    // num crate 大数计算
    let start_num: DateTime<Local> = Local::now();
    println!("{}! 阶乘，num crate 计算：{:#x}", n, factorial_num1(n));

    let end_num: DateTime<Local> = Local::now();
    let time_num = end_num - start_num;

    println!("{:?}", &time_num);

    // ibig-rs crate 大数计算
    let start_ibig: DateTime<Local> = Local::now();
    println!("{}! 阶乘，ibig crate 计算：{:#x}", n, factorial_ibig1(n));

    let end_ibig: DateTime<Local> = Local::now();
    let time_ibig = end_ibig - start_ibig;

    println!("{:?}", &time_ibig);

    // ibig-rs 是否更快？
    println!("ibig-rs 快了这么多：{:#?}", time_num - time_ibig);
}

我们以发布模式命令 cargo run --release 执行计算，返回结果大抵如下所示（secs 正值时表示 num 慢，否则快）：

cargo run --release

100! 阶乘，num crate 计算：0x1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000
Duration { secs: 0, nanos: 1093700 }

100! 阶乘，ibig crate 计算：0x1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000
Duration { secs: 0, nanos: 343900 }

ibig-rs 快了这么多：Duration {
    secs: 0,
    nanos: 749800,
}

因为 100 以上的阶乘中，计算结果非常大，非常占页面空间，所以本文页面就不做结果展示。如果感兴趣，请你通过修改 n 值，进行测试。

笔者的测试结果，在 1000 以下的阶乘中，ibig 确实是快了一些，但没有超过 1 秒。在 10000 时，互有领先，总体来说 num 还是性能占优，和 ibig 相比大约 7:3 的优势。当 100000 时，num 会快到 4 秒左右；大于 100000 及以后，运行很慢，笔者只跑了一次，测试结果不具实际意义。

第二种阶乘实现方式

编码方式的不同，对于性能也有一定的影响，所以细读 ibig 的文档后，进行了第二种阶乘实现：

use chrono::prelude::*;
use ibig::prelude::*;
use num::bigint::{BigInt, ToBigInt};

fn factorial_num2(a: u32, b: u32) -> BigInt {
    if b == a + 1 {
        a.to_bigint().unwrap()
    } else {
        let mid = a + (b - a) / 2;
        factorial_num2(a, mid) * factorial_num2(mid, b)
    }
}

fn factorial_ibig2(a: u32, b: u32) -> UBig {
    if b == a + 1 {
        UBig::from(a)
    } else {
        let mid = a + (b - a) / 2;
        factorial_ibig2(a, mid) * factorial_ibig2(mid, b)
    }
}

fn main() {
    let n: u32 = 100000;

    // num crate 大数计算
    let start_num: DateTime<Local> = Local::now();
    println!(
        "{}! 阶乘，num crate 计算：{:#x}",
        n,
        factorial_num2(1, n + 1)
    );

    let end_num: DateTime<Local> = Local::now();
    let time_num = end_num - start_num;

    println!("{:?}", &time_num);

    // // ibig-rs crate 大数计算
    let start_ibig: DateTime<Local> = Local::now();
    println!(
        "{}! 阶乘，ibig crate 计算：{:#x}",
        n,
        factorial_ibig2(1, n + 1)
    );

    let end_ibig: DateTime<Local> = Local::now();
    let time_ibig = end_ibig - start_ibig;

    println!("{:?}", &time_ibig);

    // ibig-rs 是否更快？
    println!("ibig-rs 快了这么多：{:#?}", time_num - time_ibig);
}

我们同样以发布模式命令 cargo run --release 执行计算，返回结果大抵和第一种方式类同。

但是性能比较，有了变化。在 10000 以下时，ibig 同样是占优的。在 10000 这个阶乘层次，第 1、2 个 10 次都是 5:5，第 3 个 10 次 num 快了一次。100000 及以上，等待时间过长，笔者只跑了一次，测试结果不具实际意义。

所以，目前所使用的 crate num 暂时还是不考虑替换了。

ibig 官方的基准测试

最后，附上 ibig 官方的基准测试值：每个基准测试运行 5 次，每次重复计算至少 10 秒，结果使用中位数运行。

正如前文笔者所述，代码的不同，平台的不同等，测试性能差别有可能也很大。所以这个基准测试结果，仅能参考。所谓实践出真知，还需要自己实际使用后，才晓得是否合适。

谢谢您的阅读。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-25，如有侵权请联系 cloudcommunity@tencent.com 删除

腾讯云测试服务

rust

本文分享自 Rust 生态与实践微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

腾讯云测试服务

rust

登录后参与评论

0 条评论

热度