Длинное деление в столбик

[Utkin]

Да по школьному, но для больших чисел. Собственно все получается, но основная проблема в том, что это медленно. Основная проблема в подборе числа на которое делится фрагмент делимого.
Например нужно нам 125 по-делить 6.
Так вот я беру 12 и вычитаю с него 6 пока это возможно. Ладно мелочь вроде, но если взять число 123456789 и поделить его на 6213, то вычитание будет гораздо медленней. Аналогично, чем больше разрядов, тем медленней процесс, потому что вычитание тоже самописное. А это уже потому, что есть вероятность деления на число не умещающееся в стандартный числовой тип Дельфи (собственно для этого и стараюсь). Есть варианты по ускорению процесса?

Зы. Про Окулова знаю.

[_-Re@l-_]

Ну, я например сначала реализовал длинное вычитание, а затем с помощью него делал деление. Скорость была вполне неплохая.

[Utkin]

Сообщение от _-Re@l-_

Ну, я например сначала реализовал длинное вычитание, а затем с помощью него делал деление. Скорость была вполне неплохая.

И у меня так. Я хочу быстрей . Неплохая скорость для чисел с числом разрядов менее 100. Возможно существует способ как-то не полностью вычитать...

[pu4koff]

Тут еще вопрос в том, в каком виде числа хранятся. Если это строка с десятиричным числом (1 символ = 1 разряду), то быстрее вряд ли получится. Если же попробовать замутить какую-нибудь 10000-ричную систему счисления, то ,возможно, на том же алгоритме удастся получить лучшие результаты за счет уменьшения числа операций.
Это всё правда теоретически. У самого руки до длинной арифметики так и не дошли

[still_alive]

2ой том Кнута. Он использует алгоритм получения обратной величины для деления и доказывает, что асимптотически сложность алгоритма деления в этом случае не превышает сложности алгоритма умножения. Все будет зависеть от вашей реализации умножения. Можете про это тоже у него прочитать или еще где-нибудь.

[Utkin]

Да числа хранятся так 1 байт - 1 разряд. Насчет 10000 - это тоже не выход - просто оптимально для определенного диапазона.

2ой том Кнута. Он использует алгоритм получения обратной величины для деления и доказывает, что асимптотически сложность алгоритма деления в этом случае не превышает сложности алгоритма умножения. Все будет зависеть от вашей реализации умножения. Можете про это тоже у него прочитать или еще где-нибудь.

Проблема книг Кнута в том, что они написаны Кнутом для Кнута, а не для людей. Чувствуете разницу?

[still_alive]

Сообщение от Utkin

Проблема книг Кнута в том, что они написаны Кнутом для Кнута, а не для людей. Чувствуете разницу?

Нет. Я чувствую разницу только между тем, кто понимает математику, и между тем, кто ее не понимает. Как я понимаю, вы тоже эту разницу чувствуете)

[mihali4]

Сообщение от Utkin

Есть варианты по ускорению процесса?

Зы. Про Окулова знаю.

Окулова не читал, не знаю, не приходилось.
Мысль такая (ваш пример "если взять число 123456789 и поделить его на 6213").
Делимое - М разрядов, делитель - N разрядов.
Выделяем M-N+1 старших разрядов делителя и делим на цифру старшего разряда делителя (или вычитаем, если вам так дорого именно вычитание). Получаем первое частное. Вернее, почти точную целую часть частного.
Попадаем сразу в +-1. То есть, если N младших разрядов делимого (вернее, число, соответствующее им) больше делителя, то +1 к полученному частному, если меньше - то -1. Или +0.
Ну, а насчет "ковыряния" с остатком не думал. Лень
Вот как-то примерно вот так...
А может, я и не прав...

[still_alive]

Кстати да, на алголисте был описан алгоритм деления с помощью угадывания частного с последующей его корректировкой. Сложность вроде ~O(произведение длин чисел). Не самый быстрый, конечно, но всяко быстрее тупого вычитания.

[Utkin]

Сообщение от still_alive

Нет. Я чувствую разницу только между тем, кто понимает математику, и между тем, кто ее не понимает. Как я понимаю, вы тоже эту разницу чувствуете)

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

Делимое - М разрядов, делитель - N разрядов.
Выделяем M-N+1 старших разрядов делителя и делим на цифру старшего разряда делителя (или вычитаем, если вам так дорого именно вычитание). Получаем первое частное. Вернее, почти точную целую часть частного.
Попадаем сразу в +-1. То есть, если N младших разрядов делимого (вернее, число, соответствующее им) больше делителя, то +1 к полученному частному, если меньше - то -1. Или +0.

Мысль интересная, попробую реализовать на практике. Только мне кажется в не в +-1, а именно в -1 либо нуль.