2015-06-02

2^n - 1 を素因数分解した結果一覧

雑記

http://melpon.org/wandbox/permlink/UPjHWBam24a75P9U

2^1-1 ,3
2^2-1 ,7
2^3-1 ,3,5
2^4-1 ,31
2^5-1 ,3,3,7
2^6-1 ,127
2^7-1 ,3,5,17
2^8-1 ,7,73
2^9-1 ,3,11,31
2^10-1 ,23,89
2^11-1 ,3,3,5,7,13
2^12-1 ,8191
2^13-1 ,3,43,127
2^14-1 ,7,31,151
2^15-1 ,3,5,17,257
2^16-1 ,131071
2^17-1 ,3,3,3,7,19,73
2^18-1 ,524287
2^19-1 ,3,5,5,11,31,41
2^20-1 ,7,7,127,337
2^21-1 ,3,23,89,683
2^22-1 ,47,178481
2^23-1 ,3,3,5,7,13,17,241
2^24-1 ,31,601,1801
2^25-1 ,3,2731,8191
2^26-1 ,7,73,262657
2^27-1 ,3,5,29,43,113,127
2^28-1 ,233,1103,2089
2^29-1 ,3,3,7,11,31,151,331
2^30-1 ,2147483647
2^31-1 ,3,5,17,257,65537
2^32-1 ,7,23,89,599479
2^33-1 ,3,43691,131071
2^34-1 ,31,71,127,122921
2^35-1 ,3,3,3,5,7,13,19,37,73,109
2^36-1 ,223,616318177
2^37-1 ,3,174763,524287
2^38-1 ,7,79,8191,121369
2^39-1 ,3,5,5,11,17,31,41,61681
2^40-1 ,13367,164511353
2^41-1 ,3,3,7,7,43,127,337,5419
2^42-1 ,431,9719,2099863
2^43-1 ,3,5,23,89,397,683,2113
2^44-1 ,7,31,73,151,631,23311
2^45-1 ,3,47,178481,2796203
2^46-1 ,2351,4513,13264529
2^47-1 ,3,3,5,7,13,17,97,241,257,673

mod [2^n - 1] は(比較的)高速に計算することができる
mod [2^n + 1]も何となく高速に計算できそうな気がするんだけれどとくに方法が思いつかない

2015-05-16

stateful constexpr Counter/CompiletimeTypeID

C++

stateful constexprとは？という問題についてはまずこの辺りを見ていただきたい
C++のconstexprは参照透明とは限らない - 魂をC++に捧げよ
 本の虫: constexprで非定数式の状態を保持

このように書かれるたびに(≠呼び出されるたび)違う値を返すconstexpr関数を実装することができる
これが本当にconstexprなのか？といわれると怪しいが

