Разделив два числа с более чем 50 цифр (максимум 200) алгоритм

Question

Каков наилучший способ разделяй два числа, которые имеют более 50 цифр, но менее 200.

У меня есть структуру представлять ряд:

struct number{ 

    int digit[MAX_SIZE]; // MAX_SIZE = 5; 
    bool negative; // Is it negative or positive number 
}; 

Проблема, с которой я сталкиваюсь при попытке реализовать этот алгоритм является то, что, если я пытаюсь разделить число «п» с a число 'm'(n> m), у которого есть больше цифр, которые вы можете сохранить в переменной, как вы можете ее разделить?

Например: 1234567891234567891234567/12345678912345678

Моя первая догадка делать с повторных вычитаний, но не то, что слишком медленно?

Answer 1

Подумайте о том, как сделать это вручную:

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

В вашем случае: Первое число имеет 25 цифр, а второе число - 17 цифр.

Итак, вы начинаете с цифры, соответствующей 1E8.

Вот несколько псевдокодов C-стиля.

struct number n1 = 1234567891234567891234567; 
struct number n2 = 12345678912345678; 
int start = floor(log10(n1) - log10(n2)); // Position of most significant digit in answer 
struct number result = 0; 
int i,j; 
struct number remainder = n1; 

// Start with the most significant digit 
for i = start to 0 { 
    // Find the highest digit that gives a remainder >= 0 
    for j = 9 to 0 step -1 { 
    if (remainder - j * n2 * pow(10, i) >= 0) { 
     // We found the digit! 
     result = result + j * pow(10, i); 
     remainder = remainder - j * n2 * pow(10, i); 
     break; // Move on to the next digit 
    } 
    } 
} 
// We now have the result and the remainder.