Created
December 31, 2013 11:19
-
-
Save takac/8195459 to your computer and use it in GitHub Desktop.
Constant time solutions to Fibonacci and factorial calculations.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package fact; | |
import static java.lang.Math.PI; | |
import static java.lang.Math.exp; | |
import static java.lang.Math.log; | |
import static java.lang.Math.pow; | |
import static java.lang.Math.rint; | |
import static java.lang.Math.sqrt; | |
public class FactAndFib { | |
private static long hardFib(final int n) { | |
final double sqrt = sqrt(5.0); | |
final double mult = 0.5 * sqrt; | |
return (long) rint((pow(0.5 + mult, n) - | |
pow(0.5 - mult, n)) / sqrt); | |
} | |
private static long hardFact(final int n) { | |
return (long) rint(gamma(n)); | |
} | |
// http://introcs.cs.princeton.edu/java/91float/Gamma.java.html | |
// Uses Lanczos approximation formula. | |
static double logGamma(final double x) { | |
final double tmp = (x - 0.5) * log(x + 4.5) - (x + 4.5); | |
final double ser = 1.0 + 76.18009173 / (x + 0) - 86.50532033 / (x + 1) | |
+ 24.01409822 / (x + 2) - 1.231739516 / (x + 3) | |
+ 0.00120858003 / (x + 4) - 0.00000536382 / (x + 5); | |
return tmp + log(ser * sqrt(2 * PI)); | |
} | |
static double gamma(final double x) { | |
return exp(logGamma(x)); | |
} | |
public static void main(final String[] args) { | |
System.out.println("Factorials 1..12"); | |
for (int i = 1; i < 12; i++) { | |
System.out.println(hardFact(i)); | |
} | |
System.out.println(); | |
System.out.println("Fibonacci Numbers 1..20"); | |
for (int i = 0; i < 20; i++) { | |
System.out.println(hardFib(i)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment