Содержание серии статей "Факир математики"

1. Золотое сечение

   1. Первая часть

   2. Вторая часть (вы здесь)

В прошлой статье мы узнали о последовательности Фибоначчи, золотом сечении, как рисовать золотой прямоугольник, что такое числа. Мы приоткрыли занавес красоты золотого сечения. Но нам предстоит сегодня узнать, почему 0 — самое важное число, в чем состоит иррациональность квадратного корня из двух, об Евклиде, и изучим золотую математику. Все это предстоит в следующих статьях. Если вам понравилась данная публикация, и вы хотите продолжения, то ставьте плюсы и оставляйте комментарии.

Мы, будто факиры заклинают своих змей, будем познавать математический мир. Красивый, бездонный и невероятно интересный. Добро пожаловать в серию статей «Факир математики», и тема продолжения нашей второй статьи — золотое сечение!

Немного практики

Мы обсуждали числа Фибоначчи. Так давайте попробуем реализовать последовательность Фибоначчи на Python!

Числа Фибоначчи – это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих.

Итерационное вычисление последовательности Фибоначчи

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

def fibonacci_iterative(target: int) -> int:
    """
    Эта версия использует итерацию, чтобы начать с начала последовательности и довести ее до целевого значения.
    В этом она похожа на fibonacci_bottom up
    К счастью, в итеративной версии нет проблем с объемом памяти, здесь нет глубоко вложенных цепочек вызовов.
    К сожалению, этот метод медленный, очень медленный.
    >>> fibonacci_iterative(80)
    23416728348467685
    """
    penultimate, ultimate = 0, 1  # the values at target -2 and target -1
    for i in range(target):
        penultimate, ultimate = (
                ultimate,
                penultimate + ultimate,
        )  # simple: just calculate the new values
    return penultimate

print(fibonacci_iterative(80))

Рекурсивное вычисление Фибоначчи

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

Этот метод работает в обратном направлении от начальной позиции, пока не достигнет 1 или 0. В противном случае он вычисляет сумму всех предыдущих рекурсий.

def fibonacci_recursive(i: int = None) -> int:
    """
    Самый простой способ вычислить число Фибоначчи, используя рекурсию.
    Просто работает, но не во всех случаях!
    >>> fibonacci_recursive(20)
    6765
    >>> # fibonacci_recursive(100) !!! Нет, не делайте этого, это займет вечность и истощит память вашего компьютера
    """
    if i == 0:
        return 0
    if i == 1:
        return 1
    return fibonacci_recursive(i - 1) + fibonacci_recursive(i - 2)


print(fibonacci_recursive(20))

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

Также: рекурсивный алгоритм страдает той же проблемой временной сложности, что и итерационный алгоритм - он должен вычислять все значения.

Использование умножения матриц для вычисления чисел Фибоначчи

Все предыдущие примеры страдали от одной и той же проблемы: необходимо было вычислить все предыдущие значения в последовательности. Мы можем избежать этой неэффективности, используя умножение матриц для прямого вычисления значения последовательности без вычисления предшественников.

Вы можете прочитать больше об умножении матриц здесь:

Умножение матриц - в математике, точнее в линейной алгебре, умножение матриц - это бинарная операция, которая производит матрицу...

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

def matrix_fibonacci(target: int) -> int:
    """
    Это самый быстрый способ вычисления числа Фибоначчи с использованием матричной математики.
    Он выполняется быстро.
    Математика подробно описана на странице википедии по адресу: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
    >>> matrix_fibonacci(80)
    23416728348467685
    """
    v1, v2, v3 = (
        1,
        1,
        0,
    )
    for record in bin(
            target
    )[3:]: 
        calc = v2 * v2
        v1, v2 = v1 * v1 + calc, (v1 + v3) * v2
        v3 = calc + v3 * v3

        if record == "1":
            v1, v2, v3 = v1 + v2, v1, v2
    return int(v2)

print(matrix_fibonacci(80))

Эта формула требует постоянного объема памяти для завершения и занимает линейно больше времени с увеличением значения n.

Золотое сечение

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

import math

def matrix_fibonacci(target: int) -> int:
    """
    Это самый быстрый способ вычисления числа Фибоначчи с использованием матричной математики.
    Он выполняется быстро.
    Математика подробно описана на странице википедии по адресу: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
    >>> matrix_fibonacci(80)
    23416728348467685
    """
    v1, v2, v3 = (
        1,
        1,
        0,
    )
    for record in bin(
            target
    )[3:]: 
        calc = v2 * v2
        v1, v2 = v1 * v1 + calc, (v1 + v3) * v2
        v3 = calc + v3 * v3

        if record == "1":
            v1, v2, v3 = v1 + v2, v1, v2
    return int(v2)
    

def fibonacci_goldenratio(target):
    """
    Этот метод работает путем вычисления золотого сечения, а затем
    возведения золотого сечения в степень n, где n - положение последовательности Фибоначчи.
    По мере того, как мы ищем все более высокие значения n, ошибки округления сбивают нас с толку. Этот метод работает для значений n
    меньше 72 или около того.
    :param target:
    :return:
    >>> fibonacci_goldenratio(80)
    23416728348467685
    """

    if target < 2:
        return target

    if target > 71:
        return matrix_fibonacci(target)

    sqrt5 = math.sqrt(5)
    golden_ratio = (1 + sqrt5) / 2

    return math.floor(math.pow(golden_ratio, target) / sqrt5)

print(fibonacci_goldenratio(80))

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

Формула Бине - это точная алгебра. Однако компьютеры должны использовать неточное представление чисел с плавающей запятой. По мере увеличения значений n также накапливаются ошибки округления.

Начинаем погружаться в историю и теорию

Индийский математик и астроном Брахмапутра примерно в 628 году опубликовал книгу под названием "Исправленный трактат Брахмы". Это была первая работа, в которой использовалась десятичная система, практически идентичная современной. Тем не менее сегодняшний способ записи десятичных чисел является достижением арабской цивилизации. Это произошло потому, что широкое распространение в мире, в частности в Европе, эти цифры получили благодаря арабам, их математическим сочинениям.

Ноль - самое важное число

Краеугольным камнем нашей истории счисления является число ноль. Математик и историк Жорж Ифра писал: "Без числа ноль и без позиционной системы счисления мы бы никогда не имели бы механизации, не автоматизированных вычислений".
Чтобы показать важную роль числа ноль, выполним простое умножение 138 на 570, используя непозиционную систему счисления древних римлян. В этой системе нет цифры ноль, следовательно, мы будем умножать CXXXVIII на DLXX. Даже зная, с чего начать, мы не поняли бы точно, когда нам остановиться.  Такие вычисления оказались бы нелегким и бесконечным процессом. А ведь это сравнительно простая операция умножения двух трехзначных чисел. Этот пример показывает, что ключевым свойством современной системы счисления является не просто ее основание (10), но и также то, что значения каждой цифры зависит от ее обозначения и положения относительно других цифр (сравните, например, 12 с 21). Позиционной десятичной системе, таким образом, требуется всего десять цифр для записи любого числа.
Но самым важным является наличие особого символа, обозначающего отсутствие какого-либо количества. Таким образом, чтобы показать, что ничего нет, мы не говорим "нет никакого количества", а говорим "есть нулевое количество". И вместо того, чтобы ничего не писать, мы пишем 0. Современный о-образный символ появился от простой точки, которая использовалась вначале.
Присвоение значения отсутствию количества означает отождествление несуществование чего-либо с отсутствием чего-либо, что могло бы присутствовать. Это может показаться бессмысленным, но это неразрывно связано с ростом торговли и коммерции, а на протяжении времени и с прогрессом.

Числа, числа, числа...

Первые числа, которые использовали люди, называли натуральными (1, 2, 3, 4, 5...). Согласно учению пифагорейцев, самой влиятельной теории в древнегреческой математике, имеющей основополагающее значение и для современной науки, с помощью натуральных чисел можно описать окружающий наш мир. Натуральные числа (а также ноль и целые отрицательные числа) и построенные с их помощью дроби математики называют рациональными числами. Этот термин становится более понятен, если мы заметим, что слово рациональный, имеет тот же корень, что и слово ration, которое, в свою очередь, связано со словом ratio (отношение), а именно соотношение двух величин. Число называется рациональным, поскольку является результатом отношения, деления, а не потому, что оно "разумное" - в другом смысле слова рациональный.
Пифагор и его последователи более 20 веков назад знали, что корень из двух не является рациональным числом. Это число нельзя выразить в виде отношения двух натуральных чисел - как результат деления одного числа на другое.
Пифагорейцы думали, что числа являются священными сущностями. Они верили, что все в мире может быть измеримо, все имеет численную природу. Поэтому идея невыразимого числа противоречила самой основе их философии.
Числа, которые не являются рациональными, называются иррациональными. Это довольно обманчивое название означает, что такие числа не могут быть выражены в виде отношения двух натуральных чисел. Представим только замешательство пифагорейцев, когда они обнаружили действительно иррациональные величины, которые невозможно точно отмерить, например, обычную диагональ в квадрате со стороной, равной единице (это и будет квадрат из двух).
Существует много математических отличий между рациональными и иррациональными числами, но, пожалуй, одно из самых замечательных и понятных свойств - "музыкальность". Это хотя и не строго математическое отличие имеет математическую причину, а именно: различие в десятичной записи рациональных и иррациональных чисел.
Десятичные знаки рациональных чисел образуют повторяющуюся последовательность, называемую "периодической", в то время как десятичные знаки иррациональных чисел не повторяются ни с какой закономерностью, они появляются один за другим в непредсказуемом виде. Однако, если каждой цифру мы поставим в соотвествие ноту и сыграем десятичные знаки рационального числа, мы услышим повторяющуюся мелодию, похожую на мотив песни. С другой, музыка иррациональных чисел представляет собой неприятную какофонию.

