Комментарии / Профиль lounres / Хабр

Глеб Минаев@lounres

Энтузиаст экспериментальной математики, Kotlin-ист

lounres 17 янв 2022 в 15:18

Если идёт речь о прямом (в том или ином смысле) вычислении по формуле Бине, то можно заметить, что член $\left((1 - \sqrt{5})/2\right)^n$ считать нет смысла: число $\left((1 - \sqrt{5})/2\right)^n$ по жизни находится между -0.62 и -0.61 , а значит его степени будут (по модулю) всё меньше и меньше (при возведении числа между 0 и 1 в степень оно начинает катострофически быстро стремится к нулю при росте $((1+\sqrt{5})/2)^n/\sqrt{5}$ , а затем сделать один из следующих вариантов:
1. Округлить до ближайшего целого. Поскольку, уже с нулевого члена ( n=0 ) модуль второго слагаемого $((1-\sqrt{5})/2)^n/\sqrt{5}$ будет по модулю меньше 1/2 , то банальное округление до ближайшего целого числа сделает своё дело.
2. Определить знак $((1-\sqrt{5})/2)^n/\sqrt{5}$ и округлить в соответствующую сторону до ближайщего целого. Действительно, знак это члена – когда делится на 2, и , когда не делится. Следовательно, если мы знаем, что нужно добавить число с данным знаком и по модулю и получить целое число, то это означает округление в сторону данного знака до ближайшего целого.

Главный вопрос. Пусть мы посчитали пару $(a, b) = a + \sqrt{5} b$ . Как же её поделить на $\sqrt{5}$ и округлить?

На него можно ответить так. Ну, $\sqrt{5} b / \sqrt{5} = b$ , которое можно просто вычесть и времено про него забыть (дабы на округление оно не влияет). Теперь же нам нужно найти такое число , что $a/\sqrt{5} \approx c$ . Тут два варианта: либо по-"глупому" написать ряд для $1/\sqrt{5}$ (благо, он классно сходится) или посчитать префикс цепной дроби того числа (или ещё что-нибудь) и приближать ими (но это нудно и нужно писать оценки), либо бинпоиском искать такое число , чьё c^2 будет ближе всех к 5a^2 .

С другой стороны есть другой формальный подход. Кольцо таких пар (формально, $\mathbb{Z}[\sqrt{5}]$ ) обладает ещё одной интересной операцией: операцией сопряжения, которая паре (числу) (a, b) сопоставит пару $\overline{(a,b)} := (a, -b)$ . Выглядит как странная операция, которая меняет второй аргумент, но не всё так просто. Во-первых она сохраняет операции кольца (и поля, если рассматривать пары рациональных чисел):

$\overline{(a, b) + (c, d)} = \overline{(a, b)} + \overline{(c, d)}$ . Действительно,

$\overline{(a, b) + (c, d)} = \overline{(a + b, c + d)} = (a + b, -c - d) = (a, -b) + (c, -d) = \overline{(a, b)} + \overline{(c, d)}$

$\overline{(a, b) \cdot (c, d)} = \overline{(a, b)} \cdot \overline{(c, d)}$ . Действительно,

$\begin{multline}\overline{(a, b) \cdot (c, d)} = \overline{(ab - 5cd, ac + bd)} = (ab - 5cd, -ac - bd)\\ = (a, -b) \cdot (c, -d) = \overline{(a, b)} \cdot \overline{(c, d)}\end{multline}$

А во-вторых, он позволяет упростить много счёта. Давайте немного обозначим: $\alpha := 1 + \sqrt{5}$ , $\beta := 1 - \sqrt{5}$ . Тогда нам надо посчитать $(\alpha^n + \beta^n)/2^n/\sqrt{5}.$ Но заметим, что $\overline{\beta} = \alpha$ , а тогда $\beta^n = \overline{\alpha}^n = \overline{\alpha^n}$ , т.е. высчитав пару для $\alpha^n$ мы можем буквально мгновенно получить пару для $\beta^n$ : просто измените знак второго члена на противоположный. И счёт фактически сократится в два раза.

Формула Бине без плавающей точки

lounres 17 янв 2022 в 14:32

То, что полученное кольцо пар (a, b) является полем (т.е. можно делить такие целочисленные пары на ненулевые целочисленные пары и получать сновва целочисленные пары) неверно. Действительно, если попробовать разделить пару (1, 0) (т.е. просто 1) на пару (0, 1) (т.е. \sqrt{5}), то мы должны получить пару (0, 1/5) = (0, 0.2) (т.е. \sqrt{5}/5 = 1/\sqrt{5}), что не является целочисленной парой!

В чём же ошибка в рассуждении? Всё просто: если система линейных уравнений (СЛУ) с целочисленными коэффициентами имеет ненулевой определитель, то это значит, что оно имеет решение в поле, но не обязательно в кольце (например, простое СЛУ 2x = 1 имеет определитель 2, но и единственное решение 1/2 = 0.5).

В данном случае, чтобы получить поле, нужно рассматривать пары рациональных чисел (а не целых).

P.S. Это не влияет на суть статьи: мы не пользовались тем, что это поле, а все моменты вне этих абстракций тщательно описанны. Но ошибка есть ошибка.

Формула Бине без плавающей точки

lounres 17 янв 2022 в 14:16

При умножении (a + \sqrt{5} b) (a - \sqrt{5} b) получается a^2 - 5 b^2. А у Вас в результате везде написано b^2 без квадрата.