Repository: TheAlgorithms/Java
Pull request #4513 (2023-10-01 16:38:49)

Added [FEATURE REQUEST] Golden Ration formula to find Nth Fibonacci number #4505
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


debnath003: @debasishbsws can you check the code that I have given about the golden ratio of Fibonacci Number and approve the PR?
debnath003: @debasishbsws I have given the code, awaiting your review
debnath003: @debasishbsws Awaiting your review, I have given the code much earlier
debnath003: @debasishbsws @BamaCharanChhandogi awaiting review for my PR
debnath003: @debasishbsws @BamaCharanChhandogi @yanglbme @vil02 Someone please approve my PR, I have given this PR 2 days ago!
debnath003: @BamaCharanChhandogi @debasishbsws please check my PR, awaiting review
debnath003: @vil02 can you please review this once again? Waiting for the PR and approving review!
vil02: @debnath003 as mentioned [earlier](https://github.com/TheAlgorithms/Java/pull/4513#discussion_r1349557244): please add tests.
vil02: > @vil02 looks like I have entered the right junit tests, but it is repeatedly showing errors regarding the availability of the module. Please help me!!!!!

Just move your test file `FibonacciNumberTest.java` to [`/src/test/java/com/thealgorithms/maths`](https://github.com/TheAlgorithms/Java/tree/master/src/test/java/com/thealgorithms/maths).
debnath003: > > @vil02 looks like I have entered the right junit tests, but it is repeatedly showing errors regarding the availability of the module. Please help me!!!!!
> 
> Just move your test file `FibonacciNumberTest.java` to [`/src/test/java/com/thealgorithms/maths`](https://github.com/TheAlgorithms/Java/tree/master/src/test/java/com/thealgorithms/maths).

Done @vil02, now please review the codes and approve my PR.
debnath003: @vil02 please check the code and approve my PR! Awaiting your review.
debnath003: Done @vil02, could you now check the review for PR and approve the PR? For hacktoberfest? also add hacktoberfest accepted label for the eligibility of hacktoberfest! Thank you.
vil02: > Done @vil02, could you now check the review for PR and approve the PR? For hacktoberfest? also add hacktoberfest accepted label for the eligibility of hacktoberfest! Thank you.

There is still quite long way to merge that. Few important issues:
- adding a class computing Fibonacci numbers in some _standard_ way (and tests for it),
- adding a test that verifying that the _golden ration formula_ gives the same result as the _standard way_ for all `n` from 1 to 92,
- finding right names for all of the classes and methods,
- documenting everything.

Regarding the _hacktoberfest label_ - it is not needed. This repository has the `hacktoberfest` tag and your contribution will be automatically recognized.
debnath003: > > Done @vil02, could you now check the review for PR and approve the PR? For hacktoberfest? also add hacktoberfest accepted label for the eligibility of hacktoberfest! Thank you.
> 
> There is still quite long way to merge that. Few important issues:
> 
> * adding a class computing Fibonacci numbers in some _standard_ way (and tests for it),
> * adding a test that verifying that the _golden ration formula_ gives the same result as the _standard way_ for all `n` from 1 to 92,
> * finding right names for all of the classes and methods,
> * documenting everything.
> 
> Regarding the _hacktoberfest label_ - it is not needed. This repository has the `hacktoberfest` tag and your contribution will be automatically recognized.

The 2nd and the 4th points are basically done, I have documented and tested the code using that test file
debnath003: @vil02 have you checked the PR that I have edited some times back? Awaiting your review
debnath003: @vil02 I have done what you have told me, but looks like some compile error is going on, could you please figure it out? The code is almost over btw!!!
debnath003: @vil02 please check the code and update me on what should I do now! 
debnath003: @vil02 check the code again
vil02: > @vil02 check the code again

It is still [failing](https://github.com/TheAlgorithms/Java/actions/runs/6486613710/job/17615138643?pr=4513):
```
Error:  Failures: 
Error:    FibonacciNumberTest.testNthFibonacci:14 expected: <7540113804746346429> but was: <7540113804746369024>
```
debnath003: > > @vil02 check the code again
> 
> It is still [failing](https://github.com/TheAlgorithms/Java/actions/runs/6486613710/job/17615138643?pr=4513):
> 
> ```
> Error:  Failures: 
> Error:    FibonacciNumberTest.testNthFibonacci:14 expected: <7540113804746346429> but was: <7540113804746369024>
> ```

I somehow reduced the error, but it's still showing error @vil02 
vil02: Well... something giving wrong results cannot be merged. I will have a closer look in the afternoon.

Where did the _golden ratio formula_ go?

Could you please do everything what I have asked [ealier](https://github.com/TheAlgorithms/Java/pull/4513#pullrequestreview-1671511985).
debnath003: > Well... something giving wrong results cannot be merged. I will have a closer look in the afternoon.
> 
> Where did the _golden ratio formula_ go?
> 
> Could you please do everything what I have asked [ealier](https://github.com/TheAlgorithms/Java/pull/4513#pullrequestreview-1671511985).

I actually removed that in order to check if the build is still showing error, let me rectify this again
debnath003: > Well... something giving wrong results cannot be merged. I will have a closer look in the afternoon.
> 
> Where did the _golden ratio formula_ go?
> 
> Could you please do everything what I have asked [ealier](https://github.com/TheAlgorithms/Java/pull/4513#pullrequestreview-1671511985).

I have actually done that, and the tests are already given @vil02 
debnath003: @vil02 all the checks are passed, thanks a lot! Now please review and approve this PR!!!
debnath003: @vil02 I have added all the changes that you have told in the codes, please review it, waiting for your approval!!
debnath003: Everything is done @vil02 , I thought that `compute` would have some method overriding, so I rewrote `nthFibonaccicompute` and `calFibcompute`,

Also, gave the documentation of the two main files! Now please check the codes @vil02 and approve the PR!
debnath003: @vil02 all done! Please review this again!
debnath003: @vil02 it seems like it is not getting merged automatically!
vil02: @debnath003 this was a _long one_. But very interesting: it is great to know that `71` is the smallest number for which `golden ratio formula` will give an incorrect result due to _floating points arithmetic issues_ for `double`.

Thanks for your contribution!

Patch:
diff --git a/src/main/java/com/thealgorithms/maths/FibonacciLoop.java b/src/main/java/com/thealgorithms/maths/FibonacciLoop.java
new file mode 100644
index 00000000..de23a430
--- /dev/null
+++ b/src/main/java/com/thealgorithms/maths/FibonacciLoop.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 FibonacciLoop {
+
+    private FibonacciLoop() {
+        // 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 compute(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;
+    }
+}
diff --git a/src/main/java/com/thealgorithms/maths/FibonacciNumberGoldenRation.java b/src/main/java/com/thealgorithms/maths/FibonacciNumberGoldenRation.java
new file mode 100644
index 00000000..4df37a40
--- /dev/null
+++ b/src/main/java/com/thealgorithms/maths/FibonacciNumberGoldenRation.java
@@ -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 compute(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 big to give accurate result.");
+        }
+
+        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);
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/maths/FibonacciLoopTest.java b/src/test/java/com/thealgorithms/maths/FibonacciLoopTest.java
new file mode 100644
index 00000000..93aec397
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/FibonacciLoopTest.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 FibonacciLoopTest {
+    @Test
+    public void checkValueAtZero() {
+        assertEquals(BigInteger.ZERO, FibonacciLoop.compute(0));
+    }
+
+    @Test
+    public void checkValueAtOne() {
+        assertEquals(BigInteger.ONE, FibonacciLoop.compute(1));
+    }
+
+    @Test
+    public void checkValueAtTwo() {
+        assertEquals(BigInteger.ONE, FibonacciLoop.compute(2));
+    }
+
+    @Test
+    public void checkRecurrenceRelation() {
+        for (int i = 0; i < 100; ++i) {
+            assertEquals(FibonacciLoop.compute(i + 2), FibonacciLoop.compute(i + 1).add(FibonacciLoop.compute(i)));
+        }
+    }
+
+    @Test
+    public void checkNegativeInput() {
+        assertThrows(IllegalArgumentException.class, () -> { FibonacciLoop.compute(-1); });
+    }
+}
diff --git a/src/test/java/com/thealgorithms/maths/FibonacciNumberGoldenRationTest.java b/src/test/java/com/thealgorithms/maths/FibonacciNumberGoldenRationTest.java
new file mode 100644
index 00000000..e3f7bf3e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/FibonacciNumberGoldenRationTest.java
@@ -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.compute(n);
+            final var expected = FibonacciLoop.compute(n);
+            assertEquals(expected, BigInteger.valueOf(actual));
+        }
+    }
+
+    @Test
+    public void throwsIllegalArgumentExceptionForNegativeInput() {
+        assertThrows(IllegalArgumentException.class, () -> { FibonacciNumberGoldenRation.compute(-1); });
+    }
+
+    @Test
+    public void throwsIllegalArgumentExceptionForLargeInput() {
+        assertThrows(IllegalArgumentException.class, () -> { FibonacciNumberGoldenRation.compute(FibonacciNumberGoldenRation.MAX_ARG + 1); });
+    }
+}