1 // The Computer Language Benchmarks Game
2 // http://benchmarksgame.alioth.debian.org/
3 //
4 // contributed by the Rust Project Developers
5
6 // Copyright (c) 2013-2014 The Rust Project Developers
7 //
8 // All rights reserved.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions
12 // are met:
13 //
14 // - Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // - Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in
19 // the documentation and/or other materials provided with the
20 // distribution.
21 //
22 // - Neither the name of "The Computer Language Benchmarks Game" nor
23 // the name of "The Computer Language Shootout Benchmarks" nor the
24 // names of its contributors may be used to endorse or promote
25 // products derived from this software without specific prior
26 // written permission.
27 //
28 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
31 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
32 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
33 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
34 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
35 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
37 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
38 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
39 // OF THE POSSIBILITY OF SUCH DAMAGE.
40
41 use std::io;
42 use std::str::FromStr;
43
44 use num_bigint::BigInt;
45 use num_integer::Integer;
46 use num_traits::{FromPrimitive, One, ToPrimitive, Zero};
47
48 struct Context {
49 numer: BigInt,
50 accum: BigInt,
51 denom: BigInt,
52 }
53
54 impl Context {
new() -> Context55 fn new() -> Context {
56 Context {
57 numer: One::one(),
58 accum: Zero::zero(),
59 denom: One::one(),
60 }
61 }
62
from_i32(i: i32) -> BigInt63 fn from_i32(i: i32) -> BigInt {
64 FromPrimitive::from_i32(i).unwrap()
65 }
66
extract_digit(&self) -> i3267 fn extract_digit(&self) -> i32 {
68 if self.numer > self.accum {
69 return -1;
70 }
71 let (q, r) = (&self.numer * Context::from_i32(3) + &self.accum).div_rem(&self.denom);
72 if r + &self.numer >= self.denom {
73 return -1;
74 }
75 q.to_i32().unwrap()
76 }
77
next_term(&mut self, k: i32)78 fn next_term(&mut self, k: i32) {
79 let y2 = Context::from_i32(k * 2 + 1);
80 self.accum = (&self.accum + (&self.numer << 1)) * &y2;
81 self.numer = &self.numer * Context::from_i32(k);
82 self.denom = &self.denom * y2;
83 }
84
eliminate_digit(&mut self, d: i32)85 fn eliminate_digit(&mut self, d: i32) {
86 let d = Context::from_i32(d);
87 let ten = Context::from_i32(10);
88 self.accum = (&self.accum - &self.denom * d) * &ten;
89 self.numer = &self.numer * ten;
90 }
91 }
92
pidigits(n: isize, out: &mut dyn io::Write) -> io::Result<()>93 fn pidigits(n: isize, out: &mut dyn io::Write) -> io::Result<()> {
94 let mut k = 0;
95 let mut context = Context::new();
96
97 for i in 1..=n {
98 let mut d;
99 loop {
100 k += 1;
101 context.next_term(k);
102 d = context.extract_digit();
103 if d != -1 {
104 break;
105 }
106 }
107
108 write!(out, "{}", d)?;
109 if i % 10 == 0 {
110 writeln!(out, "\t:{}", i)?;
111 }
112
113 context.eliminate_digit(d);
114 }
115
116 let m = n % 10;
117 if m != 0 {
118 for _ in m..10 {
119 write!(out, " ")?;
120 }
121 writeln!(out, "\t:{}", n)?;
122 }
123 Ok(())
124 }
125
126 const DEFAULT_DIGITS: isize = 512;
127
main()128 fn main() {
129 let args = std::env::args().collect::<Vec<_>>();
130 let n = if args.len() < 2 {
131 DEFAULT_DIGITS
132 } else if args[1] == "--bench" {
133 return pidigits(DEFAULT_DIGITS, &mut std::io::sink()).unwrap();
134 } else {
135 FromStr::from_str(&args[1]).unwrap()
136 };
137 pidigits(n, &mut std::io::stdout()).unwrap();
138 }
139