// File Fibonacci.java - Traditional and Memoized Fibonacci Calculation import java.util.Date; import java.util.HashMap; public class Fibonacci { /** * A HashMap is used for memoization */ private HashMap hm = new HashMap(100); public static final int LOW = 0, HIGH1 = 50, HIGH2 = 93; /** * Constructor -- does all the calls */ public Fibonacci() { System.out.println("\n***** Fibonacci *****\n"); runFibo(LOW, HIGH1); System.out.println(); runFiboM(LOW, HIGH2); System.out.println(); } /** * Run traditional Fibonacci */ private void runFibo(final int low, final int high) { System.out.println("Traditional Fibonacci Calculation"); long now, elapsed, fiboValue; for (int i = low; i < high; i++) { now = (new Date()).getTime(); fiboValue = fibo(i); elapsed = (new Date()).getTime() - now; System.out.printf("%4d %,16d %,9d ms\n", i, fiboValue, elapsed); } } /** * Run memoized Fibonacci */ private void runFiboM(final int low, final int high) { System.out.println("Memoized Fibonacci Calculation"); long now, elapsed, fiboValue; for (int i = low; i < high; i++) { now = (new Date()).getTime(); fiboValue = fiboM(i); elapsed = (new Date()).getTime() - now; System.out.printf("%4d %,27d %,3d ms\n", i, fiboValue, elapsed); } } /** * Traditional recursive Fibonacci */ private long fibo(final int i) { return (i <= 1) ? i : fibo(i-1) + fibo(i-2); } /** * Memoized recursive Fibonacci */ private long fiboM(final int i) { if (i <= 1) return i; Long value = hm.get(i); if (value != null) return value; long valueL = fiboM(i-1) + fiboM(i-2); hm.put(i, valueL); return valueL; } public static void main(String[] args) { new Fibonacci(); } } // end class /* ----- Runtime Output ----- ***** Fibonacci ***** Traditional Fibonacci Calculation 0 0 0 ms 1 1 0 ms 2 1 0 ms 3 2 0 ms 4 3 0 ms 5 5 0 ms 6 8 0 ms 7 13 0 ms 8 21 0 ms 9 34 0 ms 10 55 0 ms 11 89 0 ms 12 144 0 ms 13 233 0 ms 14 377 0 ms 15 610 0 ms 16 987 0 ms 17 1,597 0 ms 18 2,584 0 ms 19 4,181 0 ms 20 6,765 0 ms 21 10,946 0 ms 22 17,711 0 ms 23 28,657 0 ms 24 46,368 0 ms 25 75,025 0 ms 26 121,393 0 ms 27 196,418 0 ms 28 317,811 0 ms 29 514,229 0 ms 30 832,040 15 ms 31 1,346,269 0 ms 32 2,178,309 16 ms 33 3,524,578 31 ms 34 5,702,887 31 ms 35 9,227,465 47 ms 36 14,930,352 94 ms 37 24,157,817 156 ms 38 39,088,169 234 ms 39 63,245,986 374 ms 40 102,334,155 655 ms 41 165,580,141 983 ms 42 267,914,296 1,623 ms 43 433,494,437 2,620 ms 44 701,408,733 4,290 ms 45 1,134,903,170 6,896 ms 46 1,836,311,903 11,091 ms 47 2,971,215,073 17,940 ms 48 4,807,526,976 28,970 ms 49 7,778,742,049 46,956 ms Memoized Fibonacci Calculation 0 0 0 ms 1 1 0 ms 2 1 0 ms 3 2 0 ms 4 3 0 ms 5 5 0 ms 6 8 0 ms 7 13 0 ms 8 21 0 ms 9 34 0 ms 10 55 0 ms 11 89 0 ms 12 144 0 ms 13 233 0 ms 14 377 0 ms 15 610 0 ms 16 987 0 ms 17 1,597 0 ms 18 2,584 0 ms 19 4,181 0 ms 20 6,765 0 ms 21 10,946 0 ms 22 17,711 0 ms 23 28,657 0 ms 24 46,368 0 ms 25 75,025 0 ms 26 121,393 0 ms 27 196,418 0 ms 28 317,811 0 ms 29 514,229 0 ms 30 832,040 0 ms 31 1,346,269 0 ms 32 2,178,309 0 ms 33 3,524,578 0 ms 34 5,702,887 0 ms 35 9,227,465 0 ms 36 14,930,352 0 ms 37 24,157,817 0 ms 38 39,088,169 0 ms 39 63,245,986 0 ms 40 102,334,155 0 ms 41 165,580,141 0 ms 42 267,914,296 0 ms 43 433,494,437 0 ms 44 701,408,733 0 ms 45 1,134,903,170 0 ms 46 1,836,311,903 0 ms 47 2,971,215,073 0 ms 48 4,807,526,976 0 ms 49 7,778,742,049 0 ms 50 12,586,269,025 0 ms 51 20,365,011,074 0 ms 52 32,951,280,099 0 ms 53 53,316,291,173 0 ms 54 86,267,571,272 0 ms 55 139,583,862,445 0 ms 56 225,851,433,717 0 ms 57 365,435,296,162 0 ms 58 591,286,729,879 0 ms 59 956,722,026,041 0 ms 60 1,548,008,755,920 0 ms 61 2,504,730,781,961 0 ms 62 4,052,739,537,881 0 ms 63 6,557,470,319,842 0 ms 64 10,610,209,857,723 0 ms 65 17,167,680,177,565 0 ms 66 27,777,890,035,288 0 ms 67 44,945,570,212,853 0 ms 68 72,723,460,248,141 0 ms 69 117,669,030,460,994 0 ms 70 190,392,490,709,135 0 ms 71 308,061,521,170,129 0 ms 72 498,454,011,879,264 0 ms 73 806,515,533,049,393 0 ms 74 1,304,969,544,928,657 0 ms 75 2,111,485,077,978,050 0 ms 76 3,416,454,622,906,707 0 ms 77 5,527,939,700,884,757 0 ms 78 8,944,394,323,791,464 0 ms 79 14,472,334,024,676,221 0 ms 80 23,416,728,348,467,685 0 ms 81 37,889,062,373,143,906 0 ms 82 61,305,790,721,611,591 0 ms 83 99,194,853,094,755,497 0 ms 84 160,500,643,816,367,088 0 ms 85 259,695,496,911,122,585 0 ms 86 420,196,140,727,489,673 0 ms 87 679,891,637,638,612,258 0 ms 88 1,100,087,778,366,101,931 0 ms 89 1,779,979,416,004,714,189 0 ms 90 2,880,067,194,370,816,120 0 ms 91 4,660,046,610,375,530,309 0 ms 92 7,540,113,804,746,346,429 0 ms ----- End Runtime Output ----- */