Algorithms_in_C 1.0.0
Set of algorithms implemented in C.
Loading...
Searching...
No Matches
fibonacci_fast.c File Reference

Compute \(m^{mth}\) Fibonacci number using the formulae: More...

#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
Include dependency graph for fibonacci_fast.c:

Functions

void fib (unsigned long n, unsigned long *C, unsigned long *D)
 Get the \(n^{th}\) and \(n+1^{th}\) Fibonacci number using recursive half-interval decimation.
 
int main (int argc, char *argv[])
 main function
 

Detailed Description

Compute \(m^{mth}\) Fibonacci number using the formulae:

Author
Krishna Vedala
Date
2 October, 2019

\begin{eqnarray*} F_{2n-1} &=& F_n^2 + F_{n-1}^2 \\ F_{2n} &=& F_n\left(2F_{n-1} + F_n\right) \end{eqnarray*}

Function Documentation

◆ fib()

void fib ( unsigned long  n,
unsigned long *  C,
unsigned long *  D 
)

Get the \(n^{th}\) and \(n+1^{th}\) Fibonacci number using recursive half-interval decimation.

Parameters
[in]nindex of Fibonacci number to get
[out]Cleft half interval value - end result here. Cannot be NULL
[out]Dright half interval can be discarded at end and can be NULL
24{
25 // Out of Range checking
26 // commented out since `n` is unsigned integer
27 // if (n < 0)
28 // {
29 // printf("\nNo Such term !\n");
30 // exit(0);
31 // }
32
33 unsigned long a, b, c, d;
34
35 if (n == 0)
36 {
37 C[0] = 0;
38 if (D) /* if D is not NULL */
39 D[0] = 1;
40 return;
41 }
42
43 fib(n >> 1, &c, &d); /* Compute F(n/2) */
44
45 a = c * ((d << 1) - c);
46 b = c * c + d * d;
47 if (n % 2 == 0) /* If n is even */
48 {
49 C[0] = a;
50 if (D)
51 D[0] = b;
52 return;
53 }
54
55 /**< If n is odd */
56 C[0] = b;
57 if (D) /* if D is not NULL */
58 D[0] = a + b;
59 return;
60}
void fib(unsigned long n, unsigned long *C, unsigned long *D)
Get the and Fibonacci number using recursive half-interval decimation.
Definition fibonacci_fast.c:23
Here is the call graph for this function:

◆ main()

int main ( int  argc,
char *  argv[] 
)

main function

66{
67 unsigned long number, result;
68
69 setlocale(LC_NUMERIC, ""); // format the printf output
70
71 // Asks for the number/position of term in Fibonnacci sequence
72 if (argc == 2)
73 number = atoi(argv[1]);
74 else
75 {
76 printf("Enter the value of n(n starts from 0 ): ");
77 scanf("%lu", &number);
78 }
79
80 fib(number, &result, NULL);
81
82 printf("The nth term is : %'lu \n", result);
83
84 return 0;
85}
Here is the call graph for this function: