c++ - serie - sucesion de fibonacci ejercicios

Encontrar los números de fibonacci más cercanos

Question

Estoy tratando de resolver un problema mayor, y creo que una parte importante del programa se gasta en cálculos ineficientes.

Necesito calcular para un número dado N, el intervalo [P, Q], donde P es el mayor número de fibonacci que es <= a N, y Q es el menor número de fibonacci que es> = a N.

Actualmente, estoy usando un mapa para registrar el valor de los números de fibonacci. Una consulta normalmente implica buscar todos los números de fibonacci hasta N, y no es muy eficiente en el tiempo, ya que implica un gran número de comparaciones.

Este tipo de consultas ocurrirán con bastante frecuencia en mi programa, y ​​estoy interesado en las formas en que podría mejorar la búsqueda, preferiblemente con complejidad sub-lineal.

Answer 1

Creo que una parte importante del programa se gasta en cálculos ineficientes.

¿Has profiled tu código? Como principio general no se optimiza prematuramente; mida qué partes lo están ralentizando. De esa manera, cuando intente la optimización, puede saber si las optimizaciones le ayudaron o perjudicaron (a menudo, una buena optimización de sonidos lo hará funcionar peor; como dice el compilador no podrá hacer sus optimizaciones o no podrá usar su los registros de la CPU / caché como óptimamente).

Si esto es lo que te está ralentizando, haría una gran solución similar a la de Peng, pero pre-computaría todos los números de Fib hasta tu valor más grande y los almacenaría en una matriz indexada por la correspondiente exposición (n) desde la forma cerrada ( phi^**n - (1-phi)**n)/sqrt(5) . Su método calculará mal los números de Fib para n grande con aritmética de punto flotante; a menos que utilice alta precisión arbitraria (que es lento). Entonces su matriz inicial es fib_array = [0,1,1,2,3,5,8,13,... ] . Luego, descuide el término pequeño (1-phi)**n , invierta fib para encontrar n (p. Ej., fib_inv de Peng) y tome fib_array[n] como su primer enlace. Si este límite es más pequeño (más grande) que su valor; ha encontrado el límite inferior (superior), por lo que el otro límite debería ser fib_array[n+1] ( fib_array[n-1] ).
O si quieres calcularlo, usa algo de una N que sea mejor que la fórmula de Binet. http://en.literateprograms.org/Fibonacci_numbers_%28Python%29

Personalmente, me aseguraría de que el segundo límite esté en el lado opuesto del término como el primer límite (en casos raros en los que no deberíamos haber descuidado el término (1-phi)**n ; posiblemente podría fib_array[n+1] si el término está delimitado por, por ejemplo, fib_array[n+1] y fib_array[n+2] ). (Esta verificación puede ser redundante; pero primero tendría que demostrarlo, y la comparación adicional para estar seguro parece valer la pena en mi libro).

Answer 2

Acabo de hacer un rompecabezas de CodeChef que era este problema exacto (http://www.codechef.com/problems/DPC204). Simplemente calculé la secuencia de Fibonacci desde 0 hasta el final del rango, y conté cuántos estaban después del comienzo del rango. Mi prueba para lo que sea que tomaron sus muestras de muestra fue de 2.6M y 0.00s, por lo que la solución de nieve es bastante rápida.

Básicamente, hice una clase int-unsigned grande hecha de unsigned int[333] , y calculo dos números por bucle, para evitar intercambios.

start with A=0,B=1;
A+=B;B+=A; 
now A==1,B==2, the next two Fib. numbers, with no swaps.
A+=B;B+=A; 
now A==3,B==5, the next two Fib. numbers, with no swaps.

Es un poco complicado por el hecho de que tiene que detenerse y verificar si los números de uno, uno o ambos están en el rango, pero A

Mi solución en CodeChef registró 0,00 segundos, por lo que creo que este método debería ser lo suficientemente rápido, solo tiene que escribir una función que agregue una uint[333] a otra uint[333] (usando los 32 bits, solo los caracteres para cada dígito decimal)

Answer 3

Construye una tabla de números de Fibonacci que caben en 8 bytes; solo hay 94. Eso te ahorrará calcularlos a través de cada iteración. No hay necesidad de matemáticas de punto flotante aquí.

Luego use una búsqueda binaria para encontrar el número debajo y arriba de su número en el tiempo. Eso le ahorrará la comparación de todos los números y reducirá su búsqueda a un tiempo de búsqueda constante.

Esto cumple con sus requisitos, pero tenga en cuenta que sus requisitos no especifican lo que debe devolverse para N, por lo que no hay Q en el espacio entero de 64 bits, es decir, N> 12,200,160,415,121,876,738. Si te importa eso, decide cómo quieres manejarlo. :)

#include "stdint.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"

