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 mod extra;
  12
  13 use std::from_str::FromStr;
  14 use std::num::One;
  15 use std::num::Zero;
  16 use std::num::FromPrimitive;
  17 use extra::bigint::BigInt;
  18
  19 struct Context {
  20     numer: BigInt,
  21     accum: BigInt,
  22     denom: BigInt,
  23 }
  24
  25 impl Context {
  26     fn new() -> Context {
  27         Context {
  28             numer: One::one(),
  29             accum: Zero::zero(),
  30             denom: One::one(),
  31         }
  32     }
  33
  34     fn from_int(i: int) -> BigInt {
  35         FromPrimitive::from_int(i).unwrap()
  36     }
  37
  38     fn extract_digit(&self) -> int {
  39         if self.numer > self.accum {return -1;}
  40         let (q, r) =
  41             (self.numer * Context::from_int(3) + self.accum)
  42             .div_rem(&self.denom);
  43         if r + self.numer >= self.denom {return -1;}
  44         q.to_int().unwrap()
  45     }
  46
  47     fn next_term(&mut self, k: int) {
  48         let y2 = Context::from_int(k * 2 + 1);
  49         self.accum = (self.accum + (self.numer << 1)) * y2;
  50         self.numer = self.numer * Context::from_int(k);
  51         self.denom = self.denom * y2;
  52     }
  53
  54     fn eliminate_digit(&mut self, d: int) {
  55         let d = Context::from_int(d);
  56         let ten = Context::from_int(10);
  57         self.accum = (self.accum - self.denom * d) * ten;
  58         self.numer = self.numer * ten;
  59     }
  60 }
  61
  62 fn pidigits(n: int) {
  63     let mut k = 0;
  64     let mut context = Context::new();
  65
  66     for i in range(1, n + 1) {
  67         let mut d;
  68         loop {
  69             k += 1;
  70             context.next_term(k);
  71             d = context.extract_digit();
  72             if d != -1 {break;}
  73         }
  74
  75         print!("{}", d);
  76         if i % 10 == 0 {print!("\t:{}\n", i);}
  77
  78         context.eliminate_digit(d);
  79     }
  80
  81     let m = n % 10;
  82     if m != 0 {
  83         for _ in range(m, 10) { print!(" "); }
  84         print!("\t:{}\n", n);
  85     }
  86 }
  87
  88 fn main() {
  89     let args = std::os::args();
  90     let n = if args.len() < 2 {
  91         512
  92     } else {
  93         FromStr::from_str(args[1]).unwrap()
  94     };
  95     pidigits(n);
  96 }