3

Estoy siguiendo un curso de algoritmos y se veía como resolver el problema de fibonacci de forma eficiente que es con el siguiente código

def fibonacci_list(n):
    f = [0, 1]
    for i in range(2, (n + 1)):
        f.append(f[i - 1] + f[i - 2])

    return f.pop()

print(fibonacci_list(10000))

Hasta ahí todo perfecto funciona bien y el resultado es el esperado. El problema surge por que en el vídeo enseñan la formula matemática para resolver el problema y me pareció interesante probarla, sin embargo al momento de codificar la formula y poner la misma cantidad (n = 10000) sucede un desbordamiento de memoria, ¿No debería funcionar de igual forma? dado que al igual que en fibonacci_list esta haciendo cálculos matemáticos, la función es la siguiente:

def fibonacci_math(n):
    return round(1 / math.sqrt(5) * (((1 + math.sqrt(5)) / 2) ** n - ((1 - math.sqrt(5)) / 2) ** n ))

print(fibonacci_math(10000))

El error es el siguiente:

return round(1 / math.sqrt(5) * ( ((1 + (math.sqrt(5) / 2) ** n) - (1 - math.sqrt(5)) / 2) ** n) )
OverflowError: (34, 'Result too large')

¿Habrá alguna expresión de las que usa en la función que al hacer la operación da demasiados dígitos? La verdad no me queda claro por que da desbordamiento en este caso, en números más pequeños como 1000 por ejemplo si da el número correcto

3
  • 1
    Exactamente, ¿ Que error te da ? No es lo mismo un error de desbordamiento de memoria que un Numerical result out of range.
    – Trauma
    Commented el 1 jul. 2020 a las 19:06
  • Tienes razón se me olvido poner el error el error es el siguiente: return round(1 / math.sqrt(5) * ( ((1 + (math.sqrt(5) / 2) ** n) - (1 - math.sqrt(5)) / 2) ** n) ) OverflowError: (34, 'Result too large') Commented el 1 jul. 2020 a las 19:11
  • 1
    Te sirve esto?
    – user166844
    Commented el 1 jul. 2020 a las 19:20

1 respuesta 1

2

Considera

((1 + math.sqrt(5)) / 2)

que resulta en el valor 1.618033988749895, que es aprox. 10 ** 0,209.

Tomemos n = 1747 (el menor valor donde el calculo falla), y evaluemos

((1 + math.sqrt(5)) / 2) ** 1747

El resultado deberia ser 10 ** 0,209 ** 1747. Reduciendo la expresión queda en 10 ** 365,12.

Sin embargo, en punto flotante el máximo valor posible es 1.7976931348623157e+308. El máximo exponente (base 10) es 308. Ahí es cuando el cálculo falla.

((1 + math.sqrt(5)) / 2) ** 1747
Traceback (most recent call last):
  File "/usr/lib/python3.6/code.py", line 91, in runcode
    exec(code, self.locals)
  File "<input>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')

Observacion: Para ver los rangos del punto flotante:

import sys
sys.float_info

sys.float_info(max=1.7976931348623157e+308, max_exp=1024, max_10_exp=308, min=2.2250738585072014e-308, min_exp=-1021, min_10_exp=-307, dig=15, mant_dig=53, epsilon=2.220446049250313e-16, radix=2, rounds=1)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.