Умножение длинных чисел методом Карацубы

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

Алгоритм


Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog23. В то время, как наивный алгоритм, умножение в столбик, требует n2 операций. Следует заметить, что при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.
Представим, что есть два числа A и B длиной n в какой-то системе счисления BASE:
A = an-1an-2...a0
B = bn-1an-2...a0, где a?, b? — значение в соотв. разряде числа.
Каждое из них можно представить в виде суммы их двух частей, половинок длиной m = n / 2 (если n нечетное, то одна часть короче другой на один разряд:
A0 = am-1am-2...a0
A1 = an-1an-2...am
A = A0 + A1 * BASEm

B0 = bm-1bm-2...b0
B1 = bn-1bn-2...bm
B = B0 + B1 * BASEm

Тогда: A * B = ( A0 + A1 * BASEm ) * ( B0 + B1 * BASEm ) = A0 * B0 + A0 * B1 * BASEm + A1 * B0 * BASEm + A1 * B1 * BASE2 * m = A0 * B0 + ( A0 * B1 + A1 * B0 ) * BASEm + A1 * B1 * BASE2 * m
Здесь нужно 4 операции умножения (части формулы * BASE? * m не являются умножением, фактически указывая место записи результата, разряд). Но с другой стороны:
( A0 + A1 ) * ( B0 + B1 ) = A0 * B0 + A0 * B1 + A1 * B0 + A1 * B1
Посмотрев на выделенные части в обоих формулах. После несложных преобразований количество операций умножения можно свести к 3-м, заменив два умножения на одно и несколько операций сложения и вычитания, время выполнения которых на порядок меньше:
A0 * B1 + A1 * B0 = ( A0 + A1 ) * ( B0 + B1 ) — A0 * B0A1 * B1

Окончательный вид выражения:
A * B = A0 * B0 + (( A0 + A1 ) * ( B0 + B1 ) — A0 * B0 — A1 * B1 ) * BASEm + A1 * B1 * BASE2 * m

Графическое представление:
схема умножения


Пример


Для примера умножим два восьмизначных числа в десятичной системе 12345 и 98765:
image
Из изображении явно видна рекурсивная природа алгоритма. Для числа длиной менее четырех разрядов применялось наивное умножение.

Реализация на C++


Наверное, следует начать с того, как хранятся длинные числа. Длинные числа удобно представлять в виде массивов, где каждый элемент соответсвует разряду, причем младшие разряды хранятся в элементах с меньшими индексами (то есть задом-наперед) — так их удобнее обрабатывать. Например:
int long_value[] = { 9, 8, 7, 6, 5, 4} //представление числа 456789
Для увеличения быстродействия желательно выбрать за основание системы счисления максимальное число в рамках базовых типов. Но при этом на него накладываются следующие условия:
  1. Квадрат максимального числа в выбранной системе счисления должен помещаться в выбранный базовый тип. Это необходимо для хранения произведения одного разряда на другой в промежуточных вычислениях.
  2. Выбранный базовый тип желательно брать знаковый. Это позволить избавиться от нескольких промежуточных нормализаций.
  3. Лучше, чтобы в разряд помещалось сумма из нескольких квадратов максимального числа. Это позволит избавиться от нескольких промежуточных нормализаций.


Ниже приведена рабочая функция умножения с комментариями со всеми необходимыми вспомогательными объявлениями и функциями. Для более высокой производительности следует поменять основание системы счисления, тип для хранения разрядов и раскоментировать небольшой отрывок кода в месте отвечающем за наивное умножение:
  1. #include <cstring>
  2.  
  3. #define BASE 10 //система счисления
  4. #define MIN_LENGTH_FOR_KARATSUBA 4 //числа короче умножаются квадратичным алгоритмом
  5. typedef int digit; //взят только для разрядов числа
  6. typedef unsigned long int size_length; //тип для длинны числа
  7.  
  8. using namespace std;
  9.  
  10. struct long_value { //тип для длинных чисел
  11.   digit *values; //массив с цифрами числа записанными в обратном порядке
  12.   size_length length; //длинна числа
  13. };
  14.  
  15. long_value sum(long_value a, long_value b) {
  16.   /* функция для суммирования двух длинных чисел. Если суммируются числа разной длинны
  17.   * то более длинное передется в качестве первого аргумента. Возвращает новое
  18.   * ненормализованное число.
  19.   */
  20.   long_value s;
  21.   s.length = a.length + 1;
  22.   s.values = new digit[s.length];
  23.  
  24.   s.values[a.length - 1] = a.values[a.length - 1];
  25.   s.values[a.length] = 0;
  26.   for (size_length i = 0; i < b.length; ++i)
  27.     s.values[i] = a.values[i] + b.values[i];
  28.   return s;
  29. }
  30.  
  31. long_value &sub(long_value &a, long_value b) {
  32.   /*функция для вычитания одного длинного числа из другого. Изменяет содержимое первого
  33.   * числа. Возвращает ссылку на первое число. Результат не нормализован.
  34.   */
  35.   for (size_length i = 0; i < b.length; ++i)
  36.     a.values[i] -= b.values[i];
  37.   return a;
  38. }
  39.  
  40. void normalize(long_value l) {
  41.   /*Нормализация числа - приведение каждого разряда в соответствие с системой счисления.
  42.   *
  43.   */
  44.   for (size_length i = 0; i < l.length - 1; ++i) {
  45.     if (l.values[i] >= BASE) { //если число больше максимального, то организовавается перенос
  46.       digit carryover = l.values[i] / BASE;
  47.       l.values[i + 1] += carryover;
  48.       l.values[i] -= carryover * BASE;
  49.     } else if (l.values[i] < 0) { //если меньше - заем
  50.       digit carryover = (l.values[i] + 1) / BASE - 1;
  51.       l.values[i + 1] += carryover;
  52.       l.values[i] -= carryover * BASE;
  53.     }
  54.   }
  55. }
  56.  
  57. long_value karatsuba(long_value a, long_value b) {
  58.   long_value product; //результирующее произведение
  59.   product.length = a.length + b.length;
  60.   product.values = new digit[product.length];
  61.  
  62.   if (a.length < MIN_LENGTH_FOR_KARATSUBA) { //если число короче то применять наивное умножение
  63.     memset(product.values, 0, sizeof(digit) * product.length);
  64.     for (size_length i = 0; i < a.length; ++i)
  65.       for (size_length j = 0; j < b.length; ++j) {
  66.         product.values[i + j] += a.values[i] * b.values[j];
  67.         /*В случае изменения MIN_LENGTH_FOR_KARATSUBA или BASE расскоментировать следующие
  68.         * строки и подобрать соотв. значения для исключения переполнения разрядов.
  69.         * Например для десятичной системы счисления число 100, означает, что организовавается
  70.         * перенос 1 через один разряд, 200 - перенос 2 через один разрряд, 5000 - 5 через два.
  71.         * if (product.values[i + j] >= 100){
  72.         *   product.values[i + j] -= 100;
  73.         *   product.values[i + j + 2] += 1;
  74.         * }
  75.         */
  76.       }
  77.   } else { //умножение методом Карацубы
  78.     long_value a_part1; //младшая часть числа a
  79.     a_part1.values = a.values;
  80.     a_part1.length = (a.length + 1) / 2;
  81.  
  82.     long_value a_part2; //старшая часть числа a
  83.     a_part2.values = a.values + a_part1.length;
  84.     a_part2.length = a.length / 2;
  85.  
  86.     long_value b_part1; //младшая часть числа b
  87.     b_part1.values = b.values;
  88.     b_part1.length = (b.length + 1) / 2;
  89.  
  90.     long_value b_part2; //старшая часть числа b
  91.     b_part2.values = b.values + b_part1.length;
  92.     b_part2.length = b.length / 2;
  93.  
  94.     long_value sum_of_a_parts = sum(a_part1, a_part2); //cумма частей числа a
  95.     normalize(sum_of_a_parts);
  96.     long_value sum_of_b_parts = sum(b_part1, b_part2); //cумма частей числа b
  97.     normalize(sum_of_b_parts);
  98.     long_value product_of_sums_of_parts = karatsuba(sum_of_a_parts, sum_of_b_parts);
  99.     // произведение сумм частей
  100.  
  101.     long_value product_of_first_parts = karatsuba(a_part1, b_part1); //младший член
  102.     long_value product_of_second_parts = karatsuba(a_part2, b_part2); //старший член
  103.     long_value sum_of_middle_terms = sub(sub(product_of_sums_of_parts, product_of_first_parts), product_of_second_parts);
  104.     //нахождение суммы средних членов
  105.  
  106.     /*
  107.     * Суммирование многочлена
  108.     */
  109.     memcpy(product.values, product_of_first_parts.values,
  110.       product_of_first_parts.length * sizeof(digit));
  111.     memcpy(product.values + product_of_first_parts.length,
  112.       product_of_second_parts.values, product_of_second_parts.length
  113.       * sizeof(digit));
  114.     for (size_length i = 0; i < sum_of_middle_terms.length; ++i)
  115.       product.values[a_part1.length + i] += sum_of_middle_terms.values[i];
  116.  
  117.     /*
  118.     * Зачистка
  119.     */
  120.     delete [] sum_of_a_parts.values;
  121.     delete [] sum_of_b_parts.values;
  122.     delete [] product_of_sums_of_parts.values;
  123.     delete [] product_of_first_parts.values;
  124.     delete [] product_of_second_parts.values;
  125.   }
  126.  
  127.   normalize(product); //конечная нормализация числа
  128.  
  129.   return product;
  130. }
* This source code was highlighted with Source Code Highlighter.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 90
  • +5
    Вот это да, буквально вчера переписывал функцию перемножения в своём модуле, а сегодня статья. Надо было мне подождать день.
    • +7
      нет, не надо было. если вы хотели разобраться, то написать всё самостоятельно — это самый хороший способ. если вы хотели работающее и хорошее production решение, то написать его довольно сложно, велосипед лучше не переизобретать и смотреть в гугл.

      но сама статья интересная, автору спасибо.
    • +5
      Ну вот что вы делаете, математики-волшебники? Мой гуманитарный мозг просто сгорел.
      • +2
        Кому не охота вникать в мат. часть, могут ориентироваться по примеру. Там достаточно информации для понимания «Как такое сделать».
      • 0
        Извиняюсь, я далек от С++ но во мне затаился вопрос)) чем отличается ваше решение от банального умножения *?

        • +3
          «Умножение длинных чисел методом Карацубы» — 100-200 разрядов на число. Большинство языков не имеют встроенных типов для их представления.
          • –4
            >Большинство языков

            это вы имеете ввиду shell, c, c++ и дельфи? и то, по поводу второго сейчас прибегут знатоки какого-нибудь boost или stl и расскажут нам правду.
            • 0
              Причем здесь «shell, c, c++ и дельфи» и «boost или stl» или вы думаете, что числа там умножаются с помощью какой-то магии? Блог называется «Алгоритмы».
              • 0
                я думаю, что вы не удосужились прочитать на что я отвечал: там написано, что в большнстве языков нет встроенных типов для big integers. мне кажется, что такое мнение ошибочно и я знаю, что в нескольких языках такие типы есть.

                кроме того, наличие встроенного типа для болших чисел, позволяет мне сделать предположение о том, что операция умножения в таких языках происхдит именно по такому алгоритму, особенно если его знает каждый студент-байтикоперекладыватель
                • 0
                  Но ведь во встроенного действительно нет: basic и его вариации, Delphi, PHP (есть не встроенная хотя поставляется с оным), с, c++, javascript. Приведите, пожалуйста, ради расширения кругозора распространенный языке где есть встроенный.

                  Более верно будет предположить, что адекватно было бы применять не этот алгоритм, а с помощью БПФ.
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • +1
                      В исходники не заглядывал, но субъективно тормозная какая-то у них реализация длинных чисел.
                    • +2
                      В Python встроенный.
                      • +2
                        Насколько я помню, там прикручена сишная библиотека GMP. И это хорошо. :-)
                  • +2
                    Зато я удосужился прочитать на что отвечал собеседник, которому отвечали вы.

                    Изначальный посыл был:
                    Извиняюсь, я далек от С++ но во мне затаился вопрос)) чем отличается ваше решение от банального умножения *?

                    Т. е. человек не видит разницы, скажем, между простым mul и представленным алгоритмом.

                    Еще раз, даже если библиотеки и компилятор/интерпретатор вашего языка скрывают от вас всю сущность происходящего, это отнюдь не означает, что умножения 4 байт на 4 байта производится также, как умножение 40 байт на 40 байт.

                    Блог называется алгоритмы, приведенный код иллюстрирует пример реализации алгоритма. С тем же успехом, он бы мог быть написан на языке, который умеет умножать тысячи разрядов из коробки. Тут алгоритм показан, а не туториал по C++.
          • +3
            Плюсанул. Но… ребят, у нас этот метод рассматривался на уровне одной лабораторной работы…
            • +14
              Вам повезло с лабораторными и, похоже, что с обучением вообще.
              • +3
                А вам, похоже, не повезло с умением гуглить: вводим karatsuba multiplication c++ в Google и получаем просто килотонны кода.
                • +5
                  1. С умением гуглить у меня все нормально — как видите алгоритм был разобран.
                  2. Мне нужен был не код, а алгоритм. А прочитать готовы текст куда проще, чем разбирать исходник.
                  3. Под «беглый поиск в google ничего путнего не дал» имелось ввиду: «Русскоязычных статей с простым и детальным изложение найти не удалось (Википедию не считаю т.к. лично для меня там материал сложный). Поэтому пришлось собирать по-частям информацию из русскоязычных и англоязычных источников.»

                  PS не подумайте, что огрызаюсь — просто мне показалось Вы не совсем уловили суть.
                  • +1
                    В русскоязычной Википедии под заголовком «второй вариант» написана та же формула, что и у вас.

                    У вас, кстати, ошибка в формулах: скобка должна закрываться перед BASE^m.
              • 0
                +1, один из вопросов на экзамене — перемножить два числа Карацубой. Достаточно несложный алгоритм. Как и деления, впрочем.
                • +1
                  Поддерживаю, это проходят на втором курсе в рамках дисциплины «Дискретная математика» или «Теоретико-численные методы»
                  • 0
                    Единственная проблема, что к дискретной математике и к численным методам этот метод не имеет никакого отношения.
                    • 0
                      А мы на первом курсе проходили, на алгоритмах.
                  • –1
                    Формула написана и в той статье на Хабре. Вы похоже не учли мой прошлый комментарий. Статья писалась «поделиться с общественностью в доступной форме» и никак не претендует на краткость и тп.

                    Извиняюсь. Ошибки исправлены. Спасибо.
                  • 0
                    > время выполнения которых на порядок меньше

                    ну это не совсем верно. точнее совсем не верно. один порядок — это 10 раз. а что бы достигнуть ускорения в 10 раз число должно быть оооочень длинным.
                    • +1
                      Даже если в обоих числах по 100 знаков, то наивное умножение потребует 100*100 операций умножения, а сложение — 100 сложения. Это не учитывая того, что операция умножения сама по себе дольше выполняется процессором.
                      • +1
                        извините, я ещё разок вас процитирую:

                        > Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog23. В то время, как наивный алгоритм, умножение в столбик, требует n2 операций.

                        > при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.

                        я придираюсь к вполне конкретному слову «на порядок». я понимаю, что оно может работать и быстрее чем в 10 раз, но увы точность такого измерения надо доказать. я же просто советую использовать слово «гораздо быстрее».
                        • +1
                          Даже с учетом того, что автор допустил ошибку и скорость алгоритма явно не модет быть n*log(2,3)( так как это линейная зависимость от n), прежде чем советовать что-то другим, попробуйте сами освоиться с элементарной математикой.
                          n*log(2,3) будет в 10 раз меньше чем n^2 уже при n=15 или 16.
                          но даже если взять правильную формулу, то
                          n^log(2,3) будет в 10 раз меньше n^2 уже при n = 100.
                          • 0
                            мне конечно считать лень, и скорее всего вы правы в отношении цифр, вот только формула оценивает сложность, а не прирост скорости. производительность зависит не только от сложности алгоритма.
                          • +1
                            Наверное, в этом месте плохо построено предложение. Там где «на порядок», идет речь про сравнение операции сложения с операций умножения.
                            А насчет именно «на порядок» не спорую, цель была подчеркнуть отношение между ними как n^1 / n ^ 2. Просто в голове не нашлось правильного описания для данного отношения.
                            • 0
                              да я вас. просто придрался. каюсь. статья хорошая. мне бы её 7 месяцев назад =)
                        • 0
                          Кстати да, чего то непонятно, каким образом преобразовав 2 умножения и 1 сложение к 3 умножениям и 4 сложениям выигрывается время? Наверно нужно описать ограничение для данного утверждения?
                          • –1
                            А где Вы взяли изначальное количество операций умножения равное двум? Попробуйте два двух- трех-значных числа умножить в столбик у потом посчитать количество операция умножения относительно кол-ва цифр
                        • 0
                          А чем обусловлена необходимость хранить длинное число в виде массива десятичных цифр? Почему не использовать родную компьютеру двоичную систему?
                          • –2
                            В статье наоборот написано, что реально нужно использовать не десятичную систему. Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30. «Потери» памяти вприоритет у скорости решения, а не в занимаемой памяти
                            А насчет двоичной не совсем понятно, что Вы имеете ввиду. Выделить участок памяти и оперировать непосредственно битами? — медленно и к тому же экономия памяти в этих задачах неприоритетна — или хранить в массиве двоичные цифры? — тоже медленно и слишком расточительно (поэтому еще медленнее).
                            • –2
                              Мда… Пора идти спать. В общем надеюсь смысли мысли приблизительно понятен )
                              • 0
                                С каких пор оперировать битами стало медленнее, чем байтами? А Вы именно это и делаете. Вы храните массив цифр в порядке разрядов десятичного числа. Это дает лишний расход памяти в 4 раза. И в скорости Вы при такой организации данных ничего не выигрываете, а совсем наоборот.
                                > Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30
                                Вы путаете основание системы счисления с разрядностью двоичного числа
                                • –1
                                  «С каких пор оперировать битами стало медленнее, чем байтами?»
                                  — минимально адресуемая единица памяти в x86 — байт. Соотв. для адресации битов нужно использовать дополнительные манипуляции — это раз. Два — тут действует принцип брать максимальное за раз. Например нужно умножить два 64х разрядных числа. Процессор ето может сделать это одной командой, если начать умножать побайтно или побитно, то понадобится соотв. 8 команд умножение или 64. И это только кол-во операций умножения, а еще масса других для «соединения» результата воедино. Если не верите — проведите небольшой эксперимент — напишите парочку маленьких программ на Ассемблере.

                                  «Это дает лишний расход памяти в 4 раза.»
                                  — откуда Вы взяли число 4? В этом случае гораздо больше. 4 будет если взять за основание системы счисления 2^16, а размер базового типа 2^64. И то это расход только на само хранение. Еще куча места выделяется во время подсчета. Кстати, такую организацию памяти придумал не я, если для Вас ето будет аргументом. Так принято хранить длинные числа.

                                  «Вы храните массив цифр в порядке разрядов десятичного числа.»

                                  «Вы путаете основание системы счисления с разрядностью двоичного числа»
                                  — Да нет. Обратите внимание на
                                  #define BASE 10 //система счисления
                                  . Например, число 16400 можно представить в виде a[] = {0,0,4,6,1}, если основание системы 10. А если основание, допустим, 12000, то число примет вид a[] = {4400, 1}
                                  • 0
                                    > Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30
                                    Поясните. Почему это разумно?
                                    > «Это дает лишний расход памяти в 4 раза.»
                                    Погорячился. В Вашей реализации в 8 раз (это учитывая только избыток на хранение одного разряда), поскольку Вы используете 32 бита для хранения числа, вмещающегося в 4. А если посчитать общее занимаемое место — избыточность данных растет экспоненциально
                                    Насчет брать максимальное за раз — все верно. Только к Вашей организации вычислений жтот метод не имеет никакого отношения.
                                    • –1
                                      Поясните. Почему это разумно?
                                      — Пояснения в статье в разделе «Реализация на C++»;

                                      «Только к Вашей организации вычислений жтот метод не имеет никакого отношения.»
                                      — почему же?
                                      • –1
                                        > Длинные числа удобно представлять в виде массивов…
                                        > Для увеличения быстродействия желательно выбрать за основание системы счисления максимальное число в рамках базовых типов
                                        А где обоснование? Почему удобно? С чего Вы взяли, что это увеличит быстродействие? Где это самое увеличение?
                                        • 0
                                          Длинные числа удобно представлять в виде массивов.

                                          Легкая и наглядная форма. Близка к действительному представлению числа в памяти. Автоматически резервирует место для операций умножения и сложения на возможность переполнения разряда.

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


                                          Я с удовольствие узнаю другие методы и подходы. Подкинете?
                                          • 0
                                            Легкая и наглядная форма. Близка к действительному представлению числа в памяти. Автоматически резервирует место для операций умножения и сложения на возможность переполнения разряда.

                                            BCD числа тоже наглядны и экономят 28 байт на цифру.
                                            • 0
                                              Сам по себе BCD здесь не подходит, т.к. десятичной системой ограничиваться нельзя. А принцип тут как раз тот же. Каждый разряд кодируется соотв. двоичным числом.
                              • –3
                                Например, если у вас 100k десятичных знаков, то переводить их в двоичную систему вы их будете дольше, чем умножать. А потом еще результат обратно… Пример — питон, где самая долгая операция с длинными числами — вывод и ввод.
                                Но это в случае, если надо перемножить десятичные числа. А если просто нужна абстрактная длинная арифметика — выбор за вами. Но серьёзного выигрыша там, думаю, не будет.
                                • 0
                                  Я не предлагаю ничего никуда переводить. В памяти компьютера числа уже хранятся в двоичной системе счисления. Подобное представление длинного числа в виде последовательности цифр в последовательности разрядов — одно из самых неоптимальных, на уровне представления строками
                                • 0
                                  Это всё несущественные детали. Хоть в виде массива десятичных цифр храни, хоть в виде родных двоичных — сложность алгоритма останется той же и по расходу памяти и по времени работы.

                                  Другое дело, что массив десятичных цифр удобнее для демонстрации (а цель статьи именно в объяснении алгоритма) и в некотором (пускай и небольшом) классе задач.

                                  • –1
                                    Вы чудовищно заблуждаетесь. Ассимптотическая сложность, безусловно, остается прежней, но не в коем случае нельзя путать ее с вычислительной сложностью алгоритма. Мне попадались чудовищные реализации алгоритма быстрой сортировки, затратные по времени и по памяти, однако формально они были корректны и ассимптотическая сложность сохранялась. Но работали из рук вон плохо. То, что сложность алгоритма O(n) говорит, что рост количества вычислений есть линейная функция. Но к большим числам она может уйти очень быстро
                                    • 0
                                      Именно асимптотическую сложность я и имею в виду)

                                      Если бы автор использовал в статье и в примере двоичную систему счисления статья бы потеряла в наглядности.
                                      • –1
                                        Я к тому, что представленная автором реализация, конечно, показательна, но совершенно не практична. Профессор Карацуба, насколько мне известно, разрабатывал свой метод именно в расчете на двоичную арифметику
                                        • 0
                                          А что Вы считаете нужно изменить, чтобы реализация была практичной ( смену алгоритма на другой не рассматриваем :) )?
                                          • 0
                                            Алгоритм менять не будем, он чертовски хорош :) Я считаю, что нужно использовать не суррогатное представление числа последовательностью цифр на местах разрядов, а в виде непрерывного участка памяти требуемой длины. По результатам диалога с автором думаю заняться реализацией на досуге
                                            • 0
                                              А как Вы это представляете себе?
                                              • 0
                                                Есть такой тип замечательный. void*
                                                • 0
                                                  Я понимаю. Но в чем именно суть? Выделить кусок памяти и «бегать» по нему указателем? Это тот же массив.
                                                  • –2
                                                    Отнюдь. Массив — это последовательность независимых равноразмерных элементов. Я предлагаю хранить не массив разрядов, а непрерывное n-байтное число в двоичной системе. Можно организовать арифметику чисел размерности n.
                                                    Предлагаемый автором способ, собственно, сходится к такому хранению при основании системы счисления 2^n, где n — количество бит для хранения одной цифры разряда (то есть в реализации автора 32)
                                                    • 0
                                                      В том то и дело, что в реальности константа BASE меняется как-раз на число (2^n)
                                                      • 0
                                                        «Массив — это последовательность независимых равноразмерных элементов.»
                                                        What? Массив в C/С++ это последовательность элементов одинакового типа (а следовательно и размера).
                                                    • 0
                                                      Как вы собираетесь адресовывать void*?
                                                      • 0
                                                        По-моему в адресации void * проблем нет — правда много возни с адресной арифметикой и приведениями типов. Просто в конце-концов получится тоже самое.
                                                        • 0
                                                          Адресная арифметика просто не работает с типом void* за отсутствием информации о размере адресуемых элементов.

                                                          Я не понимаю, что автор комментария хотел этим сказать. Он собирается оперировать байтами или чем?
                                                          • 0
                                                            Адресная арифметика просто не работает с типом void*

                                                            адресной арифметикой и приведениями типов.
                                                            • 0
                                                              Чем это будет отличаться от того, что написано у вас? Ничем. Вы и сами так написали, что получится то же самое. Вот поэтому я у автора комментария и хочу узнать, может он что-то другое имел ввиду.
                                                              • 0
                                                                Смещение по указателю + приведение, Вам правильно сказали. Как я отмечал раньше, представление автора неизбыточно только для системы счисления с основанием, равным соответствующей степени двойки. В этом случае разницы нет. Если основание меньше — получается избыточность, растущая экспоненциально с количеством разрядов числа. Фактически эта избыточность не нужна, поскольку числа с верхней границей 2^n можно хранить в линейной памяти и обращаться к нему по указателю. Реализовать арифметические операции в этом случае проблем не составляет. Единственная проблема — это перевод числа в десятичную систему для вывода. Для представления автора, когда основание 10, это тривиально, а для всех других оснований представляет сложности. Поэтому я не вижу особого смысла переходить к таким системам счисления (2^32), никакого выигрыша это не дает
                                                                • 0
                                                                  «Смещение по указателю + приведение» = массив как у автора. Плюс, похоже вы еще собираетесь делать битовые операции, что будет эквивалентно приведению к нужному основанию.

                                                                  Иными словами, вы просто предлагаете способ приема числа, при котором, оно всегда будет приводится к виду, как у автора при использовании правильного основания. Но это лишь вопрос преобразования входных данных. С таким же успехом, автор мог бы строго закрепить нужное основание, а принимать числа в любом формате, хоть в ASCII строке, просто написав нужную функцию.
                                                • –1
                                                  Меня больше всего напрягает, что такое представление числа неизбыточно только для основания системы счисления 2^32, а таких систем я не встречал даже в теории. Для практически значимых систем счисления избыточность просто колоссальная
                                                  • 0
                                                    А какая разница какая система счисления? Арифметика везде одинаковая. Поэтому считать нужно в которой удобно. А приведение к заданной (нужно только в случае вывода результата пользователю) делается за линию.
                                                    • 0
                                                      Разница в скорости вычислений и объеме памяти
                                                      • 0
                                                        системы счисления 2^32, а таких систем я не встречал даже в теории.

                                                        А какая разница какая система счисления?

                                                        Разница в скорости вычислений и объеме памяти

                                                        Что-то винегрет получается. Чем же тогда этот способ плох, если он отлично подходит для этой системы?
                                                        • 0
                                                          Плох тем, что только в предельном случае для системы с основанием 2^n (см. выше) является неизбыточным
                                                          • 0
                                                            Я же и спрашиваю. Чем это плохо?
                                                            • 0
                                                              Чем плоха избыточность? Тем что она не нужна
                                                              • 0
                                                                Зачем же использовать систему счисления для которой представление избыточно? Чем плоха система «основанием 2^n»
                                                                • 0
                                                                  Учитывая, что n не может быть меньше 8, т.е. минимальное основание 256… Покажите мне задачу с использованием такой системы счисления. Тут как раз спрашивали, зачем нужны лишние преобразования систем счисления. Не нужны
                                                                  • 0
                                                                    преобразование из системы в систему за линию + мало операций умножения будет быстрее чем просто решение с большим количеством операций умножения. Еще раз:«Для практической реализации алгоритмов не имеет значение в какой системе значения. Система важна только как результирующие данные для пользователя.
                                                      • +1
                                                        > А приведение к заданной (нужно только в случае вывода результата пользователю) делается за линию
                                                        Каким образом для больших чисел?
                                                        • 0
                                                          Мм… Да, тут действительно у меня ошибка.
                                                          • 0
                                                            Не ошибка. Я столкнулся с такой же проблемой. И тут единственное очевидное решение — как раз использование Вашего представления больших чисел с основанием десять. Других решений пока не вижу. Будем искать
                                                            • 0
                                                              Ну 10 это тоже не вариант. Подойдет любое основание, являющееся степенью 10.
                                        • 0
                                          Мельком глянув заголовок, вспомнил пограничника Карацупа :)
                                          • +1
                                            На самом деле Карацуба работает не n*log23, а nlog23~n1.5. См. вики.
                                            • +1
                                              Еще раз извиняюсь. Спасибо.
                                            • 0
                                              Если я правильно понимаю, то в 32-х разрядных системах использование этого алгоритма покажет прирост в производительности с числами которые находятся за пределами 32-го разряда?
                                              • 0
                                                Да. При чем далеко за пределами.
                                              • +3
                                                в статье автор пошел не снизу, а сверху, и алгоритм по изложению сразу превратился из простейшего, реализуемому обычным студентом за несколько часов, в монстра.
                                                нам когда-то объясняли на примере двузначных чисел, а потом рекурсивно расширяли на числа любой длины, и все все схватывали на лету, и реализовывали без проблем. эту же статью куда сложнее читать
                                                • +1
                                                  Спасибо. В следующий раз учту. У меня была надежда, что тем кому интересно мат. обоснование, прочтут первую часть и пример им не понадобится. А те кому это не нужно прочитают маленький кусочек текста в главе с примером, примут во внимание, что алгоритм рекурсивный и верхний уровни добавлены только для количества примеров.
                                                  • 0
                                                    а как и для чего этот алгоритм применять?

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