-// xfail-test
+// The Computer Language Benchmarks Game
+// http://benchmarksgame.alioth.debian.org/
+//
+// contributed by the Rust Project Developers
+
+// Copyright (c) 2013-2014 The Rust Project Developers
+//
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions
+// are met:
+//
+// - Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//
+// - Redistributions in binary form must reproduce the above copyright
+// notice, this list of conditions and the following disclaimer in
+// the documentation and/or other materials provided with the
+// distribution.
+//
+// - Neither the name of "The Computer Language Benchmarks Game" nor
+// the name of "The Computer Language Shootout Benchmarks" nor the
+// names of its contributors may be used to endorse or promote
+// products derived from this software without specific prior
+// written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+// COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+// OF THE POSSIBILITY OF SUCH DAMAGE.
+
+extern crate num;
-use std::cast::transmute;
use std::from_str::FromStr;
-use std::libc::{STDOUT_FILENO, c_char, c_int, c_uint, c_void, fdopen, fputc};
-use std::libc::{fputs};
-use std::ptr::null;
-
-struct mpz_t {
- _mp_alloc: c_int,
- _mp_size: c_int,
- _mp_limb_t: *c_void,
-}
-
-impl mpz_t {
- fn new() -> mpz_t {
- mpz_t {
- _mp_alloc: 0,
- _mp_size: 0,
- _mp_limb_t: null(),
- }
- }
-}
-
-#[link_args="-lgmp"]
-extern {
- #[link_name="__gmpz_add"]
- fn mpz_add(x: *mpz_t, y: *mpz_t, z: *mpz_t);
- #[link_name="__gmpz_cmp"]
- fn mpz_cmp(x: *mpz_t, y: *mpz_t) -> c_int;
- #[link_name="__gmpz_fdiv_qr"]
- fn mpz_fdiv_qr(a: *mpz_t, b: *mpz_t, c: *mpz_t, d: *mpz_t);
- #[link_name="__gmpz_get_ui"]
- fn mpz_get_ui(x: *mpz_t) -> c_uint;
- #[link_name="__gmpz_init"]
- fn mpz_init(x: *mpz_t);
- #[link_name="__gmpz_init_set_ui"]
- fn mpz_init_set_ui(x: *mpz_t, y: c_uint);
- #[link_name="__gmpz_mul_2exp"]
- fn mpz_mul_2exp(x: *mpz_t, y: *mpz_t, z: c_uint);
- #[link_name="__gmpz_mul_ui"]
- fn mpz_mul_ui(x: *mpz_t, y: *mpz_t, z: c_uint);
- #[link_name="__gmpz_submul_ui"]
- fn mpz_submul_ui(x: *mpz_t, y: *mpz_t, z: c_uint);
-}
+use std::num::One;
+use std::num::Zero;
+use std::num::FromPrimitive;
+use num::Integer;
+use num::bigint::BigInt;
struct Context {
- numer: mpz_t,
- accum: mpz_t,
- denom: mpz_t,
- tmp1: mpz_t,
- tmp2: mpz_t,
+ numer: BigInt,
+ accum: BigInt,
+ denom: BigInt,
}
impl Context {
fn new() -> Context {
- unsafe {
- let mut result = Context {
- numer: mpz_t::new(),
- accum: mpz_t::new(),
- denom: mpz_t::new(),
- tmp1: mpz_t::new(),
- tmp2: mpz_t::new(),
- };
- mpz_init(&result.tmp1);
- mpz_init(&result.tmp2);
- mpz_init_set_ui(&result.numer, 1);
- mpz_init_set_ui(&result.accum, 0);
- mpz_init_set_ui(&result.denom, 1);
- result
+ Context {
+ numer: One::one(),
+ accum: Zero::zero(),
+ denom: One::one(),
}
}
- fn extract_digit(&mut self) -> i32 {
- unsafe {
- if mpz_cmp(&self.numer, &self.accum) > 0 {
- return -1;
- }
-
- // Compute (numer * 3 + accum) / denom
- mpz_mul_2exp(&self.tmp1, &self.numer, 1);
- mpz_add(&self.tmp1, &self.tmp1, &self.numer);
- mpz_add(&self.tmp1, &self.tmp1, &self.accum);
- mpz_fdiv_qr(&self.tmp1, &self.tmp2, &self.tmp1, &self.denom);
-
- // Now, if (numer * 4 + accum) % denom...
- mpz_add(&self.tmp2, &self.tmp2, &self.numer);
-
- // ... is normalized, then the two divisions have the same result.
- if mpz_cmp(&self.tmp2, &self.denom) >= 0 {
- return -1;
- }
-
- mpz_get_ui(&self.tmp1) as i32
- }
+ fn from_int(i: int) -> BigInt {
+ FromPrimitive::from_int(i).unwrap()
}
- fn next_term(&mut self, k: u32) {
- unsafe {
- let y2 = k*2 + 1;
+ fn extract_digit(&self) -> int {
+ if self.numer > self.accum {return -1;}
+ let (q, r) =
+ (self.numer * Context::from_int(3) + self.accum)
+ .div_rem(&self.denom);
+ if r + self.numer >= self.denom {return -1;}
+ q.to_int().unwrap()
+ }
- mpz_mul_2exp(&self.tmp1, &self.numer, 1);
- mpz_add(&self.accum, &self.accum, &self.tmp1);
- mpz_mul_ui(&self.accum, &self.accum, y2);
- mpz_mul_ui(&self.numer, &self.numer, k);
- mpz_mul_ui(&self.denom, &self.denom, y2);
- }
+ fn next_term(&mut self, k: int) {
+ let y2 = Context::from_int(k * 2 + 1);
+ self.accum = (self.accum + (self.numer << 1)) * y2;
+ self.numer = self.numer * Context::from_int(k);
+ self.denom = self.denom * y2;
}
- fn eliminate_digit(&mut self, d: u32) {
- unsafe {
- mpz_submul_ui(&self.accum, &self.denom, d);
- mpz_mul_ui(&self.accum, &self.accum, 10);
- mpz_mul_ui(&self.numer, &self.numer, 10);
- }
+ fn eliminate_digit(&mut self, d: int) {
+ let d = Context::from_int(d);
+ let ten = Context::from_int(10);
+ self.accum = (self.accum - self.denom * d) * ten;
+ self.numer = self.numer * ten;
}
}
-fn pidigits(n: u32) {
- unsafe {
- let mode = "w";
- let stdout = fdopen(STDOUT_FILENO as c_int, transmute(&mode[0]));
+fn pidigits(n: int) {
+ let mut k = 0;
+ let mut context = Context::new();
- let mut d: i32;
- let mut i: u32 = 0, k: u32 = 0, m: u32;
-
- let mut context = Context::new();
+ for i in range(1, n + 1) {
+ let mut d;
loop {
- loop {
- k += 1;
- context.next_term(k);
- d = context.extract_digit();
- if d != -1 {
- break;
- }
- }
+ k += 1;
+ context.next_term(k);
+ d = context.extract_digit();
+ if d != -1 {break;}
+ }
- fputc((d as c_int) + ('0' as c_int), stdout);
+ print!("{}", d);
+ if i % 10 == 0 {print!("\t:{}\n", i);}
- i += 1;
- m = i % 10;
- if m == 0 {
- let res = fmt!("\t:%d\n", i as int);
- fputs(transmute(&res[0]), stdout);
- }
- if i >= n {
- break;
- }
- context.eliminate_digit(d as u32);
- }
+ context.eliminate_digit(d);
+ }
- if m != 0 {
- m = 10 - m;
- while m != 0 {
- m -= 1;
- fputc(' ' as c_int, stdout);
- }
- let res = fmt!("\t:%d\n", i as int);
- fputs(transmute(&res[0]), stdout);
- }
+ let m = n % 10;
+ if m != 0 {
+ for _ in range(m, 10) { print!(" "); }
+ print!("\t:{}\n", n);
}
}
fn main() {
- let n: u32 = FromStr::from_str(os::args()[1]).get();
+ let args = std::os::args();
+ let args = args.as_slice();
+ let n = if args.len() < 2 {
+ 512
+ } else {
+ FromStr::from_str(args[1].as_slice()).unwrap()
+ };
pidigits(n);
}
projects / rust.git / blobdiff