Нахождение ближайших чисел Фибоначчи

Question

Я пытаюсь решить большую проблему и считаю, что важная часть программы расходуется на неэффективные вычисления.

Мне нужно вычислить для заданного числа N интервал [P, Q], где P - наибольшее число Фибоначчи, которое <= к N, а Q - наименьшее число Фибоначчи, которое> = к N.

В настоящее время я использую карту для записи значений чисел Фибоначчи. Запрос обычно включает в себя поиск всех чисел Фибоначчи до N, и он не очень эффективен по времени, так как требует большого числа сравнений.

Этот тип запросов будет происходить довольно часто в моей программе, и меня интересуют способы, которыми я мог бы улучшить поиск, предпочтительно с сублинейной сложностью.

Answer 1

Числа Фибоначчи задаются формулой Бине

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

, где phi - золотое сечение,

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

. Это может быть реализовано просто (пример Python):

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

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

Из-за ошибок округления с плавающей точкой это, однако, даст только правильный результат для n < 70.

Формула Бине может быть инвертирована путем игнорирования члена (1-phi)^n, который исчезает длябольшой n.Поэтому мы можем определить обратную функцию Фибоначчи, которая при задании F(n) возвращает n (игнорируя это 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)))

Здесь округление используется в наших интересах: оно устраняет введенную ошибкунашей модификацией формулы Бине.Функция фактически вернет правильный ответ, если ей будет дано любое число Фибоначчи, которое можно сохранить как точное целое число в памяти компьютера.С другой стороны, он не проверяет, что данное число на самом деле является числом Фибоначчи;ввод большого числа Фибоначчи или любого близкого к нему числа даст тот же результат.Поэтому вы можете использовать эту идею, чтобы найти число Фибоначчи, наиболее близкое к данному числу.

Идея состоит в том, чтобы применить обратную карту Фибоначчи, чтобы найти N и M, два ближайших числа Фибоначчи с обеих сторон, а затем использовать прямую карту Фибоначчи для вычисления P = F(N) и * 1027.*.Это включает в себя больше вычислений, но меньше поиска.

Answer 2

Я разместил полную реализацию этой концепции на https://ideone.com/H6SAd

• это невероятно быстро
• используется двоичный поиск adhoc
• Редактировать после прочтения других ответов у меня возникает ощущение, что изложенные там математические идеи (PengOne) приведут к более быстрому поиску (в основном: вычисление перевернутой формулы плюс пол ( ) / 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);
}

Вывод:

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 3

Вы можете использовать выражение в замкнутой форме чисел Фибоначчи.

Поскольку второе слагаемое в нем очень мало, вы можете аппроксимировать его только первым слагаемым, поэтому n можно найти с логарифмом базового золотого сечения.

Answer 4

