Fibonacci 100,000 y 1,000,000 en c

[Fw190]

Simplemente, has excedido el rango disponible para un tipo long double (80 bits), que llega hasta (algo)e+4931. Esto ocurre (en mi compilador) en el término 23599, que es 3.55e+4931 (el término 23600 ya sale Inf). El tipo __float128__ (comienza y termina con dos guiones bajos), no estandar, disponible en GCC desde la versión (creo) 4.3, no te valdría, tiene el mismo alcance (aunque más precisión). Puedes probar suerte con alguna librería multiprecisión, busca por la red.