Fibodigits - count the digits of Fibonacci

Question

I need to find the digits of Fibonacci numbers till 1000 digits.

For example: 1 has 1 digit, 10 has 2 digits, 100 has 3 digits...

The Fibonacci sequence starts this way: 0,1,2,3,5,8,13...

I have to insert 1000 and get as result 4782.

I get 4781 inserting 524 see below. I would like to insert 1000 and get 4782. Is there any possible way to get the length of my stack? In python I could use the len function, in C it will not work :)

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

int main(int s) {
    int i = 1;
    int k = 1;
    int list[1000] = { 0, 1 };
    int fibo = 0;
    int s = -1;
    int divide = 0;
    while (i < 1500) {
        i++;
        fibo = list[i - 1] + list[i - 2];
        if (i == 1000) {
            break;
        } else {
            list[i] = fibo;
            //printf("%d\n", list[i]);
        }
    }

    while (s < 524) {
        s++;
        divide = 0;
        while (list[s] != 0) {
            divide = list[s] / 10;
            list[s] = divide;
            k++;
            if(divide == 0) {
                break;
            }
        } 
    }
    printf("%d\n", k);
}

"Fibonacci has following numbers: 0,1,2,3,5,8,13,..." --> No, but [close](https://en.wikipedia.org/wiki/Fibonacci_number). — chux - Reinstate Monica, Dec 08 '19 at 22:38
Maybe all you need is `int list[1000] = {1,1};` as your stating point is questionable. — chux - Reinstate Monica, Dec 08 '19 at 22:41
I expect `list[i - 1] + list[i - 2]` to readily overflow. Need a wider representation. [example](https://stackoverflow.com/a/34360258/2410359) — chux - Reinstate Monica, Dec 08 '19 at 22:45
@ kelta063 - What do you mean by 1000 digits? Do you mean to reach a number that is 1000 digits? Or do you mean to reach the 1000 number? — Kevin Ng, Dec 08 '19 at 23:32
@kelta063 - Also, c does not store the len of the array at runtime if it decays into a pointer when being pass around. For len, use sizeof(array)/sizeof(datatype). Your case datatype is int. Sizeof give back the size of the array in byte. But if you are going to use sizeof() to get the size of your array. You probably know what it is already. Nonetheless, if you pass that array to another function. The new function will not be able to use sizeof to get the actual size of the array. After it is passed to another function, sizeof() value is the the pointer's size, of which vary by system. — Kevin Ng, Dec 08 '19 at 23:54
@kelta063 - Thus, if you are going to keep length record like Python, there are plenty of methods. For me, I know you can store the len on a separate variable, you can create a struct and store len with data. That is usually the normal method. There are other methods like using the first size_t bytes of the pointer for len. But that is somewhat similar to a struct with len at the first variable and data is the next. — Kevin Ng, Dec 08 '19 at 23:57
@kelta - I explained it like that because it seemed to me that in your code, you want to get the 1000 numbers not the numbers with 1000 digits. — Kevin Ng, Dec 09 '19 at 00:02

score 1 · Accepted Answer · answered Dec 09 '19 at 00:13

Here is a shortcut implementation using an approximation that works well even for very small numbers:

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

int main(int argc, char *argv[]) {
    int n;
    if (argc > 1) {
        n = strtol(argv[1], NULL, 0);
    } else {
        if (scanf("%d", &n) != 1)
            return 1;
    }
    double phi = (1.0 + sqrt(5.0)) / 2.0;
    printf("%g\n", ceil(n / log10(phi) - 3.0));
    return 0;
}

phi is the golden ratio. The Fibonacci sequence converges very quickly to the geometric sequence of the golden ratio. In other words, fib(n) is approximately pow(phi, n - 3). Inverting this equation for 10ⁱ gives the solution.

Thanks for the solution - helped a lot. – keita063 Dec 17 '19 at 14:23 — keita063, Dec 17 '19 at 14:23

score 0 · Answer 2 · answered Dec 08 '19 at 23:54

This simple problem is much more difficult to solve in C than in Python: unlike Python, C does not have multi-precision integer arithmetic by default, so you must implement it yourself, at least for addition, preferably in base 10.

Here is a quick and naive implementation:

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

typedef struct bignum {
    int len;
    unsigned char *digits;
} bignum;

void bignum_init(bignum *a, int v) {
    a->len = 1;
    a->digits = malloc(1);
    if (a->digits == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    a->digits[0] = (unsigned char)v;
}

void bignum_free(bignum *a) {
    free(a->digits);
    a->digits = NULL;
    a->len = 0;
}

void bignum_print(const bignum *a) {
    int i = a->len;
    while (i-- > 0)
        putchar('0' + a->digits[i]);
}

void bignum_add(bignum *c, const bignum *a, const bignum *b) {
    int i, aux;

    if (a->len < b->len) {
        const bignum *tmp = a;
        a = b;
        b = tmp;
    }
    c->digits = realloc(c->digits, a->len + 1);
    if (c->digits == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    for (i = 0, aux = 0; i < b->len; i++) {
        aux += a->digits[i] + b->digits[i];
        c->digits[i] = aux % 10;
        aux /= 10;
    }
    for (; i < a->len; i++) {
        aux += a->digits[i];
        c->digits[i] = aux % 10;
        aux /= 10;
    }
    if (aux != 0) {
        c->digits[i++] = (unsigned char)aux;
    }
    c->len = i;
}

int main(int argc, char *argv[]) {
    int i, n;

    if (argc > 1) {
        n = strtol(argv[1], NULL, 0);
    } else {
        if (scanf("%d", &n) != 1)
            return 1;
    }
    bignum B[3];
    bignum_init(&B[0], 0);
    bignum_init(&B[1], 1);
    bignum_init(&B[2], 1);
    for (i = 3;; i++) {
        bignum_add(&B[i % 3], &B[(i - 1) % 3], &B[(i - 2) % 3]);
        if (B[i % 3].len >= n)
            break;
    }
    printf("%d\n", i);
    // for debugging
    //printf("fib(%d) = ", i);
    //bignum_print(&B[i % 3]);
    //printf("\n");
    bignum_free(&B[0]);
    bignum_free(&B[1]);
    bignum_free(&B[2]);
    return 0;
}

Fibodigits - count the digits of Fibonacci

2 Answers2