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 {
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 {
writeln!(out, "\t:{}", i)?;
}
context.eliminate_digit(d);
}
let m = n % 10;
if m != 0 {
for _ in m..10 {
write!(out, " ")?;
}
writeln!(out, "\t:{}", 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();
}