連分数 (continued fraction)
こないだのJune Long ChallengeのEuler Sumを考えてる時に
Mark Jason Dominus氏のスライド
Arithmetic with Continued Fractions
を読んだ時のメモ。
連分数とかいじるのって多分昔SICPを読んだ時以来。
続きを読む小さい数n（100万までとか）の素因数分解
CodeChefのフォーラムで June Challenge 2017の問題 Chef and Prime Queries (PRMQ) の解法を読んでいて
discuss.codechef.com
素因数分解をするのに
This can be done by creating a Smallest Prime Factor array in the sieve function itself.
とあって。エラトステネスの篩 (Sieve of Eratosthenes) をするときに、篩と同時に一番小さい素因数のテーブルを作ってしまえば素因数分解が簡単、っていう話。
続きを読むTopCoder Marathon Match 93
最近ではすっかり英会話仲間なagwたんに再三誘われてたのもあり
久しぶりにMarathon Matchに出てみた話。
Marathon Match 93 (3/1 23:00EST〜3/16 0:00EDT)
最後に出たMMは４年前のTCO13らしい。
（問題文だけはとりあえず読んだもののあまり気乗りがしなくて参加に至らず、というのは何度かあった気がする。）
今回のMMの目標は、とりあえずyellow coderに上がること。（現在のratingは1424）
↓黙って出てたけど捕捉されてる
続きを読むnaoya_tさんがMarathon提出してる
— 今年は夏バテにならない (@tomerun) 2017年3月5日
GCCのビルトイン関数メモ
http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html より
関数名末尾に l が付いてるのは long、ll なら long long、無印は unsigned int。
他にもいろいろあるけど、コンテストで使うかもしれないやつだけとりあえず。
__builtin_popcount, __builtin_popcountl, __builtin_popcountll
立ってるビット数を数えて返す
0x11 (2進で10001) なら2
0x57 (2進で1010111) なら5
__builtin_parity, __builtin_parityl, __builtin_parityll
立ってるビット数の偶奇を返す。（popcount % 2 に相当）
0x11 (2進で10001) なら0（偶数）
0x57 (2進で1010111) なら1（奇数）
__builtin_ffs, __builtin_ffsl, __builtin_ffsll
2進で表した場合に小さい方から何桁目に初めて1が現れるか。
0x07 (2進で111) なら1。0x08 (2進で1000) なら 4。
0の場合は0を返す。
__builtin_clz, __builtin_clzl, __builtin_clzll
2進で表した場合に左側にいくつ0を埋める必要があるか (the number of leading 0-bits in x)
（32bit unsigned intの場合）0x07 (2進で111) なら29。
0の場合は未定義。
__builtin_ctz, __builtin_ctzl, __builtin_ctzll
2進で表した場合に、1の位からいくつ0が連なっているか (the number of trailing 0-bits in x)
0x08 (2進で1000) なら3。
0の場合は未定義。
量子情報勉強会 |4> に参加してきました
「初級ラテン語リーディング」でいつもお世話になってる @7shi さんの池袋バイナリ勉強会で開催された「量子情報勉強会」に参加してきました。
http://connpass.com/event/4858/
セレブラントの人とか来てる。さすが量子情報勉強会 #量子情報勉強会 #エンタングル
— naoya t (@naoya_t) 2014, 1月 19勉強会で使われる教科書
量子コンピュータと量子通信〈1〉量子力学とコンピュータ科学 (量子コンピュータと量子通信 1)posted with amazlet at 14.02.02
を探しに、始まる前にジュンク堂に行ってみたのだけれど売ってなくて、魔が差してファインマン物理学第５巻（量子力学）を買ってきたりとか。
昨日の昼、量子情報勉強会のテキストを探しに行った池袋の魔窟ジュンク堂で、散財天様に会ったわけでもないのに魔が差して連れて帰ってきたファインマン物理学の５巻（量子力学）を読んでる。分かりやすい。（原書はネットで無料で読めるよ http://t.co/i4OuJgoj3J ）
— naoya t (@naoya_t) 2014, 1月 19今回は、
- 前回までの復習：量子アルゴリズムの話、量子テレポーテーション、など
- §1.5 量子情報処理の実験：Stern-Gerlachの実験（§1.5.1）、量子情報処理デバイスの話（§1.5.2）
あたりをやりました。
最初の復習タイムに、以前Courseraで習った量子テレポーテーションの原理を久しぶりに追ってみた。何とかひと通り自力で追えた http://t.co/xqcZI78kGo #量子情報勉強会
— naoya t (@naoya_t) 2014, 1月 19以前にCourseraで受けた授業で概ね習っているので、復習っぽい感覚で参加できそうです。
次回 |5> は 2/15(土) 18時から、池袋バイナリ勉強会にて開催予定です。
http://connpass.com/event/4858/
Les lois de Newton
Courseraで受講中のEPELの力学のクラス (Physique générale - mécanique) でニュートンの法則が３つ出てきたのでプリンキピアのラテン語原文を探してみた、というメモ。自分用。
プリンキピア (Principia) ないしプリンキピア・マテマティカ (Principia Mathematica) と言っても
- アイザック・ニュートンの "Philosophiae Naturalis Principia Mathematica" (自然哲学の数学的諸原理)
- アルフレッド・ノース・ホワイトヘッド、バートランド・ラッセル "Principia Mathematica" (数学原理)
があるわけですが前者のニュートン力学の方のプリンキピアです
ラテン語原文の下に、クラスで出てきたフランス語版を並べてあります
LEX I. - 慣性の法則
Corpus omne perseverare in statu suo quiescendi vel movendi uniformiter in directum, nisi quatenus a viribus impressis cogitur statum illum mutare.
(Première loi de Newton) "Tout corps persévère dans l'état de repos ou de mouvement uniforme en ligne droite à moins que quelque force n'agisse sur lui et ne le contraigne à changer d'état".
LEX II. - ニュートンの運動方程式, F=ma
Mutationem motus proportionalem esse vi motrici impressae, et fieri secundum lineam rectam qua vis illa imprimitur.
(Deuxième loi de Newton) "Les changements de mouvement sont proportionnels à la force motrice, et se font dans la ligne droite dans laquelle cette force est imprimée à l'objet."
らろわ「えふぇがれま」って何の法則だっけと思ったら F=ma のことか… "la loi F égal ma" #coursera
— naoya t (@naoya_t) 2013, 10月 6LEX III. - 作用・反作用の法則
Actioni contrariam semper et aequelem esse reactionem: sive corporum duorum actiones in se mutuo semper esse aequales et in partes contrarias dirigi.
(Troisième loi de Newton) "A toute action, il y a toujours une réaction égale qui lui est opposée" ; autrement dit, les actions mutuelles de deux corps l'un sur l'autre sont toujours égales et opposées.
PRML復々習レーン#14（再）
http://connpass.com/event/3529/
前回、ワルプルギスの夜が来た為に延期（というか嵐のハッカソン）になった復々習レーン。
今日は９章。k-meansと混合ガウスとEMアルゴリズム。
sleepy_yoshiさんがsklearnとか使って10行ぐらいでさくっとコードを書いている間に、matplotlibと格闘しながら混合ガウス分布のEMアルゴリズムをごりごり実装しておりました。
図9.8（下巻p.153）的なものの再現です。
データセットはold faithful間欠泉データです。
実装はgithubに上げてあります：
https://github.com/naoyat/PRMLrevenge/tree/5632b99f79c7833c99faf3257cefaccb9a84e204/chap9
次回（11/9 or 11/23）は9章の残りと10章を読みます。
10章（近似推論法）はみんなでextreme readingします。頑張ろう！
おまけ
距離の三角不等式と距離の上限・下限を管理することで，距離の評価回数を n k e から n に近づける高速化 http://t.co/ieY6D71rjy #prmlrevenge
— naoya t (@naoya_t) 2013, 10月 5