Быстрое дублирование и объяснение алгоритма Фибоначчи - PullRequest
Новая
       73

Быстрое дублирование и объяснение алгоритма Фибоначчи

2 голосов
/ 11 апреля 2020

Рассматривая возведение в степень матрицы, я столкнулся с быстрым удвоением и реализацией ниже. У меня есть следующие вопросы:

  1. Почему для l oop происходит итерация с 31 до 0?

  2. Какова цель замаскировать я в условном? 

    private static BigInteger Fibonacci(int n) {
        BigInteger a = BigInteger.Zero;
        BigInteger b = BigInteger.One;
        for (int i = 31; i >= 0; i--) {
            BigInteger d = a * (b * 2 - a);
            BigInteger e = a * a + b * b;
            a = d;
            b = e;
            if ((((uint)n >> i) & 1) != 0) {
                BigInteger c = a + b;
                a = b;
                b = c;
            }
        }
        return a;
    }

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

Приветствия!

Ответы [ 2 ]

2 голосов
/ 11 апреля 2020

Инвариант l oop в вашем коде: 

a = Fib(n/2^i)
b = Fib(n/2^i + 1)

(здесь ^ - это возведение в степень, а не xor).

Вы можете проверить, что эти инварианты выполнены при изменении i, используя формулы быстрого удвоения: 

Fib(2k) = 2Fib(k)*Fib(k+1) - Fib(k)*Fib(k)
Fib(2k+1) = Fib(k+1)*Fib(k+1) + Fib(k)*Fib(k)

И для случая, когда n / 2 ^ i нечетно, оператор if применяет формулу: 

Fib(2k+1), Fib(2k+2) = Fib(2k+1), Fib(2k) + Fib(2k+1)

( это просто обычная формула Фибоначчи).

Может помочь рассмотреть код как нисходящую (а не восходящую) версию этого рекурсивного кода: 

def fib2(n):
    if n == 0:
        return 0, 1
    a, b = fib2(n//2)
    a, b = a*(b*2 - a), a*a + b*b
    if n % 2 != 0:
        a, b = b, a+b
    return a, b

единственное существенное отличие состоит в том, что, хотя этот код повторяется до тех пор, пока n не станет равным 0, нисходящий код всегда повторяется 32 раза.

1 голос
/ 11 апреля 2020
  1. Почему итератор l oop сократился с 31 до 0?

Отв. Потому что программист хранит данные в 32-х битах (от 0 до 31). Смысл в диапазоне от 31 до 0 заключается в том, что выполняется итерация от младшего значащего бита к старшему значащему биту.

Какова цель маскировки i в условном выражении?

Отв. Это на самом деле не маскировка. Это оператор левого сдвига. Общее выражение if ((((uint)n >> i) & 1) != 0) проверяет, имеет ли число n бит четности, добавляемый в следующем значащем бите.

Топи c, которую вы хотите узнать, называется битовой манипуляцией. Вот несколько ресурсов, где я впервые узнал о битовых манипуляциях.

...