Skip to content

Instantly share code, notes, and snippets.

@mtrojanowski
Created December 21, 2017 13:36
Show Gist options
  • Save mtrojanowski/7d9bf02ef1f2fb7602a32a16db954ab0 to your computer and use it in GitHub Desktop.
Save mtrojanowski/7d9bf02ef1f2fb7602a32a16db954ab0 to your computer and use it in GitHub Desktop.
An implementation of Fibonacci
private BigInteger f(int n, Map<Integer, BigInteger> cache) {
BigInteger result = cache.putIfAbsent(n, RESERVED);
if (result == null) {
int half = (n + 1) / 2;
CompletableFuture<BigInteger> completableFuture = new CompletableFuture<>();
CompletableFuture<BigInteger> futureResult = CompletableFuture.supplyAsync(() -> f(half - 1, cache));
futureResult.thenAcceptBothAsync(CompletableFuture.supplyAsync(
() -> f(half, cache)),
(s1, s2) -> {
BigInteger result1 = null;
if (n % 2 == 1) {
result1 = s1.multiply(s1).add(s2.multiply(s2));
} else {
result1 = s1.shiftLeft(1).add(s2).multiply(s2);
}
synchronized (RESERVED) {
cache.put(n, result1);
RESERVED.notifyAll();
completableFuture.complete(result1);
}
});
try {
return completableFuture.get();
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
} else if (result == RESERVED) {
try {
ReservedBlocker blocker = new ReservedBlocker(n, cache);
ForkJoinPool.managedBlock(blocker);
result = blocker.result;
} catch (InterruptedException e) {
throw new CancellationException("interrupted");
}
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment