Деление длинного числа на длинное

Всем привет!

Решил написать длинную арифметику в самом ее классическом варианте, когда все операции производятся школьным столбиком. Но вот незадача: я использую основание системы счисления 10^9 (миллиард), т.е. каждая цифра моего большого числа от 0 до 999999999. При написании алгоритма деления длинного числа на длинное возникла проблема: поскольку делить на длинное число мы не умеем, то в алгоритме столбика деление нескольких старших разрядов делимого на делитель я осуществляю вычитаниями. Суть в том, что если мы, например, делим число 999999999 на что-то в районе миллиарда, то вычитаний будет около 9ти, и мы спокойно запишем эту цифру в частное. Однако, если я делю число порядка миллиарда на маленькое число, например, 3ку, то вычитаний будет уже миллиард.

Чтобы было понятнее, напишу пример:
Делим число "123456789 123456789" на число "1 123456789" - двузначное на двузначное. Первым шагом вычитаем из старшего разряда "123456789" наш делитель "1 123456789" - не делится, значит берем еще разряд. Теперь вычитаем из числа "123456789 123456789" наш делитель "1 123456789" пока можем вычитать в цикле while. Видно невооруженным глазом, что вычитаний будет порядка миллиарда, что существенно увеличивает время работы деления.

Есть ли какие-то алгоритмы, в которых числа не нужно вычитать? Перерыл весь интернет, ничего не нашел.

0

в "классическом" варианте берется основание системы 2, 256 (1 байт), 2^16 (2 байта), 2^32 (4 байта) ну или 2^64 для 64 - битных систем. алгоритм для них примерно одинаков, и основан на том, как выполняется деление в процессоре. а выполняется оно на основе операций сдвиг-вычитание, насколько я помню, основных "классических" алгоритмов 3. вот то, что получилось найти за 5 минут:
алгоритм: http://www.distedu.ru/mirror/_... m/div.html
пример: http://www.distedu.ru/mirror/_... vsamp.html
еще где-то на интуите было, даже с картинками.
этот алгоритм по аналогии масштабируется на 1, 2 или 4 байта -- и становится все просто. имхо, если писать что-то такое, то имеет смысл только на ассемблере с применением sse и очень аккуратно. на 64-битных машинках основной цикл для чисел не сверх большой разрядности неплохо кладется непосредственно в регистры, без обращения к памяти на запись -- подобная реализация, наверное, была бы интересной, хотя может кто-то уже реализовал...
в противном случае, если цель поизучать алгоритмы -- то это хорошо, см. ссылки выше. если же нужно непосредстенно готовое решение, есть замечательные библиотеки gmp (целые числа), mpfr и mpc (числа с плавающей запятой). в любом случае, ради интереса, можно сравнить свою реализацию с ними=) успехов

1

HrundelB, а зачем такое огромное основание? Если основание 16, то на каждом шаге будет не более 15-ти вычитаний. Результат длинный? Эйси. Предположим в твоём варианте результат стазначный. 100*1000000000=100000000000. 100*lg(1000000000)/lg(16)*15=11220. Нужны комментарии?

0

NEbO, спасибо! Это конечно интересное предложение, но мне, во-первых, хотелось бы все таки доделать ту реализацию, которую я уже на половину сделал, а во-вторых, на ассемблере писать не вариант) А делать сдвиги и вычитания, когда каждая цифра в отдельном элементе массива или вообще односвязного списка - не очень то удобно)

Я почему-то больше чем уверен, что должен быть какой-то способ обойти эту проблему с миллиардом вычитаний. Может быть все-таки есть какие-то алгоритмы деления отличные от столбика? Кроме двоичных.


taras atavin, большое основание (а точнее не просто большое, а являющееся "машинным словом", т.е. оперируем интами, которые аккурат влезают в разрядность процессора) позволяет очень быстро производить умножение, с помощью которого тысяча факториал (1000!) вычисляется за 0,23 сек, при том, что те же методы но с основанием 10 считают его 25 секунд. И это я еще молчу, что умножение - простой столбик, а факториал - обыкновенная и медленная рекурсия.

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

Добавлено через 7 часов 47 минут
NEbO, разобрался с двоичным делением и возник вопрос - и как же это можно масштабировать такое деление на 4 байта допустим? В оригинальном алгоритме считается, что цифра может быть только 0м или 1цей, что позволяет после одного вычитания сразу сказать - надо добавить единицу в частное или нет. Если масштабировать алгоритм на 4 байта, то каждая цифра (именно цифра, не число) будет принимать значение от 0 до 11111111111111111111111111111111 (32 бита). Теперь представь, что мы делим однозначное число 11111111111111111111111111111111 (ну грубо говоря максимально возможную цифру) на число 101. Сколько ж вычитаний сделать придется?)

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

0