#include <stdio.h>
#include <time.h>
void printFibonacci(int n) {
static int n1 = 0, n2 = 1, n3;
if (n > 0) {
n3 = n1 n2;
n1 = n2;
n2 = n3;
printf("%d ", n3);
printFibonacci(n - 1);
}
}
int main() {
int n;
struct timespec start, stop;
double total_time;
clock_gettime(CLOCK_REALTIME, &start);
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Fibonacci Series: ");
printf("%d %d ", 0, 1);
printFibonacci(n - 2);
clock_gettime(CLOCK_REALTIME, &stop);
total_time = (stop.tv_sec - start.tv_sec) * 1e9;
total_time = (total_time (stop.tv_nsec - start.tv_nsec)) * 1e-9;
printf("\nTime taken for each sequence: %lf", total_time);
return 0;
}
This C program above has the user enter an integer, and the program will then output the Fibonacci sequence. What I am trying to do is to get the run-time of each number in the Fibonacci sequence down to the nanosecond. So far my attempt has been to use the clockgettime() function to get the start and stop time of the fibonacci function. However, that only outputs the total time the function took instead of how long each individual sequence took. How would I fix this code so I would get each individual sequence time instead?
For example, if the user inputs 12 the output I desire would look like this, where each sequence time is displayed:
Enter the number of elements: 12
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89
Time taken for each sequence: 0.1023, 0.2024, 0.3025, 0.7024, 0.9323, 0.12023, 0.78923, 0.6723, 0.12323, 0.9033, 0.34523, 0.123423
CodePudding user response：
As coded in the question, you compute the time for the whole sequence, including the time it takes the user to enter the number and the time it takes printf to output the values. This is meaningless.
Furthermore, you multiply the number of seconds by 109 but then divide the number of nanoseconds by 109 too: you should do one or the other but not both.
If you want to time the computation of each number, you should retrieve the clock just before the addition of the 2 previous numbers an immediately after the addition, retrieve the clock again: Trying to clock such a simple operation will be very difficult as you are more likely to measure the overhead of clock_gettime, the imprecision of the CLOCK_REALTIME, possibly polluted by asynchronous processes interrupting your program as you measure CLOCK_REALTIME instead of the current process' runtime. You probably should use clock() instead, but the measurements are likely to be insignificant. Intermediary timings should be stored in a static array for main to print them.
Here is a modified version:
#include <stdio.h>
#include <time.h>
#define MAX_TIMINGS 100
static double timings[MAX_TIMINGS];
static int timing_index = 2;
void printFibonacci(int n) {
static int n1 = 0, n2 = 1, n3;
if (n > 0) {
struct timespec start, stop;
clock_gettime(CLOCK_REALTIME, &start);
n3 = n1 n2;
n1 = n2;
n2 = n3;
clock_gettime(CLOCK_REALTIME, &stop);
if (timing_index < MAX_TIMINGS) {
timings[n] = (stop.tv_sec - start.tv_sec) * 1e9
(stop.tv_nsec - start.tv_nsec);
}
printf("%d ", n3);
printFibonacci(n - 1);
}
}
int main() {
int i, n;
double total_time = 0;
printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Fibonacci Series: ");
printf("%d %d ", 0, 1);
printFibonacci(n - 2);
printf("\n");
printf("Time taken for each number:");
for (i = 0; i <= n; i ) {
printf(" %.0fns", timings[i]);
total_time = timings[i];
}
printf("\n");
printf("Total time: %.0fns\n", total_time);
return 0;
}
Output:
Enter the number of elements: 20
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Time taken for each number: 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns
Total time: 0ns
Measuring the time for each number is significant for the classic recursive implementation where many recursive calls are involved for even moderately large arguments, but not for your sequential generator.
Here is a more classic example:
#include <stdio.h>
#include <time.h>
unsigned long long fib(int n) {
if (n < 2)
return n;
else
return fib(n - 1) fib(n - 2);
}
int main() {
int i, n;
double total_time = 0;
printf("Enter the number of elements: ");
if (scanf("%d", &n) != 1)
return 1;
double timings[n 1];
printf("Fibonacci Series:");
for (i = 0; i <= n; i ) {
struct timespec start, stop;
unsigned long long res;
clock_gettime(CLOCK_REALTIME, &start);
res = fib(i);
clock_gettime(CLOCK_REALTIME, &stop);
timings[i] = ((stop.tv_sec - start.tv_sec) * 1e9
(stop.tv_nsec - start.tv_nsec));
printf(" %llu", res);
}
printf("\n");
printf("Time taken for each number:");
for (i = 0; i <= n; i ) {
printf(" %.0fns", timings[i]);
total_time = timings[i];
}
printf("\n");
printf("Total time: %.0fns\n", total_time);
return 0;
}
Output:
Enter the number of elements: 20
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Time taken for each number: 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 0ns 1000ns 0ns 1000ns 1000ns 2000ns 5000ns 6000ns 10000ns 18000ns 38000ns 69000ns
Total time: 151000ns
CodePudding user response：
Seems like you're using the clock on your main program which means it really as you said calculates the total runtime of the function. in order to calculate how much time it took you to commit one sequence you should consider moving the
clock_gettime(CLOCK_REALTIME, &start);
And:
clock_gettime(CLOCK_REALTIME, &stop);
total_time = (stop.tv_sec - start.tv_sec) * 1e9;
total_time = (total_time (stop.tv_nsec - start.tv_nsec)) * 1e-9;
To the start and end of the printFibonacci , respectfully and in that case in each recursion you'll see the exact time it took a sequence to happen.