Приветствую вас, друзья! Мой сегодняшний рассказ будет посвящен всем знакомой теме — умножению целых чисел. Я постараюсь рассказывать популярно, поэтому прошу специалистов не сильно ругаться на упрощения и неизбежные в таком случае неточности.
Как вы знаете, существует много разных способов проделывать это арифметическое действие, хотя в школе учат всего нескольким из них. Долгое время считалось, что их объединяет общее ограничение: полагали, что нельзя умножить два числа за за количество действий, меньшее чем квадрат от размера умножаемого числа (n^2). Первым, кто догадался создать алгоритм «быстрого умножения» был математик Карацуба. Он открыл, как проделывать умножение за n^1.585 действий для очень больших чисел. За его открытием последовали другие, которые позволяли умножать ещё быстрее. Особенность всех этих замечательных алгоритмов в том, что они работают эффективнее классического только на относительно больших числах.
Но есть среди них один малоизвестный подход, который эффективнее классического умножения на числах «среднего» размера (примерно от 130 бит и больше), о нём и пойдёт речь в первом комментарии.

Tagged with →  

17 Responses to Про умножение целых чисел

  1. ZvnRain:

    Решение относительно простое, но довольно неочевидное. Как вы знаете, есть разные системы счисления. Всем привычны десятичная, двенадцатиричная, кому–то двоичная. Ключевым моментом для нашего алгоритма является использование особенной системы счисления.
    Итак, начнём с того, что есть способ представлять любые целые числа в виде суммы чисел Фибоначчи (F(n)). Напомню первые числа этой последовательности: 0, 1, 1, 2, 3, 5, 8…, последовательность задаётся как F(0)=0, F(1)=1, F(n)=F(n–1)+F(n–2). Любое целое число можно пердставить как сумму чисел Фибоначчи, и есть интересная особенность: это можно сделать единственным способом, если допустить ограничение на то, чтобы не использовать никакие два соседних числа в последовательности (теорема Цекендорфа). Поясню на примере: число 6 мы представим как F(2)+F(5) = 1+5, и это единственный вариант в наших правилах. Думаю, становится понятно, как устроена эта система счисления: 1 и 0 в записи обозначают, есть или нет нужное нам слагаемое из последовательности Фибоначчи в представлении нашего числа. По нашим правилам две единицы подряд не встречаются никогда, и, как некоторые, возможно, догадались, нулей в среднем получается больше, чем единиц (единиц в записи всего примерно 28% ). В двоичной системе счисления в среднем их получается поровну. Увы, фибоначчиева система счисления не «экономична»: чтобы записать в ней число, нужно больше знаков, чем при использовании привычной двоичной системы счисления, примерно на 44%.
    Продолжим. Математики попробовали рассмотреть несколько других последовательностей, похожих на последовательность Фибоначчи, и среди них обнаружили одну с очень интересными свойствами. Задается интересующая нас последовательность так: T(0)=T(1)=0, T(2)=T(3)=1, T(n)=T(n–1)+T(n–2)+T(n–3)+T(n–4); n?4. При помощи этой последовательности также можно записать любое число в виде суммы её членов, и также существует единственный способ это сделать, если задать ограничение на использование соседних членов прогрессии: в данном случае не могут встретиться четыре единицы подряд (по обобщенной теореме Цекендорфа, о которой я уже упоминал ранее).

    У этой прогрессии есть интересные свойства: с одной стороны, она относительно «экономичная» — для записи числа в ней требуется лишь немногим больше знаков (всего на 5% ), чем в обычной двоичной системе. С другой стороны, в среднем нулей в записи чисел больше, чем единиц (единиц в среднем всего 43% ), а не примерно поровну, как в двоичной системе. Эти две особенности и дают выигрыш в скорости при умножении.

    Остаётся ещё одна проблема: как перекодировать число из двоичной системы в нашу и обратно. Для этого существует элегантное решение, которое требует всего около 2.1*n операций для больших чисел. Я не буду подробно останавливаться на этом алгоритме, ему посвящены отдельные работы, например эта (см. теорему 4), а тут есть пример кода.

    В целом, с учётом перекодирования из двоичной системы и обратно, в пределе понадобится порядка 0.484*2*n2 операций, чтобы выполнить умножение при помощи нашего метода, а быстрее чем обычное умножение он становится уже для чисел размером порядка 130 бит.

  2. ZvnRain:

    : ох, время позднее, и я пропустил двойку и скобки, конечно же за 0.484*2*(n^2).

  3. M2yRain M2yRain:

    Вот это действительно круто, интересно, довольно просто и весьма доходчиво.
    Спасибо.

  4. M2yRain M2yRain:

    : Эта двойка многое портит. Получается, что по сравнению с n2 выигрыш составляет всего 0.032?

  5. supef:

    : а где выгода-то, с квадратом?

  6. ZvnRain:

    : Конечно, это всего лишь курьёз, выгода в этих 0.968n^2, в 3.2%. Это кажется очень несущественным, но представь, что серьёзные математики ещё не так давно считали, что быстрее чем за n^2 умножать невозможно в принципе. Мне показалось это забавным, да и в википедии о таком не прочтёшь, вот я и решил рассказать вам.

  7. Copoff:

    : ну так напиши статью в википедию, действительно интересно же

  8. Amtodin:

    : к тому же 3% машинного времени — это, сами понимаете, не 31 день расчётов, а 30.
    Так-то вообще неплохо.

  9. Peeen:

    : С точки зрения компьютер сайенс подсчет каждой операции (вместо общепринятой O-нотации) — это конечно чепуха, и упомянутое выше утверждение что «умножать быстрее чем за n^2 нельзя» скорее всего должно читаться как «умножать быстрее чем за O(n^2) нельзя». Вот его данный алгоритм не опровергает никак.

    Более того, даже если считать операции поштучно, как делается здесь, то стоит обратить внимание что вот это вот 0.98 выскакивает только после усреднения по всем возможным числам. Т.е. грубо говоря, для некоторым образом распределенных чисел среднее ожидаемое время получается меньше n^2. Ну дык можно найти другое распределение, для которого классическое умножение будет в среднем быстрее чем n^2.

    Ну и если реализовать это все на практике то скорее всего классическое умножение будет работать в разы быстрее, т.к. оно в железе.

  10. ZvnRain:

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

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

  11. Peeen:

    : мы бы здесь замучились объяснять, что это значит и для чего нужно.

    ДЛЯ ТЕХ КОМУ НЕПОНЯТНО ПРО О-НОТАЦИЮ, ОБЪЯСНЯЕМ ЗДЕСЬ НА ПАЛЬЦАХ (ведь это сейчас в тренде)

    Алгоритмы, как известно, выполняются в виде последовательности шагов и скорость работы алгоритмов разумно измерять как количество этих самых шагов. Однако есть одно «но». Если мы подумаем, применение алгоритмов на практике означает, что кто-то должен их реализовать на каком-то языке программирования, а потом еще и запустить на каком-то компьютере. И в таком случае вполне может оказаться, что плохо реализованный алгоритм из 100 шагов работает медленее, чем хорошо реализованный алгоритм из 100 000 шагов. Вдобавок различия могут быть обусловлены выбором языка программирования, а так же конкреного процессора. Что же делать и как сравнивать алгоритмы?
    Что бы учесть такой разброс сред выполнения, в информатике применяется простой трюк — скорость работы рассматривается с точностью до константы. Т.е. если алгоритму А нужно n шагов, то с практической точки зрения он настолько же хорош, как и алгоритм которому нужно 0.1n, 2n или даже 100n + log n + 4 шагов, т.к. каждый из этих трех вариантов можно сделать быстрее двух других подобрав для него достаточно быстрый компьютер.
    Тут возникает немаловажный вопрос — а не получится ли так, что подбором компьютера можно любой алгоритм сделать быстрее любых других. Оказывается что нет. Например, алгоритм, которому нужно n^2 шагов для достаточно больших n будет работать медленнее алгоритма, которому нужно n шагов вне зависимости от выбора среды выполнения.
    Поэтому именно такое вот «поведение алгоритма с точностью до константы» и является его основной характеристикой, используемой в информатике. Для записи этой характеристики чаще всего применяется т.н. О-нотация. Т.е. вместо того, чтобы сказать что «алгоритму требуется с точностью до константы не более n^2 шагов» пишут O(n^2).

    большое количество случайных.

    «Равномерно распределенных», ты хотел сказать. Т.е. в твоем случае «особенным» распределением является равномерное. OK.

  12. M2yRain M2yRain:

    : Как удачно я в тренд «на пальцах» буковки TM вставил.
    Глядишь, начну 1% собирать, как Михалков… 🙂

  13. Peeen:

    : ОК. Когда мой комментарий наберет 100 плюсиков, отстегну тебе один сюда.

  14. AsaDead:

    : Хочется только добавить, что О-нотация применяется не только для количества шагов. Например, поиск в каком-нибудь множестве обычно имеет сложность от количества элементов, а поиск подстроки — сложность по длине.

  15. Peeen:

    : Ну так «количество элементов» или «длина строки» — это вот этот параметр n, который конечно же можно выбирать на свой вкус, в зависимости от задачи. В примере романвз n — это количество бит в числе.
    При этом сложность алгоритма в — это, тем не менее, всегда количество шагов, выраженное через n.

    В более общем контексте О-нотацию можно конечно где угодно применять, где есть смысл рассматривать поведение функций при больших n. Например «рост количества пользователей в блоге — O(exp(n)) от времени».

  16. Jitwhite:

    почитал и подумал, что вроде как еще в школе говорилось о сложностях алгоритмов типа N^A, log(2)N и так далее, а про проценты как то клали. А тут на тебе. Срыв шаблона. О-нотация, операции. Круто.
    Кстати, а ведь получается, что все равно про N^2 люди были правы с поправкой на то, по каким правилам мы выполняем задачу. И что ускорение алгоритма приводит к увеличению необходимой памяти. Некоторый закон сохранения должен быть. я чую

  17. Ef7No:

    Способ Шёнхаге и Штрассена понравился, ну и Фюрера заодно, потому что он продолжение. Очевидное сочетание БПФ и теоремы о свертке. Численные методы это непаханное поле все-таки, и будет таким еще пару десятилетий.

Добавить комментарий

Ваш e-mail не будет опубликован.