非常大在一個非常大的B分數

Question

我已經做了長數乘法，長數加法，長數減法和長整數除法的功能。但分工需要很長時間，如何改進？這裏是我的代碼：

/// removes unnecessary zeros 
vector<int> zero(vector<int> a) 
{ 
    bool f=false; 
    int size=0; 
    for(int i=a.size()-1;i>=0;i--) 
    { 
     if(a[i]!=0) 
     { 
      f=true; 
      size=i; 
      break; 
     } 
    } 
    if(f) 
    { 
     vector<int> b(size+1); 
     for(int i=0;i<size+1;i++) 
      b[i]=a[size-i]; 
     return b; 
    } 
    else 
     return a; 
} 
/// a+b 
vector<int> sum(vector<int> a,vector<int> b) 
{ 
    if(a.size()>b.size()) 
    { 
     vector<int> rez(3000); 
     int a_end=a.size()-1; 
     int remainder=0,k=0,ans; 
     for(int i=b.size()-1;i>=0;i--) 
     { 
      ans=a[a_end]+b[i]+remainder; 
      if(ans>9) 
      { 
       rez[k]=ans%10; 
       remainder=ans/10; 
      } 
      else 
      { 
       rez[k]=ans; 
       remainder=0; 
      } 
      k++; 
      a_end--; 
     } 
     int kk=k; 
     for(int i=a.size();i>kk;i--) 
     { 
      ans=a[a_end]+remainder; 
      if(ans>9) 
      { 
       rez[k]=ans%10; 
       remainder=ans/10; 
      } 
      else 
      { 
       rez[k]=ans; 
       remainder=0; 
      } 
      k++; 
      a_end--; 
     } 
     if(remainder!=0) 
      rez[k]=remainder; 
     return zero(rez); 
    } 
    else 
    { 
     vector<int> rez(3000); 
     int b_end=b.size()-1; 
     int remainder=0,k=0,ans; 
     for(int i=a.size()-1;i>=0;i--) 
     { 
      ans=b[b_end]+a[i]+remainder; 
      if(ans>9) 
      { 
       rez[k]=ans%10; 
       remainder=ans/10; 
      } 
      else 
      { 
       rez[k]=ans; 
       remainder=0; 
      } 
      k++; 
      b_end--; 
     } 
     int kk=k; 
     for(int i=b.size();i>kk;i--) 
     { 
      ans=b[b_end]+remainder; 
      if(ans>9) 
      { 
       rez[k]=ans%10; 
       remainder=ans/10; 
      } 
      else 
      { 
       rez[k]=ans; 
       remainder=0; 
      } 
      k++; 
      b_end--; 
     } 
     if(remainder!=0) 
      rez[k]=remainder; 

     return zero(rez); 
    } 
} 
/// a & b comparison 
int compare(vector<int> a,vector<int> b) 
{ 
    if(a.size()>b.size()) 
     return 1; 
    if(b.size()>a.size()) 
     return 2; 
    int r=0; 
    for(int i=0;i<a.size();i++) 
    { 
     if(a[i]>b[i]) 
     { 
      r=1; 
      break; 
     } 
     if(b[i]>a[i]) 
     { 
      r=2; 
      break; 
     } 
    } 
    return r; 
} 
/// a-b 
vector<int> subtraction(vector<int> a,vector<int> b) 
{ 
    vector<int> rez(1000); 
    int a_end=a.size()-1; 
    int k=0,ans; 
    for(int i=b.size()-1;i>=0;i--) 
    { 
     ans=a[a_end]-b[i]; 
     if(ans<0) 
     { 
      rez[k]=10+ans; 
      a[a_end-1]--; 
     } 
     else 
      rez[k]=ans; 
     k++; 
     a_end--; 
    } 
    int kk=k; 
    for(int i=a.size();i>kk;i--) 
    { 
     ans=a[a_end]; 
     if(ans<0) 
     { 
      rez[k]=10+ans; 
      a[a_end-1]--; 
     } 
     else 
      rez[k]=ans; 
     k++; 
     a_end--; 
    } 
    return zero(rez); 
} 
/// a div b 
vector<int> div(vector<int> a,vector<int> b) 
{ 
    vector<int> rez(a.size()); 
    rez=a; 
    int comp=-1; 
    vector<int> count(1000); 
    vector<int> one(1); 
    one[0]=1; 
    while(comp!=0 || comp!=2) 
    { 
     comp=compare(rez,b); 
     if(comp==0) 
      break; 
     rez=subtraction(rez,b); 
     count=sum(count,one); 
    } 
    count=sum(count,one); 
    return count; 
} 

Answer 1

你的整個大數量的實現可能相當緩慢。作爲一般規則，您可能需要使用base-2（在32位機器上），即使用機器每個字中的一半位，而不是使用base-10。

確保乘法運算不會溢出32位寄存器。開始實施normalize函數，該函數將規範化爲大數字（即，對於每個存儲的數字，檢查它是否溢出並且如果它確實將餘數應用於下一個數字）。由於數字的範圍較大，因此您將需要更少的存儲器以及更少的模數和除法運算。此外，基數爲2的冪，模數和除法運算比基數爲10的方法快得多。

然後，所有的操作可以基本上按元素進行。此外，預留一位數字比兩位數字更大，然後逐位加數字，最後正常化結果。

在你的分區功能中，它會刪除大量的矢量複製。目前，您正在創建一個3000 int的矢量，該矢量在循環的每次迭代中都被複制和處理，您可能需要考慮實施一個適當的+=(vector,int)操作，該操作將修改矢量，而不是創建具有所有複製的新矢量。

Answer 2

您使用慢速除法算法，並有快速除法算法http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 3

你的問題是你反覆減法，這意味着你正在通過大量迭代運行大量數據。這將導致非常糟糕的表現。

我在年初（在uni任務中）遇到了這個確切的問題。我估計我的原始分裂（使用重複減法）將需要100年才能完成。我實施了長時間分工（就像手工分配數字一樣），同樣的計算花費了大約5毫秒。不是一個壞的改善:)

不幸的是，我沒有使用多年的分裂，所以我忘記了如何去做。我很快找到了我可以嘗試重新學習並實施長期分工的最專業的網站。我用這個：http://www.coolmath4kids.com/long-division/long-division-lesson-1.html。是的，這是正確的哈哈哈。該網站實際上幫助。我在幾個小時內修復了我的算法。

顯然你不必使用該網站，但你必須使你的算法更好。除了長期分工之外，還有更有效的方式來做這件事，但我發現長期分工在效率和實施的難易之間取得了良好的平衡。