shootout-pidigits.rs 3.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
  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(test)]
  40. extern crate num;
  41. extern crate test;
  42. use std::str::FromStr;
  43. use num::traits::{FromPrimitive, ToPrimitive};
  44. use test::Bencher;
  45. use num::{BigInt, Integer, One, Zero};
  46. struct Context {
  47. numer: BigInt,
  48. accum: BigInt,
  49. denom: BigInt,
  50. }
  51. impl Context {
  52. fn new() -> Context {
  53. Context {
  54. numer: One::one(),
  55. accum: Zero::zero(),
  56. denom: One::one(),
  57. }
  58. }
  59. fn from_i32(i: i32) -> BigInt {
  60. FromPrimitive::from_i32(i).unwrap()
  61. }
  62. fn extract_digit(&self) -> i32 {
  63. if self.numer > self.accum {return -1;}
  64. let (q, r) =
  65. (&self.numer * Context::from_i32(3) + &self.accum)
  66. .div_rem(&self.denom);
  67. if r + &self.numer >= self.denom {return -1;}
  68. q.to_i32().unwrap()
  69. }
  70. fn next_term(&mut self, k: i32) {
  71. let y2 = Context::from_i32(k * 2 + 1);
  72. self.accum = (&self.accum + (&self.numer << 1)) * &y2;
  73. self.numer = &self.numer * Context::from_i32(k);
  74. self.denom = &self.denom * y2;
  75. }
  76. fn eliminate_digit(&mut self, d: i32) {
  77. let d = Context::from_i32(d);
  78. let ten = Context::from_i32(10);
  79. self.accum = (&self.accum - &self.denom * d) * &ten;
  80. self.numer = &self.numer * ten;
  81. }
  82. }
  83. fn pidigits(n: isize) {
  84. let mut k = 0;
  85. let mut context = Context::new();
  86. for i in (1..(n+1)) {
  87. let mut d;
  88. loop {
  89. k += 1;
  90. context.next_term(k);
  91. d = context.extract_digit();
  92. if d != -1 {break;}
  93. }
  94. print!("{}", d);
  95. if i % 10 == 0 {print!("\t:{}\n", i);}
  96. context.eliminate_digit(d);
  97. }
  98. let m = n % 10;
  99. if m != 0 {
  100. for _ in (m..10) { print!(" "); }
  101. print!("\t:{}\n", n);
  102. }
  103. }
  104. static DEFAULT_DIGITS: isize = 512;
  105. #[bench]
  106. fn use_bencher(b: &mut Bencher) {
  107. b.iter(|| pidigits(DEFAULT_DIGITS))
  108. }
  109. #[allow(dead_code)]
  110. fn main() {
  111. let args = std::env::args().collect::<Vec<_>>();
  112. let n = if args.len() < 2 {
  113. DEFAULT_DIGITS
  114. } else {
  115. FromStr::from_str(&args[1]).unwrap()
  116. };
  117. pidigits(n);
  118. }