Алгоритм деления очень больших чисел

Мне нужно написать алгоритм(я не могу использовать любую стороннюю библиотеку, потому что это задание) для деления (целочисленное деление, плавающие части не важны) очень больших чисел, таких как 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 11
c++ algorithm largenumber

5 ответов:

Кнут, Дональд Искусство программирования, книги 0-201-89684-2, Том 2 получисленные алгоритмы, раздел 4.3.1: в классических алгоритмов

8

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

Шаг 0: 

   /-----------------
13 | 453453453435....
Шаг 1 :" Сколько раз 13 переходит в 4? 0 
     0
   /-----------------
13 | 453453453435....
Шаг 2: "Сколько раз 13 переходит в 45? 3 
     03
   /-----------------
13 | 453453453435....
   - 39
     --
      6
Шаг 3: "Сколько раз 13 переходит в 63? 4

И т. д. С помощью этой стратегии вы можете иметь любую длину числа и только действительно, нужно держать в памяти достаточно цифр для int (делитель) и double (дивиденд). (Предполагая, что я правильно понял эти термины). Результат сохраняется как последняя цифра в строке результата.

Когда вы попадаете в точку, где не остается цифр и вычисление не будет идти в 1 или более раз, вы возвращаете свой результат, который уже отформатирован в виде строки (потому что он может быть потенциально больше, чем int).

11

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

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, то вы можете сделать long разделение довольно легко.

10

Вам, вероятно, следует попробовать что-то вроде длинного деления, но с использованием компьютерных слов вместо цифр.

На языке высокого уровня удобнее всего считать, что ваша" цифра " равна половине размера вашего самого большого числа с фиксированной точностью. Для метода длинного деления вам нужно будет обработать случай, когда ваш частичный промежуточный результат может быть отклонен на единицу, так как ваше деление с фиксированной точностью может обрабатывать только самую значительную часть вашей произвольной точности делитель.

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

2

Если бы часть вашего задания не была полностью оригинальной, я бы пошел с алгоритмом, которому меня (и я предполагаю, что вас) учили в начальной школе для выполнения большого деления вручную.

1