code_junkie

How would you write a non-recursive algorithm to calculate factorials?

Nov 11th, 2011
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.56 KB | None | 0 0
  1. public int factorial(int n) {
  2. int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320,
  3. 362880, 3628800, 39916800, 479001600};
  4. return fact[n];
  5. }
  6.  
  7. ans = 1
  8. for i = n down to 2
  9. ans = ans * i
  10. next
  11.  
  12. public double factorial(int n) {
  13. double result = 1;
  14. for(double i = 2; i<=n; ++i) {
  15. result *= i;
  16. }
  17. return result;
  18. }
  19.  
  20. int factorial(int i) {
  21. static int factorials[] = {1, 1, 2, 6, 24, 120, 720,
  22. 5040, 40320, 362880, 3628800, 39916800, 479001600};
  23. if (i<0 || i>12) {
  24. fprintf(stderr, "Factorial input out of rangen");
  25. exit(EXIT_FAILURE); // You could also return an error code here
  26. }
  27. return factorials[i];
  28. }
  29.  
  30. C++ C#
  31. ---------------------
  32. Iterative 1.0 1.6
  33. Lookup .28 1.1
  34. Recursive 2.4 2.6
  35.  
  36. C++ C#
  37. ---------------------
  38. Iterative 1.0 2.9
  39. Lookup .16 .53
  40. Recursive 1.9 3.9
  41.  
  42. long fact(int n) {
  43. long x = 1;
  44. for(int i = 1; i <= n; i++) {
  45. x *= i;
  46. }
  47. return x;
  48. }
  49.  
  50. int total = 1
  51. loop while n > 1
  52. total = total * n
  53. n--
  54. end while
  55.  
  56. def fact(n): return (reduce(lambda x, y: x * y, xrange(1, n+1)))
  57.  
  58. total = 1
  59. For i = 1 To n
  60. total *= i
  61. Next
  62.  
  63. fac = 1 ;
  64. for( i = 1 ; i <= n ; i++){
  65. fac = fac * i ;
  66. }
  67.  
  68. public int factorialNonRecurse(int n) {
  69. int product = 1;
  70.  
  71. for (int i = 2; i <= n; i++) {
  72. product *= i;
  73. }
  74.  
  75. return product;
  76. }
  77.  
  78. #define int MAX_PRECALCFACTORIAL = 13;
  79.  
  80. public double factorial(int n) {
  81. ASSERT(n>0);
  82. int[MAX_PRECALCFACTORIAL] fact = {1, 1, 2, 6, 24, 120, 720, 5040, 40320,
  83. 362880, 3628800, 39916800, 479001600};
  84. if(n < MAX_PRECALCFACTORIAL)
  85. return (double)fact[n];
  86.  
  87. //else we are at least n big
  88. double total = (float)fact[MAX_PRECALCFACTORIAL-1]
  89. for(int i = MAX_PRECALCFACTORIAL; i <= n; i++)
  90. {
  91. total *= (double)i; //cost of incrimenting a double often equal or more than casting
  92. }
  93. return total;
  94.  
  95. }
  96.  
  97. long fact(int n)
  98. {
  99. long fact=1;
  100. while(n>1)
  101. fact*=n--;
  102. return fact;
  103. }
  104.  
  105. long fact(int n)
  106. {
  107. for(long fact=1;n>1;n--)
  108. fact*=n;
  109. return fact;
  110. }
  111.  
  112. //Note: many compilers have an upper limit on the number of recursive templates allowed.
  113.  
  114. template <int N>
  115. struct Factorial
  116. {
  117. enum { value = N * Factorial<N - 1>::value };
  118. };
  119.  
  120. template <>
  121. struct Factorial<0>
  122. {
  123. enum { value = 1 };
  124. };
  125.  
  126. // Factorial<4>::value == 24
  127. // Factorial<0>::value == 1
  128. void foo()
  129. {
  130. int x = Factorial<4>::value; // == 24
  131. int y = Factorial<0>::value; // == 1
  132. }
  133.  
  134. int fact(int n){
  135. int r = 1;
  136. for(int i = 1; i <= n; i++) r *= i;
  137. return r;
  138. }
Add Comment
Please, Sign In to add comment