C++ で大きな数値入力を処理する最良の方法は何ですか? (例: 10^100
)?
アルゴリズムについては、通常は Ruby に切り替え、文字列を使用することもあります。
他に良い方法はありますか?
C++ で大きな数値入力を処理する最良の方法は何ですか? (例: 10^100
)?
アルゴリズムについては、通常は Ruby に切り替え、文字列を使用することもあります。
他に良い方法はありますか?
Owen Astrachan によるThe Large Integer Case Study in C++.pdfを参照してください。このファイルは、詳細な紹介とコードの実装に非常に役立つことがわかりました。サードパーティのライブラリは使用しません。これを使用して、問題なく膨大な数を処理しました(保存するのに十分なメモリがある限りvector<char>
)。
アイデア: big int を a に格納することにより、任意精度の整数クラスを実装しvector<char>
ます。
vector<char> myDigits; // stores all digits of number
次に、 を含む big int に関連するすべての操作は<<, >>, +, -, *, ==, <, !=, >, etc.
、 this の操作に基づいて実行できますchar array
。
コードの味: これがヘッダー ファイルです。その cpp とコードは pdf ファイルにあります。
#include <iostream>
#include <string> // for strings
#include <vector> // for sequence of digits
using namespace std;
class BigInt
{
public:
BigInt(); // default constructor, value = 0
BigInt(int); // assign an integer value
BigInt(const string &); // assign a string
// may need these in alternative implementation
// BigInt(const BigInt &); // copy constructor
// ~BigInt(); // destructor
// const BigInt & operator = (const BigInt &);
// assignment operator
// operators: arithmetic, relational
const BigInt & operator += (const BigInt &);
const BigInt & operator -= (const BigInt &);
const BigInt & operator *= (const BigInt &);
const BigInt & operator *= (int num);
string ToString() const; // convert to string
int ToInt() const; // convert to int
double ToDouble() const; // convert to double
// facilitate operators ==, <, << without friends
bool Equal(const BigInt & rhs) const;
bool LessThan(const BigInt & rhs) const;
void Print(ostream & os) const;
private:
// other helper functions
bool IsNegative() const; // return true iff number is negative
bool IsPositive() const; // return true iff number is positive
int NumDigits() const; // return # digits in number
int GetDigit(int k) const;
void AddSigDigit(int value);
void ChangeDigit(int k, int value);
void Normalize();
// private state/instance variables
enum Sign{positive,negative};
Sign mySign; // is number positive or negative
vector<char> myDigits; // stores all digits of number
int myNumDigits; // stores # of digits of number
};
// free functions
ostream & operator <<(ostream &, const BigInt &);
istream & operator >>(istream &, BigInt &);
BigInt operator +(const BigInt & lhs, const BigInt & rhs);
BigInt operator -(const BigInt & lhs, const BigInt & rhs);
BigInt operator *(const BigInt & lhs, const BigInt & rhs);
BigInt operator *(const BigInt & lhs, int num);
BigInt operator *(int num, const BigInt & rhs);
bool operator == (const BigInt & lhs, const BigInt & rhs);
bool operator < (const BigInt & lhs, const BigInt & rhs);
bool operator != (const BigInt & lhs, const BigInt & rhs);
bool operator > (const BigInt & lhs, const BigInt & rhs);
bool operator >= (const BigInt & lhs, const BigInt & rhs);
bool operator <= (const BigInt & lhs, const BigInt & rhs);
目的のために独自のコードを作成したい場合は、文字列を使用して大きな数値を格納してみてください... + - / * などの基本的な操作をそれらに作成できます...たとえば -
#include <iostream>
using namespace std;
string add (string &s1, string &s2){
int carry=0,sum,i;
string min=s1,
max=s2,
result = "";
if (s1.length()>s2.length()){
max = s1;
min = s2;
} else {
max = s2;
min = s1;
}
for (i = min.length()-1; i>=0; i--){
sum = min[i] + max[i + max.length() - min.length()] + carry - 2*'0';
carry = sum/10;
sum %=10;
result = (char)(sum + '0') + result;
}
i = max.length() - min.length()-1;
while (i>=0){
sum = max[i] + carry - '0';
carry = sum/10;
sum%=10;
result = (char)(sum + '0') + result;
i--;
}
if (carry!=0){
result = (char)(carry + '0') + result;
}
return result;
}
int main (){
string a,b;
cin >> a >> b;
cout << add (a,b)<<endl;
return 0;
}
受け取った大量の入力に対して操作を実行する方法をお探しですか? 算術演算を実行できる大きな整数 C++ライブラリ (Java に類似) があります...
数値の入力について話していると仮定すると、倍精度は最大 1.7976931348623157 x 10^308 になります
C および C++ 用の任意精度数値処理ライブラリであるgmplibを参照してください。
正確にしたい場合は、大きな数を処理するために作成されたライブラリが必要です。Javaには、桁数に関係なく常に正確なBigIntがあり、それらに対する数学演算を提供します。すべてのソース コードが含まれており、転送することもできますが、これは実際には C++ が得意とする種類のものではありません。JVM ベースの言語を使用し、ビッグ ライブラリの 1 つを使用します。
遅くしたくない限り、これにルビーを使用するとは思いません.C++について話しているので、速度は設計上の考慮事項であると思います。
他の人がすでに指摘しているように、C++ にはさまざまな bignum/arbitrary 精度ライブラリがあり、役に立つと思われます。速度が必要ない場合は、Python と Lisp の両方がデフォルトで bignum を使用するという印象を受けます。
boost::cpp_intを検討してください
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
int main()
{
using namespace boost::multiprecision;
cpp_int u = 1;
for(unsigned i = 1; i <= 100; ++i)
u *= i;
// prints 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 (i.e. 100!)
std::cout << u << std::endl;
return 0;
}
このような算術計算を行う最善の方法は、文字列を使用することだと思います。入力をコマンド ライン引数として指定し、atoi()
やitoa()
!などの文字列関数を使用してロジック全体を操作します。でも、かけ算や割り算はこれでいいのかな?このようstrlen
に入力された文字列は、ロジックがうまくいくまでコンパイラのプログラミングには関係ないと思います。