Как разделить большие числа и какой алгоритм использовать

Question

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

Мне было интересно, какой алгоритм (ы) использовать? Можно ли использовать алгоритм Newton–Raphson division или, может быть, следует использовать алгоритм, который мы узнали в школе?

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

Answer 1

Это мои любимые алгоритмы, которые я использую:

1. Деление
   Посмотрите здесь: http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html
   Это то, что вы должны начать с. Это не так медленно, и это просто. Не забудьте правильно проверить свои операции +, -, <<, >> перед началом работы. Они должны работать безупречно на любой вход

2. Division наполовину биты арифметике
   посмотреть здесь: https://stackoverflow.com/a/19381045/2521214
   С небольшой настройки вы можете адаптировать его к массивам. Использует +, -, *, /, %. Если вы правильно закодировали, это должно быть намного быстрее, чем двоичное деление.

3. приближение разделения
   Посмотрите здесь: https://stackoverflow.com/a/18398246/2521214
   Или для некоторой скорости до точки х^2, х * у здесь: Fast bignum square computation
   Это больше подходит для плавающей/точка разделения фиксированной. Это немного сложнее понять, но скорость и точность стоит того. Кроме того, существует множество других алгоритмов аппроксимации, поэтому google!