/* build a table of all fibonacci numbers that fit in a uint64_t. */
static const int fibonacciCount = 94;
uint64_t fibonacciSequence[fibonacciCount];
static void precalc(void) {
    fibonacciSequence[0] = 0;
    fibonacciSequence[1] = 1;
    for (int i = 2; i < fibonacciCount; ++i) {
        fibonacciSequence[i] = fibonacciSequence[i-2] + fibonacciSequence[i-1];
    }
}

/* do a binary search for the Fibonacci numbers >= N and <= N */
static void find_closest_fibonacci(uint64_t N, uint64_t *P, uint64_t *Q) {
    int upper = fibonacciCount;
    int lower = 0;
    do {
        int mid = ((upper - lower) >> 1) + lower;
        uint64_t midValue = fibonacciSequence[mid];
        if ( midValue > N ) {
            upper = mid;
        } else if ( midValue < N ) {
            lower = mid + 1;
        } else {
            *P = fibonacciSequence[ mid ];
            *Q = fibonacciSequence[ mid ];
            return;
        }
    } while ( upper > lower );
    *P = fibonacciSequence[ lower - 1 ];
    *Q = fibonacciSequence[ lower ];
}

/* hacked together 64 bit random number generator,
 used just in tester only */
static uint64_t rand64(void) {
    /* totally flawed as a random number generator,
     but that''s not the point here. */
    uint64_t v = 0;
    for (int i = 0; i < 8; ++i) {
        v = (v << 8) + (rand() % 256);
    }
    return v;
}

int main (int argc, const char * argv[]) {
    srand( (unsigned)time( NULL ) );

    precalc(); /* do this once only */

    uint64_t upperBound = fibonacciSequence[fibonacciCount - 1];
    printf( "Upper bound is %qu/n", upperBound );

    /* build a sample to run against the algorithm
     we favor mostly numbers below RAND_MAX, because
     if we test across all of UINT64_MAX the results are
     pretty boring. */
    static const int sampleCount = 100;
    static const int normalSampleCount = 90;
    uint64_t numbers[sampleCount];
    for (int i = 0; i < normalSampleCount; ++i) {
        numbers[i] = rand();
    }
    for (int i = normalSampleCount; i < sampleCount; ++i) {
        uint64_t number;
        do {
            number = rand64();
        } while ( number > upperBound );
        numbers[i] = number;
    }

    /* use described algorithm */
    for (int i = 0; i < 100; ++i) {
        uint64_t P;
        uint64_t Q;
        uint64_t N = numbers[i];
        find_closest_fibonacci(N, &P, &Q);
        printf( "%qu [%qu,%qu]/n", N, P, Q );
    }

    return 0;
}

Coloque cualquier otro algoritmo que tenga en el mismo archivo y ejecútelo contra el mismo comprobador.

Answer 4

Dado que considera solo enteros de 64 bits, hay como máximo unos 100 números de Fibonacci para considerar. Puede precalibrarlos usando su definición F _n = F _n-1 + F _n-2 .

Luego precaliente otra tabla que asigne el número de bits de cero iniciales a un índice en la tabla de números de Fibonacci, al primer número con tantos bits de cero iniciales.

Ahora, para encontrar el intervalo, use el número de bits de cero iniciales de su número (esto se puede calcular rápidamente ya que muchos procesadores tienen una instrucción especial para ello) para encontrar un punto de inicio utilizando la segunda tabla, y buscar linealmente en la primera tabla intervalo. Dado que hay a lo sumo dos números de Fibonacci entre potencias adyacentes de dos, esto toma como máximo 2 pasos.

Esto tiene la ventaja de que solo utiliza la aritmética de enteros, que es exacta y tiende a ser más rápida que los cálculos de punto flotante.

Answer 5

Los números de Fibonacci están dados por la fórmula de Binet

F(n) = ( phi^n - (1-phi)^n ) / /sqrt{5}

donde phi es la proporción de oro,

phi = (1 + /sqrt{5}) / 2. 

Esto se puede implementar directamente (ejemplo de Python):

<<fibonacci_binet.py>>=
phi = (1 + 5**0.5) / 2

def fib(n):
    return int(round((phi**n - (1-phi)**n) / 5**0.5))

Debido a los errores de redondeo de punto flotante, esto solo dará el resultado correcto para n < 70 .

La fórmula de Binet se puede invertir al ignorar el término (1-phi)^n , que desaparece para n grande. Por lo tanto, podemos definir la función de Fibonacci inversa que, cuando se le da F(n) , devuelve n (ignorando que F(1) = F(2) ):

<<fibonacci_binet.py>>=
from math import log

def fibinv(f):
    if f < 2:
        return f
    return int(round(log(f * 5**0.5) / log(phi)))

Aquí el redondeo se utiliza para nuestra ventaja: elimina el error introducido por nuestra modificación a la fórmula de Binet. De hecho, la función devolverá la respuesta correcta cuando se le asigne cualquier número de Fibonacci que pueda almacenarse como un número entero exacto en la memoria de la computadora. Por otro lado, no verifica que el número dado sea realmente un número de Fibonacci; ingresar un número grande de Fibonacci o cualquier número cercano a él dará el mismo resultado. Por lo tanto, puede utilizar esta idea para encontrar el número de Fibonacci más cercano a un número dado.

