Skip to content

Commit 24a8223

Browse files
debnath003vil02
debnath003
and
vil02
authored
Added [FEATURE REQUEST] Golden Ration formula to find Nth Fibonacci number TheAlgorithms#4505 (TheAlgorithms#4513)
* Create FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Create FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Delete src/main/java/com/thealgorithms/maths/FibonacciNumberTest.java * Create FibonacciNumberTest.java * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update src/test/java/com/thealgorithms/maths/FibonacciNumberTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Create FibonacciCalculator.java * Update FibonacciNumberTest.java * Update and rename FibonacciCalculator.java to FibCalc.java * Update FibonacciNumberTest.java * Update FibCalc.java * Update FibonacciNumber.java * Delete src/test/java/com/thealgorithms/maths/FibCalc.java * Create FibCalc.java * Update FibonacciNumberTest.java * Update FibCalc.java * Update FibonacciNumberTest.java * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update FibonacciNumber.java * fix: use proper name * fix: use proper class name * tests: add `returnsCorrectValues` * Update and rename FibCalc.java to Fibonacci.java * Update Fibonacci.java * Update FibonacciNumber.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update Fibonacci.java * Update FibonacciNumber.java * Update and rename FibCalcTest.java to FibonacciTest.java * Update FibonacciNumber.java * Update Fibonacci.java * Update Fibonacci.java * Update Fibonacci.java * Update FibonacciTest.java * Update Fibonacci.java * Update src/main/java/com/thealgorithms/maths/Fibonacci.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/maths/FibonacciNumberTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/maths/FibonacciNumberTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update FibonacciTest.java * Update FibonacciNumberTest.java * Update FibonacciNumberTest.java * Update FibonacciTest.java * Update src/main/java/com/thealgorithms/maths/Fibonacci.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/maths/FibonacciNumberTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/maths/FibonacciTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/Fibonacci.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/maths/FibonacciNumber.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/maths/FibonacciNumberTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/maths/FibonacciNumberTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/maths/FibonacciNumberTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update FibonacciNumber.java * Update FibonacciNumber.java * Update Fibonacci.java * Update FibonacciNumber.java * Update and rename FibonacciNumber.java to FibonacciNumberGoldenRation.java * Update and rename FibonacciNumberTest.java to FibonacciNumberGoldenRationTest.java * Update Fibonacci.java * Update FibonacciNumberGoldenRation.java * Update FibonacciNumberGoldenRationTest.java * Update FibonacciTest.java * Update Fibonacci.java * Update FibonacciNumberGoldenRationTest.java * Update FibonacciNumberGoldenRationTest.java * Update FibonacciNumberGoldenRation.java * Update FibonacciNumberGoldenRation.java * Update FibonacciNumberGoldenRationTest.java * Update FibonacciNumberGoldenRationTest.java * Update src/main/java/com/thealgorithms/maths/FibonacciNumberGoldenRation.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update and rename Fibonacci.java to FibonacciLoop.java * Update FibonacciNumberGoldenRation.java * Update FibonacciNumberGoldenRationTest.java * Update and rename FibonacciTest.java to FibonacciLoopTest.java * Update FibonacciLoop.java * Update FibonacciLoop.java * Update FibonacciNumberGoldenRation.java * docs: add missing dot --------- Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> Co-authored-by: vil02 <vil02@o2.pl>
1 parent 1dc64b1 commit 24a8223

4 files changed

Lines changed: 156 additions & 0 deletions

File tree

‎src/main/java/com/thealgorithms/maths/FibonacciLoop.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.thealgorithms.maths;
2+
3+
import java.math.BigInteger;
4+
5+
/**
6+
* This class provides methods for calculating Fibonacci numbers using BigInteger for large values of 'n'.
7+
*/
8+
public final class FibonacciLoop {
9+
10+
private FibonacciLoop() {
11+
// Private constructor to prevent instantiation of this utility class.
12+
}
13+
14+
/**
15+
* Calculates the nth Fibonacci number.
16+
*
17+
* @param n The index of the Fibonacci number to calculate.
18+
* @return The nth Fibonacci number as a BigInteger.
19+
* @throws IllegalArgumentException if the input 'n' is a negative integer.
20+
*/
21+
public static BigInteger compute(final int n) {
22+
if (n < 0) {
23+
throw new IllegalArgumentException("Input 'n' must be a non-negative integer.");
24+
}
25+
26+
if (n <= 1) {
27+
return BigInteger.valueOf(n);
28+
}
29+
30+
BigInteger prev = BigInteger.ZERO;
31+
BigInteger current = BigInteger.ONE;
32+
33+
for (int i = 2; i <= n; i++) {
34+
BigInteger next = prev.add(current);
35+
prev = current;
36+
current = next;
37+
}
38+
39+
return current;
40+
}
41+
}

