m1b on 10/09/11

Fun with Fibonacci, Golden Ratio and Factorials, with loops vs recursives

/ Published in: Java   1. import java.math.*;
2. import static java.math.BigInteger.*;
3.
4. /**
5.  * Fun with Fibonacci, Golden Ratio and Factorials, with loops vs recursives.
6.  */
7. public class FiboFact {
8.
9. /**
10.   * Fibonacci in a loop, no recursion.
11.   */
12. private static int fibLoop(int n) {
13. if(n < 2) return n;
14. int previous = 0;
15. int next = 1;
16. for(int i = 1; i < n; i++) {
17. int save = next;
18. next += previous;
19. previous = save;
20. }
21. return next;
22. }
23.
24. /**
25.   * Fibonacci recursive. Although sleek, short and with nothing that could go wrong, there is a serious
26.   * performance issue for large N: there is an exponential explosion of reevaluations and Java does not provide memoization without
27.   * a dedicated effort to it. Therefore, for an N, N-2 will be evaluated by N and N-1. N-3 will be evaluated by N, N-1 and N-2,
28.   * and so on.
29.   */
30. private static int fibRecursive(int n) {
31. // uncomment the following line to see the exponential explosion of reevaluations:
32. //System.out.printf("<fib:" + n + '>');
33. return n < 2 ? n : fibRecursive(n-1) + fibRecursive(n-2); // this fork is the cause of exponential explosion
34. }
35.
36. /**
37.   * Factorial in a loop with long, good till n = 20. With int, the biggest n would be 12.
38.   */
39. private static long factLoop(long n) {
40. if(n < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);
41. if(n == 0) return 1;
42. long result = 1;
43. for(int i = 1; i <= n; i++) result *= i;
44. return result;
45. }
46.
47. private static long factRecursive(long n) {
48. if(n < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);
49. return n <= 1 ? 1 : n * factRecursive(n - 1);
50. }
51.
52. /**
53.   * Big Integer for factorials of integers greater than 20.
54.   */
55. private static BigInteger factBdLoop(final BigInteger n) {
56. if(n.compareTo(ZERO) < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);
57. if(n.compareTo(ONE) <= 0) return ONE;
58. BigInteger result = ONE;
59. for(int i = 1; i <= n.intValue(); i++) result = result.multiply(BigInteger.valueOf(i));
60. return result;
61. }
62.
63. private static BigInteger factBdRecursive(final BigInteger n) {
64. if(n.compareTo(ZERO) < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);
65. return n.compareTo(ONE) <= 0 ? ONE : n.multiply(factBdRecursive(n.subtract(ONE)));
66. }
67. public static void main(String[] args) {
68. int prev = 0;
69. for(int n = 0; n <= 15; n++) {
70. int f = fibLoop(n);
71. System.out.printf("%nn=%2d, loop: %d, recurse: %d", n, f, fibRecursive(n));
72. if(prev != 0) System.out.printf(", golden ratio= %19.17f", Double.valueOf(f)/Double.valueOf(prev));
73. prev = f;
74. }
75. final int goldenBase = 46; // max fib that fits in an int
76. // for 92, 7540113804746346429/4660046610375530309=1.618033988749894848204586834365638117699
77. final BigDecimal fiBigger = BigDecimal.valueOf(fibLoop(goldenBase));
78. final BigDecimal fiSmaller = BigDecimal.valueOf(fibLoop(goldenBase - 1));
79. // for fib/fib we get 17 correct digits of golden ratio
80. System.out.printf("%nGolden Ratio of %,.0f/%,.0f: %19.17f", fiBigger, fiSmaller, fiBigger.divide(fiSmaller, 44, RoundingMode.HALF_UP));
81. for(int n = 0; n <= 21; n++) { // 21! already blows the Long range of -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 inclusive
82. // 20! is the last valid factorial for Long; for int it's 12
83. System.out.printf("%nn=%2d, loop: %,25d; recurse: %,25d", n, factLoop(n), factRecursive(n));
84. }
85. System.out.printf(" <<<< WOOPS!! Too big for a Long!");
86. for(int n = 0; n < 31; n++) { // with big integer the limit is memory
87. final BigInteger bigN = BigInteger.valueOf(n);
88. System.out.printf("%nn=%2d, loop: %,45d; recurse: %,45d", n, factBdLoop(bigN), factBdRecursive(bigN));
89. }
90. System.out.printf("%nLong: min=%,d, max=%,d", Long.MIN_VALUE, Long.MAX_VALUE);
91. }
92. }