多倍長整数の掛け算

プログラム言語で使える整数の変数は通常はサイズが決まっており、それ以上の大きさの整数を扱うことができない。例えばC++のint型は通常32bitなので2^32 - 1 = 4294967295(ゼロを含むので-1がある)までしか扱えない。signedなら負の値も使うのでその半分までである。もしそれを超えるような大きな整数を計算したい場合は色々と工夫が必要です。

私が初めて多倍長整数の掛け算を実装したのは確か中学生のころだったと思われる。何を計算したかったかは忘れてしまったが単純に大きな数字が見たかっただけかもしれない。当時使っていた言語はN88Basicで、当時の私にメモリの概念や知識が殆どなく、配列の一つ一つに10進数の桁の値を入れて普通に筆算を計算していた。なお実装で一番苦労したのは計算そのものよりその表示だった覚えがある。その後、また実装する機会があった(例によって理由は覚えていない)のだが、その時は10進数である必要がないことに気が付いて1万進数とかで計算していた。10進数ベースなところが相変わらずメモリ構造とか知識がなかったようだ。

さて、最近になってまた実装する機会ができた。理由はLucas–Lehmer primality testを実装してみたくなったから。現在ではメモリ構造とかの知識があるのでより効率的な実装ができた。しかし試しにpythonで簡単に作ったLucas–Lehmer primality testに比べて桁外れに遅かったことに疑問を覚えた(ちなみにpythonはdefaultで多倍長整数になっており扱える整数の上限がないので実装が簡単。同時に普通の整数演算が遅い原因でもある)。いろいろと調べて分かったことだが、多倍長整数の掛け算はいろいろ研究されており、通常の筆算ならO(N^2)の計算量があるのに対し、例えばカラツバ法という計算方法ならO(N^long2(3))ですむ。pythonの整数計算ではカラツバ法が使われているらしく、それで計算時間に大きな差があったらしい。

多倍長整数の掛け算でよく使われるアルゴリズムはカラツバ法の他にショーンハーゲ・ストラッセン法という方法がある。桁が大きくなってくるとこちらの方が速いらしい。というわけでこちらの実装を試そうと思ったがなかなか難しい。原理は理解したが環の選び方等、細かい部分の理解が足りず実装できずにいる。わざわざ自分で実装せずともGMP等のライブラリが存在するのだが、試しにGMPを使ってみたがおそらくSIMDやThread並列は使われておらずまだまだ速くする余地はありそうである。なのでやはり自作してみることにする。

生存確認

新年度を迎えたので記念更新。1年も経ってしまった。これ以上ないくらいの新記録である。
この1年、特に大きな変化はないが、以前よりやや仕事に余裕が出てきた気がする。余裕が出てきていろいろ勉強ができるようになってきた。よってここも少し更新頻度が上がるかもしれない。何か勉強に結果が出てきたら書き込むかもしれません。勉強内容は趣味で数学や物理が多いが一応現在の専門の機械学習系も少しはやっている。いや、専門をしっかりやろうよとも思うが私は基本的に論文を解読できないので技術が枯れるのを待って誰かがわかりやすくまとめてくれてからじっくり手を動かすタイプなのでなかなか最新技術には手がでない。まあなんにせよ、まとめられる可能性は低そうだ。
少しずつ更新を増やしていこうと思う。今日はこのへんで。

復活しました

随分と滞ってしまったが生存しています。

hatenaダイアリからhatenablogに移行するのが遅れたため一時ロックがかかってしまい書くに書けなくなってしまいました。まあどちらにしろ書くことなかったから同じことなんだけど。

プライベートでは特に変わりなく、3人の子供たちも健やかに育っています。仕事面では大きな変化がありました。一言でいえば開発の第一線を退いて第二線に下がりました。裏方でサポートする側になりました。内政マネジメントといえば少しかっこいいかもしれませんがさてはて・・・。時代の変化についていけず悩んでいたのですがとりあえず落ち着いたというところでしょうか。

だんだん年も取ってきて身の振り方を考えるようになってきました。これもその一つの結論かもしれません。

娘が生まれて3カ月が経ちました

順調に育っています。3歳の息子がやや赤ちゃん返りしているようです。

今回、育児のため、1カ月休みました。当初は育児休暇を取得しようと思ってました。ちなみに数年前からうちの会社でも男性でも育児休暇がとれるようになりました。なので取得しようと思ったのだが、考えてみたら1カ月くらいなら育児休暇より普通に有給休暇を取得したほうが得だということに気がついてそちらに変更しました。というわけて1カ月専業主夫をやってました。仕事のほうはあらかじめ伝えていたので特に問題はなかったです、グループ内部では・・・。しかし他部署はそんなことお構いなしなので何回か在宅勤務でフォローしていました。なかなか大変でした。

10月半ばあたりに異動になりました。いや正確にはグループごとオフィス移転になりました。少し遠くなったけど駅から近くなったのでトータルはあまり変わらず。それどころか帰りも座れるようになったのでむしろ楽になりました。当分の悩みは昼食をどうするか。また弁当を復活させたいです。

3世代を超えた送金

ゆうちょの定期貯金の満期の知らせが来て普通貯金に移動させた。
はるか昔、私がもらったお年玉を親が毎年定期貯金に入れていた。それが満期を迎えたのだ。明らかに長すぎるのでおそらく2回目か3回目の満期かと思われる。
現在、ゆうちょの口座は娘の給食費の支払いにしか使われていないのでいずれそちらに支払われるだろう。
お年玉は主に祖父母や親せきからもらったものだ。なので祖父母からもらったお金が娘の給食費に充てられていることになった。
祖父母もまさか自分のひ孫の給食費を払っているとは夢にも思わなかっただろう。

私も既にお年玉をあげる側になって久しいが、渡しているお年玉が今後どのように使われていくのだろうか想像もつかない。

あけましておめでとうございます(違)

新年どころか新年度も明けてしまいました。半年程過ぎてしまいました。いつもながらの生存確認更新です。
まあ実際、この1年ほど死にそうな程きつかったです。真面目に退職を考えていたのですがなんやかんやと結局辞めずに続けています。ただし上司と半分喧嘩状態で話し合いになり、結果、仕事の内容が大きく変わりました。おかげで大分余裕が出てきました。今年度から少し生活スタイルが変化するのではないかと考えています。

ここのところ、仕事でpythonを書きまくっている。とりあえず単純なプログラムを書く際には何も見ずに書けるようになったので初心者から初級者にUPしたかなと考えている。
一方、趣味でswiftを書いている。趣味の時間は殆ど取れないのでswiftはまだまだ初心者のまま。もうすこし頑張りたい。しかしpythonとswiftが微妙に似ているから紛らわしい。
本業のC++は最近simdをゴリゴリ書いた。実に10年ぶりである。VisualStudioが2010から2015に移行したのでC++11を本格的に使い始めた。まだまだ知らない文法やライブラリが多い。初心に帰った気分である。

さて少し余裕が出てきたしここももうちょっと報告を増やせればよいなと考えています。ここのところ、意識改革の一つとして仕事の日誌をつけている。誰に見せるというわけでないが書いていると割と捗るような気がする。同様にここももう少し更新を増やしたらいろいろ捗るのではないだろうか。何が捗るかはよくわからないがなんとなく捗りそうな気がする。

そういうわけでせめて週1くらいを目指して頑張ってみます。