元の記事では32から0までflagが立てられているものを探していく、という実装である
しかし、この実装では当然32以上のものは作れないので1から数え上げていく方法に変えた
ついでにTypeIDを実装した
これによりUnique関数のオーダーがO(NlogN)に下がるだろう
[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

無限ループをオーバーロードで無限ループをはじいている

現状の方式の問題点

・何かとO(N)であること
next()関数はO(N)時間かかる関数でありあまり効率的ではない
また、constexprの再起制限も気になるところだ。C++11の悪夢再び
再起制限のほうは何とかなるような気もするが、検索オーダーを下げると折角減らしたwarningがまた増えるような気がする

・GCCでwarningが消えきらない
ライブラリがwarningを吐くのは当然いいことではない

2015-03-31

非constexpr文脈内でconstexpr関数をコンパイル時評価したような気分になる方法

C++

どうやら本日学生生活最終日らしいです。不思議

std::cout<<log(42);

このような場合logがconstexpr関数であってもコンパイル時に評価されない
constexpr関数はconstexprな文脈でのみ呼び出されからだ。上記はconstexpr文脈ではない

よってlogをコンパイル時に評価したい場合constexprな文脈で呼び出す必要がある
例えば以下の通りだ

constexpr auto a=log(42);//コンパイル時に処理される
std::cout<<a;

このプログラムは以下と同等に動くことが期待される

std::cout<<3.73767;

しかしこれはだるい。なのでこんなマクロを作ってみた

#define MACRO(expr) ([]{constexpr auto a=(expr);return a;}())

これを使うとconstexpr呼び出ししたような気分になれる。気分？気分

以下のようになるはずだ

std::cout<<MACRO(log(42));

↓

std::cout<<[]{constexpr auto a=log(42);return a;}();

std::cout<<[]{return 3.73767;}();

最後は関数がinline展開されて

std::cout<<3.73767;

となるはずだ。コンパイラの最適化が十分に働いてくれれば

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ
この場合だとマクロを使わずベタに書いている場合0.75秒かかっているのに対し
マクロ版は0.09秒で計算を終えている

ただし、コンパイラ最適化を強くした場合
[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ
両者ほとんど変わらない数値を出している。人生大体コンパイラがどうにかしてくれる。コンパイラに母性を求める日も近い

2015-03-06

C++コードを投げるとアセンブラを投げ返すハイテックなオンラインサービス

C++

最近聞いたいい話
Compiler Explorer
タイトルの通りC++のコードを打ち込むとアセンブラで返してくれる

ちなみにそのままC++11/14なコードを打ってもコンパイルエラーとなる
コンパイラオプションは適当に[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯとかから必要そうなところを切り抜いてもってこよう

ところでこういうサービスもオンラインコンパイラと呼んでいいのだろうか

例

std=gnu++1y -O2 -march=native

@Fuyutsubaki http://t.co/F4iRJPPev9 こういうのがありますよ。
— yoh (@yohhoy) 2015, 3月 2

yoh on Twitter: "@Fuyutsubaki http://t.co/F4iRJPPev9 こういうのがありますよ。"

2015-02-15

神と腹痛と科学

雑記

諸君お気づきであろうか？神や真理というのは病める時も健やかな時も我々の理と無関係に在るのである

先日腹痛に見舞われた。正露丸の瓶は空であった
幸い自宅であったため好きなだけトイレの住人と化すことはできたのだが、私は襲い来る痛みの波をただただ耐えるほかなかったのである

腹痛というのは内臓痛であり、外傷などによって引き起こされる痛みとはプロセスが異なる。格闘家でも腹痛は耐え難い痛みであると聞く。つまりとても痛い

正露丸はない。科学は私を見放した
私は腹部を出来る限り温め、チャント*1を唱え、神に祈った

するとだんだんと腹痛が引いていくではないか
私は精神を持ち直た。神のことは忘れた

これでも私は一応科学を修めた人間である。ゆえに似非科学というのは鼻で笑うような対象であると考えている

しかし、もしも腹痛下、トイレにたまたま「おなかに効くお地蔵」がいたらどうしただろうか
多分拝んだと思う。拝み倒したと思う。現に神に祈ったし

今回は腹痛であったが、これがもし癌であったら私はどうしたであろうか

療法(正露丸)は尽きた。そしてがんが治る水なる怪しげなものを売りつける輩が来た
恐らく私はその水をがぶ飲みするだろう。私は腹痛で神に祈る人間である。私はその似非科学を使うだろう。普段であれば鼻で笑ったその水を

そんな時も神や科学と言ったものは、私とは無関係に在る
病める時は科学を忘れ神に祈り、健やかな時は神を忘れ科学を信じ。

もしかすると、そんな私を神や科学はどこかで見下ろしているかもしれない。それはさすがに自意識過剰か

私という人間は痛いだ熱いだ苦しいだで真理というものを容易に失うが、それでも科学や神は在って
私という人間は病める時の言うことはあてにならず、ゆえに健やかな時も言うことはあてにならず、私という人間と無関係に神や科学はあるのです

当たり前のようであたりまえな話

*1:ｲﾀｲﾉｲﾀｲﾉﾄﾝﾃﾞｲｹ

2014-12-06

constexpr でテンプレートメタプログラミング

C++

この記事はC++ AdventCalendar2014 6日目の記事になります

祝C++14!!祝C++14!!祝C++14!!祝C++14!!

C++14においてconstexprの大幅な規制緩和が制定された
これによりconstexprにおいてforなどループ文の記述が可能になった

一方そのころTMPは

残念ながらテンプレート用for文が入ることはなかった
しかしTMPはfor文を必要としている。forは力だ。力はいい。持ちすぎて困ることはない

そしてTMPにかなり近いところにいるconstexprは今、for文を持っている。これを利用しない手はない

constexprを用いたフィルターメタ関数の実装

template<class tList,template<class>class Pred>
struct filter
{
    static const std::size_t N=tList::size;
    template<std::size_t...Idxs>
    static constexpr sprout::pair<std::size_t,sprout::array<std::size_t ,N>> impl(std::index_sequence<Idxs...>)
    {
        sprout::array<bool ,N> v{{(Pred<at<tList,Idxs>>{}())...}};
        sprout::array<std::size_t ,N>idx{{Idxs...}};
	std::size_t k=0;
	for(std::size_t i=0;i<N;++i)
	{
		if(v[idx[i]])
		{
			idx[k]=idx[i];
			++k;
		}
	}
         return {k,idx};
    }
    static constexpr auto res=impl(std::make_index_sequence<N>{});
    template<std::size_t...Idxs>
    static constexpr List<at<tList,res.second[Idxs]>...> impl2(std::index_sequence<Idxs...>){return {};}

    using type=decltype(impl2(std::make_index_sequence<res.first>{}));
};

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

Impl は必要な型のインデックス配列とその長さを返す
impl2は結果の長さと同じ長さのindex_sequence→残す型のインデックス→残す型に変換していきタイプリストにする

結果、タイプリストと評価用メタ関数を受け取り、タイプリストを返すメタ関数を作ることができた

せっかくだからバブルソートも書いてみた
[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ
比較するときにis_base_ofを使うような場合は使えないが実用上問題はないだろう*1

型安全printfなど構文解析が必要な所作もconstexprを用いて実装可能だ*2

このようにconstexprを使い頭皮に優しい、もしかしたらコンパイラにも優しいTMPが可能になる

まとめ

このように今まで型を必要としていた分野、今までゴリゴリとTMPしていた分野でもconstexprを用いることができる。やるやらない出来る出来ないは別としてゴリゴリと型を用いるプログラミングをする際は頭の片隅に入れておくべきである

なおこれらのコードはClangでしか動かない
各コンパイラ、とくにMS社の蒼いコンパイラには頑張ってもらいたい

C++ Advent Calendar 2014 - Qiita

明日はh_hiro_ さんです
よろしくお願いします

おまけ。

値と型、そして未来

2014年現在型安全printfは実用上マクロ(SPROUT_TYPES_STRING_TYPEDEFなど)に頼る必要がある

printf(MACRO("%d%d%d"),a,b,c)

値を型に用意に変換する構文がないのだ。マクロを使わない場合ラムダ式内で構造体を作って云々

[]{struct hoge{constexpr auto operator()(){return "%d%d%d";}};return hoge{};}()

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

もしくは

mpl_string<'%','d','%','d','%','d'>{}

非常に残念な感じだ

残念な感じなので未来に願いを託そう
まず文字列ユーザー定義リテラル
 すごいユーザ定義リテラルたのしく遊ぼう - ボレロ村上 - ENiyGmaA Code
の一番下に載っているヤツだ

これはmpl_stringの構築を容易にする構文だ
mpl_stringからconstexprな文字列に変換するのは容易なのでコレがあれば型printfつらい問題は解決する

もう一つの可能性はラムダ式だ。ラムダ式がデフォルトコンストラクタを持ち、constexprになれば、つまり

[]{return "%d%d%d";}

が

struct _
{
	constexpr auto operator()()const{return "%d%d%d";}
}

を生成するようになれば,ラムダ式はintegral_constant的な関数とみなせるようになる
[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ
なぜラムダ式がconstexprではないかというと
本の虫: もしlambda式がconstexprだったら

という経緯があるためである
逆にいうとコンセプトが入った段階でラムダ式がconstexpr化する可能性も無きにしも非ず、かもしれない

*1:その場合はバイトニックソートとか使おう

*2:面倒なので実装しないが

2014-11-21

デジゲー博で頒布したはるはあけぼのの不具合について

制作物(ゲーム)関連

デジゲー博で頒布したゲームにいくつか不具合が見つかりました
申し訳ありません

お手数ですが以下のファイルの中身をすべてゲームのフォルダにコピーしてください。同じ名前のものは置き換えてください。
https://www.dropbox.com/sh/p7foxjuvncedu8p/AAAi6brXT5eeWW5ql0Xi67Hka?dl=0