Fibonacci

Fibonacci.java

import java.io.IOException;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.time.Duration;
import java.time.Instant;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.LongAdder;
import java.util.function.IntFunction;
import java.util.stream.Collectors;

public final class Fibonacci {

    private static volatile int PROGRESS;

    // Pre-Optimized TailRec
    static final class SerialMode {

        static BigInteger fib(int n) {
            BigInteger old;
            BigInteger current = BigInteger.ZERO;
            BigInteger next = BigInteger.ONE;
            while (n > 0) {
                old = current;
                current = next;
                next = old.add(next);
                --n;
                PROGRESS = n;
            }
            return current;
        }

    }

    // https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0#%E4%B8%80%E8%88%AC%E9%A0%85
    static final class GeneralMode {

        static BigInteger fib(int n) {
            return BigDecimal.valueOf(1. + Math.sqrt(5)).divide(BigDecimal.valueOf(2)).pow(n)
                .subtract(BigDecimal.valueOf(1. - Math.sqrt(5)).divide(BigDecimal.valueOf(2)).pow(n))
                .divide(BigDecimal.valueOf(Math.sqrt(5)), RoundingMode.HALF_UP)
                .toBigInteger();
        }

    }

    // fib: https://qiita.com/mod_poppo/items/4f78d135bb43b7fd1743#%E8%A1%8C%E5%88%97%E3%81%AE%E3%81%B9%E3%81%8D%E4%B9%97%E3%82%92%E4%BD%BF%E3%81%86
    // pow: https://qiita.com/mincoshi/items/53c520d4e04c7fdffe76
    static final class MatrixMode {

        static BigInteger fib(int n) {
            return new MatrixMode(
                BigInteger.ZERO, BigInteger.ONE,
                BigInteger.ONE, BigInteger.ONE
            ).pow(n).b;
        }

        public final BigInteger a;
        public final BigInteger b;
        public final BigInteger c;
        public final BigInteger d;

        public MatrixMode(BigInteger i) {
            this(i, i, i, i);
        }

        public MatrixMode(BigInteger a, BigInteger b, BigInteger c, BigInteger d) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;
        }

        public MatrixMode mul(MatrixMode o) {
            return new MatrixMode(
                (a.multiply(o.a)).add(b.multiply(o.c)),
                (a.multiply(o.b)).add(b.multiply(o.d)),
                (c.multiply(o.a)).add(d.multiply(o.c)),
                (c.multiply(o.b)).add(d.multiply(o.d))
            );
        }

