Вычисления с целыми числами (разминка для мозгов)

[B3LYP]

Я написал программу на Delphi - простой калькулятор для вычислений с целыми числами любого размера (мне захотелось написать такую программу, чтобы разобраться с RSA-шифрованием). Предлагаю пораскинуть мозгами, какой должен быть алгоритм для такой программы при правильном программировании. Опишу что написал, но сознательно не буду цитировать свой код, потому что тема скорее не программистская а математическая или может быть философская.
Ясно, что каждое такое число должно быть динамическим массивом. Я сделал десятичные числа, т.е. каждый элемент массива это цифра от 0 до 9.
Всем понятно, как сделать сложение двух таких чисел - один прогон цикла от последней цифры справа до крайней цифры слева у большего числа. Сделать умножение чуть сложнее, и здесь уже возникает такой вопрос - если мы говорим что "оптимизацией мы можем особо не заморачиваться", до какого предела этот принцип можно притворять в жизнь. Скажем, самый простой алгоритм умножения A на B - взять 0 и прибавлять к нему B, и так A раз. Но понятно что если мы будем работать с числами длиной 200 байт (какие используются в RSA шифровании), то с таким алгоритмом умножение двух чисел займёт тысячу лет. Значит в какой-то степени придётся всё-таки "заморочиться" с оптимизацией.
И тут я могу сказать, что мой опыт говорит, что для оптимизации сложных алгоритмов бывает важно не делать никакую низкоуровневую оптимизацию. Дело в том что сложный алгоритм надо писать без ошибок, оптимизация повышает вероятность ошибок, поэтому писать надо максимально структурированный код - разбивая код на отдельные "ортогональные" фрагменты, упакованные например в классы. Проиллюстрирую это описанием своего алгоритма умножения чисел: с ним чуть-чуть падает скорость из-за всяких присвоений от одного объекта к другому, но это мелочь, а важнее чтобы алгоритм был максимально понятен (это тоже причина почему я под спойлером пишу текст а не код - понятный алгоритм можно выразить словами а не кодом, подобно тому как в хорошем научпопе автор пытается по возможности вместо формул писать текстом):

(Оффтоп)

Чтобы умножить A на B, делаем прогон цикла по всем цифрам A; берём цифру, умножаем на неё B (это значит что надо добавить функцию - умножение длинного числа на одну цифру от 0 до 9, это один цикл), далее сдвигаем разряды у произведения влево на номер цифры считая справа (это значит что надо добавить функцию shl, по сути умножение числа на 10 в степени n), и это всё суммируем. Итоговая сумма будет искомым произведениием.

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

[dgwuqtj]

Вы переизобретаете длинную арифметику? Это всё написано в классических учебниках. Например, Кнут, Искусство программирования, том 2.

[peg59]

Гораздо быстрее умножать/делить алгоритмом "в столбик/уголком" по-школьному, используя вместо десятичных разрядов (цифр), например, сразу 32-битные (или 64-битные) числа, которые процессор перемножает за один такт.

[B3LYP]

dgwuqtj в сообщении #1721484 писал(а):

Вы переизобретаете длинную арифметику? Это всё написано в классических учебниках. Например, Кнут, Искусство программирования, том 2.

Ну я всю жизнь "изобретаю велосипеды", у меня мозг так работает что проще самому придумать сложный алгоритм, чем читать документацию. Мне кажется довольно интересно обсудить на форуме такие подробности про числа.

[Евгений Машеров]

Оптимизация бывает "по-маленькому" и "по-большому". Первое это шлифовка программы, избавление от повторных вычислений уже имеющегося, удаление ненужных присваиваний и т.п. При этом современные компиляторы уже в значительной степени эту работу выполняют. И в любом случае ею осмысленно заниматься, когда исчерпаны возможности большой оптимизации - замены алгоритма на более эффективный.
Истязать себя Кнутом стоит, не только ради неизобретения велосипедов, но прежде всего потому, что там уже и мотоциклы есть.
Ваш алгоритм квадратичен по сложности (да, и про это Кнут тоже написал), а уже есть куда более эффективные. Вплоть до $n \log n$

[B3LYP]

Мой алгоритм деления:

(Оффтоп)

Предположим, надо разделить 236587 на 871. Берём 871 и сдвигаем на 3 разряда влево, получаем 871000. Пытаемся вычесть 871000 из 236587 - не получилось, соответственно первая цифра результата 0. После этого сдвигаем делитель на разряд вправо, получаем 87100. Теперь вычитаем 87100 из 236587 до тех пор, пока не упрёмся в отрицательные числа (точнее моя процедура A-B возвращает false, если B>A). Вычесть удалось 2 раза, соответственно вторая цифра результата 2, а после вычитания осталось 62387. Теперь сдвигаем 87100 ещё вправо, получаем 8710, и вычитаем 8710 из 62387 до тех пор пока не упёрлись в ноль (удалось вычесть 7 раз), и так далее. В итоге получаем результат 271, а то что осталось от исходного числа после всех вычитаний (546) это остаток от деления.