La idea, entonces, es aplicar el mapa de Fibonacci inverso para encontrar N y M , los dos números de Fibonacci más cercanos en cada lado, luego usar el mapa de Fibonacci directo para calcular P = F(N) y Q = F(M) . Esto implica más computación, pero menos búsqueda.

Answer 6

Publiqué una implementación completa de Prueba de concepto de esto en https://ideone.com/H6SAd

• es increíblemente rápido
• utiliza una búsqueda binaria adhoc
• Después de leer las otras respuestas, tengo la sensación de que las ideas matemáticas que se describen allí (PengOne) llevarán a una búsqueda más rápida (básicamente: ¿un cálculo de la fórmula invertida más una llamada floor () / ceil ()?)

.

#include <cmath>
#include <iostream>

const double pheta = 0.5*(std::sqrt(5)+1);

double fib(unsigned int n)
{
    return (std::pow(pheta, n) - std::pow(1 - pheta, n)) / std::sqrt(5);
}

unsigned int fibo_lowerbound(double N, unsigned min=0, unsigned max=1000)
{
    unsigned newpivot = (min+max)/2;
    if (min==newpivot)
        return newpivot;

    if (fib(newpivot) <= N)
        return fibo_lowerbound(N, newpivot, max);
    else
        return fibo_lowerbound(N, min, newpivot);
}

std::pair<double, double> fibo_range(unsigned int n)
{
    unsigned int lbound = fibo_lowerbound(n);
    return std::make_pair(fib(lbound), fib(lbound+1));
}

void display(unsigned int n)
{
    std::pair<double, double> range = fibo_range(n);
    std::cout << "Fibonacci range wrapping " << n << " is "
              << "[" << (unsigned long long) range.first << ", " << (unsigned long long) range.second << "]"
              << std::endl;
}

int main()
{
    display(1044);
    display(8999913);
    display(7);
    display(67);
}

La salida es:

Fibonacci range wrapping 1044 is [987, 1597]
Fibonacci range wrapping 8999913 is [5702887, 9227465]
Fibonacci range wrapping 7 is [5, 8]
Fibonacci range wrapping 67 is [55, 89]

Answer 7

Puede utilizar la expresión de forma cerrada de los números de fibonacci.

Dado que el segundo término es muy pequeño, puede aproximarlo con solo el primer término, por lo que n puede encontrarse con el logaritmo de relación base-dorada.

Answer 8

Un número es Fibonacci si y solo si uno o ambos de (5 * n ^ 2 + 4) o (5 * n ^ 2 - 4) es un cuadrado perfecto. Estoy usando esta premisa para verificar si el número de entrada pertenece o no a una serie de fibonacci.

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

typedef struct node{

    int64_t value;
    struct node *next;

}Node;

Node *head ;

void readElements(int);
int isPerfectSquare(int64_t sqrValue);

int main(){

    int input_count , flag=0;
    Node *temp_node = NULL;
    int64_t sqrValue = 0;

    scanf("%d" , &input_count);

    if((input_count < 1 )||(input_count > 100000)){
        printf("Total number of Inputs out of Range ..!!/n");
        return 1;
    }

    readElements(input_count);

    /*Reading the elements from the list*/

    temp_node = head;

    while(temp_node != NULL){

        sqrValue = 5*pow(temp_node->value , 2);
        flag = (isPerfectSquare(sqrValue+4) || isPerfectSquare(sqrValue-4));

        if(flag == 1){
            printf("IsFibo/n");
        }
        else{
            printf("IsNotFibo/n");
        }

        temp_node = temp_node->next;

    }   



    return 0;

}


void readElements(int input_count){

    int temp = 0;
    int64_t val = 0;
    Node *temp_node =NULL , *cur = NULL;
    char b[20];


    while (temp < input_count) {

        scanf("%s" , b);
        val = atol(b);

        if(val < 0 || val >10000000000)
            continue;

        temp_node = (Node*) malloc(sizeof(Node));

        temp_node->value = val;
        temp_node->next = NULL;

        if(head == NULL){
            head = cur = temp_node;
        }
        else{
            cur->next = temp_node;
            cur = temp_node;
        }

        temp++;

    }

}

int isPerfectSquare(int64_t sqrValue){

    int64_t s = 0;

    s = sqrt(sqrValue);

    return(s*s == sqrValue);

}

Answer 9

Usando la última forma aquí para el inverso, puede encontrar los dos índices para los números Fib alrededor del número actual. http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

log(N * sqrt(5)) / log((1+sqrt(5))/2) le dará un número que se encuentra entre los dos índices enteros para P y Q Luego puede usar la forma cerrada (como se muestra en las otras respuestas) para dar los números reales P y Q

Tenga en cuenta que puede estar apagado en uno dependiendo de sus condiciones iniciales de Fib.

Answer 10

Use la fórmula de formulario cerrado: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

Entonces busco binario