src/test/bench/shootout-pidigits.rs

   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 extern crate num;
  42
  43 use std::from_str::FromStr;
  44 use std::num::One;
  45 use std::num::Zero;
  46 use std::num::FromPrimitive;
  47 use num::Integer;
  48 use num::bigint::BigInt;
  49
  50 struct Context {
  51     numer: BigInt,
  52     accum: BigInt,
  53     denom: BigInt,
  54 }
  55
  56 impl Context {
  57     fn new() -> Context {
  58         Context {
  59             numer: One::one(),
  60             accum: Zero::zero(),
  61             denom: One::one(),
  62         }
  63     }
  64
  65     fn from_int(i: int) -> BigInt {
  66         FromPrimitive::from_int(i).unwrap()
  67     }
  68
  69     fn extract_digit(&self) -> int {
  70         if self.numer > self.accum {return -1;}
  71         let (q, r) =
  72             (self.numer * Context::from_int(3) + self.accum)
  73             .div_rem(&self.denom);
  74         if r + self.numer >= self.denom {return -1;}
  75         q.to_int().unwrap()
  76     }
  77
  78     fn next_term(&mut self, k: int) {
  79         let y2 = Context::from_int(k * 2 + 1);
  80         self.accum = (self.accum + (self.numer << 1)) * y2;
  81         self.numer = self.numer * Context::from_int(k);
  82         self.denom = self.denom * y2;
  83     }
  84
  85     fn eliminate_digit(&mut self, d: int) {
  86         let d = Context::from_int(d);
  87         let ten = Context::from_int(10);
  88         self.accum = (self.accum - self.denom * d) * ten;
  89         self.numer = self.numer * ten;
  90     }
  91 }
  92
  93 fn pidigits(n: int) {
  94     let mut k = 0;
  95     let mut context = Context::new();
  96
  97     for i in range(1, n + 1) {
  98         let mut d;
  99         loop {
 100             k += 1;
 101             context.next_term(k);
 102             d = context.extract_digit();
 103             if d != -1 {break;}
 104         }
 105
 106         print!("{}", d);
 107         if i % 10 == 0 {print!("\t:{}\n", i);}
 108
 109         context.eliminate_digit(d);
 110     }
 111
 112     let m = n % 10;
 113     if m != 0 {
 114         for _ in range(m, 10) { print!(" "); }
 115         print!("\t:{}\n", n);
 116     }
 117 }
 118
 119 fn main() {
 120     let args = std::os::args();
 121     let args = args.as_slice();
 122     let n = if args.len() < 2 {
 123         512
 124     } else {
 125         FromStr::from_str(args[1].as_slice()).unwrap()
 126     };
 127     pidigits(n);
 128 }