Поиск ближайших чисел фибоначчи

Ответ 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) и Q = F(M). Это требует большего количества вычислений, но меньше поиска.

Ответ 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]

Ответ 3

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

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

Ответ 4

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

Затем двоичный поиск

Ответ 5

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

В принципе, я сделал класс с большим 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 бита, просто символы для каждой десятичной цифры)

Ответ 6

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

Если это то, что замедляет вас, я бы сделал подобное Peng большое решение, но предварительно вычислил все номера Fib до вашего наибольшего значения и сохранил их в массиве, индексированном соответствующим экспонентом (n) form (phi^**n - (1-phi)**n)/sqrt(5)). Его метод будет ошибочным включать числа Fib для больших n с арифметикой с плавающей запятой, если вы не используете произвольную высокую точность (которая медленная). Таким образом, ваш начальный массив fib_array = [0,1,1,2,3,5,8,13,... ]. Тогда пренебрегая малым членом (1-phi)**n, инвертируйте фид, чтобы найти n (например, Peng 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]). (Эта проверка может быть излишней, но сначала вам нужно будет доказать это, и одно дополнительное сравнение будет безопасным в моей книге).

Ответ 9

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

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

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

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

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

Ответ 10

На Scala найти шкаф Фибоначчи также выглядит очень просто:

val phi = (1 + sqrt(5))/2
def fib(n: Long): Long =  round( ( pow(phi,n) -  pow((1-phi),n) ) / sqrt(5)  )
def fibinv(f: Long): Long =  if (f < 2) f else round( log(f * sqrt(5) ) /log(phi))

Ответ 11

Число является Фибоначчи тогда и только тогда, когда один или оба из (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);

}