考え方が簡単で間違いやすい大整数四則演算
9594 ワード
問題の構想が簡単で間違いやすい大整数四則演算のように、
加減算の考え方は似ていて、まず加減算後の処理進位や借位に対応しています.
加算と減算は、進位しながら加減しながら進位を処理することもできます.乗算はずれのサイクルでちょうど私たちの手で計算する過程なので、最後に進位を処理するのは便利です.
除算についてしばらく考えていたが,インターネットで検索したところ,ほとんどがシミュレーション手算の過程であり,シフト後に対応ビットが減算され,負数になるまで減算され,減算の回数−1が対応ビットの商値が外ループから飛び出した条件は除数より余剰が小さいことである
午後中書いてやっと書けました...手作業能力の向上が待たれる.基本的に1つの演算子は1時間で、除算は最も長いです...これから何度も書くと速度が上がるでしょう.
最初はクラスを書かずに直接書いたいくつかの関数は,授業で学んだオブジェクト向けに応答するためにbigNumクラスにカプセル化された.
参考ページ
大数乗算http://sumile.blog.hexun.com/62509182_d.htmlhttp://www.cnblogs.com/hicjiajia/archive/2010/09/26/1836337.html
moocフォーラムのプログラム設計実習討論
「機械演算除算のような方法を使って、実際に減算することができます.12345で13を除算すると、まず1300(さらに10倍拡大すると12345より大きくなります)を見つけ、12345から1300を繰り返し減算し、9回後に減少しないと、1番目の商は9で、残りの数から130を繰り返し減算し、2番目の商を得ることができます.」
大数除算は最も実現しにくいはずだ.配列aをbで割ったと仮定すると、実現には2つの方法がある.さらにa[1]a[2]すなわち12を取り、bより小さいことを発見すると、1ビット多く取り、a[1]a[2]a[3]すなわち123を取り、bを5回減らし、a={0 0 0 0 0 0 8 1}を得、result={0 1 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0}を得る.さらにa[3]a[4]すなわち81をとり,bを3回減らしてa={0 0 0 0 1 2},result={0 1 0 5 3}とする.方法によって計算すれば、効率は許せない.11111を1で割ると、方法は1で11111回計算され、方法2では5回しか計算されません.以下は方法2のコードで、簡単なテストを経た(データ検査をしていないで、データがすべて正常だと仮定します):http://blog.csdn.net/sunmenggmail/article/details/7532522加算:O(n)は手で計算する方法に似ていて、1つのforサイクルの小さいその数、それから1つのビットごとに対応して加算して、進位があるのは前のビットの数に1つの減算を加えます:O(n)は同じ理屈で加算して、ただ1つのビットごとに対応して減算して、もし対応して減算するならば負の数で、このビット+10、前のビットを1つ減算します:O(n^2)私は手のアルゴリズムを使って、2つのfor、1サイクル乗数1サイクル被乗数を乗数のあるビットで被乗数の各ビットに乗算した結果/10がキャリー、%10が保持除算を行います:O(nlogn)これは特に難しく、2日間==と考えました.ここのフォーラムのもう一つのpo主のアルゴリズム、すなわちA/B(w.l.o.g.A>B)を仮定し、まず2つの数のビット差を計算する.すなわち、Aが10ビット、Bが5ビットであると仮定すると、ビット差は5になる.Bを左に5ビットシフトする(自分でメンバー関数を書いたが、<機械演算除算のような方法を再構築することはできず、実際には減算を行う.12345除算13を仮定すると、まず1300(さらに10倍拡大すると12345より大きくなる)を見つけ、12345から1300を繰り返し、9回後に減少が足りない場合は、1番目の商は9であり、残りの数から130を繰り返し減算し、2番目の商を得る.このように推す.基本的な考え方は引き算を繰り返して、被除数から最大何個の除数を減らすことができるかを見て、商はいくらです.一つ一つ減らすのは明らかに遅すぎて、どのようにもっと速く減らすのですか?7546を23で割った例で見ると、開始商は0です.まず23の100倍を引くと2300になり、3回減らすことができ、残りは646だった.すると商の値は300増加します.その後646で230を引くと、2回減らすことができ、残りの186は、商の値が20増加した.最後に186で23を減らして8回減らすことができるので、最終商は328です.そこで本題の核心は,大きな整数の減算関数を書き,その関数を繰り返し呼び出して減算操作を行うことである.除数の10倍、100倍を計算する場合は、乗算せずに除数の後に0を補うだけです.http://www.cnblogs.com/c840136/articles/2168405.html http://wenwen.soso.com/z/q24755485.htm http://www.melory.me/2013/03/09/%E5%A4%A7%E6%95%B0%E9%99%A4%E6%B3%95%E8%BF%90%E7%AE%97/http://www.melory.me/2013/03/09/%E5%A4%A7%E6%95%B0%E9%99%A4%E6%B3%95%E8%BF%90%E7%AE%97/
簡単な時間分析をして、間違ったところがあれば、軽く撮ります.+,何も言うことはありませんが,O(max(m,n)),m,nはそれぞれoperand 1,operand 2の桁数で,ここでは100にしましょう.-、プラスと同じか、またはそれ以上のシングル、例えば、999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999X,アナログ手算時間はO(m*n),m,nここで最大100とし,時間はO(n^2),n=100とする.もっと早い「karatsuba algorithms」O(n^(3/2))、実現しやすいです.もっと速い私にはよくわかりませんが、O(n*log(n)./、いろいろな実現方法があるそうです:1)9800000/12=」9800000-1200000=)つまり12を補い、残りが12未満になるまで連続して減らします.時間O(n^2)あ、だって、最悪は一桁ごとに減らさなきゃいけないから、99999999/1とか、毎回減算して、時間は、O(1+2+3+4+…+n)=O(n^2).2)シミュレーション手算時間はO(((n−m＋1)*m),nは被除数のビット数長,mは99999999/11のような除数のビット数長,ここではN=7,m=2である.mが小さい場合は速く、mが大きい場合は速く、m=n/2の場合は遅くなります.99/11を求めるときは連減を使います.3)試商は最も遅いもので,Xを用いるため,Xの時間O(N^2)を用いると,最も速い試商法もO((n−m)*m*(log(10^(n−m))を用いる.nが被除数の桁数長であれば,mが除数の桁数長であり,binary searchで試商する時間もO(log(10^(n−m))を要するため,m=n/2であれば遅い.それから除法がないので、binary searchの使い方が分かりません.Xを用いる時間がO(N^(3/2))、運転時間も、O((n-m)*m)^(3/2)*(log(10^(n-m))だから除算は乗算に使われたほうがいいです. https://class.coursera.org/pkupop-001/forum/thread?thread_id=463
私は主にシフトと減算を利用して除算演算を行います:例えば123456/12.まず12を4ビット(6-2=4)にシフトして120000になり、次いで123456でマイナス数まで減少する.2.次に、12を3ビットシフト、12000とし、第1ステップの減算残り数(3456)で12000を負の数まで減算.このようにして、12シフト0まで.皆さんはもっと简単な方法がありますか??https://class.coursera.org/pkupop-001/forum/thread?thread_id=404
加減算の考え方は似ていて、まず加減算後の処理進位や借位に対応しています.
加算と減算は、進位しながら加減しながら進位を処理することもできます.乗算はずれのサイクルでちょうど私たちの手で計算する過程なので、最後に進位を処理するのは便利です.
除算についてしばらく考えていたが,インターネットで検索したところ,ほとんどがシミュレーション手算の過程であり,シフト後に対応ビットが減算され,負数になるまで減算され,減算の回数−1が対応ビットの商値が外ループから飛び出した条件は除数より余剰が小さいことである
午後中書いてやっと書けました...手作業能力の向上が待たれる.基本的に1つの演算子は1時間で、除算は最も長いです...これから何度も書くと速度が上がるでしょう.
最初はクラスを書かずに直接書いたいくつかの関数は,授業で学んだオブジェクト向けに応答するためにbigNumクラスにカプセル化された.
#include
using namespace std;
class bigNum
{
public:
string result,big;
string add(const string &a_,const string &b_);
string sub(const string &a_,const string &b_);
string mul(const string &a_,const string &b_);
string div(const string &a_,const string &b_);
string operator + (const bigNum &B_);
string operator - (const bigNum &B_);
string operator * (const bigNum &B_);
string operator / (const bigNum &B_);
};
string bigNum::operator + (const bigNum &B_)
{
add(big,B_.big);
return result;
}
string bigNum::operator - (const bigNum &B_)
{
sub(big,B_.big);
return result;
}
string bigNum::operator * (const bigNum &B_)
{
mul(big,B_.big);
return result;
}
string bigNum::operator / (const bigNum &B_)
{
div(big,B_.big);
return result;
}
string bigNum::add(const string &a_,const string &b_)
{
string a,b,c_tem;
int *tem;
char *re;
unsigned i,j;
a = a_ ;b = b_;
if(a.length() < b.length()){c_tem = a; a = b; b = c_tem;}
tem = new int[a.length() + 1];// 1
re = new char[a.length() + 2];// '\0'
for(i = 0;i < a.length() + 1;i++)tem[i] = 0;//
for(i = 0;i < a.length() + 2;i++)re[i] = '\0';
for(i = 0,j = 0;i < a.length();i++)
{
if(i >= (a.length() - b.length()))
tem[i+1] = (a[i] - 48) + (b[j++] -48);
else tem[i+1] = a[i] - 48;
}
for(i = a.length();i > 0;i--)//
{
if(tem[i] >= 10)
{
tem[i-1] += 1;
tem[i] -= 10;
}
}
i = 0;
while(tem[i] == 0)i++;// 0
for(j = 0;i < a.length() + 1;i++,j++)// 0
re[j] = tem[i] + 48;
result = re;
delete []re;
delete []tem;
return result;
}
string bigNum::sub(const string &a_,const string &b_)
{
string a,b,c_tem;
unsigned sign = 0,i,j;
int *tem ;
char *re ;
a = a_; b = b_;
if(a.length() < b.length()){c_tem = a; a = b; b = c_tem;sign = 1;}
else if(a == b){result = "0";return result;}
else if(a.length() == b.length() && a < b){c_tem = a; a = b; b = c_tem;sign = 1;}
tem = new int[a.length()];
re = new char[a.length() + 1];//
for(i = 0;i < a.length();i++)tem[i] = 0;
for(i = 0;i < a.length() + 1;i++)re[i] = '\0';
for(i = 0 ,j = 0;i < a.length();i++)
{
if(i >= (a.length() - b.length()))tem[i] = a[i] - b[j++];
else
tem[i] = a[i] -48;
}
for(i = a.length() -1;i > 0 ;i--)//
{
if(tem[i] < 0)
{
tem[i-1] -= 1;
tem[i] += 10;
}
}
i = 0;
while(tem[i] == 0)i++;//
if(sign)
{
for(j = 1; i < a.length();i++,j++)re[j] = tem[i] + 48;
re[0] = '-';
}
else
for(j = 0; i < a.length();i++,j++)re[j] = tem[i] + 48;
result = re;
delete []tem;
delete []re;
return result;
}
string bigNum::mul(const string &a_,const string &b_)
{
unsigned i,j;
string a,b,c_tem;
int *tem;
char *re;
a = a_,b = b_;
tem = new int[a.length() + b.length()];
re = new char[a.length() + b.length() + 1];
for(i = 0;i < a.length() + b.length();i++)tem[i] = 0;
for(i = 0;i < a.length() + b.length() + 1;i++)re[i] = '\0';
for(i = 0;i < a.length();i++)
for(j = 0;j < b.length();j++) //
tem[i + j + 1] += (a[i] - 48) * (b[j] - 48);
for(i = a.length() + b.length() - 1;i > 0;i--)//
{
if(tem[i] >= 10)
{
tem[i-1] += tem[i] / 10;
tem[i] %= 10;
}
}
i = 0;
while(tem[i] == 0)i++;
for(j = 0;i < a.length() + b.length();i++,j++)
re[j] = tem[i] + 48;
result = re;
delete []re;
delete []tem;
return result;
}
string bigNum::div(const string &a_,const string &b_)
{
string a,b,c_tem,mod,test;
char *re;
unsigned i,len_a,len_b;
int tem = -1,n_re = 0,k = 0;
a = a_; b = b_;
if(a.length() < b.length()){result = "0";return result;}
else if(a.length() == b.length())
{
if(a < b)
{
result = "0";
return result;
}
else if(a == b)
{
result = "1";
return result;
}
}
re = new char[a.length() - b.length() + 2];
for(i = 0; i < a.length() - b.length() + 2;i++)re[i] = '\0';
len_a = a.length();len_b = b.length();
while(1)
{
b = b_;
mod = a;
for(i = 0;i < len_a - len_b - k;i++)b.insert(i + len_b ,"0");//b
while(1)
{
c_tem = mod;
mod = sub(mod,b);
tem++;
if(mod[0] == '-')
{
re[n_re] = tem + 48;
a = c_tem;
n_re++;
k++;
tem = -1;
break;
}
}
test = sub(a,b_);//
if(test[0] == '-' || test == "0")break;
}
for(i = n_re;i < len_a - len_b + 1;i++) re[i] = '0';
result = re;
delete []re;
return result;
}
int main()
{
char x;
bigNum A,B;
while(cin>>A.big>>x>>B.big)
{
switch(x)
{
case '+':cout< 参考ページ
大数乗算http://sumile.blog.hexun.com/62509182_d.htmlhttp://www.cnblogs.com/hicjiajia/archive/2010/09/26/1836337.html
moocフォーラムのプログラム設計実習討論
「機械演算除算のような方法を使って、実際に減算することができます.12345で13を除算すると、まず1300(さらに10倍拡大すると12345より大きくなります)を見つけ、12345から1300を繰り返し減算し、9回後に減少しないと、1番目の商は9で、残りの数から130を繰り返し減算し、2番目の商を得ることができます.」
大数除算は最も実現しにくいはずだ.配列aをbで割ったと仮定すると、実現には2つの方法がある.さらにa[1]a[2]すなわち12を取り、bより小さいことを発見すると、1ビット多く取り、a[1]a[2]a[3]すなわち123を取り、bを5回減らし、a={0 0 0 0 0 0 8 1}を得、result={0 1 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0}を得る.さらにa[3]a[4]すなわち81をとり,bを3回減らしてa={0 0 0 0 1 2},result={0 1 0 5 3}とする.方法によって計算すれば、効率は許せない.11111を1で割ると、方法は1で11111回計算され、方法2では5回しか計算されません.以下は方法2のコードで、簡単なテストを経た(データ検査をしていないで、データがすべて正常だと仮定します):http://blog.csdn.net/sunmenggmail/article/details/7532522加算:O(n)は手で計算する方法に似ていて、1つのforサイクルの小さいその数、それから1つのビットごとに対応して加算して、進位があるのは前のビットの数に1つの減算を加えます:O(n)は同じ理屈で加算して、ただ1つのビットごとに対応して減算して、もし対応して減算するならば負の数で、このビット+10、前のビットを1つ減算します:O(n^2)私は手のアルゴリズムを使って、2つのfor、1サイクル乗数1サイクル被乗数を乗数のあるビットで被乗数の各ビットに乗算した結果/10がキャリー、%10が保持除算を行います:O(nlogn)これは特に難しく、2日間==と考えました.ここのフォーラムのもう一つのpo主のアルゴリズム、すなわちA/B(w.l.o.g.A>B)を仮定し、まず2つの数のビット差を計算する.すなわち、Aが10ビット、Bが5ビットであると仮定すると、ビット差は5になる.Bを左に5ビットシフトする(自分でメンバー関数を書いたが、<機械演算除算のような方法を再構築することはできず、実際には減算を行う.12345除算13を仮定すると、まず1300(さらに10倍拡大すると12345より大きくなる)を見つけ、12345から1300を繰り返し、9回後に減少が足りない場合は、1番目の商は9であり、残りの数から130を繰り返し減算し、2番目の商を得る.このように推す.基本的な考え方は引き算を繰り返して、被除数から最大何個の除数を減らすことができるかを見て、商はいくらです.一つ一つ減らすのは明らかに遅すぎて、どのようにもっと速く減らすのですか?7546を23で割った例で見ると、開始商は0です.まず23の100倍を引くと2300になり、3回減らすことができ、残りは646だった.すると商の値は300増加します.その後646で230を引くと、2回減らすことができ、残りの186は、商の値が20増加した.最後に186で23を減らして8回減らすことができるので、最終商は328です.そこで本題の核心は,大きな整数の減算関数を書き,その関数を繰り返し呼び出して減算操作を行うことである.除数の10倍、100倍を計算する場合は、乗算せずに除数の後に0を補うだけです.http://www.cnblogs.com/c840136/articles/2168405.html http://wenwen.soso.com/z/q24755485.htm http://www.melory.me/2013/03/09/%E5%A4%A7%E6%95%B0%E9%99%A4%E6%B3%95%E8%BF%90%E7%AE%97/http://www.melory.me/2013/03/09/%E5%A4%A7%E6%95%B0%E9%99%A4%E6%B3%95%E8%BF%90%E7%AE%97/
簡単な時間分析をして、間違ったところがあれば、軽く撮ります.+,何も言うことはありませんが,O(max(m,n)),m,nはそれぞれoperand 1,operand 2の桁数で,ここでは100にしましょう.-、プラスと同じか、またはそれ以上のシングル、例えば、999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999X,アナログ手算時間はO(m*n),m,nここで最大100とし,時間はO(n^2),n=100とする.もっと早い「karatsuba algorithms」O(n^(3/2))、実現しやすいです.もっと速い私にはよくわかりませんが、O(n*log(n)./、いろいろな実現方法があるそうです:1)9800000/12=」9800000-1200000=)つまり12を補い、残りが12未満になるまで連続して減らします.時間O(n^2)あ、だって、最悪は一桁ごとに減らさなきゃいけないから、99999999/1とか、毎回減算して、時間は、O(1+2+3+4+…+n)=O(n^2).2)シミュレーション手算時間はO(((n−m＋1)*m),nは被除数のビット数長,mは99999999/11のような除数のビット数長,ここではN=7,m=2である.mが小さい場合は速く、mが大きい場合は速く、m=n/2の場合は遅くなります.99/11を求めるときは連減を使います.3)試商は最も遅いもので,Xを用いるため,Xの時間O(N^2)を用いると,最も速い試商法もO((n−m)*m*(log(10^(n−m))を用いる.nが被除数の桁数長であれば,mが除数の桁数長であり,binary searchで試商する時間もO(log(10^(n−m))を要するため,m=n/2であれば遅い.それから除法がないので、binary searchの使い方が分かりません.Xを用いる時間がO(N^(3/2))、運転時間も、O((n-m)*m)^(3/2)*(log(10^(n-m))だから除算は乗算に使われたほうがいいです. https://class.coursera.org/pkupop-001/forum/thread?thread_id=463
私は主にシフトと減算を利用して除算演算を行います:例えば123456/12.まず12を4ビット(6-2=4)にシフトして120000になり、次いで123456でマイナス数まで減少する.2.次に、12を3ビットシフト、12000とし、第1ステップの減算残り数(3456)で12000を負の数まで減算.このようにして、12シフト0まで.皆さんはもっと简単な方法がありますか??https://class.coursera.org/pkupop-001/forum/thread?thread_id=404