Print first n Fibonacci Numbers using direct formula
Given a number n, the task is to print first n Fibonacci numbers.
Prerequisite: Program to print first n Fibonacci Numbers | Set 1
Examples:
Input : 7 Output :0 1 1 2 3 5 8 Input : 5 Output :0 1 1 2 3
N-th Fibonacci Number = [(1 + ?5)n – (1 – ?5)n)] / [2n * ?5]
Below is the implementation.
C++
// C++ code to print fibonacci // numbers till n using direct formula. #include<bits/stdc++.h> using namespace std; // Function to calculate fibonacci // using recurrence relation formula void fibonacci( int n){ long long int fib; for ( long long int i = 0; i < n; i++) { // Using direct formula fib = ( pow ((1 + sqrt (5)), i) - pow ((1 - sqrt (5)), i)) / ( pow (2, i) * sqrt (5)); cout << fib << " " ; } } // Driver code int main() { long long int n = 8; fibonacci(n); return 0; } |
Java
// Java code to print fibonacci // numbers till n using direct formula. class GFG{ // Function to calculate fibonacci // using recurrence relation formula static void fibonacci( double n){ double fib; for ( double i = 0 ; i < n; i++) { // Using direct formula fib = (Math.pow(( 1 + Math.sqrt( 5 )), i) - Math.pow(( 1 - Math.sqrt( 5 )), i)) / (Math.pow( 2 , i) * Math.sqrt( 5 )); System.out.print(( int )fib+ " " ); } } // Driver code public static void main(String[] args) { double n = 8 ; fibonacci(n); } } // This code is contributed by mits |
Python3
# Python3 code to print fibonacci # numbers till n using direct formula. import math # Function to calculate fibonacci # using recurrence relation formula def fibonacci(n): for i in range (n): # Using direct formula fib = (( pow (( 1 + math.sqrt( 5 )), i) - pow (( 1 - math.sqrt( 5 )), i)) / ( pow ( 2 , i) * math.sqrt( 5 ))); print ( int (fib), end = " " ); # Driver code n = 8 ; fibonacci(n); # This code is contributed by mits |
C#
// C# code to print fibonacci // numbers till n using direct formula.\ using System; public class GFG{ // Function to calculate fibonacci // using recurrence relation formula static void fibonacci( double n){ double fib; for ( double i = 0; i < n; i++) { // Using direct formula fib = (Math.Pow((1 + Math.Sqrt(5)), i) - Math.Pow((1 - Math.Sqrt(5)), i)) / (Math.Pow(2, i) * Math.Sqrt(5)); Console.Write(( int )fib+ " " ); } } // Driver code static public void Main (){ double n = 8; fibonacci(n); } } // This code is contributed by ajit. |
PHP
<?php // PHP code to print fibonacci // numbers till n using direct formula. // Function to calculate fibonacci // using recurrence relation formula function fibonacci( $n ) { for ( $i = 0; $i < $n ; $i ++) { // Using direct formula $fib = (pow((1 + sqrt(5)), $i ) - pow((1 - sqrt(5)), $i )) / (pow(2, $i ) * sqrt(5)); echo $fib , " " ; } } // Driver code $n = 8; fibonacci( $n ); // This code is contributed by jit_t ?> |
Javascript
<script> // Javascript code to print fibonacci // numbers till n using direct formula. // Function to calculate fibonacci // using recurrence relation formula function fibonacci(n) { var fib; for (i = 0; i < n; i++) { // Using direct formula fib = (Math.pow((1 + Math.sqrt(5)), i) - Math.pow((1 - Math.sqrt(5)), i)) / (Math.pow(2, i) * Math.sqrt(5)); document.write(parseInt(fib) + " " ); } } // Driver code var n = 8; fibonacci(n); // This code is contributed by gauravrajput1 </script> |
Output:
0 1 1 2 3 5 8 13
Time Complexity: O(n)
Auxiliary Space: O(1)
Note: The above program is costly compared to method 1 as it causes power computations in floating point. Also, it may not work perfectly due to floating point precision errors.