‎src/main/java/com/thealgorithms/maths/FibonacciNumberGoldenRation.java‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.thealgorithms.maths;
2+
3+
/**
4+
* This class provides methods for calculating Fibonacci numbers using Binet's formula.
5+
* Binet's formula is based on the golden ratio and allows computing Fibonacci numbers efficiently.
6+
*
7+
* @see <a href="https://en.wikipedia.org/wiki/Fibonacci_sequence#Binet's_formula">Binet's formula on Wikipedia</a>
8+
*/
9+
public final class FibonacciNumberGoldenRation {
10+
private FibonacciNumberGoldenRation() {
11+
// Private constructor to prevent instantiation of this utility class.
12+
}
13+
14+
/**
15+
* Compute the limit for 'n' that fits in a long data type.
16+
* Reducing the limit to 70 due to potential floating-point arithmetic errors
17+
* that may result in incorrect results for larger inputs.
18+
*/
19+
public static final int MAX_ARG = 70;
20+
21+
/**
22+
* Calculates the nth Fibonacci number using Binet's formula.
23+
*
24+
* @param n The index of the Fibonacci number to calculate.
25+
* @return The nth Fibonacci number as a long.
26+
* @throws IllegalArgumentException if the input 'n' is negative or exceeds the range of a long data type.
27+
*/
28+
public static long compute(int n) {
29+
if (n < 0) {
30+
throw new IllegalArgumentException("Input 'n' must be a non-negative integer.");
31+
}
32+
33+
if (n > MAX_ARG) {
34+
throw new IllegalArgumentException("Input 'n' is too big to give accurate result.");
35+
}
36+
37+
if (n <= 1) {
38+
return n;
39+
}
40+
41+
// Calculate the nth Fibonacci number using the golden ratio formula
42+
final double sqrt5 = Math.sqrt(5);
43+
final double phi = (1 + sqrt5) / 2;
44+
final double psi = (1 - sqrt5) / 2;
45+
final double result = (Math.pow(phi, n) - Math.pow(psi, n)) / sqrt5;
46+
47+
// Round to the nearest integer and return as a long
48+
return Math.round(result);
49+
}
50+
}

‎src/test/java/com/thealgorithms/maths/FibonacciLoopTest.java‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.thealgorithms.maths;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertThrows;
5+
6+
import java.math.BigInteger;
7+
import org.junit.jupiter.api.Test;
8+
9+
public class FibonacciLoopTest {
10+
@Test
11+
public void checkValueAtZero() {
12+
assertEquals(BigInteger.ZERO, FibonacciLoop.compute(0));
13+
}
14+
15+
@Test
16+
public void checkValueAtOne() {
17+
assertEquals(BigInteger.ONE, FibonacciLoop.compute(1));
18+
}
19+
20+
@Test
21+
public void checkValueAtTwo() {
22+
assertEquals(BigInteger.ONE, FibonacciLoop.compute(2));
23+
}
24+
25+
@Test
26+
public void checkRecurrenceRelation() {
27+
for (int i = 0; i < 100; ++i) {
28+
assertEquals(FibonacciLoop.compute(i + 2), FibonacciLoop.compute(i + 1).add(FibonacciLoop.compute(i)));
29+
}
30+
}
31+
32+
@Test
33+
public void checkNegativeInput() {
34+
assertThrows(IllegalArgumentException.class, () -> { FibonacciLoop.compute(-1); });
35+
}
36+
}

‎src/test/java/com/thealgorithms/maths/FibonacciNumberGoldenRationTest.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.thealgorithms.maths;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertThrows;
5+
6+
import java.math.BigInteger;
7+
import org.junit.jupiter.api.Test;
8+
9+
public class FibonacciNumberGoldenRationTest {
10+
11+
@Test
12+
public void returnsCorrectValues() {
13+
for (int n = 0; n <= FibonacciNumberGoldenRation.MAX_ARG; ++n) {
14+
final var actual = FibonacciNumberGoldenRation.compute(n);
15+
final var expected = FibonacciLoop.compute(n);
16+
assertEquals(expected, BigInteger.valueOf(actual));
17+
}
18+
}
19+
20+
@Test
21+
public void throwsIllegalArgumentExceptionForNegativeInput() {
22+
assertThrows(IllegalArgumentException.class, () -> { FibonacciNumberGoldenRation.compute(-1); });
23+
}
24+
25+
@Test
26+
public void throwsIllegalArgumentExceptionForLargeInput() {
27+
assertThrows(IllegalArgumentException.class, () -> { FibonacciNumberGoldenRation.compute(FibonacciNumberGoldenRation.MAX_ARG + 1); });
28+
}
29+
}

0 commit comments

Comments
 (0)