C++ Long Division

Question

Во время работы над моим личным проектом я столкнулся с необходимостью разделить два очень больших произвольных числа (каждое число имеет примерно 100 цифр). Итак, я написал очень простой код для деления (т. Е. Answer = a/b, где a и b вменяется пользователем) и быстро обнаружил, что он имеет только 16 цифр! На этом может быть очевидно, что Im не кодер!

Итак, я обыскал в Интернете и нашел код, который, насколько я могу судить, использует традиционный метод длинного деления, создавая строку (но тоже честно, не уверен, что их довольно смущает). Но после запуска кода он выдает некоторые неправильные ответы и вообще не работает, если a> b. Я даже не уверен, есть ли лучший способ решить эту проблему, чем метод в коде ниже !? Может быть, есть более простой код?

Так что в основном мне нужна помощь для написания кода на C++ для разделения двух очень больших чисел. Любая помощь или предложения приветствуются!

#include <iostream> 
#include <iomanip> 
#include <cmath> 

using namespace std; //avoids having to use std:: with cout/cin 



int main (int argc, char **argv) 
{ 
    string dividend, divisor, difference, a, b, s, tempstring = ""; // a and b used to store dividend and divisor. 
    int quotient, inta, intb, diff, tempint = 0; 
    char d; 

    quotient = 0; 

    cout << "Enter the dividend? ";  //larger number (on top) 
    cin >> a; 
    cout << "Enter the divisor? ";   //smaller number (on bottom) 
    cin >> b; 

    //making the strings the same length by adding 0's to the beggining of string. 
    while (a.length() < b.length()) a = '0'+a;   // a has less digits than b add 0's 
    while (b.length() < a.length()) b = '0'+b;   // b has less digits than a add 0's 

    inta = a[0]-'0';      // getting first digit in both strings 
    intb = b[0]-'0'; 

    //if a<b print remainder out (a) and return 0 
    if (inta < intb) 
    { 
     cout << "Quotient: 0 " << endl << "Remainder: " << a << endl; 
    } 


    else 
    { 
     a = '0'+a; 
     b = '0'+b; 
     diff = intb; 
     //s = b; 
     // while (s >= b) 

     do 
     { 
      for (int i = a.length()-1; i>=0; i--)   // do subtraction until end of string 
      { 
      inta = a[i]-'0';     // converting ascii to int, used for munipulation 
      intb = b[i]-'0'; 
      if (inta < intb)     // borrow if needed 
      { 
       a[i-1]--;       //borrow from next digit 
       a[i] += 10; 
      } 
      diff = a[i] - b[i]; 
      char d = diff+'0'; 
      s = d + s;       //this + is appending two strings, not performing addition. 

      } 
     quotient++; 
     a = s; 
     // strcpy (a, s); 
     } 

     while (s >= b); // fails after dividing 3 x's 

    cout << "s string: " << s << endl; 
    cout << "a string: " << a << endl; 
    cout << "Quotient: " << quotient << endl; 
    //cout << "Remainder: " << s << endl; 

    } 

    system ("pause"); 
    return 0; 
    cin.get(); // allows the user to enter variable without instantly ending the program 
    cin.get(); // allows the user to enter variable without instantly ending the program 

}

Answer 1

Есть гораздо более эффективные методы, чем это. Этот вычитательный метод сколь угодно мал для больших дивидендов и малых делителей. Канонический метод приведен в качестве алгоритма D в Knuth, D.E., Искусство программирования, том 2, но я уверен, что вы найдете его в Интернете. Я был бы удивлен, если бы он не был в Википедии.