Я только что сделал головоломку CodeChef, которая была именно этой проблемой (http://www.codechef.com/problems/DPC204). Я просто вычислил последовательность Фибоначчи от 0 до конца диапазона и посчитал, сколько их было после начала диапазона. Мой тест на любые ихвходные данные для выборки заняли 2,6 млн. и 0,00 с, поэтому решение nieve достаточно быстрое.

По сути, я создал класс big-unsigned-int из unsigned int[333] и вычислил два числа на цикл,чтобы избежать перестановок.

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.

Это немного усложняется тем, что вам нужно остановиться и проверить, находятся ли ни одно, ни одно, или оба числа в диапазоне, но A

Мое решение на CodeChef работаетза 0,00 секунды, так что я думаю, что этот метод должен быть достаточно быстрым, вам просто нужно написать функцию, которая добавляет один uint[333] к другому uint[333] (используя все 32 бита, просто символы для каждой десятичной цифры)

Answer 5

Используйте формулу закрытой формы: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

Тогда бинарный поиск

Answer 6

Поскольку вы учитываете только 64-битные целые числа, необходимо учитывать не более 100 чисел Фибоначчи.Вы можете предварительно вычислить их, используя их определение F _n = F _n-1 + F _n-2 .

Затем предварительно вычислите другую таблицу, которая отображаетколичество начальных нулевых битов к индексу в таблице чисел Фибоначчи, к первому числу с таким количеством начальных нулевых битов.

Теперь, чтобы найти интервал, используйте количество начальных нулевых битов вашего числа (этоможет быть вычислен быстро, так как многие процессоры имеют специальную инструкцию для него) найти начальную точку, используя вторую таблицу, и выполнить линейный поиск по первой таблице для интервала.Поскольку между соседними степенями двух существует не более двух чисел Фибоначчи, это занимает не более 2 шагов.

Преимущество этого метода в том, что он использует только целочисленную арифметику, которая является точной и имеет тенденцию быть быстрее, чем вычисления с плавающей запятой.

Answer 7

Число есть число Фибоначчи тогда и только тогда, когда один или оба из (5 * n ^ 2 + 4) или (5 * n ^ 2 - 4) - идеальный квадрат. Я использую эту предпосылку, чтобы проверить, принадлежит ли входной номер серии Фибоначчи или нет.

#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 8

Построить таблицу чисел Фибоначчи, которая уместится в 8 байтов; есть только 94. Это поможет вам вычислить их на каждой итерации. Здесь нет необходимости в математике с плавающей точкой.

Затем используйте двоичный поиск, чтобы найти число ниже и выше вашего числа во времени. Это сэкономит вам сравнение всех чисел и сократит ваш поиск до постоянного времени поиска.

Это соответствует вашим требованиям, но обратите внимание, что ваши требования не указывают, что должно быть возвращено для N, так что в 64-битном целочисленном пространстве нет Q, т.е. Если вы заботитесь об этом, решите, как вы хотите справиться с этим. :)

#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;
}

Поместите любой другой алгоритм в тот же файл и запустите его на том же тестере.

Answer 9

Я думаю, что важная часть программы расходуется на неэффективные вычисления.

Вы профилировали свой код? Как общий принцип, не оптимизируйте преждевременно; измерить, какие части замедляют его. Таким образом, когда вы пытаетесь оптимизировать, вы можете сказать, помогла оптимизация или помешала (часто хорошая звуковая оптимизация ухудшит ее работу; как, например, компилятор не сможет выполнить оптимизацию, или вы не сможете использовать свой метод оптимизации). регистры / кэш процессора как оптимально).

Если это то, что вас тормозит, я бы сделал то же самое, что и отличное решение Пенга, но предварительно вычислил все числа Фибоначчи до вашего наибольшего значения и сохранил их в массив, индексированный соответствующей экспозицией (n) из закрытого form (phi^**n - (1-phi)**n)/sqrt(5). Его метод будет неправильно вычислять числа Фибоначчи для больших n с арифметикой с плавающей запятой; если только вы не используете произвольную высокую точность (что является медленным). Таким образом, ваш начальный массив равен fib_array = [0,1,1,2,3,5,8,13,... ]. Затем пренебрегая небольшим членом (1-phi)**n , инвертируйте fib, чтобы найти n (например, fib_inv Пенга), и возьмите fib_array[n] в качестве первой границы. Если эта граница меньше (больше) вашего значения, вы нашли нижнюю (верхнюю) границу и так другая граница должна быть fib_array[n+1] (fib_array[n-1]).
Или, если вы хотите вычислить его, используйте что-то из заданного N, которое лучше, чем формула Бине. http://en.literateprograms.org/Fibonacci_numbers_%28Python%29

Лично я бы удостоверился, что вторая граница находится на противоположной стороне термина от первой границы (в редких случаях, когда мы не должны были пренебрегать термином (1-phi)**n; вы могли бы сделать к другому поиску, видя, ограничен ли термин, например, fib_array[n+1] и fib_array[n+2]). (Эта проверка может быть излишней; но сначала вам нужно будет это доказать, и одно дополнительное сравнение для обеспечения безопасности, похоже, стоит в моей книге).

Answer 10

Используя последнюю форму здесь для инверсии, вы можете найти два индекса для чисел Фибоначчи вокруг текущего числа. http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

log(N * sqrt(5)) / log((1+sqrt(5))/2) должен дать вам число, которое находится между двумя целочисленными индексами для P и Q. Затем вы можете использовать закрытую форму (как показано в других ответах), чтобы дать действительные числа P и Q.

Обратите внимание, что вы можете быть выключены на один в зависимости от ваших начальных условий Фибоначчи.