Как я могу ускорить реализацию Project Euler 25, чтобы я мог вычислить ответ?

Question

Вот моя реализация Задача 25 - Project Euler (см. Комментарии в коде для объяснения того, как это работает):

#include <iostream> //Declare headers and use correct namespace
#include <math.h>

using namespace std;

//Variables for the equation F_n(newTerm) = F_n-1(prevTerm) + Fn_2(currentTerm)
unsigned long long newTerm = 0;
unsigned long long prevTerm = 1; //F_1 initially = 1
unsigned long long currentTerm = 1; //F_2 initially = 2

unsigned long long termNo = 2; //Current number for the term

void getNextTerms() { //Iterates through the Fib sequence, by changing the global variables.
    newTerm = prevTerm + currentTerm; //First run: newTerm = 2
    unsigned long long temp = currentTerm; //temp = 1
    currentTerm = newTerm; //currentTerm = 2
    prevTerm = temp; //prevTerm = 1
    termNo++; //termNo = 3
}

unsigned long long getLength(unsigned long long number) //Returns the length of the number
{
    unsigned long long length = 0;
    while (number >= 1) {
        number = number / 10;
        length++;
    }
    return length;
}

int main (int argc, const char * argv[])
{
    while (true) {
        getNextTerms(); //Gets next term in the Fib sequence
        if (getLength(currentTerm) < 1000) { //Checks if the next terms size is less than the desired length
        }
        else { //Otherwise if it is perfect print out the term.
            cout << termNo;
            break;
        }
    }
}

Это работает для примера и будет работать до тех пор, пока эта строка:

        if (getLength(currentTerm) < 1000) { //Checks if the next term's size is less than the desired length

говорит 20 или ниже вместо 1000. Но если это число больше 20, это займет целую вечность, мое терпение одержит верх и я остановлю программу, как я могу сделать этот алгоритм более эффективным?

Если у вас есть какие-либо вопросы, просто задавайте их в комментариях.

Answer 1

Существует замкнутая формула для чисел Фибоначчи (а также для любой линейной рекуррентной последовательности).

То есть F_n = C1 * a^n + C2 * b^n, где C1, C2, a и b являются числами, которые можно найти из начальных условий, то есть для случая Fib из

F_n + 2 = F_n + 1 + F_n

F_1 = 1

F_2 = 1

Я не даю их значения специально. Это просто подсказка.

Answer 2

nth число Фибоначчи is =

(g1^n-g2^n)/sqrt(5). 
where g1 = (1+sqrt(5))/2 = 1.61803399
      g2 = (1-sqrt(5))/2 = -0.61803399

Для нахождения длины n-го числа Фибоначчи мы можем просто вычислить логарифм (n-е число Фибоначчи). Таким образом, длина n-го числа Фибоначчи равна,

 log((g1^n-g2^n)/sqrt(5)) = log(g1^n-g2^n)-0.5*log(5).
 you can just ignore g2^n, since it is very small negative number.

Следовательно, длина n-го Фибоначчи равна

n*log(g1)-0.5*log(5)

и нам нужно найти наименьшее значение 'n', такое, что эта длина = 1000, поэтому мы можем найти значение n, для которого длина чуть больше 999.

Итак,

n*log(g1)-0.5*log(5) > 999
n*log(g1) > 999+0.5*log(5)
n > (999+0.5*log(5))/log(g1)
n > (999.3494850021680094)/(0.20898764058551)
n > 4781.859263075

Следовательно, наименьшее необходимое n - 4782. Никакого кодирования не используется, самый простой способ.

Примечание: везде используется журнал в базе 10.

Answer 3

Это, вероятно, ускорит процесс:

int getLength(unsigned long long number) //Returns the length of the number when expressed in base-10
{
    return (int)log10(number) + 1;
}

... но вы не можете набрать 1000 цифр, используя unsigned long long. Я предлагаю изучить арифметические библиотеки произвольной точности или языки, в которые встроена арифметика произвольной точности.

Answer 4

Я просто использовал рекурсивную функцию, которая добавляет массивы по вертикали, чтобы завершить задачу. В основном нулевое время выполнения, менее 50 строк кода. Наслаждайтесь:

#include <stdio.h>

int Calc_Fib (int numA[], int numB[], int temp[], int index) {
    int i = 0;

    //Check 1000th digit for non-zero value.
    if (numB[999] != 0) return index;

    //Add arrays A and B vertically.
    for (i = 0; i < 1000; ++i)   {
        temp[i] += (numA[i] + numB[i]);

        if (temp[i] > 9)   {
            temp[i + 1] = temp[i] / 10;
            temp[i] %= 10;
        }

        numA[i] = numB[i];
        numB[i] = temp[i];
        temp[i] = 0;
    }
    Calc_Fib(numA, numB, temp, ++index);
}

int main()  {
    int numA[1000];   //Holds previous term.
    int numB[1000];   //Holds current term.
    int temp[1000];   //Holds temporary number for vertical addition.
    int i        = 0;
    int indexVal = 2;

    for (i = 0; i < 1000; ++i)  {
        numA[i] = 0;
        numB[i] = 0;
        temp[i] = 0;
    }

    //Initialize first two terms.
    numA[0] = (numB[0] = 1);

    indexVal = Calc_Fib(numA, numB, temp, indexVal);

    printf("Tada: %d\n", indexVal);

    return 0;
}

Answer 5

C ++ код может быть следующим:

#include "iostream"
#include "string.h"
#include "algorithm"
using namespace std;

string addTwoString(string a, string b)
{
    if (a.length() == 0)
    {
        return b;
    }

    if (b.length() == 0)
    {
        return a;
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string result = "";
    string str_1, str_2;
    if (a.length() > b.length())
    {
        str_1 = b;
        str_2 = a;
    }
    else
    {
        str_1 = a;
        str_2 = b;
    }
    int index = 0;
    int value = 0, over_value = 0;
    for (; index < str_1.length(); ++index)
    {
        int temp_1 = (int)(str_1[index] - '0');
        int temp_2 = (int)(str_2[index] - '0');
        int temp = temp_1 + temp_2 + over_value;
        value = temp % 10; 
        over_value = temp / 10; 
        char c = (char)(value + '0');
        result += c;
    }
    for (; index < str_2.length(); ++index)
    {
        int temp_2 = (int)(str_2[index] - '0');
        int temp = temp_2 + over_value;
        value = temp % 10;
        over_value = temp / 10;
        char c = (char)(value + '0');
        result += c;
    }

    if (over_value > 0)
    {
        char c = (char)(over_value + '0');
        result += c;
    }
    reverse(result.begin(), result.end());
    return result;
}

int main()
{
    string a = "1";
    string b = "1";
    string c = addTwoString(a, b);
    int index = 3;
    while (c.length() < 1000)
    {
        a = b;
        b = c;
        c = addTwoString(a, b);
        ++ index;
    }
    cout << index << endl;
}

Answer 6

с помощью двойных чисел вы можете прийти к решению, зная, что наибольшая экспонента равна 308:

получите последовательность до значения 250, а затем разделите два числа на 1e250.Перезапустите алгоритм с этими двумя числами

, если вы сделаете это 4 раза, вы получите правильный ответ

Answer 7

Вы можете попробовать вычислить число Фибоначчи, используя матричное возведение в степень. Затем повторите удвоение, чтобы получить число, которое имеет более 1000 цифр, и используйте двоичный поиск в этом диапазоне, чтобы найти первый.