src/test/bench/shootout-pidigits.rs

   1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 extern crate num;
  12
  13 use std::from_str::FromStr;
  14 use std::num::One;
  15 use std::num::Zero;
  16 use std::num::FromPrimitive;
  17 use num::Integer;
  18 use num::bigint::BigInt;
  19
  20 struct Context {
  21     numer: BigInt,
  22     accum: BigInt,
  23     denom: BigInt,
  24 }
  25
  26 impl Context {
  27     fn new() -> Context {
  28         Context {
  29             numer: One::one(),
  30             accum: Zero::zero(),
  31             denom: One::one(),
  32         }
  33     }
  34
  35     fn from_int(i: int) -> BigInt {
  36         FromPrimitive::from_int(i).unwrap()
  37     }
  38
  39     fn extract_digit(&self) -> int {
  40         if self.numer > self.accum {return -1;}
  41         let (q, r) =
  42             (self.numer * Context::from_int(3) + self.accum)
  43             .div_rem(&self.denom);
  44         if r + self.numer >= self.denom {return -1;}
  45         q.to_int().unwrap()
  46     }
  47
  48     fn next_term(&mut self, k: int) {
  49         let y2 = Context::from_int(k * 2 + 1);
  50         self.accum = (self.accum + (self.numer << 1)) * y2;
  51         self.numer = self.numer * Context::from_int(k);
  52         self.denom = self.denom * y2;
  53     }
  54
  55     fn eliminate_digit(&mut self, d: int) {
  56         let d = Context::from_int(d);
  57         let ten = Context::from_int(10);
  58         self.accum = (self.accum - self.denom * d) * ten;
  59         self.numer = self.numer * ten;
  60     }
  61 }
  62
  63 fn pidigits(n: int) {
  64     let mut k = 0;
  65     let mut context = Context::new();
  66
  67     for i in range(1, n + 1) {
  68         let mut d;
  69         loop {
  70             k += 1;
  71             context.next_term(k);
  72             d = context.extract_digit();
  73             if d != -1 {break;}
  74         }
  75
  76         print!("{}", d);
  77         if i % 10 == 0 {print!("\t:{}\n", i);}
  78
  79         context.eliminate_digit(d);
  80     }
  81
  82     let m = n % 10;
  83     if m != 0 {
  84         for _ in range(m, 10) { print!(" "); }
  85         print!("\t:{}\n", n);
  86     }
  87 }
  88
  89 fn main() {
  90     let args = std::os::args();
  91     let args = args.as_slice();
  92     let n = if args.len() < 2 {
  93         512
  94     } else {
  95         FromStr::from_str(args[1].as_slice()).unwrap()
  96     };
  97     pidigits(n);
  98 }