TheAlgorithms · vil02 · Oct 13, 2023 · Oct 1, 2023 · Oct 1, 2023 · Oct 1, 2023
diff --git a/src/main/java/com/thealgorithms/maths/Fibonacci.java b/src/main/java/com/thealgorithms/maths/Fibonacci.java
@@ -0,0 +1,41 @@
+package com.thealgorithms.maths;
+
+import java.math.BigInteger;
+
+/**
+ * This class provides methods for calculating Fibonacci numbers using BigInteger for large values of 'n'.
+ */
+public final class Fibonacci {
+
+    private Fibonacci() {
+        // Private constructor to prevent instantiation of this utility class.
+    }
+
+    /**
+     * Calculates the nth Fibonacci number.
+     *
+     * @param n The index of the Fibonacci number to calculate.
+     * @return The nth Fibonacci number as a BigInteger.
+     * @throws IllegalArgumentException if the input 'n' is a negative integer.
+     */
+    public static BigInteger calFibcompute(final int n) {
+        if (n < 0) {
+            throw new IllegalArgumentException("Input 'n' must be a non-negative integer.");
+        }
+
+        if (n <= 1) {
+            return BigInteger.valueOf(n);
+        }
+
+        BigInteger prev = BigInteger.ZERO;
+        BigInteger current = BigInteger.ONE;
+
+        for (int i = 2; i <= n; i++) {
+            BigInteger next = prev.add(current);
+            prev = current;
+            current = next;
+        }
+
+        return current;
+    }
+}
@@ -0,0 +1,50 @@
+package com.thealgorithms.maths;
+
+/**
+ * This class provides methods for calculating Fibonacci numbers using Binet's formula.
+ * Binet's formula is based on the golden ratio and allows computing Fibonacci numbers efficiently.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Fibonacci_sequence#Binet's_formula">Binet's formula on Wikipedia</a>
+ */
+public final class FibonacciNumberGoldenRation {
+    private FibonacciNumberGoldenRation() {
+        // Private constructor to prevent instantiation of this utility class.
+    }
+
+    /**
+     * Compute the limit for 'n' that fits in a long data type.
+     * Reducing the limit to 70 due to potential floating-point arithmetic errors
+     * that may result in incorrect results for larger inputs.
+     */
+    public static final int MAX_ARG = 70;
+
+    /**
+     * Calculates the nth Fibonacci number using Binet's formula.
+     *
+     * @param n The index of the Fibonacci number to calculate.
+     * @return The nth Fibonacci number as a long.
+     * @throws IllegalArgumentException if the input 'n' is negative or exceeds the range of a long data type.
+     */
+    public static long nthFibonaccicompute(int n) {
+        if (n < 0) {
+            throw new IllegalArgumentException("Input 'n' must be a non-negative integer.");
+        }
+
+        if (n > MAX_ARG) {
+            throw new IllegalArgumentException("Input 'n' is too large to fit into a long data type.");
+        }
+
+        if (n <= 1) {
+            return n;
+        }
+
+        // Calculate the nth Fibonacci number using the golden ratio formula
+        final double sqrt5 = Math.sqrt(5);
+        final double phi = (1 + sqrt5) / 2;
+        final double psi = (1 - sqrt5) / 2;
+        final double result = (Math.pow(phi, n) - Math.pow(psi, n)) / sqrt5;
+
+        // Round to the nearest integer and return as a long
+        return Math.round(result);
+    }
+}
@@ -0,0 +1,29 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.math.BigInteger;
+import org.junit.jupiter.api.Test;
+
+public class FibonacciNumberGoldenRationTest {
+
+    @Test
+    public void returnsCorrectValues() {
+        for (int n = 0; n <= FibonacciNumberGoldenRation.MAX_ARG; ++n) {
+            final var actual = FibonacciNumberGoldenRation.nthFibonaccicompute(n);
+            final var expected = Fibonacci.calFibcompute(n);
+            assertEquals(expected, BigInteger.valueOf(actual));
+        }
+    }
+
+    @Test
+    public void throwsIllegalArgumentExceptionForNegativeInput() {
+        assertThrows(IllegalArgumentException.class, () -> { FibonacciNumberGoldenRation.nthFibonaccicompute(-1); });
+    }
+
+    @Test
+    public void throwsIllegalArgumentExceptionForLargeInput() {
+        assertThrows(IllegalArgumentException.class, () -> { FibonacciNumberGoldenRation.nthFibonaccicompute(FibonacciNumberGoldenRation.MAX_ARG + 1); });
+    }
+}
diff --git a/src/test/java/com/thealgorithms/maths/FibonacciTest.java b/src/test/java/com/thealgorithms/maths/FibonacciTest.java
@@ -0,0 +1,36 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.math.BigInteger;
+import org.junit.jupiter.api.Test;
+
+public class FibonacciTest {
+    @Test
+    public void checkValueAtZero() {
+        assertEquals(BigInteger.ZERO, Fibonacci.calFibcompute(0));
+    }
+
+    @Test
+    public void checkValueAtOne() {
+        assertEquals(BigInteger.ONE, Fibonacci.calFibcompute(1));
+    }
+
+    @Test
+    public void checkValueAtTwo() {
+        assertEquals(BigInteger.ONE, Fibonacci.calFibcompute(2));
+    }
+
+    @Test
+    public void checkRecurrenceRelation() {
+        for (int i = 0; i < 100; ++i) {
+            assertEquals(Fibonacci.calFibcompute(i + 2), Fibonacci.calFibcompute(i + 1).add(Fibonacci.calFibcompute(i)));
+        }
+    }
+
+    @Test
+    public void checkNegativeInput() {
+        assertThrows(IllegalArgumentException.class, () -> { Fibonacci.calFibcompute(-1); });
+    }
+}