Иррациональность числа √2

Допустим, что число √2 рационально. Это значит, что √2 можно выразить в виде дроби:

где p - целое, а q - натуральное число, причем p и q не имеют общих делителей. Избавляясь от знаменателя и возводя в квадрат. получим:

Отсюда следует, что p должно быть четным числом.

Тогда мы можем написать p = 2r и

Раздлеим обе части на 2, получим:

откуда следует, что q также должно быть четным. Так как оба числа p и q четные, они имеют общий делитель, равный 2. Какой бы подход мы ни использовали, в результате всегда получается противоречие. Таким образом, первоначальное предположение, что число √2 рационально, неверно.

Определение золотого сечения

Золотое сечение является иррациональным числом, которое мы будем обозначать, как уже говорили, греческой буквой фи (Ф). Оно было открыто древни греками, и его документированная история начинается с одной из самых известных и много раз переиздаваемых книг всех времен и народов "Начал" Евклида Александрийского, написанной около 300 года до нашей эры. Не путайте Александрийского Евклида с Евклидом из Мегары.
Шедевр Евклида является первым научным бестселлером в истории. Ученый преследовал две цели, когда писал эту работу, с одной стороны, он хотел собрать все математические результаты того времени и составить энциклопедию, которая служила бы учебником. С другой стороны, он хотел разработать определенную методологию доказательств и построить новую математическую теорию, основанную на аксиомах и законах дедукции.
Успех "Начал" был бесспорен, эта книга оказала значительное влияние на развитие всех областей математики.
"Начала" состоят из 13 книг. Первые шесть посвящены элементарной геометрии, книги с седьмой до десятую - вопросам чисел, а с одиннадцатой по тринадцатую - стереометрии. Шестая книга содержит текст, с которого началась история золотого сечения:
Разделить прямую линию в крайнем и среднем отношении значит разделить ее на два таких отрезка, чтобы отношение всей линии к большему отрезку равнялось отношению большего отрезка к меньшему
Или, кратко: целое относится к большей части, как большая часть к меньшей.
Крайнее и среднее отношение, которое прозвучало так, что его нетрудно упустить из вида, является тем самым числом, которое впоследствии стало известно как золотое сечение и которому в 1509 году Лука Пачоли посвятил целый научный трактат "О божественной пропорции". Современное обозначение золотого числа фи, появилось намного позже, в начале 20 века, когда американец Марк Барр предложил использовать первую букву имени Фидий, архитектора Парфенона в Афинах.
Теперь мы рассказали историю золотого сечения и определили его как иррациональное число, мы можем наконец начать изучение его математических свойств. Прежде всего, посчитаем значение числа Ф.

Разделим отрезок на две части, тогда он будет разделен в крайнем и среднем отношении в терминах Евклида, иначе говоря, в золотом отношении, если

Если дроби равны, то равны и соотвествующие произведения по правилу "крест-накрест":

Это приводит нас к квадратному уравнению:

У этого уравнения есть два решения. Нас интересует только лишь положительное:

Это и есть искомое число, которое мы обозначим Ф:

Сначала разделим единицу на Ф. Что мы получим? Число 0,61803, те же самые десятичные знаки после запятой. Оказывается, что 1/Ф = ф - 1.

Теперь давайте возведем наше число в квадрат. Получаем Ф2 = Ф + 1

Последовательность Фибоначчи

Мы практиковались в алгоритмах по последовательности Фибоначчи в начале статьи. Но история математики полна неожиданностей. Одна из них касается золотого сечения, известного еще с древних времен и тесно связанного с геометрией. Однако спустя столетия это соотношение было найдено в ряде дробей, возникших из чисто арифметической последовательности. Гением, нашедшим эту связь, был между геометрий и арифметикой, был один из самых выдающихся математиков средневековья был Леонардо Пизанский - Фибоначчи.

Заключение

Вторая статья подошла к концу. Здесь мы узнали немного, но зато есть практика.

В следующей статье мы поговорим опять о золотом прямоугольнике.

Всем удачи, с вами был доктор Аргентум!