        public MatrixMode pow(int n) {
            MatrixMode r = new MatrixMode(BigInteger.ONE, BigInteger.ZERO, BigInteger.ZERO, BigInteger.ONE);
            MatrixMode c = this;
            while (n > 0) {
                PROGRESS = n;
                if ((n & 1) == 1) {
                    r = r.mul(c);
                }
                n >>= 1;
                c = c.mul(c);
            }
            return r;
        }

    }

    // https://blog.miz-ar.info/2019/01/fast-fibonacci/#i-4
    static final class FibPairMode {

        static BigInteger fib(int n) {
            return new FibPairMode(BigInteger.ONE).pow(n).a;
        }

        public final BigInteger a;
        public final BigInteger b;

        public FibPairMode(BigInteger i) {
            this(i, i);
        }

        public FibPairMode(BigInteger a, BigInteger b) {
            this.a = a;
            this.b = b;
        }

        public FibPairMode mul(FibPairMode o) {
            return new FibPairMode(
                (a.multiply(o.b)).add(b.subtract(a).multiply(o.a)),
                (a.multiply(o.a)).add(b.multiply(o.b))
            );
        }

        public FibPairMode pow(int n) {
            FibPairMode r = new FibPairMode(BigInteger.ZERO, BigInteger.ONE);
            FibPairMode c = this;
            while (n > 0) {
                PROGRESS = n;
                if ((n & 1) == 1) {
                    r = r.mul(c);
                }
                n >>= 1;
                c = c.mul(c);
            }
            return r;
        }

    }

    // Reducing instance calls (slightly faster)
    static final class OptimizedFibPairMode {

        static BigInteger fib(int n) {
            return pow(new BigInteger[] { BigInteger.ONE, BigInteger.ONE }, n)[0];
        }

        private static void mul(BigInteger[] n) {
            final BigInteger ta = n[0];
            final BigInteger tb = n[1];
            n[0] = (ta.multiply(tb)).add(tb.subtract(ta).multiply(ta));
            n[1] = (ta.multiply(ta)).add(tb.multiply(tb));
        }

        private static void mul(BigInteger[] l, BigInteger[] r) {

            final BigInteger ta = l[0];
            final BigInteger tb = l[1];
            final BigInteger oa = r[0];
            final BigInteger ob = r[1];
            l[0] = (ta.multiply(ob)).add(tb.subtract(ta).multiply(oa));
            l[1] = (ta.multiply(oa)).add(tb.multiply(ob));
        }

        private static BigInteger[] pow(BigInteger[] c, int n) {
            BigInteger[] r = { BigInteger.ZERO, BigInteger.ONE };
            while (n > 0) {
                PROGRESS = n;
                if ((n & 1) == 1) {
                    mul(r, c);
                }
                n >>= 1;
                mul(c);
            }
            return r;
        }

    }

    // FibPair with Mutable BigInteger (Slower, Memory-saving)
    static final class OptimizedMutableFibPairMode {

        static BigInteger fib(int n) {
            BigIntegerMutable[] arr = { new BigIntegerMutable(0), new BigIntegerMutable(1) };
            pow(arr, n);
            return arr[0].toBigInteger();
        }

        private static void mul(BigIntegerMutable[] l, BigIntegerMutable[] r, BigIntegerMutable[] a, BigIntegerMutable[] b) {
            // l[0] = (l[0] * r[1])) + ((l[1] - l[0]) * r[0]);
            // ... is ->
            // l[1] -= l[0];
            // l[1] *= r[0];
            // l[0] *= r[1];
            // l[0] += l[1]
            a[1].set(l[1]);
            a[1].subtract(l[0]);
            a[1].multiply(r[0]);
            a[0].set(l[0]);
            a[0].multiply(r[1]);
            a[0].add(a[1]);

            // l[1] = (l[0].multiply(r[0])).add(l[1].multiply(r[1]));
            // ... is ->
            // l[0] *= r[0]
            // l[1] *= r[1]
            // l[1] += l[0]
            b[0].set(l[0]);
            b[0].multiply(r[0]);
            b[1].set(l[1]);
            b[1].multiply(r[1]);
            b[0].add(b[1]);

            // Copy
            l[0].set(a[0]);
            l[1].set(b[0]);
        }

        private static void pow(BigIntegerMutable[] r, int n) {
            BigIntegerMutable[] c = { new BigIntegerMutable(1), new BigIntegerMutable(1) };
            BigIntegerMutable[] a = { new BigIntegerMutable(0), new BigIntegerMutable(0) };
            BigIntegerMutable[] b = { new BigIntegerMutable(0), new BigIntegerMutable(0) };
            while (n > 0) {
                PROGRESS = n;
                if ((n & 1) == 1) {
                    mul(r, c, a, b);
                }
                n >>= 1;
                mul(c, c, a, b);
            }
        }

    }

    // Recursive call with Fork/Join and Simple Memoization
    static final class ForkJoinMode extends RecursiveTask<BigInteger> {

        private static final AtomicInteger ID = new AtomicInteger(0);

        static BigInteger fib(int n) {
            ForkJoinPool.ForkJoinWorkerThreadFactory factory = ForkJoinPool.commonPool().getFactory();
            int workerSize = Runtime.getRuntime().availableProcessors() << 1;
            return new ForkJoinPool(workerSize,
                p -> {
                    ForkJoinWorkerThread thread = factory.newThread(p);
                    thread.setName("Fibonacci-Worker-" + ID.getAndIncrement());
                    thread.setPriority(Thread.MIN_PRIORITY);
                    return thread;
                }, Thread.getDefaultUncaughtExceptionHandler(), false)
                .invoke(new ForkJoinMode(n, BigInteger.valueOf(n)));
        }

        private static final ConcurrentHashMap<BigInteger, BigInteger>
            CACHE = new ConcurrentHashMap<>();

        private static final LongAdder ADDER = new LongAdder();

        private final int base;
        private final BigInteger n;

        ForkJoinMode(int base, BigInteger n) {
            this.base = base;
            this.n = n;
        }

        @Override
        protected BigInteger compute() {
            BigInteger n = this.n;
            if (n.compareTo(BigInteger.ZERO) == 0) return n;
            if (n.compareTo(BigInteger.ONE) == 0) return n;

            ADDER.increment();
            PROGRESS = (int) (base - ADDER.sum());
            BigInteger v = CACHE.get(n);
            if (v != null)
                return v;

            ForkJoinMode f1 = new ForkJoinMode(base, n.subtract(BigInteger.ONE));
            f1.fork();

            ForkJoinMode f2 = new ForkJoinMode(base, n.subtract(BigInteger.valueOf(2)));
            f2.fork();

            v = f1.join().add(f2.join());
            CACHE.put(n, v);
            return v;
        }

    }

    static final class Benchmark {

        private static final boolean PREFER_PRECISION = true;

        static <K, V> Map.Entry<K, V> entryOf(K k, V v) {
            return new AbstractMap.SimpleImmutableEntry<>(k, v);
        }

        static Map<String, Long> calculate(int n) {
            Set<Map.Entry<String, IntFunction<BigInteger>>> es = ALGORITHMS.entrySet();
            return (PREFER_PRECISION ? es.stream() : es.parallelStream())
                .map(e -> {
                    System.out.println("Benchmarking " + e.getKey());
                    if (PREFER_PRECISION)
                        System.gc();
                    Instant start = Instant.now();
                    BigInteger result = null;
                    try {
                        result = e.getValue().apply(n);
                    } catch (Exception exception) {
                        exception.printStackTrace();
                    }
                    if (result == null)
                        return entryOf(e.getKey(), -1L);
                    Instant end = Instant.now();
                    return entryOf(e.getKey(), Duration.between(start, end).toMillis());
                })
                .sorted(Map.Entry.comparingByKey())
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (l, r) -> r, TreeMap::new));
        }

    }

    private static final Map<String, IntFunction<BigInteger>> ALGORITHMS;

    static {
        ALGORITHMS = new TreeMap<>();
        ALGORITHMS.put("serial", SerialMode::fib);
        ALGORITHMS.put("matrix", MatrixMode::fib);
        ALGORITHMS.put("fibpair", FibPairMode::fib);
        ALGORITHMS.put("fibpairfast", OptimizedFibPairMode::fib);
        ALGORITHMS.put("fibpairmut", OptimizedMutableFibPairMode::fib);
        ALGORITHMS.put("general", GeneralMode::fib);
        ALGORITHMS.put("forkjoin", ForkJoinMode::fib);
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage:");
            System.out.println("   - fib <n> -> calculates fib(n) using fastest algorithm");
            System.out.println("   - fib <n> <" + String.join("|", ALGORITHMS.keySet()) + "> -> calculating fib(n) using specified algorithm");
            System.out.println("   - fib <n> benchmark -> Benchmarks all algorithms");
            System.exit(2);
            return;
        }
        int n = Integer.parseInt(args[0]);
        String mode = args.length > 1 ? String.valueOf(args[1]).toLowerCase() : "fibpairfast";

        if (mode.equals("benchmark")) {
            System.out.println("Benchmark Mode");
            Map<String, Long> result = Benchmark.calculate(n);
            System.out.println("Benchmark Result:");
            result.forEach((k, v) -> System.out.printf("   - %s: about %d ms", k, v).println());
            return;
        }

        // BigInteger f = fibonacci(n, mode);
        PROGRESS = n;
        CompletableFuture<BigInteger> ftask = CompletableFuture.supplyAsync(() -> {
            Instant begin = Instant.now();
            BigInteger result = fibonacci(n, mode);
            Instant end = Instant.now();
            System.out.printf("%nDone! Took about %d millis%n", Duration.between(begin, end).toMillis());
            return result;
        });

        while (!ftask.isDone()) {
            float p = (float) (n - PROGRESS) / n;
            int bar = Math.round(p * 30);
            synchronized (System.out) {
                System.out.print("\r");
                System.out.printf("[%s>%s] (%.1f%%, %d)                                                             \r",
                    repeat('=', bar), repeat(' ', 30 - bar), p * 100F, PROGRESS);
            }
            try {
                Thread.sleep(50);
            } catch (InterruptedException ignored) {
            }
        }
        System.out.println();

        BigInteger f = ftask.join();

        try {
            System.out.println("Writing...");
            String str = f.toString();
            Files.write(Paths.get("fib-" + n + ".txt"),
                Collections.singletonList(str),
                StandardCharsets.UTF_8, StandardOpenOption.CREATE, StandardOpenOption.TRUNCATE_EXISTING);
            if (str.length() < 1048576)
                System.out.append("Result: ").println(str);
        } catch (IOException exception) {
            exception.printStackTrace();
        }
        System.exit(0);
    }

    private static BigInteger fibonacci(int n, String algorithm) {
        IntFunction<BigInteger> kernel = ALGORITHMS.get(algorithm);
        if (kernel != null) {
            return kernel.apply(n);
        }
        throw new IllegalArgumentException("Algorithm " + algorithm + " is not installed!");
    }

    private static String repeat(char c, int n) {
        if (n < 0)
            return "";
        StringBuilder sb = new StringBuilder(n);
        for (; n != 0; --n) {
            sb.append(c);
        }
        return sb.toString();
    }

    private Fibonacci() {
    }

}

