皆様おはようございます。@plasma_effector です。この記事はAizuアドベントカレンダー4日目です。
#自己紹介
数学系の3回生です。何も考えず登録した後Aizuとあんま関係ないと気付きましたが気にせずやります。
普段はC++とC#でなんか作ってます。たまにTypeScriptでゲームを作ります。
#やること
C++のconstexprには様々な可能性が存在します。
多倍長整数をコンパイル時に使えたらいいなぁって思ったのでconstexprな多倍長整数を作ろうって思いました。
#補足 constexprとは
※この項は普段C++使ってる方は読み飛ばしてもらって構いません
C++11で追加された定数評価に関する指定子です。gccとclangとmsvcでは使えます。
##変数でのconstexpr
基本的にconst定数と同じですがコンパイル時に値が確定しないとエラーになります。
constexpr int value = 0;//OK
int u=10;//普通の変数
constexpr int v = u;//NG(uは定数評価されない)##関数でのconstexpr 定数式として評価されうる関数を生成します。関数本体は実質的にreturn文一つでなければなりません。(実質的と言ったのはusingなどが使えるため)
constexpr int fact(int v)
{
return v == 0 ? 1 : fact(v-1)*v;
}
constexpr int v = fact(5);//OKC++14ではconstexpr関数本体の制限が緩和されました。が、msvcが2015年にもなって対応してないので今回はC++11準拠でいきます。
##リテラル型
組み込み型やポインタ型はconstexprで使えます。またaggregate(C言語における構造体みたいなの)もconstexprで使えます。
ユーザー定義の型でも以下の条件を満たせばconstexprで使えるようになります。constexprで使える型をリテラル型といいます(実際は若干定義が違う気がするがここではそういうことにしておく)
・デストラクタがtrivial
・constexprなコンストラクタを持つ
・staticでないデータメンバが全てリテラル型でかつvolatileでない
C++11ではリテラル型の参照もリテラル型となります。C++14では任意の型の参照がリテラル型となります。
またリテラル型の配列もリテラル型
struct literal
{
int x;
constexpr literal(int v):x(v){}
literal() = default;//default指定したコンストラクタはconstexprコンストラクタとして扱われる
literal(literal const&)=default;
literal(literal&&)=default;
~literal()=default;
};
constexpr literal v{10};//OK
constexpr literal u{};//OK#多倍長整数型を定義する ##データメンバ 何かと使い勝手のいいstd::array型を使います。
template<std::size_t Size>struct big_int
{
std::array<unsigned, Size> data;
};これを(32×Size)bitの整数とみなして計算します。ただし今後の実装を楽にするために2^32進数表記でdata[0]を1桁目とし以後2桁...とします。
##コンストラクタ
コンストラクタは「通常の整数型」「配列型」の2つにします。
###unsigned intとunsigned long long
unsigned intはそのまま代入します。
unsigned long longは下位32bitをdata[0]に、上位32bitをdata[1]に代入します。
constexpr big_int(unsigned int value) :data{ { value } } {}
constexpr big_int(unsigned long long value) : data{ { static_cast<unsigned>(value),static_cast<unsigned>(value >> 32) } } {}###intとlong long
意外と厄介です。そのまま代入すると-10が4294967286になったりします。
ここで注目したいのは「-nは内部では1+(~n)で表されている」ということです(~はビット反転)。
つまり「0xFF...F-n+1で表されている」ということになります。
したがって「0xFF...F-n+1=0xFF...F00000000+(0xFFFFFFFF-n+1)」であることに注目すると残りの桁を0xFFFFFFFF、つまり-1で埋めれば良いということがわかります。
というわけで「先頭がvalueで残りが0xFFFFFFFFであるようなstd::array< std::size_t, Size>」を生成する関数を作ります。
なお以下ではindex_sequence idiomを用いますが詳しくは解説しません。
//int型用
template<std::size_t... Is>constexpr auto make_minus_array(unsigned top, std::index_sequence<Is...>)
{
return std::array<unsigned, 1 + sizeof...(Is)>{ {top, (Is * 0 + 0xFFFFFFFF)...}};
}
//long long型用
template<std::size_t... Is>constexpr auto make_minus_array(unsigned top0, unsigned top1, std::index_sequence<Is...>)
{
return std::array<unsigned, 2 + sizeof...(Is)>{ {top0, top1, (Is * 0 + 0xFFFFFFFF)...}};
}引数がマイナスでないとき用の関数も用意します
template<std::size_t... Is>constexpr auto make_plus_array(unsigned top, std::index_sequence<Is...>)
{
return std::array<unsigned, 1 + sizeof...(Is)>{ {top, (Is * 0)...}};
}
template<std::size_t... Is>constexpr auto make_plus_array(unsigned top0, unsigned top1, std::index_sequence<Is...>)
{
return std::array<unsigned, 2 + sizeof...(Is)>{ {top0, top1, (Is * 0)...}};
}これを用いると以下のように書けます。
constexpr big_int(int value) : data(
value < 0 ?
make_minus_array(static_cast<unsigned>(value), std::make_index_sequence<Size - 1>()) :
make_plus_array(value, std::make_index_sequence<Size - 1>())) {};
constexpr big_int(long long value) : data(
value < 0 ?
make_minus_array(static_cast<unsigned>(value), static_cast<unsigned>(value >> 32), std::make_index_sequence<Size - 2>()) :
make_plus_array(static_cast<int>(value), static_cast<int>(value >> 32), std::make_index_sequence<Size - 2>())) {}###int const(&)[Size] 明らかに見えて意外と厄介です。そのままstd::arrayに初期化できません。
constexpr int ar[]={1, 2, 3, 4};
constexpr std::array<int, 4> v{ar};//NGというわけで一旦展開して再構築します。
template<std::size_t I, std::size_t... Is>constexpr auto make_array(unsigned const(&ar)[I], std::index_sequence<Is...>)
{
return std::array<unsigned, sizeof...(Is)>{ {ar[Is]...}};
}これを用いてコンストラクタを書きます。
constexpr big_int(unsigned const (&value)[Size]) : data{ make_array(value,std::make_index_sequence<Size>()) } {}###std::array デフォルトコンストラクタ コピーコンストラクタ ムーブコンストラクタ 一番簡単だと思いますが一応載せておきます。
constexpr big_int(std::array<unsigned, Size>const& ar) : data(ar) {}
big_int() = default;
big_int(big_int const&) = default;
big_int(big_int&&) = default;##キャスト演算子
より大きいサイズにする場合など、サイズを変更する必要が出てきたとき用にキャスト演算子を定義しておきます。
そのために上のmake_arrayを応用しますが「範囲外アクセスは定数式として評価されない」のでstd::enable_ifで範囲外アクセスかどうかで処理をわけておきます。
enable_ifについても詳しく説明しませんが参考になるであろうページを貼っておきます。
参考：本の虫: Boostのenable_ifについて
template<std::size_t I, std::size_t Size>constexpr auto array_access(std::array<unsigned, Size> const&, std::enable_if_t<(I >= Size)>* = nullptr)
{
return 0u;
}
template<std::size_t I, std::size_t Size>constexpr auto array_access(std::array<unsigned, Size> const& ar, std::enable_if_t<(I<Size)>* = nullptr)
{
return ar[I];
}
template<std::size_t I, std::size_t... Is>constexpr auto make_array(std::array<unsigned, I> const& ar, std::index_sequence<Is...>)
{
return std::array<unsigned, sizeof...(Is)>{ {array_access<Is>(ar)...}};
}これを使えば簡単にキャスト演算子が書けます。
template<std::size_t S>constexpr operator big_int<S>()const
{
return big_int<S>(make_array(data, std::make_index_sequence<S>()));
}###まとめて書く 定義の補助関数を含めてまとめて書いておきます。
template<std::size_t... Is>constexpr auto make_minus_array(unsigned top, std::index_sequence<Is...>)
{
return std::array<unsigned, 1 + sizeof...(Is)>{ {top, (Is * 0 + 0xFFFFFFFF)...}};
}
template<std::size_t... Is>constexpr auto make_minus_array(unsigned top0, unsigned top1, std::index_sequence<Is...>)
{
return std::array<unsigned, 2 + sizeof...(Is)>{ {top0, top1, (Is * 0 + 0xFFFFFFFF)...}};
}
template<std::size_t... Is>constexpr auto make_plus_array(unsigned top, std::index_sequence<Is...>)
{
return std::array<unsigned, 1 + sizeof...(Is)>{ {top, (Is * 0)...}};
}
template<std::size_t... Is>constexpr auto make_plus_array(unsigned top0, unsigned top1, std::index_sequence<Is...>)
{
return std::array<unsigned, 2 + sizeof...(Is)>{ {top0, top1, (Is * 0)...}};
}
template<std::size_t I, std::size_t... Is>constexpr auto make_array(unsigned const(&ar)[I], std::index_sequence<Is...>)
{
return std::array<unsigned, sizeof...(Is)>{ {ar[Is]...}};
}
template<std::size_t I, std::size_t Size>constexpr auto array_access(std::array<unsigned, Size> const&, std::enable_if_t<(I >= Size)>* = nullptr)
{
return 0u;
}
template<std::size_t I, std::size_t Size>constexpr auto array_access(std::array<unsigned, Size> const& ar, std::enable_if_t<(I<Size)>* = nullptr)
{
return ar[I];
}
template<std::size_t I, std::size_t... Is>constexpr auto make_array(std::array<unsigned, I> const& ar, std::index_sequence<Is...>)
{
return std::array<unsigned, sizeof...(Is)>{ {array_access<Is>(ar)...}};
}
template<std::size_t Size>struct big_int
{
std::array<unsigned, Size> data;
constexpr big_int(unsigned int value) :data{ { value } } {}
constexpr big_int(unsigned long long value) : data{ { static_cast<unsigned>(value),static_cast<unsigned>(value >> 32) } } {}
constexpr big_int(int value) : data(
value < 0 ?
make_minus_array(static_cast<unsigned>(value), std::make_index_sequence<Size - 1>()) :
make_plus_array(value, std::make_index_sequence<Size - 1>())) {};
constexpr big_int(long long value) : data(
value < 0 ?
make_minus_array(static_cast<unsigned>(value), static_cast<unsigned>(value >> 32), std::make_index_sequence<Size - 2>()) :
make_plus_array(static_cast<int>(value), static_cast<int>(value >> 32), std::make_index_sequence<Size - 2>())) {}
constexpr big_int(unsigned const (&value)[Size]) : data{ make_array(value,std::make_index_sequence<Size>()) } {}
constexpr big_int(std::array<unsigned, Size>const& ar) : data(ar) {}
big_int() = default;
big_int(big_int const&) = default;
big_int(big_int&&) = default;
template<std::size_t S>constexpr operator big_int<S>()const
{
return big_int<S>(make_array(data, std::make_index_sequence<S>()));
}
};#演算子を定義する ##operator& operator| operator^ operator~ ビット演算のこれらはとても簡単です。
namespace detail
{
template<std::size_t Size, std::size_t... Is>constexpr auto bit_and(std::array<unsigned, Size> const& lhs, std::array<unsigned, Size> const& rhs, std::index_sequence<Is...>)
{
return big_int<Size>(std::array<unsigned, Size>{ {(lhs[Is] & rhs[Is])...}});
}
template<std::size_t Size, std::size_t... Is>constexpr auto bit_or(std::array<unsigned, Size> const& lhs, std::array<unsigned, Size> const& rhs, std::index_sequence<Is...>)
{
return big_int<Size>(std::array<unsigned, Size>{ {(lhs[Is] | rhs[Is])...}});
}
template<std::size_t Size, std::size_t... Is>constexpr auto bit_xor(std::array<unsigned, Size> const& lhs, std::array<unsigned, Size> const& rhs, std::index_sequence<Is...>)
{
return big_int<Size>(std::array<unsigned, Size>{ {(lhs[Is] ^ rhs[Is])...}});
}
template<std::size_t Size, std::size_t... Is>constexpr auto bit_not(std::array<unsigned, Size> const& v, std::index_sequence<Is...>)
{
return big_int<Size>(std::array<unsigned, Size>{ {(~v[Is])...}});
}
}
template<std::size_t Size>constexpr auto operator|(big_int<Size> const& lhs, big_int<Size> const& rhs)
{
return detail::bit_or(lhs.data, rhs.data, std::make_index_sequence<Size>());
}
template<std::size_t Size>constexpr auto operator&(big_int<Size> const& lhs, big_int<Size> const& rhs)
{
return detail::bit_and(lhs.data, rhs.data, std::make_index_sequence<Size>());
}
template<std::size_t Size>constexpr auto operator^(big_int<Size> const& lhs, big_int<Size> const& rhs)
{
return detail::bit_xor(lhs.data, rhs.data, std::make_index_sequence<Size>());
}
template<std::size_t Size>constexpr auto operator~(big_int<Size> const& v)
{
return detail::bit_not(v.data, std::make_index_sequence<Size>());
}##operator+ operator- これは意外と厄介です。まず非constexprで軽く書いてみます。
std::array<int,16> plus(std::array<int, 16>const& lhs, std::array<int, 16>const& rhs)
{
std::array<int, 16> ar{};
auto d=static_cast<unsigned long long>(lhs[0])+static_cast<unsigned long long>(rhs[0]);
ar[0]=d;
for(int i=1;i<16;++i)
{
d=static_cast<unsigned long long>(lhs[i])+static_cast<unsigned long long>(rhs[i])+(d>=0x100000000ull);
ar[i]=static_cast<int>(d);
}
return ar;
}このようなコードをC++11constexprでエミュレートしたい。例えばこうします。
namespace detail
{
template<std::size_t I, std::size_t Size, class... Ts>constexpr std::enable_if_t<(Size == I), std::array<unsigned, Size>> plus(
std::array<unsigned, Size>const&,
std::array<unsigned, Size>const&,
unsigned long long d,
Ts const&... args)
{
return std::array<unsigned, Size>{ {static_cast<unsigned>(args)..., static_cast<unsigned>(d)}};
}
template<std::size_t I, std::size_t Size, class... Ts>constexpr std::enable_if_t<(Size != I), std::array<unsigned, Size>> plus(
std::array<unsigned, Size>const& lhs,
std::array<unsigned, Size>const& rhs,
unsigned long long d,
Ts const&... args)
{
return plus<I + 1>(lhs, rhs, static_cast<unsigned long long>(lhs[I]) + static_cast<unsigned long long>(rhs[I]) + static_cast<unsigned long long>(d >= 0x100000000ull), args..., d);
}
}
template<std::size_t Size>constexpr auto operator+(big_int<Size> const& lhs, big_int<Size> const& rhs)
{
return big_int<Size>(detail::plus<1>(lhs.data, rhs.data, static_cast<unsigned long long>(lhs.data[0]) + static_cast<unsigned long long>(rhs.data[0])));
}I < SizeのときはI桁目を計算しそれを次の引数に渡します。返り値はVariadic Templateで一旦保持します。
I==Sizeで一気にstd::arrayに展開してbig_intに展開します。
operator-は実質operator+です。
template<std::size_t Size>constexpr auto operator-(big_int<Size> const& lhs, big_int<Size> const& rhs)
{
return lhs + (~rhs) + big_int<Size>(1);
}##operator<< operator>> 32より大きいか小さいかにわけて考えます。
namespace detail
{
template<std::size_t Size, std::size_t... Is>constexpr auto bit_shift_left_over32(std::array<unsigned, Size>const& v, std::index_sequence<Is...>)
{
return std::array<unsigned, Size>{ {0u, v[Is]...}};
}
template<std::size_t Size, std::size_t... Is>constexpr auto bit_shift_left_under32(std::array<unsigned, Size>const& v, int i, std::index_sequence<Is...>)
{
return std::array<unsigned, Size>{ {v[0] << i, ((v[Is + 1] << i) + (v[Is] >> (32 - i)))...}};
}
template<std::size_t Size, std::size_t... Is>constexpr auto bit_shift_right_over32(std::array<unsigned, Size>const& v, std::index_sequence<Is...>)
{
return std::array<unsigned, Size>{ {v[Is]..., 0u}};
}
template<std::size_t Size, std::size_t... Is>constexpr auto bit_shift_right_under32(std::array<unsigned, Size>const& v, int i, std::index_sequence<Is...>)
{
return std::array<unsigned, Size>{ {v[0] >> i, ((v[Is + 1] << (32 - i)) + (v[Is] >> i))...}};
}
template<std::size_t Size>constexpr std::array<unsigned, Size> bit_shift_left(std::array<unsigned, Size>const& v, int u)
{
return u == 0 ? v : (u >= 32 ? bit_shift_left(bit_shift_left_over32(v, std::make_index_sequence<Size - 1>()), u - 32) : bit_shift_left_under32(v, u, std::make_index_sequence<Size - 1>()));
}
template<std::size_t Size>constexpr std::array<unsigned, Size> bit_shift_right(std::array<unsigned, Size>const& v, int u)
{
return u == 0 ? v : (u >= 32 ? bit_shift_left(bit_shift_right_over32(v, std::make_index_sequence<Size - 1>()), u - 32) : bit_shift_right_under32(v, u, std::make_index_sequence<Size - 1>()));
}
}
template<std::size_t Size>constexpr auto operator<<(big_int<Size>const& lhs, int rhs)
{
return big_int<Size>(detail::bit_shift_left(lhs.data, rhs));
}
template<std::size_t Size>constexpr auto operator>>(big_int<Size>const& lhs, int rhs)
{
return big_int<Size>(detail::bit_shift_right(lhs.data, rhs));
}##operator*
一番わかりやすい方法でやります。記事を書く時間がないとも言う。
2^32進数の掛け算を考えます。まず1桁×N桁の処理を書きます。考え方は上のoperator+とほとんど同じです。
template<std::size_t I, std::size_t Size, class... Ts>constexpr std::enable_if_t<(I == Size), big_int<Size + 1>> multi_one(
std::array<unsigned, Size>const&,
unsigned,
unsigned long long d,
Ts const&... v)
{
return big_int<Size + 1>(std::array<unsigned, Size + 1>{ {v..., static_cast<unsigned>(d), static_cast<unsigned>(d >> 32)}});
}
template<std::size_t I, std::size_t Size, class... Ts>constexpr std::enable_if_t<(I != Size), big_int<Size + 1>> multi_one(
std::array<unsigned, Size>const& ar,
unsigned m,
unsigned long long d,
Ts const&... v)
{
return multi_one<I + 1>(ar, m,static_cast<unsigned long long>(ar[I]) * static_cast<unsigned long long>(m) + (d /0x100000000llu), v..., static_cast<unsigned>(d));
}あとは小学校で習った筆算と同様に計算します。
template<std::size_t I, std::size_t Lhs, std::size_t Rhs>constexpr std::enable_if_t<(I + 1 == Lhs), big_int<Lhs+Rhs>> multi(std::array<unsigned, Lhs>const& lhs, std::array<unsigned, Rhs>const& rhs)
{
return static_cast<big_int<Lhs + Rhs>>(multi_one<1>(rhs, lhs[I], static_cast<unsigned long long>(rhs[0]) * static_cast<unsigned long long>(lhs[I]))) << (32 * I);
}
template<std::size_t I, std::size_t Lhs, std::size_t Rhs>constexpr std::enable_if_t<(I + 1 != Lhs), big_int<Lhs+Rhs>> multi(std::array<unsigned, Lhs>const& lhs, std::array<unsigned, Rhs>const& rhs)
{
return (static_cast<big_int<Lhs + Rhs>>(multi_one<1>(rhs, lhs[I], static_cast<unsigned long long>(rhs[0]) * static_cast<unsigned long long>(lhs[I]))) << (32 * I)) + multi<I + 1>(lhs, rhs);
}まとめて書きます。
namespace detail
{
template<std::size_t I, std::size_t Size, class... Ts>constexpr std::enable_if_t<(I == Size), big_int<Size + 1>> multi_one(
std::array<unsigned, Size>const&,
unsigned,
unsigned long long d,
Ts const&... v)
{
return big_int<Size + 1>(std::array<unsigned, Size + 1>{ {v..., static_cast<unsigned>(d), static_cast<unsigned>(d >> 32)}});
}
template<std::size_t I, std::size_t Size, class... Ts>constexpr std::enable_if_t<(I != Size), big_int<Size + 1>> multi_one(
std::array<unsigned, Size>const& ar,
unsigned m,
unsigned long long d,
Ts const&... v)
{
return multi_one<I + 1>(ar, m,static_cast<unsigned long long>(ar[I]) * static_cast<unsigned long long>(m) + (d /0x100000000llu), v..., static_cast<unsigned>(d));
}
template<std::size_t I, std::size_t Lhs, std::size_t Rhs>constexpr std::enable_if_t<(I + 1 == Lhs), big_int<Lhs+Rhs>> multi(std::array<unsigned, Lhs>const& lhs, std::array<unsigned, Rhs>const& rhs)
{
return static_cast<big_int<Lhs + Rhs>>(multi_one<1>(rhs, lhs[I], static_cast<unsigned long long>(rhs[0]) * static_cast<unsigned long long>(lhs[I]))) << (32 * I);
}
template<std::size_t I, std::size_t Lhs, std::size_t Rhs>constexpr std::enable_if_t<(I + 1 != Lhs), big_int<Lhs+Rhs>> multi(std::array<unsigned, Lhs>const& lhs, std::array<unsigned, Rhs>const& rhs)
{
return (static_cast<big_int<Lhs + Rhs>>(multi_one<1>(rhs, lhs[I], static_cast<unsigned long long>(rhs[0]) * static_cast<unsigned long long>(lhs[I]))) << (32 * I)) + multi<I + 1>(lhs, rhs);
}
}
template<std::size_t Lhs, std::size_t Rhs>constexpr auto operator*(big_int<Lhs>const& lhs, big_int<Rhs>const& rhs)
{
return detail::multi<0>(lhs.data, rhs.data);
}#使ってみる 12345678987654321*98765432123456789をします。どちらもunsigned long longで収まりますが掛けると明らかに収まりません。
#include<iostream>
int main()
{
constexpr big_int<2> v{12345678987654321};
constexpr big_int<2> u{98765432123456789};
constexpr auto r = v * u;
for(auto v: r.data)
std::cout<<std::hex<<v<<std::endl;
}11e17f85
c1bb77be
fd45713
3c1e
と出力されました。計算するとどうやらあってるらしいです。
#今後の課題
・char const*型と相互変換できるようにしたい
・FFTを使った乗法アルゴリズムがあるらしいのでそれを実装したい
#まとめ
・constexprな多倍長整数を作った
・乗法のオーバーフロー関連のバグで4時間ぐらい時間が溶けた
リハビリのつもりで作ってみましたが思った以上にハードでした。オススメしません。
#next Aizu AdC Hint!! 明日は@misoton665 さんです。