Алгоритм: алгоритм деления алгоритма Дональда Кнута

Question

Я пытаюсь реализовать программу, которая делит два больших числа точности (я беру их как строки). Кто-то из другого вопроса о переполнении стека предложил реализовать алгоритм, описанный в книге «Искусство программирования» Дональда Кнута. Во время чтения у меня есть общее представление об алгоритме, но я смутился в некоторых частях.

1. В алгоритме используется концепция долгосрочного отделения от школы. Я не понял, как программа «угадывает» цифры фактора при выполнении алгоритма.

2. Даже если это «догадывается», как мне разделить часть дивиденда на дивизор? Предполагая, что я должен преобразовать divisor в int ...

3. ... что, если делитель является большим числом? Разве проблема не остается прежней?

Любая помощь будет оценена по достоинству.

Заранее спасибо.

Answer 1

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

UPDATE Принимая намек термином элементарно. Предположим, 1923/695 As | 695 | = 3, возьмите первые 3 цифры divident и попытайтесь разделить. Как 193 < 695 добавьте коэффициент 0 и добавьте еще одну цифру в divident. Теперь мы должны разделить 1923 на 695. Одна плюс стороны этого алгоритма состоит в том, что вы должны угадывать число между 1-9 каждый раз. Чтобы оптимизировать и уменьшить количество догадок, вы можете реализовать, если условия, такие как, если divident -> divisor * 5, ваша догадка будет 6,7,8 и 9. Etcetc.

Я использовал этот метод для вычисления факториалов больших чисел раньше. Надеюсь, это тоже поможет.