shootout-pidigits.rs 3.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
  1. // The Computer Language Benchmarks Game
  2. // http://benchmarksgame.alioth.debian.org/
  3. //
  4. // contributed by the Rust Project Developers
  5. // Copyright (c) 2013-2014 The Rust Project Developers
  6. //
  7. // All rights reserved.
  8. //
  9. // Redistribution and use in source and binary forms, with or without
  10. // modification, are permitted provided that the following conditions
  11. // are met:
  12. //
  13. // - Redistributions of source code must retain the above copyright
  14. // notice, this list of conditions and the following disclaimer.
  15. //
  16. // - Redistributions in binary form must reproduce the above copyright
  17. // notice, this list of conditions and the following disclaimer in
  18. // the documentation and/or other materials provided with the
  19. // distribution.
  20. //
  21. // - Neither the name of "The Computer Language Benchmarks Game" nor
  22. // the name of "The Computer Language Shootout Benchmarks" nor the
  23. // names of its contributors may be used to endorse or promote
  24. // products derived from this software without specific prior
  25. // written permission.
  26. //
  27. // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  28. // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  29. // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  30. // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  31. // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  32. // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  33. // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  34. // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  35. // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  36. // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  37. // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  38. // OF THE POSSIBILITY OF SUCH DAMAGE.
  39. #![feature(core)]
  40. #![feature(test)]
  41. extern crate num;
  42. extern crate test;
  43. use std::str::FromStr;
  44. use std::num::{FromPrimitive, ToPrimitive};
  45. use test::Bencher;
  46. use num::{BigInt, Integer, One, Zero};
  47. struct Context {
  48. numer: BigInt,
  49. accum: BigInt,
  50. denom: BigInt,
  51. }
  52. impl Context {
  53. fn new() -> Context {
  54. Context {
  55. numer: One::one(),
  56. accum: Zero::zero(),
  57. denom: One::one(),
  58. }
  59. }
  60. fn from_i32(i: i32) -> BigInt {
  61. FromPrimitive::from_i32(i).unwrap()
  62. }
  63. fn extract_digit(&self) -> i32 {
  64. if self.numer > self.accum {return -1;}
  65. let (q, r) =
  66. (&self.numer * Context::from_i32(3) + &self.accum)
  67. .div_rem(&self.denom);
  68. if r + &self.numer >= self.denom {return -1;}
  69. q.to_i32().unwrap()
  70. }
  71. fn next_term(&mut self, k: i32) {
  72. let y2 = Context::from_i32(k * 2 + 1);
  73. self.accum = (&self.accum + (&self.numer << 1)) * &y2;
  74. self.numer = &self.numer * Context::from_i32(k);
  75. self.denom = &self.denom * y2;
  76. }
  77. fn eliminate_digit(&mut self, d: i32) {
  78. let d = Context::from_i32(d);
  79. let ten = Context::from_i32(10);
  80. self.accum = (&self.accum - &self.denom * d) * &ten;
  81. self.numer = &self.numer * ten;
  82. }
  83. }
  84. fn pidigits(n: isize) {
  85. let mut k = 0;
  86. let mut context = Context::new();
  87. for i in (1..(n+1)) {
  88. let mut d;
  89. loop {
  90. k += 1;
  91. context.next_term(k);
  92. d = context.extract_digit();
  93. if d != -1 {break;}
  94. }
  95. print!("{}", d);
  96. if i % 10 == 0 {print!("\t:{}\n", i);}
  97. context.eliminate_digit(d);
  98. }
  99. let m = n % 10;
  100. if m != 0 {
  101. for _ in (m..10) { print!(" "); }
  102. print!("\t:{}\n", n);
  103. }
  104. }
  105. static DEFAULT_DIGITS: isize = 512;
  106. #[bench]
  107. fn use_bencher(b: &mut Bencher) {
  108. b.iter(|| pidigits(DEFAULT_DIGITS))
  109. }
  110. #[allow(dead_code)]
  111. fn main() {
  112. let args = std::env::args().collect::<Vec<_>>();
  113. let n = if args.len() < 2 {
  114. DEFAULT_DIGITS
  115. } else {
  116. FromStr::from_str(args[1].as_slice()).unwrap()
  117. };
  118. pidigits(n);
  119. }