summaryrefslogtreecommitdiffstats
path: root/third_party/rust/num-bigint/benches
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/num-bigint/benches')
-rw-r--r--third_party/rust/num-bigint/benches/bigint.rs368
-rw-r--r--third_party/rust/num-bigint/benches/factorial.rs44
-rw-r--r--third_party/rust/num-bigint/benches/gcd.rs86
-rw-r--r--third_party/rust/num-bigint/benches/roots.rs176
-rw-r--r--third_party/rust/num-bigint/benches/shootout-pidigits.rs142
5 files changed, 816 insertions, 0 deletions
diff --git a/third_party/rust/num-bigint/benches/bigint.rs b/third_party/rust/num-bigint/benches/bigint.rs
new file mode 100644
index 0000000000..bc0875d8f6
--- /dev/null
+++ b/third_party/rust/num-bigint/benches/bigint.rs
@@ -0,0 +1,368 @@
+#![feature(test)]
+#![cfg(feature = "rand")]
+
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+extern crate rand;
+extern crate test;
+
+use num_bigint::{BigInt, BigUint, RandBigInt};
+use num_traits::{FromPrimitive, Num, One, Pow, Zero};
+use rand::{SeedableRng, StdRng};
+use std::mem::replace;
+use test::Bencher;
+
+fn get_rng() -> StdRng {
+ let mut seed = [0; 32];
+ for i in 1..32 {
+ seed[usize::from(i)] = i;
+ }
+ SeedableRng::from_seed(seed)
+}
+
+fn multiply_bench(b: &mut Bencher, xbits: usize, ybits: usize) {
+ let mut rng = get_rng();
+ let x = rng.gen_bigint(xbits);
+ let y = rng.gen_bigint(ybits);
+
+ b.iter(|| &x * &y);
+}
+
+fn divide_bench(b: &mut Bencher, xbits: usize, ybits: usize) {
+ let mut rng = get_rng();
+ let x = rng.gen_bigint(xbits);
+ let y = rng.gen_bigint(ybits);
+
+ b.iter(|| &x / &y);
+}
+
+fn remainder_bench(b: &mut Bencher, xbits: usize, ybits: usize) {
+ let mut rng = get_rng();
+ let x = rng.gen_bigint(xbits);
+ let y = rng.gen_bigint(ybits);
+
+ b.iter(|| &x % &y);
+}
+
+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
+}
+
+/// Compute Fibonacci numbers
+fn fib(n: usize) -> BigUint {
+ let mut f0: BigUint = Zero::zero();
+ let mut f1: BigUint = One::one();
+ for _ in 0..n {
+ let f2 = f0 + &f1;
+ f0 = replace(&mut f1, f2);
+ }
+ f0
+}
+
+/// Compute Fibonacci numbers with two ops per iteration
+/// (add and subtract, like issue #200)
+fn fib2(n: usize) -> BigUint {
+ let mut f0: BigUint = Zero::zero();
+ let mut f1: BigUint = One::one();
+ for _ in 0..n {
+ f1 = f1 + &f0;
+ f0 = &f1 - f0;
+ }
+ f0
+}
+
+#[bench]
+fn multiply_0(b: &mut Bencher) {
+ multiply_bench(b, 1 << 8, 1 << 8);
+}
+
+#[bench]
+fn multiply_1(b: &mut Bencher) {
+ multiply_bench(b, 1 << 8, 1 << 16);
+}
+
+#[bench]
+fn multiply_2(b: &mut Bencher) {
+ multiply_bench(b, 1 << 16, 1 << 16);
+}
+
+#[bench]
+fn multiply_3(b: &mut Bencher) {
+ multiply_bench(b, 1 << 16, 1 << 17);
+}
+
+#[bench]
+fn divide_0(b: &mut Bencher) {
+ divide_bench(b, 1 << 8, 1 << 6);
+}
+
+#[bench]
+fn divide_1(b: &mut Bencher) {
+ divide_bench(b, 1 << 12, 1 << 8);
+}
+
+#[bench]
+fn divide_2(b: &mut Bencher) {
+ divide_bench(b, 1 << 16, 1 << 12);
+}
+
+#[bench]
+fn remainder_0(b: &mut Bencher) {
+ remainder_bench(b, 1 << 8, 1 << 6);
+}
+
+#[bench]
+fn remainder_1(b: &mut Bencher) {
+ remainder_bench(b, 1 << 12, 1 << 8);
+}
+
+#[bench]
+fn remainder_2(b: &mut Bencher) {
+ remainder_bench(b, 1 << 16, 1 << 12);
+}
+
+#[bench]
+fn factorial_100(b: &mut Bencher) {
+ b.iter(|| factorial(100));
+}
+
+#[bench]
+fn fib_100(b: &mut Bencher) {
+ b.iter(|| fib(100));
+}
+
+#[bench]
+fn fib_1000(b: &mut Bencher) {
+ b.iter(|| fib(1000));
+}
+
+#[bench]
+fn fib_10000(b: &mut Bencher) {
+ b.iter(|| fib(10000));
+}
+
+#[bench]
+fn fib2_100(b: &mut Bencher) {
+ b.iter(|| fib2(100));
+}
+
+#[bench]
+fn fib2_1000(b: &mut Bencher) {
+ b.iter(|| fib2(1000));
+}
+
+#[bench]
+fn fib2_10000(b: &mut Bencher) {
+ b.iter(|| fib2(10000));
+}
+
+#[bench]
+fn fac_to_string(b: &mut Bencher) {
+ let fac = factorial(100);
+ b.iter(|| fac.to_string());
+}
+
+#[bench]
+fn fib_to_string(b: &mut Bencher) {
+ let fib = fib(100);
+ b.iter(|| fib.to_string());
+}
+
+fn to_str_radix_bench(b: &mut Bencher, radix: u32) {
+ let mut rng = get_rng();
+ let x = rng.gen_bigint(1009);
+ b.iter(|| x.to_str_radix(radix));
+}
+
+#[bench]
+fn to_str_radix_02(b: &mut Bencher) {
+ to_str_radix_bench(b, 2);
+}
+
+#[bench]
+fn to_str_radix_08(b: &mut Bencher) {
+ to_str_radix_bench(b, 8);
+}
+
+#[bench]
+fn to_str_radix_10(b: &mut Bencher) {
+ to_str_radix_bench(b, 10);
+}
+
+#[bench]
+fn to_str_radix_16(b: &mut Bencher) {
+ to_str_radix_bench(b, 16);
+}
+
+#[bench]
+fn to_str_radix_36(b: &mut Bencher) {
+ to_str_radix_bench(b, 36);
+}
+
+fn from_str_radix_bench(b: &mut Bencher, radix: u32) {
+ let mut rng = get_rng();
+ let x = rng.gen_bigint(1009);
+ let s = x.to_str_radix(radix);
+ assert_eq!(x, BigInt::from_str_radix(&s, radix).unwrap());
+ b.iter(|| BigInt::from_str_radix(&s, radix));
+}
+
+#[bench]
+fn from_str_radix_02(b: &mut Bencher) {
+ from_str_radix_bench(b, 2);
+}
+
+#[bench]
+fn from_str_radix_08(b: &mut Bencher) {
+ from_str_radix_bench(b, 8);
+}
+
+#[bench]
+fn from_str_radix_10(b: &mut Bencher) {
+ from_str_radix_bench(b, 10);
+}
+
+#[bench]
+fn from_str_radix_16(b: &mut Bencher) {
+ from_str_radix_bench(b, 16);
+}
+
+#[bench]
+fn from_str_radix_36(b: &mut Bencher) {
+ from_str_radix_bench(b, 36);
+}
+
+fn rand_bench(b: &mut Bencher, bits: usize) {
+ let mut rng = get_rng();
+
+ b.iter(|| rng.gen_bigint(bits));
+}
+
+#[bench]
+fn rand_64(b: &mut Bencher) {
+ rand_bench(b, 1 << 6);
+}
+
+#[bench]
+fn rand_256(b: &mut Bencher) {
+ rand_bench(b, 1 << 8);
+}
+
+#[bench]
+fn rand_1009(b: &mut Bencher) {
+ rand_bench(b, 1009);
+}
+
+#[bench]
+fn rand_2048(b: &mut Bencher) {
+ rand_bench(b, 1 << 11);
+}
+
+#[bench]
+fn rand_4096(b: &mut Bencher) {
+ rand_bench(b, 1 << 12);
+}
+
+#[bench]
+fn rand_8192(b: &mut Bencher) {
+ rand_bench(b, 1 << 13);
+}
+
+#[bench]
+fn rand_65536(b: &mut Bencher) {
+ rand_bench(b, 1 << 16);
+}
+
+#[bench]
+fn rand_131072(b: &mut Bencher) {
+ rand_bench(b, 1 << 17);
+}
+
+#[bench]
+fn shl(b: &mut Bencher) {
+ let n = BigUint::one() << 1000;
+ b.iter(|| {
+ let mut m = n.clone();
+ for i in 0..50 {
+ m = m << i;
+ }
+ })
+}
+
+#[bench]
+fn shr(b: &mut Bencher) {
+ let n = BigUint::one() << 2000;
+ b.iter(|| {
+ let mut m = n.clone();
+ for i in 0..50 {
+ m = m >> i;
+ }
+ })
+}
+
+#[bench]
+fn hash(b: &mut Bencher) {
+ use std::collections::HashSet;
+ let mut rng = get_rng();
+ let v: Vec<BigInt> = (1000..2000).map(|bits| rng.gen_bigint(bits)).collect();
+ b.iter(|| {
+ let h: HashSet<&BigInt> = v.iter().collect();
+ assert_eq!(h.len(), v.len());
+ });
+}
+
+#[bench]
+fn pow_bench(b: &mut Bencher) {
+ b.iter(|| {
+ let upper = 100_usize;
+ for i in 2..upper + 1 {
+ for j in 2..upper + 1 {
+ let i_big = BigUint::from_usize(i).unwrap();
+ i_big.pow(j);
+ }
+ }
+ });
+}
+
+/// This modulus is the prime from the 2048-bit MODP DH group:
+/// https://tools.ietf.org/html/rfc3526#section-3
+const RFC3526_2048BIT_MODP_GROUP: &'static str =
+ "\
+ FFFFFFFF_FFFFFFFF_C90FDAA2_2168C234_C4C6628B_80DC1CD1\
+ 29024E08_8A67CC74_020BBEA6_3B139B22_514A0879_8E3404DD\
+ EF9519B3_CD3A431B_302B0A6D_F25F1437_4FE1356D_6D51C245\
+ E485B576_625E7EC6_F44C42E9_A637ED6B_0BFF5CB6_F406B7ED\
+ EE386BFB_5A899FA5_AE9F2411_7C4B1FE6_49286651_ECE45B3D\
+ C2007CB8_A163BF05_98DA4836_1C55D39A_69163FA8_FD24CF5F\
+ 83655D23_DCA3AD96_1C62F356_208552BB_9ED52907_7096966D\
+ 670C354E_4ABC9804_F1746C08_CA18217C_32905E46_2E36CE3B\
+ E39E772C_180E8603_9B2783A2_EC07A28F_B5C55DF0_6F4C52C9\
+ DE2BCBF6_95581718_3995497C_EA956AE5_15D22618_98FA0510\
+ 15728E5A_8AACAA68_FFFFFFFF_FFFFFFFF";
+
+#[bench]
+fn modpow(b: &mut Bencher) {
+ let mut rng = get_rng();
+ let base = rng.gen_biguint(2048);
+ let e = rng.gen_biguint(2048);
+ let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap();
+
+ b.iter(|| base.modpow(&e, &m));
+}
+
+#[bench]
+fn modpow_even(b: &mut Bencher) {
+ let mut rng = get_rng();
+ let base = rng.gen_biguint(2048);
+ let e = rng.gen_biguint(2048);
+ // Make the modulus even, so monty (base-2^32) doesn't apply.
+ let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap() - 1u32;
+
+ b.iter(|| base.modpow(&e, &m));
+}
diff --git a/third_party/rust/num-bigint/benches/factorial.rs b/third_party/rust/num-bigint/benches/factorial.rs
new file mode 100644
index 0000000000..4392df8319
--- /dev/null
+++ b/third_party/rust/num-bigint/benches/factorial.rs
@@ -0,0 +1,44 @@
+#![feature(test)]
+
+extern crate num_bigint;
+extern crate num_traits;
+extern crate test;
+
+use num_bigint::BigUint;
+use num_traits::One;
+use std::ops::{Div, Mul};
+use test::Bencher;
+
+#[bench]
+fn factorial_mul_biguint(b: &mut Bencher) {
+ b.iter(|| {
+ (1u32..1000)
+ .map(BigUint::from)
+ .fold(BigUint::one(), Mul::mul)
+ });
+}
+
+#[bench]
+fn factorial_mul_u32(b: &mut Bencher) {
+ b.iter(|| (1u32..1000).fold(BigUint::one(), Mul::mul));
+}
+
+// The division test is inspired by this blog comparison:
+// <https://tiehuis.github.io/big-integers-in-zig#division-test-single-limb>
+
+#[bench]
+fn factorial_div_biguint(b: &mut Bencher) {
+ let n: BigUint = (1u32..1000).fold(BigUint::one(), Mul::mul);
+ b.iter(|| {
+ (1u32..1000)
+ .rev()
+ .map(BigUint::from)
+ .fold(n.clone(), Div::div)
+ });
+}
+
+#[bench]
+fn factorial_div_u32(b: &mut Bencher) {
+ let n: BigUint = (1u32..1000).fold(BigUint::one(), Mul::mul);
+ b.iter(|| (1u32..1000).rev().fold(n.clone(), Div::div));
+}
diff --git a/third_party/rust/num-bigint/benches/gcd.rs b/third_party/rust/num-bigint/benches/gcd.rs
new file mode 100644
index 0000000000..5fe5260ddf
--- /dev/null
+++ b/third_party/rust/num-bigint/benches/gcd.rs
@@ -0,0 +1,86 @@
+#![feature(test)]
+#![cfg(feature = "rand")]
+
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+extern crate rand;
+extern crate test;
+
+use num_bigint::{BigUint, RandBigInt};
+use num_integer::Integer;
+use num_traits::Zero;
+use rand::{SeedableRng, StdRng};
+use test::Bencher;
+
+fn get_rng() -> StdRng {
+ let mut seed = [0; 32];
+ for i in 1..32 {
+ seed[usize::from(i)] = i;
+ }
+ SeedableRng::from_seed(seed)
+}
+
+fn bench(b: &mut Bencher, bits: usize, gcd: fn(&BigUint, &BigUint) -> BigUint) {
+ let mut rng = get_rng();
+ let x = rng.gen_biguint(bits);
+ let y = rng.gen_biguint(bits);
+
+ assert_eq!(euclid(&x, &y), x.gcd(&y));
+
+ b.iter(|| gcd(&x, &y));
+}
+
+fn euclid(x: &BigUint, y: &BigUint) -> BigUint {
+ // Use Euclid's algorithm
+ let mut m = x.clone();
+ let mut n = y.clone();
+ while !m.is_zero() {
+ let temp = m;
+ m = n % &temp;
+ n = temp;
+ }
+ return n;
+}
+
+#[bench]
+fn gcd_euclid_0064(b: &mut Bencher) {
+ bench(b, 64, euclid);
+}
+
+#[bench]
+fn gcd_euclid_0256(b: &mut Bencher) {
+ bench(b, 256, euclid);
+}
+
+#[bench]
+fn gcd_euclid_1024(b: &mut Bencher) {
+ bench(b, 1024, euclid);
+}
+
+#[bench]
+fn gcd_euclid_4096(b: &mut Bencher) {
+ bench(b, 4096, euclid);
+}
+
+// Integer for BigUint now uses Stein for gcd
+
+#[bench]
+fn gcd_stein_0064(b: &mut Bencher) {
+ bench(b, 64, BigUint::gcd);
+}
+
+#[bench]
+fn gcd_stein_0256(b: &mut Bencher) {
+ bench(b, 256, BigUint::gcd);
+}
+
+#[bench]
+fn gcd_stein_1024(b: &mut Bencher) {
+ bench(b, 1024, BigUint::gcd);
+}
+
+#[bench]
+fn gcd_stein_4096(b: &mut Bencher) {
+ bench(b, 4096, BigUint::gcd);
+}
diff --git a/third_party/rust/num-bigint/benches/roots.rs b/third_party/rust/num-bigint/benches/roots.rs
new file mode 100644
index 0000000000..51e67d9f3d
--- /dev/null
+++ b/third_party/rust/num-bigint/benches/roots.rs
@@ -0,0 +1,176 @@
+#![feature(test)]
+#![cfg(feature = "rand")]
+
+extern crate num_bigint;
+extern crate num_traits;
+extern crate rand;
+extern crate test;
+
+use num_bigint::{BigUint, RandBigInt};
+use num_traits::Pow;
+use rand::{SeedableRng, StdRng};
+use test::Bencher;
+
+// The `big64` cases demonstrate the speed of cases where the value
+// can be converted to a `u64` primitive for faster calculation.
+//
+// The `big1k` cases demonstrate those that can convert to `f64` for
+// a better initial guess of the actual value.
+//
+// The `big2k` and `big4k` cases are too big for `f64`, and use a simpler guess.
+
+fn get_rng() -> StdRng {
+ let mut seed = [0; 32];
+ for i in 1..32 {
+ seed[usize::from(i)] = i;
+ }
+ SeedableRng::from_seed(seed)
+}
+
+fn check(x: &BigUint, n: u32) {
+ let root = x.nth_root(n);
+ if n == 2 {
+ assert_eq!(root, x.sqrt())
+ } else if n == 3 {
+ assert_eq!(root, x.cbrt())
+ }
+
+ let lo = root.pow(n);
+ assert!(lo <= *x);
+ assert_eq!(lo.nth_root(n), root);
+ assert_eq!((&lo - 1u32).nth_root(n), &root - 1u32);
+
+ let hi = (&root + 1u32).pow(n);
+ assert!(hi > *x);
+ assert_eq!(hi.nth_root(n), &root + 1u32);
+ assert_eq!((&hi - 1u32).nth_root(n), root);
+}
+
+fn bench_sqrt(b: &mut Bencher, bits: usize) {
+ let x = get_rng().gen_biguint(bits);
+ eprintln!("bench_sqrt({})", x);
+
+ check(&x, 2);
+ b.iter(|| x.sqrt());
+}
+
+#[bench]
+fn big64_sqrt(b: &mut Bencher) {
+ bench_sqrt(b, 64);
+}
+
+#[bench]
+fn big1k_sqrt(b: &mut Bencher) {
+ bench_sqrt(b, 1024);
+}
+
+#[bench]
+fn big2k_sqrt(b: &mut Bencher) {
+ bench_sqrt(b, 2048);
+}
+
+#[bench]
+fn big4k_sqrt(b: &mut Bencher) {
+ bench_sqrt(b, 4096);
+}
+
+fn bench_cbrt(b: &mut Bencher, bits: usize) {
+ let x = get_rng().gen_biguint(bits);
+ eprintln!("bench_cbrt({})", x);
+
+ check(&x, 3);
+ b.iter(|| x.cbrt());
+}
+
+#[bench]
+fn big64_cbrt(b: &mut Bencher) {
+ bench_cbrt(b, 64);
+}
+
+#[bench]
+fn big1k_cbrt(b: &mut Bencher) {
+ bench_cbrt(b, 1024);
+}
+
+#[bench]
+fn big2k_cbrt(b: &mut Bencher) {
+ bench_cbrt(b, 2048);
+}
+
+#[bench]
+fn big4k_cbrt(b: &mut Bencher) {
+ bench_cbrt(b, 4096);
+}
+
+fn bench_nth_root(b: &mut Bencher, bits: usize, n: u32) {
+ let x = get_rng().gen_biguint(bits);
+ eprintln!("bench_{}th_root({})", n, x);
+
+ check(&x, n);
+ b.iter(|| x.nth_root(n));
+}
+
+#[bench]
+fn big64_nth_10(b: &mut Bencher) {
+ bench_nth_root(b, 64, 10);
+}
+
+#[bench]
+fn big1k_nth_10(b: &mut Bencher) {
+ bench_nth_root(b, 1024, 10);
+}
+
+#[bench]
+fn big1k_nth_100(b: &mut Bencher) {
+ bench_nth_root(b, 1024, 100);
+}
+
+#[bench]
+fn big1k_nth_1000(b: &mut Bencher) {
+ bench_nth_root(b, 1024, 1000);
+}
+
+#[bench]
+fn big1k_nth_10000(b: &mut Bencher) {
+ bench_nth_root(b, 1024, 10000);
+}
+
+#[bench]
+fn big2k_nth_10(b: &mut Bencher) {
+ bench_nth_root(b, 2048, 10);
+}
+
+#[bench]
+fn big2k_nth_100(b: &mut Bencher) {
+ bench_nth_root(b, 2048, 100);
+}
+
+#[bench]
+fn big2k_nth_1000(b: &mut Bencher) {
+ bench_nth_root(b, 2048, 1000);
+}
+
+#[bench]
+fn big2k_nth_10000(b: &mut Bencher) {
+ bench_nth_root(b, 2048, 10000);
+}
+
+#[bench]
+fn big4k_nth_10(b: &mut Bencher) {
+ bench_nth_root(b, 4096, 10);
+}
+
+#[bench]
+fn big4k_nth_100(b: &mut Bencher) {
+ bench_nth_root(b, 4096, 100);
+}
+
+#[bench]
+fn big4k_nth_1000(b: &mut Bencher) {
+ bench_nth_root(b, 4096, 1000);
+}
+
+#[bench]
+fn big4k_nth_10000(b: &mut Bencher) {
+ bench_nth_root(b, 4096, 10000);
+}
diff --git a/third_party/rust/num-bigint/benches/shootout-pidigits.rs b/third_party/rust/num-bigint/benches/shootout-pidigits.rs
new file mode 100644
index 0000000000..f90a697357
--- /dev/null
+++ b/third_party/rust/num-bigint/benches/shootout-pidigits.rs
@@ -0,0 +1,142 @@
+// The Computer Language Benchmarks Game
+// http://benchmarksgame.alioth.debian.org/
+//
+// contributed by the Rust Project Developers
+
+// Copyright (c) 2013-2014 The Rust Project Developers
+//
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions
+// are met:
+//
+// - Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//
+// - Redistributions in binary form must reproduce the above copyright
+// notice, this list of conditions and the following disclaimer in
+// the documentation and/or other materials provided with the
+// distribution.
+//
+// - Neither the name of "The Computer Language Benchmarks Game" nor
+// the name of "The Computer Language Shootout Benchmarks" nor the
+// names of its contributors may be used to endorse or promote
+// products derived from this software without specific prior
+// written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+// COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+// OF THE POSSIBILITY OF SUCH DAMAGE.
+
+extern crate num_bigint;
+extern crate num_integer;
+extern crate num_traits;
+
+use std::io;
+use std::str::FromStr;
+
+use num_bigint::BigInt;
+use num_integer::Integer;
+use num_traits::{FromPrimitive, One, ToPrimitive, Zero};
+
+struct Context {
+ numer: BigInt,
+ accum: BigInt,
+ denom: BigInt,
+}
+
+impl Context {
+ fn new() -> Context {
+ Context {
+ numer: One::one(),
+ accum: Zero::zero(),
+ denom: One::one(),
+ }
+ }
+
+ fn from_i32(i: i32) -> BigInt {
+ FromPrimitive::from_i32(i).unwrap()
+ }
+
+ fn extract_digit(&self) -> i32 {
+ if self.numer > self.accum {
+ return -1;
+ }
+ let (q, r) = (&self.numer * Context::from_i32(3) + &self.accum).div_rem(&self.denom);
+ if r + &self.numer >= self.denom {
+ return -1;
+ }
+ q.to_i32().unwrap()
+ }
+
+ fn next_term(&mut self, k: i32) {
+ let y2 = Context::from_i32(k * 2 + 1);
+ self.accum = (&self.accum + (&self.numer << 1)) * &y2;
+ self.numer = &self.numer * Context::from_i32(k);
+ self.denom = &self.denom * y2;
+ }
+
+ fn eliminate_digit(&mut self, d: i32) {
+ let d = Context::from_i32(d);
+ let ten = Context::from_i32(10);
+ self.accum = (&self.accum - &self.denom * d) * &ten;
+ self.numer = &self.numer * ten;
+ }
+}
+
+fn pidigits(n: isize, out: &mut dyn io::Write) -> io::Result<()> {
+ let mut k = 0;
+ let mut context = Context::new();
+
+ for i in 1..(n + 1) {
+ let mut d;
+ loop {
+ k += 1;
+ context.next_term(k);
+ d = context.extract_digit();
+ if d != -1 {
+ break;
+ }
+ }
+
+ write!(out, "{}", d)?;
+ if i % 10 == 0 {
+ write!(out, "\t:{}\n", i)?;
+ }
+
+ context.eliminate_digit(d);
+ }
+
+ let m = n % 10;
+ if m != 0 {
+ for _ in m..10 {
+ write!(out, " ")?;
+ }
+ write!(out, "\t:{}\n", n)?;
+ }
+ Ok(())
+}
+
+const DEFAULT_DIGITS: isize = 512;
+
+fn main() {
+ let args = std::env::args().collect::<Vec<_>>();
+ let n = if args.len() < 2 {
+ DEFAULT_DIGITS
+ } else if args[1] == "--bench" {
+ return pidigits(DEFAULT_DIGITS, &mut std::io::sink()).unwrap();
+ } else {
+ FromStr::from_str(&args[1]).unwrap()
+ };
+ pidigits(n, &mut std::io::stdout()).unwrap();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-27 19:51:23 +0000