src/test/bench/shootout-pidigits.rs

   1 // xfail-test
   2
   3 use std::cast::transmute;
   4 use std::from_str::FromStr;
   5 use std::libc::{STDOUT_FILENO, c_char, c_int, c_uint, c_void, fdopen, fputc};
   6 use std::libc::{fputs};
   7 use std::ptr::null;
   8
   9 struct mpz_t {
  10     _mp_alloc: c_int,
  11     _mp_size: c_int,
  12     _mp_limb_t: *c_void,
  13 }
  14
  15 impl mpz_t {
  16     fn new() -> mpz_t {
  17         mpz_t {
  18             _mp_alloc: 0,
  19             _mp_size: 0,
  20             _mp_limb_t: null(),
  21         }
  22     }
  23 }
  24
  25 #[link_args="-lgmp"]
  26 extern {
  27     #[link_name="__gmpz_add"]
  28     fn mpz_add(x: *mpz_t, y: *mpz_t, z: *mpz_t);
  29     #[link_name="__gmpz_cmp"]
  30     fn mpz_cmp(x: *mpz_t, y: *mpz_t) -> c_int;
  31     #[link_name="__gmpz_fdiv_qr"]
  32     fn mpz_fdiv_qr(a: *mpz_t, b: *mpz_t, c: *mpz_t, d: *mpz_t);
  33     #[link_name="__gmpz_get_ui"]
  34     fn mpz_get_ui(x: *mpz_t) -> c_uint;
  35     #[link_name="__gmpz_init"]
  36     fn mpz_init(x: *mpz_t);
  37     #[link_name="__gmpz_init_set_ui"]
  38     fn mpz_init_set_ui(x: *mpz_t, y: c_uint);
  39     #[link_name="__gmpz_mul_2exp"]
  40     fn mpz_mul_2exp(x: *mpz_t, y: *mpz_t, z: c_uint);
  41     #[link_name="__gmpz_mul_ui"]
  42     fn mpz_mul_ui(x: *mpz_t, y: *mpz_t, z: c_uint);
  43     #[link_name="__gmpz_submul_ui"]
  44     fn mpz_submul_ui(x: *mpz_t, y: *mpz_t, z: c_uint);
  45 }
  46
  47 struct Context {
  48     numer: mpz_t,
  49     accum: mpz_t,
  50     denom: mpz_t,
  51     tmp1: mpz_t,
  52     tmp2: mpz_t,
  53 }
  54
  55 impl Context {
  56     fn new() -> Context {
  57         unsafe {
  58             let mut result = Context {
  59                 numer: mpz_t::new(),
  60                 accum: mpz_t::new(),
  61                 denom: mpz_t::new(),
  62                 tmp1: mpz_t::new(),
  63                 tmp2: mpz_t::new(),
  64             };
  65             mpz_init(&result.tmp1);
  66             mpz_init(&result.tmp2);
  67             mpz_init_set_ui(&result.numer, 1);
  68             mpz_init_set_ui(&result.accum, 0);
  69             mpz_init_set_ui(&result.denom, 1);
  70             result
  71         }
  72     }
  73
  74     fn extract_digit(&mut self) -> i32 {
  75         unsafe {
  76             if mpz_cmp(&self.numer, &self.accum) > 0 {
  77                 return -1;
  78             }
  79
  80             // Compute (numer * 3 + accum) / denom
  81             mpz_mul_2exp(&self.tmp1, &self.numer, 1);
  82             mpz_add(&self.tmp1, &self.tmp1, &self.numer);
  83             mpz_add(&self.tmp1, &self.tmp1, &self.accum);
  84             mpz_fdiv_qr(&self.tmp1, &self.tmp2, &self.tmp1, &self.denom);
  85
  86             // Now, if (numer * 4 + accum) % denom...
  87             mpz_add(&self.tmp2, &self.tmp2, &self.numer);
  88
  89             // ... is normalized, then the two divisions have the same result.
  90             if mpz_cmp(&self.tmp2, &self.denom) >= 0 {
  91                 return -1;
  92             }
  93
  94             mpz_get_ui(&self.tmp1) as i32
  95         }
  96     }
  97
  98     fn next_term(&mut self, k: u32) {
  99         unsafe {
 100             let y2 = k*2 + 1;
 101
 102             mpz_mul_2exp(&self.tmp1, &self.numer, 1);
 103             mpz_add(&self.accum, &self.accum, &self.tmp1);
 104             mpz_mul_ui(&self.accum, &self.accum, y2);
 105             mpz_mul_ui(&self.numer, &self.numer, k);
 106             mpz_mul_ui(&self.denom, &self.denom, y2);
 107         }
 108     }
 109
 110     fn eliminate_digit(&mut self, d: u32) {
 111         unsafe {
 112             mpz_submul_ui(&self.accum, &self.denom, d);
 113             mpz_mul_ui(&self.accum, &self.accum, 10);
 114             mpz_mul_ui(&self.numer, &self.numer, 10);
 115         }
 116     }
 117 }
 118
 119 fn pidigits(n: u32) {
 120     unsafe {
 121         let mode = "w";
 122         let stdout = fdopen(STDOUT_FILENO as c_int, transmute(&mode[0]));
 123
 124         let mut d: i32;
 125         let mut i: u32 = 0, k: u32 = 0, m: u32;
 126
 127         let mut context = Context::new();
 128         loop {
 129             loop {
 130                 k += 1;
 131                 context.next_term(k);
 132                 d = context.extract_digit();
 133                 if d != -1 {
 134                     break;
 135                 }
 136             }
 137
 138             fputc((d as c_int) + ('0' as c_int), stdout);
 139
 140             i += 1;
 141             m = i % 10;
 142             if m == 0 {
 143                 let res = fmt!("\t:%d\n", i as int);
 144                 fputs(transmute(&res[0]), stdout);
 145             }
 146             if i >= n {
 147                 break;
 148             }
 149             context.eliminate_digit(d as u32);
 150         }
 151
 152         if m != 0 {
 153             m = 10 - m;
 154             while m != 0 {
 155                 m -= 1;
 156                 fputc(' ' as c_int, stdout);
 157             }
 158             let res = fmt!("\t:%d\n", i as int);
 159             fputs(transmute(&res[0]), stdout);
 160         }
 161     }
 162 }
 163
 164 fn main() {
 165     let n: u32 = FromStr::from_str(os::args()[1]).get();
 166     pidigits(n);
 167 }