Алгоритм целочисленного деления

Я думал об алгоритме деления больших чисел: деление с остатком bigint C на bigint D, где мы знаем представление C в базе b, а D имеет форму b ^ k- 1. Наверное, проще всего показать это на примере. Давайте попробуем разделить C = 21979182173 на D = 999.

• Запишем число в виде наборов из трех цифр: 21 979 182 173
• Возьмем суммы (по модулю 999) последовательных наборов, начиная слева: 21 001 183 356
• Мы добавляем 1 к тем наборам, которые предшествуют тем, в которых мы «прошли 999»: 22 001 183 356

Действительно, 21979182173/999 = 22001183 и остаток 356.

Я вычислил сложность, и, если не ошибаюсь, алгоритм должен работать за O (n), где n - количество цифр C в представлении с основанием b. Я также сделал очень грубую и неоптимизированную версию алгоритма (только для b = 10) на C ++, протестировал ее против общего алгоритма целочисленного деления GMP, и он действительно работает лучше, чем GMP. Я не мог найти ничего подобного, реализованного где бы то ни было, поэтому мне пришлось прибегнуть к тестированию на предмет общего деления.

Я нашел несколько статей, в которых обсуждаются довольно похожие вопросы, но ни одна из них не концентрируется на реальных реализациях. , особенно в базах, отличных от 2. Я полагаю, что это связано с тем, как числа хранятся внутри, хотя упомянутый алгоритм кажется полезным, скажем, для b = 10, даже с учетом этого. Я также пытался связаться с некоторыми другими людьми, но, опять же, безрезультатно.

Таким образом, мой вопрос был бы таков: есть ли статья или книга или что-то еще, где описан вышеупомянутый алгоритм, возможно, обсуждаются его реализации? Если нет, имел бы смысл попробовать реализовать и протестировать такой алгоритм, скажем, на C / C ++, или этот алгоритм каким-то образом плох по своей сути?

Кроме того, я не программист, и хотя я неплохо разбираюсь в программировании, я, по общему признанию, не очень разбираюсь в "внутренностях" компьютера. Таким образом, извините за мое незнание - вполне возможно, что в этом посте есть одна или несколько очень глупых вещей. Еще раз извините.

Большое спасибо!

Дальнейшее разъяснение вопросов, поднятых в комментариях / ответах:

Спасибо всем, как и я » Я не хочу комментировать все замечательные ответы и советы одним и тем же, я просто хотел бы остановиться на одном моменте, который многие из вас затронули.

Я полностью осознаю, что работа с базами 2 ^ n, вообще говоря, , безусловно, наиболее эффективный способ работы. Практически все библиотеки bigint используют 2 ^ 32 или что-то еще. Однако что, если (и я подчеркиваю, это было бы полезно только для этого конкретного алгоритма!) Мы реализуем bigints как массив цифр в базе b? Конечно, мы требуем, чтобы b было «разумным»: b = 10, наиболее естественный случай, кажется достаточно разумным. Я знаю, что это более или менее неэффективно как с точки зрения памяти, так и с учетом времени, с учетом того, как числа хранятся внутри, но я смог, если мои (базовые и, возможно, некорректные) тесты верны, давать результаты быстрее, чем общее деление GMP, что дало бы смысл реализации такого алгоритма.

Ninefingers замечает, что в этом случае мне пришлось бы использовать дорогостоящую операцию по модулю. Надеюсь, что нет: я могу увидеть, пересекается ли старый + новый, скажем, 999, просто взглянув на количество цифр старого + нового + 1. Если в нем 4 цифры, все готово. Более того, поскольку old <999 и new <= 999, мы знаем, что если old + new + 1 имеет 4 цифры (больше не может быть), то (old + new)% 999 равно удалению самой левой цифры ( old + new + 1), что, как я полагаю, можно сделать дешево.

Конечно, я не оспариваю очевидные ограничения этого алгоритма и не утверждаю, что его нельзя улучшить - он может делиться только на определенный класс числа, и мы должны априори знать представление дивиденда в базе b. Однако, например, для b = 10 последнее кажется естественным

. скажем, мы реализовали bignums, как я обрисовал выше. Скажем, C = (a_1a_2 ... a_n) в базе b и D = b ^ k-1. Алгоритм (который, вероятно, можно было бы значительно оптимизировать) выглядел бы так. Надеюсь, здесь не так много опечаток.

• если k> n, мы, очевидно, закончили
• добавляем ноль (т.е. a_0 = 0) в начало C (на всякий случай, если мы попытаемся разделить скажем, 9999 с 99)
• l = n% k (мод для "обычных" целых чисел - не должен быть слишком дорогим)
• old = (a_0 ... a_l) ( первый набор цифр, возможно с менее чем k цифрами)
• для (i = l + 1; i (У нас будет этаж (n / k) или около того итераций)
  • new = (a_i ... a_ (i + k-1))
  • new = new + old (это сложение bigint, поэтому O (k))
  • aux = new + 1 (опять же, сложение bigint - O (k) - что меня не устраивает)
  • если aux имеет более k цифр На самом деле у меня есть некоторые (очень базовые!) Знания о том, как работает GMP, что он делает, и об общих алгоритмах деления bigint, поэтому я смог понять большую часть ваших аргументов. Я также знаю, что GMP сильно оптимизирован и в некотором смысле настраивается для разных платформ, поэтому я, конечно же, не пытаюсь «победить его» в целом - это кажется столь же плодотворным, как атака танка острой палкой. Однако идея этого алгоритма не в этом - он работает в очень особых случаях (которые GMP, похоже, не охватывает). Кстати, вы уверены, что общие деления сделаны за O (n)? Самое большее, что я видел, это M (n). (И это может, если я правильно понимаю, на практике (Шенхаге-Штрассен и т. Д.) Не достичь O (n). Алгоритм Фюрера, который все еще не достигает O (n), является, если я прав, почти чисто теоретический. )

    @Avi Berger: На самом деле это не похоже на «изгнание девяток», хотя идея похожа. Однако вышеупомянутый алгоритм должен работать постоянно, если я не ошибаюсь.