Calculating the 100th Fibonacci number

help
1

How to calculate 100th Fibonacci number in C ?

As 100th fibonacci number is 21 digits long, how to deal with it?

2

Not too sure about big integer limits for C.
But if you understand python, here’s an easy solution.

3

But I need it in C language.
I don’t think it is possible using any integer data type in C, so can we calculate this using character array or any other approach ?

4

Even unsigned long long int will not be sufficient to store 100^{th} Fibonacci Number. Anyways, you can calculate 100^{th} Fibonacci number using character arrays - by defining your own methods to add numbers represented as strings.

5

Here’s the code I’ve worked on:

C Code 
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct big_integer {
    int sign;
    char *digits;
    int size;
} big_integer;

big_integer new_big_integer(char* num) {
    if(num[0] == '-') {
        big_integer bi = {-1, num + 1, strlen(num) - 1};
        return bi;
    }
    else if(num[0] == '+') {
        big_integer bi = {1, num + 1, strlen(num) - 1};
        return bi;
    }
    else {
        big_integer bi = {1, num, strlen(num)};
        return bi;
    }
}

bool equal(big_integer a, big_integer b) {
    if (a.sign != b.sign) return false;
    if (a.size != b.size) return false;
    for (int i = 0; i < a.size; i++) {
        if (a.digits[i] != b.digits[i]) return false;
    }
    return true;
}

bool greater(big_integer num1, big_integer num2) {
    if (num1.sign != num2.sign) return num1.sign > num2.sign;
    if (num1.size != num2.size) return num1.size > num2.size;
    for (int i = num1.size - 1; i >= 0; i--) {
        if (num1.digits[i] != num2.digits[i]) return num1.digits[i] > num2.digits[i];
    }
    return false;
}

bool smaller(big_integer num1, big_integer num2) {
    if (num1.sign != num2.sign) return num1.sign < num2.sign;
    if (num1.size != num2.size) return num1.size < num2.size;
    for (int i = num1.size - 1; i >= 0; i--) {
        if (num1.digits[i] != num2.digits[i]) return num1.digits[i] < num2.digits[i];
    }
    return false;
}

big_integer add(big_integer num1, big_integer num2) {
    if (num1.sign == num2.sign) {
        big_integer res = {num1.sign, NULL, 0};
        res.size = num1.size > num2.size ? num1.size : num2.size;
        res.digits = (char*)malloc(sizeof(char) * res.size);
        int carry = 0;
        for (int i = 0; i < res.size; i++) {
            int digit1 = (i < num1.size ? num1.digits[i] : '0') - '0';
            int digit2 = (i < num2.size ? num2.digits[i] : '0') - '0';
            int sum = digit1 + digit2 + carry;
            res.digits[i] = '0' + sum % 10;
            carry = sum / 10;
        }
        if (carry) {
            res.digits[res.size] = carry + '0';
            res.size++;
        }
        return res;
    }
    else {
        big_integer res = {num1.sign * num2.sign, NULL, 0};
        res.size = num1.size > num2.size ? num1.size : num2.size;
        res.digits = (char*)malloc(sizeof(char) * res.size);
        int carry = 0;
        for (int i = 0; i < res.size; i++) {
            int digit1 = (i < num1.size ? num1.digits[i] : '0') - '0';
            int digit2 = (i < num2.size ? num2.digits[i] : '0') - '0';
            int sum = digit1 + digit2 + carry;
            if (sum >= 10) {
                res.digits[i] = sum - 10 + '0';
                carry = 1;
            }
            else {
                res.digits[i] = sum + '0';
                carry = 0;
            }
        }
        if (carry) {
            res.digits[res.size] = carry + '0';
            res.size++;
        }
        return res;
    }
}

char* to_string(big_integer num) {
    char *res = (char*)malloc(sizeof(char) * (num.size + 1));
    for (int i = 0; i < num.size; i++) {
        res[i] = num.digits[num.size - i - 1];
    }
    res[num.size] = '\0';
    return res;
}

int main() {
    big_integer fib[101];
    fib[0] = new_big_integer("0");
    fib[1] = new_big_integer("1");
    for (int i = 2; i < 101; i++) {
        fib[i] = add(fib[i - 1], fib[i - 2]);
    }
    printf("100th fibonacci Number: %s\n", to_string(fib[100]));

    return 0;
}
2 Likes