Project Euler - Problema 2 en R

Continuamos con los problemas planteados en Project Euler.

Problema

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Cada nuevo término en la sucesión de Fibonacci se genera mediante la adición de los dos términos anteriores. Al comenzar con 1 y 2 , los primeros 10 términos serán:

1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , ...

De los términos de la sucesión de Fibonacci cuyos valores no superan los cuatro millones, hallar la suma de aquellos que son pares.

Solución

Creando nuestra función

fib <- function(n) {
    a = 0
    b = 1
    for (i in 1:n) {
        tmp = b
        b = a
        a = a + tmp
    }
    return(a)
}
x <- sapply(1:33, fib)
sum(x[x%%2 == 0]) 

Utilizamos el paquete numbers

require(numbers) # función Fibonacci 
x <- fibonacci(33, TRUE) # Secuencia de números Fibonacci. Ver notas.
even <- x%%2 == 0 # Par o impar
df <- data.frame(x, even)
sum(df[even == TRUE, ]$x)

# Con la función subset
sum(subset(df, even == TRUE)$x) 

# Empleando el paquete dplyr
require(dplyr)
filter(df, even == TRUE) %>% summarise(sum(x))

[1] 4613732

Notas

Creamos la secuencia de números Fibonacci de 34 hacia abajo pues fibonacci(34) es el primero en exceder los 4 millones: 5702887. Por tanto, no sería necesaria la condición < 4000000, pero la dejamos como referencias por si hubiéramos partido de un número Fibonacci mayor.

fibonacci(33)

[1] 3524578

fibonacci(34)

[1] 5702887

Referencias

• Project Euler - Problema 1 en R
• Problem 2
• numbers
• dplyr

Sucesión de Fibonacci en R

Para calcular números de la secuencia de Fibonacci en R, he empleado el código de Neha Pandey

fib <- function(n) {
    a = 0
    b = 1
    for (i in 1:n) {
        tmp = b
        b = a
        a = a + tmp
    }
    return(a)
}
print(fib(79), digits=20)

Sin embargo, si el número sobrepasa los 16 dígitos, de fib(79) en adelante, obtenemos resultados imprecisos. Por ejemplo: fib(79) = 14472334024676220 cuando el resultado correcto es: fib(79) = 14472334024676221.

fib(77) = 5527939700884757 16 dígitos
+
fib(78) = 8944394323791464 16 dígitos
=
fib(79) = 14472334024676221 17 dígitos

Esto es debido a que R almacena los números como números de doble precisión. Una precisión de 53 bits (16 dígitos decimales significativos aproximadamente.

Resolvemos el problema usando el paquete gmp (Multiple Precision Arithmetic). Específicamente la función add.bigz, con la que sumamos bigz (Large Sized Integer Values) números enteros muy grandes.

install.packages("gmp")
require(gmp)
fib <- function(n) {
    a = 0
    b = 1
    for (i in 1:n) {
        tmp = b
        b = a
        a = add.bigz(a, tmp)  # gmp function
    }
    return(a)
}
fib(79)

Así calculamos correctamente números de más de 16 dígitos. He comprobado los resultados para números mucho más largos fib(25000), 5225 dígitos, y los resultados parecen ser precisos hasta el último dígito.

R al igual que otros lenguajes tiene limitaciones internas. Aunque en la práctica es poco probable que topemos con ellas, es útil tenerlas presentes y, si es posible, ser capaces de sobrepasarlas. En este caso, ya sabemos como sortear la limitación en la precisión de los cálculos más allá de los 16 dígitos con el paquete gmp.

Referencias:

Double-precision floating-point format
R Accuracy
?double en la consola de R

Entradas relacionadas:
Sucesión de Fibonacci en Excel y VBA

Sucesión de Fibonacci en Excel y VBA

La sucesión de Fibonacci es una sucesión infinita en la que los dos primeros elementos son 0 y 1, y los siguientes términos son la suma de los dos anteriores:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...

En Excel podemos generar la sucesión mediante fórmulas. Sumamos los dos primeros elementos y arrastramos el controlador de relleno.

Sin embargo, como el elemento 74, fib(74) = 1304969544928657, excede los 15 dígitos, Excel devuelve un número incorrecto: 1304969544928660.

Microsoft Excel admite un máximo de 15 dígitos significativos en todo momento. Este límite se aplica a un valor que se calcula mediante una fórmula. Debido a esta limitación, en cualquier momento una fórmula calcula un valor que supere los 15 dígitos de longitud, dígitos más allá el decimoquinto dígito significativo se cambian a ceros.

Función

Para resolver este comportamiento recurrimos a VBA. Traté con el código publicado en rosettacode.org. Pero fib(46) provoca un desbordamiento. Además, provocaría siempre el desbordamiento un término antes del máximo posible porque calcula el próximo nº Fibonacci un término antes de lo necesario, .

'Desbordamiento en fib(46)
Public Function Fib(n As Integer) As Long
    Dim fib0, fib1, sum As Long
    Dim i As Integer
    fib0 = 0
    fib1 = 1
    For i = 1 To n
        sum = fib0 + fib1 'Calcula nº siguiente antes de tiempo
        fib0 = fib1
        fib1 = sum
    Next
    Fib = fib0
End Function

Finalmente, ver notas abajo, modificando este código consigo calcular hasta fib(139) sin desbordamiento.

'Desbordamiento en fib(139)
Public Function Fibonacci(ByVal n As Long)
    Dim i As Long
    Dim a As Variant, b As Variant, tmp As Variant
    a = 0
    b = 1
    For i = 1 To n
        tmp = b
        b = a
        a = CDec(a + tmp) 'Conversión de Variant a Decimal
    Next
    Fibonacci = CStr(a) 'Mostrar todos los dígitos como texto
End Function

Subrutina

A continuación transformamos la función definida por el usuario (FDU) anterior en subrutina. En el cuadro de diálogo escribimos el número Fibonacci que queremos calcular.

'Desbordamiento en fib(139)
Sub Secuencia_Fibonacci()
    n = VBA.InputBox("Número de la serie Fibonacci a calcular. Máx. 139.")
    Dim i As Long
    Dim a As Variant, b As Variant, tmp As Variant
    a = 0
    b = 1
    For i = 1 To n
        tmp = b
        b = a
        a = CDec(a + tmp) 
    Next
    MsgBox "Fib(" & n & ")= " & a, vbInformation 
End Sub
End Sub

Notas

Necesitamos forzar la conversión del resultado a = CDec(a + tmp) con CDec de Variant a Decimal (28 dígitos). De esta manera, evitamos que VBA pierda la precisión necesaria y redondee a 15 dígitos a partir de fib(74) = 1,30496954492866E+15 en lugar de 1304969544928657 (16 dígitos). No podemos declarar las variables como Decimal directamente. Debemos definirlas como Variant y luego asignarles el tipo Decimal. Finalmente, convertimos el resultado de la función en texto con CStr para que Excel conserve todos los dígitos en las celdas y no vuelva redondear a 15 dígitos.

En cualquier caso, el término máximo de la sucesión Fibonacci que Excel puede calcular es el 139. Pues fib(140) = 81055900096023504197206408605 excede el valor máximo que Excel puede usar: 79228162514264337593543950335.

Referencias:

Límite de 15 dígitos.
Definir variable como Decimal.
Calculadora de sucesión de Fibonacci

Entradas relacionadas:
Sucesión de Fibonacci en R