ライブラリは世の中にたくさんあるんですけれど、簡単なアルゴリズムなら自分にも実装できるなと思い、作ってみた今日この頃。
► スポイラーを表示
pragma once
#include
#include
#include
#include
#include
#include
#include
#include
namespace Numeric
{
//numeric_limitが constexprに対応していないので、それに対処する
template
struct Max;
//最大値を計算する
template
struct Max
{
static const unsigned long value = ULONG_MAX;
};
template
struct Max
{
static const unsigned long long value = ULLONG_MAX;
};
template
struct Max
{
static const unsigned short value = USHRT_MAX;
};
//Typeのビット数を求める
template
struct Bit{
//Bitすうを求めるコア関数
template
struct CalculateBit
{
enum
{
value = ( CalculateBit> 1) >::value ) + 1
};
};
template
struct CalculateBit
{
enum{ value = 0 };
};
//ビット数
enum{
value = CalculateBit::value>::value,
};
//最大の桁のビットのみがONの時の値
static const Type leftMost = ( static_cast(1)
class basic_BigInteger;
template
const basic_BigInteger operator lhs, typename basic_BigInteger::SizeType rhs );
template
const basic_BigInteger operator >> ( basic_BigInteger lhs, typename basic_BigInteger::SizeType rhs );
template
class basic_BigInteger:
boost::operators>
{
public:
typedef typename ContainerType::value_type ValueType;
typedef typename ContainerType::size_type SizeType;
enum InternalStatus
{
Status = 0, //ステータスを格納する配列番号
ValueOffset, //実際に値が格納される配列番号
NumOfBits = Bit::value, //ValueTypeのビット数
Plus = 0x008, //正の数を表す(Status上では反映されない)
Minus = 0x001, //負の数を表すビット数
Infinity = 0x002, //無限大を表すビット数
Null = 0x004, //数が無効になっているときのビット数
Invalid = Infinity | Null, //何らかの不正な値を保持している
};
static const ValueType GreatestBit = Bit::leftMost;
ContainerType value_;
public:
/*
constructors
*/
basic_BigInteger()
:value_( SizeAtFirst, 0)
{
value_[0] = Null;
}
basic_BigInteger( const basic_BigInteger& other )
{
value_ = other.value_;
}
/*basic_BigInteger( const basic_BigInteger && other )
{
value_ = other.value_;
}*/
basic_BigInteger& operator = ( const basic_BigInteger & other )
{
value_ = other.value_;
}
/*basic_BigInteger& operator = ( const basic_BigInteger&& other )
{
value_ = other.value_;
}*/
explicit basic_BigInteger( long long value )
:value_( SizeAtFirst, 0)
{
value_[Status] = (value value_[Status]^= Minus;
}
else
{
if(IsSameSigns( other ) )
AbsSub( other );
else
AbsAdd( other );
}
return *this;
}
/*ビット演算*/
basic_BigInteger& operator > ( NumOfBits - shift );
*itr >= ( SizeType value )
{
SizeType remove = value / NumOfBits;
SizeType shift = value % NumOfBits;
if( remove )
{
auto vbegin = value_.begin() + ValueOffset;
value_.erase( vbegin, vbegin + remove );
}
ValueType next = 0;
for( auto itr = value_.rbegin(); itr != value_.rend() - ValueOffset; ++itr )
{
ValueType nextTemp = next;
next = *itr >= shift;
(*itr) += nextTemp;
}
return *this;
}
basic_BigInteger& operator &= ( const basic_BigInteger& other )
{
if( value_.size() > other.value_.size() )
{
std::fill(value_.begin() + other.value_.size(), value_.end(), 0 );
std::transform(
other.value_.begin() + ValueOffset,
other.value_.end(),
value_.begin() + ValueOffset,
value_.begin() + ValueOffset,
[]( ValueType lhs, ValueType rhs )
{
return lhs & rhs;
}
);
auto ritr = value_.rbegin();
return *this;
}
std::transform(
value_.begin() + ValueOffset,
value_.end(),
other.value_.begin() + ValueOffset,
value_.begin() + ValueOffset,
[]( ValueType lhs, ValueType rhs )
{
return lhs & rhs;
}
);
return *this;
}
basic_BigInteger& operator |= ( const basic_BigInteger& other )
{
if( value_.size() = ten*/ !value.IsAbsSmallerThan( ten ) )
{
basic_BigInteger temp(0);
value.GetQuotientAndRemainder( ten, temp );
ss basic_BigInteger(0) )
{
if( (*this & value) != basic_BigInteger(0) )
returnValue += "1";
else
returnValue += "0";
value >>= 1;
}
return returnValue;
}
//以下ロジック
private:
bool IsAbsSmallerThan( const basic_BigInteger& other ) const
{
using std::swap;
if( *this == Infinity) return false;
if( other == Infinity) return true;
auto itr = value_.rbegin();
auto oitr = other.value_.rbegin();
if( value_.size() ::max() )
{
++value_[i];
return;
}
value_[i] = 0;
++i;
}
value_.push_back(1);
return;
};
for( SizeType i = ValueOffset; i ::max();
++it;
}
*it -= 1;
};
auto oitr = other.value_.begin() + ValueOffset;
auto itr = value_.begin() + ValueOffset;
for( ;oitr != other.value_.end() && itr != value_.end(); ++oitr, ++itr )
{
if( *itr >= *oitr )
{
*itr -= *oitr;
continue;
}
//oitrはconst_iteratorなので、内部の変数をバッファ
ValueType o = (~*oitr) + 1; //*oitrのビットを反転
*itr += o;
DecreaseInDigit( itr );
}
}
SizeType GetGreatestBit() const
{
auto itr = value_.rbegin();
SizeType size = value_.size();
while( *itr == 0 && itr != value_.rend() ) --size, ++itr;
SizeType i = 0;
ValueType v = *itr;
for( ; v > 0; ++i )
{
v >>= 1;
}
if( size 0 )
{
temp >>= 1;
*this -= temp;
quotient += ( basic_BigInteger(1)
const basic_BigInteger operator lhs, typename basic_BigInteger::SizeType rhs )
{
return (lhs
const basic_BigInteger operator >> ( basic_BigInteger lhs, typename basic_BigInteger::SizeType rhs )
{
return (lhs >>= rhs );
}
template
std::ostream& operator & rhs )
{
lhs > BigInteger;
}
#include "BigInteger.h"
#include
using namespace std;
using namespace Numeric;
int main(){
BigInteger i(1);
for( int j = 1; j <= 1000; ++j )
{
i *= BigInteger(j);
}
cout << "1000! = " << i << endl;
}
► スポイラーを表示1000! = 402387260077093773543702433923003985719374864210714632543799910429938512
39862902059204420848696940480047998861019719605863166687299480855890132382966994
45909974245040870737599188236277271887325197795059509952761208749754624970436014
18278094646496291056393887437886487337119181045825783647849977012476632889835955
73543251318532395846307555740911426241747434934755342864657661166779739666882029
12073791438537195882498081268678383745597317461360853795345242215865932019280908
78297308431392844403281231558611036976801357304216168747609675871348312025478589
32076716913244842623613141250878020800026168315102734182797770478463586817016436
50241536913982812648102130927612448963599287051149649754199093422215668325720808
21333186116811553615836546984046708975602900950537616475847728421889679646244945
16076535340819890138544248798495995331910172335555660213945039973628075013783761
53071277619268490343526252000158885351473316117021039681759215109077880193931781
14194545257223865541461062892187960223838971476088506276862967146674697562911234
08243920816015378088989396451826324367161676217916890977991190375403127462228998
80051954444142820121873617459926429565817466283029555702990243241531816172104658
32036786906117260158783520751516284225540265170483304226143974286933061690897968
48259012545832716822645806652676995865268227280707578139185817888965220816434834
48259932660433676601769996128318607883861502794659551311565520360939881806121385
58600301435694527224206344631797460594682573103790084024432438465657245014402821
88525247093519062092902313649327349756551395872055965422874977401141334696271542
28458623773875382304838656889764619273838149001407673104466402598994902222217659
04339901886018566526485061799702356193897017860040811889729918311021171229845901
64192106888438712185564612496079872290851929681937238864261483965738229112312502
41866493531439701374285319266498753372189406942814341185201580141233448280150513
99694290153483077644569099073152433278288269864602789864321139083506217095002597
38986355427719674282224875758676575234422020757363056949882508796892816275384886
33969099598262809561214509948717012445164612603790293091208890869420285106401821
54399457156805941872748998094254742173582401063677404595741785160829230135358081
84009699637252423056085590370062427124341690900415369010593398383577793941097002
77534720000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000
実行してみてわかるのだが、掛け算自体は一瞬で終わってる。
問題は文字列に直すときに10で割っていくという操作。ここにもんっのっすごい時間がかかっているみたい。
たぶんもっと快適に行うアルゴリズムがあるだろう。
(日記を書いているときに思ったけど10じゃなくて100000000とかで割ればよくね?てかそうだよねw)
ホントはフーリエ変換とか使えばもっともっと高速にできるみたいですが、理解する気力もないのでパスっす。
取りあえず自分の欲求は十分満たせたもん