Euler #25

https://projecteuler.net/problem=25 => 1000-digit Fibonacci number

Volvemos a intentar cumplir los nuevos propósitos: vamos a probar con un lenguaje que no conocemos: Go.

Primera aproximación, por fuerza bruta, tras varias horas, no obtenemos resultado alguno:

package main

import ("math"
        "fmt")

func fib(n int) int {
    if n <= 2 {
        return 1
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    nDigits := 1000
    limit := int(math.Pow(10, float64(nDigits) - 1)) - 1    
    index := 1
    for {
        num := fib(index)
        if num > limit {
            fmt.Printf("Index => %d\n", index)
            return
        }
        index++
    } 
}

El problema es que cada vez que iteramos, se empieza todo de nuevo. La mejora que vamos a intentar es ir guardando los números de Fibonacci que vamos generando en algún tipo de estructura de datos. Al igual que con C cuando manejamos enteros muy grandes, nos volvemos a encontrar con problemas de desbordamiento, hay que utilizar números enteros de precisión arbitraria (definidos en el package math/big de Go). Al implementarlo, de nuevo, me siento desbordado con los detalles del lenguaje y me doy por vencido, como en el anterior intento, que dejé la implementación en Perl sin hacer.

Implementamos en Python:

fib_numbers_cache = {}

def fib(num):
 if num in fib_numbers_cache:
  return fib_numbers_cache[num]
 if num <= 2:
  fibNum = 1
 else:
  fibNum = fib(num - 1) + fib(num - 2)
 fib_numbers_cache[num] = fibNum
 return fibNum

n = 1
n_digits = 1000
fib_num_max = 10**(n_digits - 1) - 1
while True:
 fn = fib(n)
 if fn > fib_num_max:
  print "END: ", n, "=>", fn
  break
 n += 1

Tras varios intentos de implementar las cosas en distintos lenguajes, siempre vuelvo al que más me gusta, que es Python ;)