[Евгений Машеров]

Ну, изобрели Вы деление в столбик. Меня где-то в третьем классе ему научили, но, возможно, школьная программа изменилась. Это работающий алгоритм, но малопригодный для длинной арифметики. Обычно находят методом Ньютона обратную к делителю, а затем на неё умножают (да, и алгоритм умножения тоже не Ваш).

[dgwuqtj]

B3LYP в сообщении #1721528 писал(а):

Теперь вычитаем 87100 из 236587 до тех пор, пока не упрёмся в отрицательные числа (точнее моя процедура A-B возвращает false, если B>A).

В серьёзных программах так не делают, потому что все работают сразу в $2^{32}$-ричной или $10^9$-ричной системе счисления (или ещё больше), а вычитать миллиард раз долго. Хотя для десятичной системы счисления сойдёт.

Если так хочется поизобретать велосипед, лучше придумайте, как извлекать квадратные корни. Этому хотя бы не учат в школе.

Евгений Машеров в сообщении #1721529 писал(а):

Это работающий алгоритм, но малопригодный для длинной арифметики. Обычно находят методом Ньютона обратную к делителю, а затем на неё умножают (да, и алгоритм умножения тоже не Ваш).

Как я понимаю, в эффективных реализациях и умножение, и деление в столбик вполне используются, когда одно из чисел не слишком большой длины, скажем, до $2^{320}$.

[nnosipov]

dgwuqtj в сообщении #1721531 писал(а):

Этому хотя бы не учат в школе.

Раньше учили. Думаю, и сейчас в некоторых школах учат.

[B3LYP]

Евгений Машеров в сообщении #1721529 писал(а):

Ну, изобрели Вы деление в столбик. Меня где-то в третьем классе ему научили, но, возможно, школьная программа изменилась. Это работающий алгоритм, но малопригодный для длинной арифметики. Обычно находят методом Ньютона обратную к делителю, а затем на неё умножают (да, и алгоритм умножения тоже не Ваш).

Моя тема всё-таки была отчасти про программирование: как закодить этот алгоритм, чтобы минимизировать вероятность сделать ошибки. Тут используются всякие ООП, структурное программирование (ну вот у меня, как можно догадаться, каждое "суперчисло" это класс).
Поясните, что такое метод Ньютона - вроде градиентного спуска?
Если градиентным спуском находить цифру от 0 до 9, всё равно решающего ускорения не добиться, можно только ускорить вычисление в 2-3 раза.
Мой алгоритм станет ещё понятнее, если перейти от десятеричных чисел к двоичным: тогда не нужны циклы, их можно заменить if-ами. Вот ещё раз алгоритм:

(Оффтоп)

Предположим, нам надо поделить двоичное число 100010 на 101. Сначала делаем shl на три разряда для второго, получаем 101000. Далее нам надо вычесть 101000 из 100010. И тут по-моему оптимально именно не вычитать вначале, а сравнить эти два числа - по разрядам слева направо. Мы видим что второе число больше, соответственно первую цифру результата пишем как 0, и делаем shr 1 для второго числа, получаем 10100. Далее вычитаем 10100 из 100010 и так далее.

[realeugene]

B3LYP
Вы издеваетесь?

Ну пойдите в школу юного программиста для начала. Основы программирования нужно изучать до переходя к алгоритмам. Вы не сможете научиться умножать, не освоив предварительно сложение.

[wrest]

B3LYP в сообщении #1721533 писал(а):

как закодить этот алгоритм, чтобы минимизировать вероятность сделать ошибки.

Ну как-как... Закодить и проверить работает ли.

[B3LYP]

Раз уж тема про разминку для мозгов, может кто-нибудь напишет понятное описание алгоритма Бурникеля — Циглера для деления чисел?
Мне кажется у меня хорошо получается понятно излагать многие вещи, только сначала самому надо понять, а это самое сложное т.к. никто мне нормально не излагает. Напишу как пример, как работает алгоритм быстрой сортировки в варианте структурного программирования. У нас есть массив из N чисел, и их надо отсортировать. Находим среднее значение по всем числам. Создаём два массива, в первый добавляем все числа меньше этого среднего, во второй - больше. В обоих массивах запускаем точно такую же процедуру быстрой сортировки (т.е. включаем рекурсию). Переводим числа из двух этих вспомогательных массивов в исходный.

[dgwuqtj]

B3LYP в сообщении #1721564 писал(а):

Находим среднее значение по всем числам. Создаём два массива, в первый добавляем все числа меньше этого среднего, во второй - больше.

Какой-то плохой вариант быстрой сортировки. Тут и используется специфика чисел (у строк или пар чисел вы среднее не посчитаете), и могут быть проблемы с переполнением/точностью, и легко подобрать пример, когда время работы квадратично зависит от длины. А ещё среднее долго считается и тратится память, но это уже не фундаментальные проблемы.

[Dmitriy40]

Если что, на другом форуме обсуждение ровно этого же (очевидно ТС там тот же и пишет идентичные тексты) идёт более активно.