Деление больших чисел на строки

Question

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

For ex:
16/5 
Subtract 16-5=11
11-5=6
6-5=1
1 is less than 5 so stop
quotient = 3 and remainder = 1

Но проблема в том, что этот метод очень медленный для очень больших чисел. Какой еще возможный способ сделать это быстро?

Answer 1

Один из способов получить быстрое вычисление bignum - использовать высокие значения для базы.

В качестве примера рассмотрим сумму

12301922342343 +
39234932348823
--------------
51536854691166

При выполнении этого вычисления вручную вы начинаете с самого правогоцифру и сложите их, помня «перенос», если результат превысит 9. Справа налево 3 + 3 = 6, 4 + 2 = 6, 3 + 8 = 1 + перенос 1, 2 + 8 + 1 = 1+ нести 1 и т. д.

Однако вы можете сделать вычисления в виде нескольких цифр ... например,

012 301 922 342 343 +
039 234 932 348 823
-------------------
051 536 854 691 166

Это то же вычисление, что и раньше, но теперь яЯ использую базу 1000 вместо базы 9 (цифры идут от 000 до 999), и я могу использовать тот же подход.Самая правая цифра - 343 + 823 = 166 переноса 001, 342 + 384 + 001 = 691, 922 + 932 = 854 переноса 001 и т. Д.

Для возможности простого умножения (необходимо также для алгоритма деления)) разумный выбор для базы с 32-разрядными целыми числами - 9999, поскольку 9999 * 9999 по-прежнему меньше 2 ** 32 и поэтому может быть вычислен напрямую без переполнений.

Использование базы в форме 10 ** n позволяет легко распечатывать результаты в десятичном виде по одной цифре за раз.

Answer 2

Я вычитаю n * раз число.Однако, как вы говорите, это медленно.

но учтите это:

Dividend   Divisor

123456789  987 

9 digits  vs 3 digits


9 digits - 3 digits = 6 , subtract 1 so the factor is 5: 10^5 = 100.000

так:

9 digits      3+5 digits = 100.000 times

123.456.789 - 987*100.000 = 24.756.789
----------------------------------------------
8 digits      3+4 digits = 10.000 times (now 110.000 times)

24.756.789  - 9.870.000  = 14.886.789
-----------------------------------------------
8 digits      3+4 digits = 10.000 times (120.000 times)

14.886.789  - 9.870.000  = 5.016.789
-----------------------------------------------
7 digits      3+3 digits = 1000 times  (121.000 times)

5.016.789   - 987.000    = 4.029.789
-------------------------------------------------

и так далее ...

Надеждаэто помогает!

Answer 3

есть несколько очень быстрых (O (n log n)) алгоритмов для умножения bignum, поэтому вы можете использовать это с двоичным поиском, чтобы получить O (n * (log n) ^ 2) общее время

Answer 4

В прошлом я пытался запрограммировать bignums, и мое решение состояло в том, чтобы разделить старшие цифры числителя на наиболее значимые цифры знаменателя и откорректировать разницу шкалы. Это первая цифра (ы) ответа. Умножьте это на мой знаменатель и вычтите его из числителя. Затем повторите с этим как новый числитель. Это так же, как долгое деление в начальной школе

10000 / 3
=10/3 * 1000 + ? 
=3*1000 + ?
=3000 + (10000-3000*3)/3
=3000 + (1000 / 3)  //repeat recursively from beginning