Posted By

m1b on 10/09/11


Tagged

java long fibonacci recursion precision factorial memoization


Versions (?)

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[46]/fib[45] 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. }

Report this snippet  

You need to login to post a comment.