Simple fibonacci number calculator.
Usage: fib nth Fibonacci number
// Calculate Fibonacci Numbers | |
// Public Domain | |
// https://creativecommons.org/publicdomain/zero/1.0/ | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <stdint.h> | |
#include <ctype.h> | |
#include <gmp.h> | |
#include <time.h> | |
long limit, i = 0; | |
int main(int argc, char *argv[]) | |
{ | |
// Get User Input | |
if (argc != 2) | |
{ | |
printf("Improper input. Exiting.\n"); | |
return -1; | |
} | |
limit = strtol(argv[1], NULL, 10); | |
// Setup GMP | |
mpz_t a, b, c; | |
mpz_init_set_ui(a, 1); | |
mpz_init_set_ui(b, 0); | |
mpz_init(c); | |
// Start timing | |
clock_t start_time = clock(); | |
for (i = 0; i < limit; i++) | |
{ | |
// Perform the Fibonacci Calculation | |
mpz_add(c, a, b); | |
mpz_set(a, b); | |
mpz_set(b, c); | |
} | |
// End timing | |
clock_t end_time = clock(); | |
// Print the results to stdout | |
printf("Fibonacci Number %ld: ", i); | |
mpz_out_str(stdout, 10, b); | |
printf("\n"); | |
// Cleanup | |
mpz_clear(a); | |
mpz_clear(b); | |
mpz_clear(c); | |
// Print time taaken | |
double time_taken = ((double) end_time - start_time) / CLOCKS_PER_SEC; | |
printf("Calculation Time: %f seconds\n", time_taken); | |
return 0; | |
} |
The instruction
(count % 2 == 0)
can be optimized withcount & 1
, and the instructioncount /= 2;
withcount *= 0.5
. I've tested and:. . .
while (count > 0)
{
if (count & 1)
{
mpz_mul(tmp, q, q);
mpz_mul(q, q, p);
mpz_mul_2exp(q, q, 1);
mpz_add(q, q, tmp);
mpz_mul(p, p, p);
mpz_add(p, p, tmp);
count *= 0.5;
}
else
{
mpz_mul(tmp, a, q);
mpz_mul(a, a, p);
mpz_addmul(a, b, q);
mpz_add(a, a, tmp);
mpz_mul(b, b, p);
mpz_add(b, b, tmp);
count -= 1;
}
}
// End timing
//.......
return EXIT_SUCCESS;
}
@Francesco146 Testing your code out I found some weird behavior (unless I'm misunderstanding something).
Here's the output of the above code (fibtest.exe) compared to a program I made with that and some other code in the comment chain (fib.exe). I checked the output of fib.exe with WolframAlpha to make sure the results were the correct element of the fib sequence.
./fibtest.exe 1
0
Calculation Time: 0.000000 seconds
./fib.exe 1
1
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 2
1
Calculation Time: 0.000000 seconds
./fib.exe 2
1
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 5
1
Calculation Time: 0.000000 seconds
./fib.exe 5
5
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 6
2
Calculation Time: 0.000000 seconds
./fib.exe 6
8
Calculation Time: 0.000000 seconds
Number of Digits: 1
./fibtest.exe 15
0
Calculation Time: 0.000000 seconds
./fib.exe 15
610
Calculation Time: 0.000000 seconds
Number of Digits: 3
./fibtest.exe 30
610
Calculation Time: 0.000000 seconds
./fib.exe 30
832040
Calculation Time: 0.001000 seconds
Number of Digits: 6
The code I used is here, it's a mix from @Francesco146 and @LizzyFleckenstein03:
// Calculate Fibonacci Numbers
// Public Domain
// https://creativecommons.org/publicdomain/zero/1.0/
#include <stdio.h>
#include <ctype.h>
#include <gmp.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
int main(int argc, char *argv[])
{
// Get User Input
if (argc != 2)
{
fprintf(stderr, "Usage: %s <number>\n", argv[0]);
return EXIT_FAILURE;
}
long count = strtol(argv[1], NULL, 10);
// Setup GMP
mpz_t a, b, p, q;
mpz_init_set_ui(a, 1);
mpz_init_set_ui(b, 0);
mpz_init_set_ui(p, 0);
mpz_init_set_ui(q, 1);
mpz_t tmp;
mpz_init(tmp);
// Start timing
const clock_t start_time = clock();
while (count > 0) {
if (count % 2 == 0) {
mpz_mul(tmp, q, q);
mpz_mul(q, q, p);
mpz_mul_2exp(q, q, 1);
mpz_add(q, q, tmp);
mpz_mul(p, p, p);
mpz_add(p, p, tmp);
count /= 2;
} else {
mpz_mul(tmp, a, q);
mpz_mul(a, a, p);
mpz_addmul(a, b, q);
mpz_add(a, a, tmp);
mpz_mul(b, b, p);
mpz_add(b, b, tmp);
count -= 1;
}
}
// End timing
const clock_t end_time = clock();
if (end_time == (clock_t){-1})
{
fprintf(stderr, "Error end_time clock()\n");
return EXIT_FAILURE;
}
mpz_out_str(stdout, 10, b);
unsigned int digits = strlen(mpz_get_str(NULL, 10, b));
printf("\n");
// Cleanup
mpz_clear(a);
mpz_clear(b);
mpz_clear(p);
mpz_clear(q);
mpz_clear(tmp);
// Print time taken
const double time_taken = ((double) (end_time - start_time)) / (double) CLOCKS_PER_SEC;
if (printf("Calculation Time: %lf seconds\n", time_taken) < 0)
return EXIT_FAILURE;
if (fflush(stdout) == EOF)
return EXIT_FAILURE;
printf("Number of Digits: %u\n", digits);
return EXIT_SUCCESS;
}
Which also gave me these times:
./fib.exe 100000
Calculation Time: 0.000000 seconds
Number of Digits: 20899
./fib.exe 1000000
Calculation Time: 0.008000 seconds
Number of Digits: 208988
./fib.exe 10000000
Calculation Time: 0.097000 seconds
Number of Digits: 2089877
./fib.exe 100000000
Calculation Time: 1.316000 seconds
Number of Digits: 20898764
./fib.exe 1000000000
Calculation Time: 16.641000 seconds
Number of Digits: 208987640
Fun!
@NoahTheBaker not sure what's going on here, can you test the latest code? that version is a bit outdated
@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb
@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb
after the bit-shift analysis, I replaced the 0.5 with that, I'll send you the full version which I ask you to test right here. perhaps with some optimizations I made a simplification that changes the actual result. I would be happy if you decided to test it in order to exclude quick but incorrect calculations.
@Francesco146 I believe I used the latest one you posted (Oct 27th), at least that's the last one I see aside from your timing script? I could be pulling a dumb
after the bit-shift analysis, I replaced the 0.5 with that, I'll send you the full version which I ask you to test right here. perhaps with some optimizations I made a simplification that changes the actual result. I would be happy if you decided to test it in order to exclude quick but incorrect calculations.
3rd Edit: Fixed a mistake I made
When running your code it gives the following values:
./fibtest.exe 15
fib(15): 0.000000 seconds
0
./fibtest.exe 30
fib(30): 0.000000 seconds
610
./fibtest.exe 1000
fib(1000): 0.000000 seconds
700601527838707533318724871765523284890968696066716357168446685359555050818763462119969522887130023714
./fibtest.exe 10000
fib(10000): 0.000000 seconds
511865913905822858393252140857692303019370496328583286846703611276316160829121874839117811096377890223341760784520464441363883635008221595005409607506796552046773590457456727956781799070386310526276130521173224078490428727580439211685193830890011304948013193753096345077838097891781185513053353450228725836492609250758663599068124138189622708238726010261183052860309857905748834
But running my code gives:
./fib.exe 15
Fibonacci Value: 610
Number of Digits: 3
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0020 seconds
./fib.exe 30
Fibonacci Value: 832040
Number of Digits: 6
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0020 seconds
./fib.exe 1000
Fibonacci Value: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
Number of Digits: 209
./fib.exe 10000
Fibonacci Value: 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088.....
Number of Digits: 2090
Calculation Time: 0.0000 seconds
Total Time Taken: 0.0520 seconds
And checking with WolframAlpha gives:
fib(15) = 610
fib(30) = 832040
fib(1000) = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
fib(10000) = 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088.....
2nd Edit: Here is the current version that I am using with verified Fibonacci values up to F(100,000,000), but I cannot check further than that as WolframAlpha seems to break.
GMP function mpz_fib_ui()
does the same computation. Here's how they compare on my slowest laptop:
./fib 100000000
Calculation Time: 6.037008 seconds
./fib-gmp 100000000
Calculation Time: 1.592325 seconds
./fib 1000000000
Calculation Time: 82.556466 seconds
./fib-gmp 1000000000
Calculation Time: 20.184274 seconds
It uses the low-level mpn_*()
functions with lots of bit shifting and manual memory allocations. A lot of optimization work appears to have gone into it.
@NoahTheBaker i couldn't find the problem in my optimization, you came to what conclusion?
not sure what are you referring to, have you installed the basic libraries?