Fibonacci sequence: C vs Python

Question

This is a code I wrote in C for Fibonacci sequence:

#include <stdio.h>
#include <stdlib.h>

int fib(int n)
{
    int a = 0, b = 1, c, i;
    if (n == 0)
        return a;
    for (i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main()
{
    printf("%d",fib(1000));
    return 0;
}

And this is the direct translation in Python:

def fib(n):
    a=0
    b=1
    if n == 0:
        return a

    for _ in range(n-1):
        c = a + b
        a = b
        b = c

    return b

print(fib(1000))

The C program outputs:

1556111435

Where Python (correctly) outputs:

    43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

I realize the problem with C is with the variable type (since the fib(50) works just fine in C), but I have two major questions:

How should I correct the C program in a way that I can calculate fib of any number? In other words, rather than just using double (which has its own limitation), how can I calculate any fib in C?
How does Python handle this? Because apparently, it has no limitation in the size of integers.

@Ctznkane525 instead it ends in n-1, the sequence is just shifted. If you run the code, they both have the same output (for small values). — Amirhossein Rezaei, Apr 11 '21 at 10:55
https://stackoverflow.com/questions/3340511/what-is-the-simplest-way-of-implementing-bigint-in-c — Ctznkane525, Apr 11 '21 at 10:56

soulsource · Answer 1 · 2021-04-12T06:59:01.990

C does not offer any dynamically sized integer types directly. The biggest you can go within the language itself is long long. However there is nothing stopping you from writing your own big-integer functions that allocate memory and handle carry as needed. Or you can just use someone else's big integer lib, for instance BigInt.

(Looking at BigInt's source code will also answer the question how Python does this.)

Edit: I just had a bit of a closer look at BigInt myself. Beware that it uses the regular pen&paper method unconditionally for multiplication, which is fast for "small" numbers, but for "large" numbers has worse performance than the Karatsuba method. However please note that the border between "small" and "large" in this context is probably so high, that in most practical cases the pen&paper method is enough (see the linked Wiki article). It's also worth noting that you can combine both algorithms for multiplication, by writing them recursively and having Karatsuba's method fall back to pen&paper if the number of bits is below a given threshold.

`Or you can just use someone else's big integer lib, for instance` [GNU bignum](https://gmplib.org/) — KamilCuk, Apr 12 '21 at 07:01

Fibonacci sequence: C vs Python

1 Answers1