final class BigIntegerMutable {

    private static Object newInstance(int value) {
        try {
            return CONSTRUCTOR.newInstance(value);
        } catch (InstantiationException | IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    private static final Constructor<?> CONSTRUCTOR;
    private static final Method ADD;
    private static final Method SUBTRACT;
    private static final Method MULTIPLY;
    private static final Method IS_ZERO;
    private static final Method IS_ONE;
    private static final Method RESET;
    private static final Method COPY_VALUE;
    private static final Method TO_BIG_INTEGER;

    static {
        try {
            Class<?> MutableBigInteger = Class.forName("java.math.MutableBigInteger");
            CONSTRUCTOR = MutableBigInteger.getDeclaredConstructor(int.class);
            ADD = MutableBigInteger.getDeclaredMethod("add", MutableBigInteger);
            SUBTRACT = MutableBigInteger.getDeclaredMethod("subtract", MutableBigInteger);
            MULTIPLY = MutableBigInteger.getDeclaredMethod("multiply", MutableBigInteger, MutableBigInteger);
            IS_ZERO = MutableBigInteger.getDeclaredMethod("isZero");
            IS_ONE = MutableBigInteger.getDeclaredMethod("isOne");
            RESET = MutableBigInteger.getDeclaredMethod("reset");
            COPY_VALUE = MutableBigInteger.getDeclaredMethod("copyValue", MutableBigInteger);
            TO_BIG_INTEGER = MutableBigInteger.getDeclaredMethod("toBigInteger");

            CONSTRUCTOR.setAccessible(true);
            ADD.setAccessible(true);
            SUBTRACT.setAccessible(true);
            MULTIPLY.setAccessible(true);
            IS_ZERO.setAccessible(true);
            IS_ONE.setAccessible(true);
            RESET.setAccessible(true);
            COPY_VALUE.setAccessible(true);
            TO_BIG_INTEGER.setAccessible(true);
        } catch (ReflectiveOperationException exception) {
            throw new ExceptionInInitializerError(exception);
        }
    }

    private static final Object BUFFER = newInstance(0);

    private final Object handle;

    public BigIntegerMutable(int value) {
        this.handle = newInstance(value);
    }

    public boolean isZero() {
        try {
            return (boolean) IS_ZERO.invoke(handle);
        } catch (IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    public boolean isOne() {
        try {
            return (boolean) IS_ONE.invoke(handle);
        } catch (IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    public void set(BigIntegerMutable source) {
        try {
            COPY_VALUE.invoke(handle, source.handle);
        } catch (IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    public void add(BigIntegerMutable other) {
        try {
            ADD.invoke(handle, other.handle);
        } catch (IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    public void subtract(BigIntegerMutable other) {
        try {
            SUBTRACT.invoke(handle, other.handle);
        } catch (IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    public void multiply(BigIntegerMutable other) {
        try {
            if (isZero() || other.isOne())
                return;
            if (other.isZero()) {
                RESET.invoke(handle);
                return;
            }
            if (isOne()) {
                COPY_VALUE.invoke(handle, other.handle);
                return;
            }
            synchronized (BUFFER) {
                Object buffer = BUFFER;
                MULTIPLY.invoke(handle, other.handle, buffer);
                COPY_VALUE.invoke(handle, buffer);
            }
        } catch (IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    public BigInteger toBigInteger() {
        try {
            return (BigInteger) TO_BIG_INTEGER.invoke(handle);
        } catch (IllegalAccessException | InvocationTargetException exception) {
            throw new InternalError(exception);
        }
    }

    @Override
    public String toString() {
        return toBigInteger().toString();
    }

}