Алгоритм для деления очень больших количеств
Я должен записать алгоритм (я не могу пользоваться никакой сторонней библиотекой, потому что это - присвоение) для деления (целочисленное деление, плавающие части не важны), очень большие количества как 100 - 1000 цифр. Я нашел алгоритм http://en.wikipedia.org/wiki/Fourier_division, но я не знаю - ли это правильный способ пойти. У Вас есть какие-либо предложения?
1) check divisior < dividend, otherwise it's zero (because it will be an int division)
2) start from the left
3) get equal portion of digits from the dividend
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1
5) multiply divisor by 1-9 through the loop
6) when it exceeds the dividend portion, previous multiplier is the answer
7) repeat steps 3 to 5 until reaching to the end
5 ответов
Кнут, Дональд, Искусство компьютерного программирования, ISBN 0-201-89684-2, том 2: получисловые алгоритмы, раздел 4.3.1: Классические алгоритмы
Вероятно, вам стоит попробовать что-то вроде длинного деления, но с использованием компьютерных слов вместо цифр.
На языке высокого уровня удобнее всего рассматривать вашу «цифру» как половину вашего наибольшего целого числа фиксированной точности. Для метода деления в длинную строку вам нужно будет обработать случай, когда ваш частичный промежуточный результат может отличаться на единицу, поскольку ваше деление с фиксированной точностью может обрабатывать только наиболее значимую часть вашего делителя произвольной точности.
Существуют более быстрые и сложные способы выполнения арифметических операций произвольной точности. Посетите соответствующую страницу википедии . В частности, метод Ньютона-Рафсона при тщательном внедрении может гарантировать, что временная характеристика вашего деления находится в пределах постоянного множителя вашего умножения произвольной точности.
Если часть вашего задания не должна быть полностью оригинальной, я бы использовал алгоритм, которому меня (и я полагаю, вас) учили в начальной школе, чтобы делать большие деления вручную.
Самый простой алгоритм деления для больших чисел - это сдвиг и вычитание.
if numerator is less than denominator then finish
shift denominator as far left as possible while it is still smaller than numerator
set bit in quotient for amount shifted
subtract shifted denominator from numerator
repeat
the numerator is now the remainder
Сдвиг не обязательно должен быть буквальным. Например, вы можете написать алгоритм для вычитания сдвинутого влево значения из другого значения вместо фактического сдвига всего значения влево перед вычитанием. То же самое и для сравнения.
Деление в столбик сложно реализовать, потому что одним из этапов деления в столбик является деление в столбик. Если делитель - это int, вы можете довольно легко выполнить деление в столбик.
Я полагаю, что разделение «долгого» пути, как в начальной школе, было бы потенциальным путем. Я предполагаю, что вы получаете исходный номер в виде строки, поэтому вам нужно проанализировать каждую цифру. Пример:
Шаг 0:
/-----------------
13 | 453453453435....
Шаг 1: «Сколько раз 13 переходит в 4? 0
0
/-----------------
13 | 453453453435....
Шаг 2:« Сколько раз 13 переходит в 45? 3
03
/-----------------
13 | 453453453435....
- 39
--
6
Шаг 3: «Сколько раз 13 переходит в 63? 4
и т.д. и удвоение (делимое). (Предполагая, что я правильно понял эти термины). Вы сохраняете результат как последнюю цифру в строке результата.
Когда вы достигаете точки, в которой не осталось цифр, и расчет не будет повторяться 1 или более раз , вы возвращаете результат, который уже отформатирован как строка (потому что он потенциально может быть больше, чем int).