tag:blogger.com,1999:blog-92459212024-03-06T04:20:45.219+09:00サルノオボエガキ技術系の話題が多め。deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.comBlogger289125tag:blogger.com,1999:blog-9245921.post-43163547868490782222022-03-21T17:33:00.004+09:002022-03-26T12:56:36.957+09:00Operations Anti-Patternsの翻訳版が出るのでおすすめする #システム運用アンチパターン<p>2020年にTwitterで紹介されているのを見つけて読んだ <a href="https://www.manning.com/books/operations-anti-patterns-devops-solutions">Operations Anti-Patterns</a> の邦訳が4月に出るそうです。<br>
とても良い内容だったので事前におすすめしておきたい。</p>
<blockquote style="color: rgb(90,90,90); font-size: 0.9em;">
<p>上層部がDevOpsに理解のない組織で働き、組織構造を変える権限を持っていない開発者であっても、チームにDevOpsを導入するための現実的な方法を紹介します。</p>
<p>重厚な承認プロセス、可視化されていない運用、プロセスの最後でのみ行われるソフトウェアテスト、ノイズだらけのアラート、インシデントから学習しない習慣、時間外のデプロイ、情報のため込みなどを取り上げ、ソフトウェアシステムの開発運用が滞るチームや組織に共通してみられる陥りがちな状況や犯しがちな間違いをアンチパターンとして紹介します。そして管理職やマネージャでなく、エンジニアが実行し、繰り返すことで改善できる具体的な行動を解説します。</p>
<p>組織で必要とされる変化を、エンジニアが行動することで実現する本書は、ソフトウェアシステムをよりよく開発運用したいエンジニア必携の一冊です。<br>
<a href="https://www.oreilly.co.jp/editors/archives/2022/03/1984_operations_anti-patterns_devops.html">O’Reilly Village/オラの村 - 4月新刊情報『システム運用アンチパターン』</a></p>
</blockquote>
<p>紹介文からつらみが溢れていて良いですねー。「現実的」「具体的」というのは本当にそうで、この本の良いところです。</p>
<a name='more'></a>
<p>原著は Manning Publications から出てます。電子書籍で買うとLiveBookというブラウザで読める形式も使えるので自動翻訳使いつつ読めて便利でした。<br>
LiveBookは一部試し読みできます。</p>
<p><a href="https://www.manning.com/books/operations-anti-patterns-devops-solutions">Operations Anti-Patterns, DevOps Solutions</a></p>
<p>この本の特徴は一般の開発者に向けた改善方法の紹介ということです。私は開発者が全員で5名未満の小さな会社でのキャリアを2回経験しているのですが、そこでぶつかった問題と重なることの多い非常に泥臭い内容でした。DevOpsというとマネージャ向けの本は何冊か読んだんですが、この本ぐらい地に足のついた本は読んだことなかったです。</p>
<p>小さな会社の開発チームからメンバの増員、上場などを経ていく過程ではみんな同じような問題にぶつかって解決してきてると思うんですが、それがまとめられたことはあまり無かったんじゃないでしょうか。<br>
開発プロセスがまだ固まっていない小さな会社ならこの本を読むことで良い習慣を知ることが出来ると思います。しかもそれはしゃらくさい意識高いものではなく、具体的ですぐ始められるテクです。開発プロセスがある程度固まっている大きめの会社でもいろんなトピックを紹介しているので抜けている部分が見つけられるかもしれません。<br>
ユニークな本だと思います。</p>
<p>原著の目次を引用。つらみが透けて見えてきたら読んで後悔しないはずです(私は目次を見た時点で即買いしました)。</p>
<p>(追記:訳書の目次が公開されました <a href="https://www.oreilly.co.jp/books/9784873119847/" target="_blank">O'Reilly Japan - システム運用アンチパターン</a>)</p>
<ol>
<li>THE DEVOPS INGREDIENTS
<ul>
<li>DevOpsの定義などの導入</li>
</ul>
</li>
<li>THE PATERNALIST SYNDROME
<ul>
<li>重すぎる承認プロセスについて</li>
</ul>
</li>
<li>OPERATIONAL BLINDNESS
<ul>
<li>サービスの動きを知るためのカスタムメトリクスの作り方</li>
</ul>
</li>
<li>DATA INSTEAD OF INFORMATION
<ul>
<li>ダッシュボードの具体的な作り方</li>
</ul>
</li>
<li>QUALITY AS A CONDIMENT
<ul>
<li>テスト戦略</li>
</ul>
</li>
<li>ALERT FATIGUE
<ul>
<li>アラートは多すぎると嗅覚疲労のように感じなくなる、適切なしきい値をどう決めるか</li>
<li>アラート一次請けのローテーション、報酬をどう決めればいいか</li>
</ul>
</li>
<li>THE EMPTY TOOLBOX
<ul>
<li>作業の自動化をする場合の優先順位</li>
</ul>
</li>
<li>OFF-HOUR DEPLOYMENTS
<ul>
<li>リリースサイクル、ステージング、切り戻し可能なデプロイ</li>
</ul>
</li>
<li>WASTING A PERFECTLY GOOD INCIDENT
<ul>
<li>障害のポストモーテム</li>
</ul>
</li>
<li>INFORMATION HOARDING: ONLY BRENT KNOWS
<ul>
<li>組織内の情報共有</li>
</ul>
</li>
<li>CULTURE BY DECREE
<ul>
<li>社内文化の醸成、人材採用など</li>
</ul>
</li>
<li>TOO MANY YARDSTICKS
<ul>
<li>チームと全体の目標のズレ、タスクの優先順位</li>
</ul>
</li>
</ol>
<p>下は読んだときの感想ツイートです。章ごとに内容がわかれているのでつまみ食いできるのもいいところ。</p>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">10章だけまず読んだ。属人知識を文書化するだけでは伝達はされない、学習の習慣を作らないとダメ。そうだよな… ドキュメント書いたら読んでくれるもんだと思っていたわ…</p>— deltam (@deltam) <a href="https://twitter.com/deltam/status/1334284007698169856?ref_src=twsrc%5Etfw">December 2, 2020</a></blockquote>
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">6章アラート疲労。ノイズの多いアラートばっかだと無視するようになるから基準設けて調整、アラート一次請けスタッフのローテーションとその報酬どうしたらいいか。生々しいところである。</p>— deltam (@deltam) <a href="https://twitter.com/deltam/status/1338452062334373891?ref_src=twsrc%5Etfw">December 14, 2020</a></blockquote>
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr"><a href="https://t.co/dH8oCsBFVD">https://t.co/dH8oCsBFVD</a><br>3章Operational Blindness。CPU使用率やDisk容量だけ監視しててもサービスがちゃんと動いているかは分かりませんよ、カスタムメトリクス設定して健全性を定義しましょう。というのを具体的ケースで書いてて良い。</p>— deltam (@deltam) <a href="https://twitter.com/deltam/status/1346511503747211266?ref_src=twsrc%5Etfw">January 5, 2021</a></blockquote>
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">開発者個人の視点で書かれているので、ログ集約のSaaSの費用を会社が出したくないと言われたときにどう説得すると良いのかなど泥臭くて良い。<br>良い本だからどこか翻訳版出してくれんかな<a href="https://t.co/FpRqLgaF7C">https://t.co/FpRqLgaF7C</a></p>— deltam (@deltam) <a href="https://twitter.com/deltam/status/1346512364116480000?ref_src=twsrc%5Etfw">January 5, 2021</a></blockquote>
<p>待っていた翻訳が出た、めでたい! 英語だったから同僚に勧めにくかったけどこれで心置きなくオススメできます。</p>
<iframe style="width:120px;height:240px;" marginwidth="0" marginheight="0" scrolling="no" frameborder="0" src="//rcm-fe.amazon-adsystem.com/e/cm?lt1=_blank&bc1=000000&IS2=1&bg1=FFFFFF&fc1=000000&lc1=0000FF&t=deltam-22&language=ja_JP&o=9&p=8&l=as4&m=amazon&f=ifr&ref=as_ss_li_til&asins=4873119847&linkId=516899a16ecba58e14ab05dd48e2c7b6"></iframe>
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-23599871110565462012021-12-08T00:00:00.054+09:002021-12-17T14:33:56.281+09:00golang: 一時的/恒久的なエラーの隙間をハンドリングする<p>これは<a href="https://qiita.com/advent-calendar/2021/go">Goアドベントカレンダー3</a>の8日目の記事です。</p>
<p>外部のAPIと連携して仕事をするサービスを長年運用・開発しています。
エラーが発生しある仕事が完了できないことがあり、その場合はエラーレポートを見て手動対応します。
なるべく運用負荷を減らすため、エラーの自動対応を進めていく過程で見つけた方針・実装テクがあるので紹介します。</p>
<p>ポイント</p>
<ul>
<li>一時的なエラー、恒久的なエラーのあいだにはグラデーションがある</li>
<li>エラー自身にエラー対応をさせると複雑さが減る</li>
</ul>
<br/>
<br/>
<h2 id="エラーのグラデーション">エラーのグラデーション</h2>
<p>エラーハンドリングの記事を探すと、<code>func Temporary(err) bool</code> で一時的なエラーか判別してリトライをかますのをよく見ます。
一時的なエラーとは例えばネットワークのTimeoutなど。時間をおけば自動的に回復ししそうなもの。
それ以外はぜんぶ恒久的(Permanent)なエラーとしてレポートを上げてしまう。</p>
<p>実際に運用していると上がってきたエラーにはなにか対応が必要なので手を取られてしまいます。
可能ならば自動対応してエラーレポートしないようにしたい。</p>
<p>運用をつづけていて一時的なエラーと恒久的なエラーのあいだに次のようなエラーの種類があることに気づきました。</p>
<ul>
<li>そのままではリトライしても成功しないけれど、何かの操作をすれば成功する状態に持っていける<strong>回復可能なエラー</strong>。</li>
<li>どうやってもリトライ成功にはできないけど、失敗した状況をマシにしたり詳細なレポートを作れる<strong>フォロー可能なエラー</strong>。</li>
</ul>
<p>単に一時的なエラーかそうでないかだけでなく、これらを区別してハンドリングすることで成功率を上げて手動対応を減らすことを目指します。</p>
<style type="text/css">
div.inner > table { border: solid 2px black; border-collapse: collapse;}
div.inner > table > thead > tr > th { border: solid 1px black; padding: 4px; border-collapse: collapse;}
div.inner > table > tbody > tr > td { border: solid 1px black; padding: 4px; border-collapse: collapse;}
</style>
<div class="inner">
<table>
<colgroup>
<col></col>
<col></col>
<col></col>
</colgroup>
<thead>
<tr>
<th>区分 </th>
<th>自動対応</th>
<th>レポート</th>
<th>説明</th>
</tr>
</thead>
<tbody>
<tr>
<td>一時的</td>
<td>可</td>
<td>不要</td>
<td></td>
</tr>
<tr>
<td>回復可能</td>
<td>可</td>
<td>不要</td>
<td>なにか操作することで回復可能</td>
</tr>
<tr>
<td>フォロー可能 </td>
<td>不可</td>
<td>必要</td>
<td>回復不能だがより良い状態に出来る</td>
</tr>
<tr>
<td>恒久的</td>
<td>不可</td>
<td>必要</td>
<td></td>
</tr>
</tbody>
</table>
</div>
<div><br /></div><div><br /></div><br />
<a name='more'></a>
<h2 id="エラーハンドリングを丁寧にやるとごちゃごちゃになる">エラーハンドリングを丁寧にやるとごちゃごちゃになる</h2>
<p>なんらかの仕事をする関数があり、そのなかで複数のAPIにリクエストを投げるとします。
この仕事はサービスにとってコアなもので毎日大量に発生しているので、一度の実行でなるべく成功してほしいです。
なお説明の簡単のため <code>FooBarWork()</code> は冪等性があるとおもってください(なので何度リトライしても結果は変わらない)。</p>
<pre><code class="go">func FooBarWork(params api.Params) error {
result, err := api.RequestFoo(params)
if err != nil {
return fmt.Errorf("api.RequestFoo() failed: %w", err)
}
params2 := calcSomething(result)
_, err := api.RequestBar(params2)
if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
return nil
}
</code></pre>
<p>運用していくあいだに <code>api.RequestFoo(), api.RequestBar()</code> がタイムアウトした場合は0.5秒おいてリトライすると成功する確率が高いとわかりました。
なので次のようにエラーハンドリング部分を書き直します。</p>
<pre><code class="go">func FooBarWork(params api.Params) error {
result, err := api.RequestFoo(params)
if errors.Is(err, api.ErrTimeout) {
time.Sleep(time.Second/2) // 0.5秒置いてリトライ
result, err = api.RequestFoo(params)
if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
} else if err != nil {
return fmt.Errorf("api.RequestFoo() failed: %w", err)
}
params2 := calcSomething(result)
_, err := api.RequestBar(params2)
if errors.Is(err, api.ErrTimeout) {
time.Sleep(time.Second/2) // 0.5秒置いてリトライ
_, err = api.RequestBar(params)
if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
} else if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
return nil
}
</code></pre>
<p>さらに <code>api.RequestBar()</code> が <code>ErrHogeHoge</code> を返す場合は <code>api.RequestHoge()</code> を叩くと回復できるとわかりました。
書き直しましょう。</p>
<pre><code class="go">func FooBarWork(params api.Params) error {
result, err := api.RequestFoo(params)
if errors.Is(err, api.ErrTimeout) {
time.Sleep(time.Second/2) // 0.5秒置いてリトライ
result, err = api.RequestFoo(params)
if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
} else if err != nil {
return fmt.Errorf("api.RequestFoo() failed: %w", err)
}
params2 := calcSomething(result)
_, err := api.RequestBar(params2)
if errors.Is(err, api.ErrTimeout) {
time.Sleep(time.Second/2) // 0.5秒置いてリトライ
_, err = api.RequestBar(params)
if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
} else if errors.Is(err, api.ErrHogeHoge) {
if hogeErr := api.RequestHoge(); hogeErr != nil {
return fmt.Errorf("api.RequestHoge() failed: err=%w, hogeErr=%v", err, hogeErr)
}
_, err = api.RequestBar(params)
if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
} else if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
return nil
}
</code></pre>
<p>よかった! これで運用しやすくなりました。
でも最初のコードと比べると…</p>
<ul>
<li>エラーハンドリングが異様にごちゃごちゃしている</li>
<li>分岐が増えたのでテストコードもゴッチャゴチャになっている(はず)</li>
<li>時間にシビアな状況の場合、勝手に0.5秒待たれるのは困る</li>
</ul>
<p>などあり、面倒な事態になっています。</p>
<p>コードのシンプルさを保ったまま、同じことをさせるにはどうしたらいいでしょう?</p>
<h2 id="エラー自身に対応させる">エラー自身に対応させる</h2>
<p>まずエラーハンドリングのifのなかで何かの処理をするのをやめます。リトライなどは呼び出し側にやらせます。
これによりコードとテストのごちゃごちゃが軽減されます。</p>
<pre><code class="go">func XXXHandler(params api.Params) {
err := FooBarWork(params)
if errors.Is(err, api.ErrTimeout) {
log.Warnf("FooBarWork() failed: %v", err)
time.Sleep(time.Second/2)
err := FooBarWork(params)
if err != nil {
log.Errorf("Retry FooBarWork() failed: %v", err)
}
} else if errors.Is(err, api.ErrHogeHoge) {
log.Warnf("FooBarWork() failed: %v", err)
if err := api.RequestHoge(); err != nil {
log.Errorf("api.RequestHoge() failed: %v", err)
} else {
err := FooBarWork(params)
if err != nil {
log.Errorf("Retry FooBarWork() failed: %v", err)
}
}
} else if err != nil {
log.Errorf("FooBarWork() failed: %v", err)
}
}
func FooBarWork(params api.Params) error {
result, err := api.RequestFoo(params)
if err != nil {
return fmt.Errorf("api.RequestFoo() failed: %w", err)
}
params2 := calcSomething(result)
_, err := api.RequestBar(params2)
if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
return nil
}
</code></pre>
<p><code>FooBarWork()</code> はシンプルになりました。このままだと呼び出し側にゴチャゴチャを移動しただけなのでもうひと工夫します。</p>
<p>エラーには一時的/回復可能/フォロー可能/恒久的なエラーがあると書いたのを思い出してください。
この分類に沿って<a href="https://dave.cheney.net/2016/04/27/dont-just-check-errors-handle-them-gracefully">振る舞いによるエラーハンドリング</a>ができるようにしてみましょう。
つぎのようなinterfaceを定義してみます。</p>
<pre><code class="go">// これは api.ErrTimeout で実装済みとする
type Temporary interface {
Temporary() bool
}
// 回復可能
type Recoverer interface {
Recover() error
}
</code></pre>
<p><code>RequestBar()</code> のエラーのラッパーをカスタムエラーとして作ります。
このカスタムエラー自身に回復処理のメソッドを生やしてしまいます<a class="footnote" href="#fn:1" id="fnref:1" title="see footnote"><sup>1</sup></a>。</p>
<pre><code class="go">// RequestBar() のエラーを回復するようのWrapper
type HogeErrorWrapper struct {
Err error
}
func (e *HogeErrorWrapper) Error() string { return e.Err.Error() }
func (e *HogeErrorWrapper) Unwrap() error { return e.Err }
func (e *HogeErrorWrapper) Recover() error {
if err := api.RequestHoge(); err != nil {
return fmt.Errorf("api.RequestHoge() failed: %w", err)
}
return nil
}
</code></pre>
<p>これを使い書き換えれば、呼び出し側はエラー対応を詳細を知らなくてOKになります。</p>
<pre><code class="go">func XXXHandler(params api.Params) {
err := FooBarWork(params)
var temporary Temporary
var recoverer Recoverer
if errors.As(err, &temporary) && temporary.Temporary() {
log.Warnf("FooBarWork() failed: %v", err)
time.Sleep(time.Second/2)
err := FooBarWork(params)
if err != nil {
log.Errorf("Retry FooBarWork() failed: %v", err)
}
} else if errors.As(err, &recoverer) {
log.Warnf("FooBarWork() failed: %v", err)
if rerr := recoverer.Recover(); rerr != nil {
log.Errorf("FooBarWork() recover failed: %v", err)
} else {
err := FooBarWork(params)
if err != nil {
log.Errorf("Retry FooBarWork() failed: %v", err)
}
}
} else if err != nil {
log.Errorf("FooBarWork() failed: %v", err)
}
}
func FooBarWork(params api.Params) error {
result, err := api.RequestFoo(params)
if errors.Is(err, api.ErrHogeHoge) {
return &HogeErrorWrapper{Err:err}
} else if err != nil {
return fmt.Errorf("api.RequestFoo() failed: %w", err)
}
params2 := calcSomething(result)
_, err := api.RequestBar(params2)
if errors.Is(err, api.ErrHogeHoge) {
return &HogeErrorWrapper{Err:err}
} else if err != nil {
return fmt.Errorf("api.RequestBar() failed: %w", err)
}
return nil
}
</code></pre>
<p><code>FooBarWork()</code> 側はエラーの種類に応じてカスタムエラーでWrapするようにします。テストコードはエラーが起こる状況で特定のカスタムエラーが返っているかだけチェックすれば良くなりました。</p>
<h2 id="フォロー可能エラー">フォロー可能エラー</h2>
<p>コード上では回復可能エラーとほぼ同じなので例示はしません。
回復可能エラーと違ってリトライしても成功しないものなのでエラーレポートが必須です。</p>
<pre><code class="go">type FollowUpper interface {
FollowUp() string
}
</code></pre>
<p><code>FollowUp()</code> はエラーレポートの補足情報を返します。エラー発生時点での <code>params</code> などを整形したり、対応に必要な情報をDBから引っ張ってきたりします。
ログ以外にエラーレポートシステム<a class="footnote" href="#fn:2" id="fnref:2" title="see footnote"><sup>2</sup></a>を使っているところは多いと思いますが、そういうところで見やすく便利な情報があると運用が楽になります。</p>
<p>そのほかにもリソースを確保するようなAPIの場合に指定したすべてのリソースだと失敗するから<code>params</code>を編集してリトライなどする場合もあります(全部は確保できてないからその旨レポート必要)。
回復可能エラーより使用頻度は高いかもしれません。</p>
<h2 id="カスタムエラーラッパーの利点">カスタムエラーラッパーの利点</h2>
<p>ざっと見ただけだと大してシンプルになっていないように思えるかもしれません。
しかし最初の方法で既存のコードにエラー自動対応を埋め込んでいくことを続けていると、すぐに手に負えないレベルの複雑さになってしまいます。
運用の負荷を下げたい、コードの複雑さも抑えたいと考えるとこの方法がバランス取れています。</p>
<ul>
<li>回復作業自体は関数のなかではやらないのでテストコードがゴチャゴチャしない。特定のカスタムエラーが返っているかチェックするだけで良い。
<ul>
<li>なので後付で自動対応を追加するときもテストコードの複雑さに怯まず実装できる(開発者として心休まる大事ポイント)</li>
</ul></li>
<li>なにか一つの原因で複数のエラーが起こっている場合がよくある。回復可能エラーを別に作っておくことで再利用できる。</li>
<li>回復に必要な情報を関数の中から外へ受け渡せるのでエラーレポートから対応へスムーズに受け渡せる</li>
</ul>
<p>呼び出し側がゴチャっているように見えますが、振る舞いによるエラーハンドリングを行っているので共通化できます。
ここではやってませんが <a href="https://github.com/cenkalti/backoff">backoff</a> のような仕組みで簡単化できるでしょう。</p>
<h2 id="まとめ">まとめ</h2>
<p>エラーには一時的/回復可能/フォロー可能/恒久的などの種類があり、それぞれ対応することで成功率を上げられます。
その際の実装の複雑さはエラー自身に対応メソッドを生やすのと<a href="https://dave.cheney.net/2016/04/27/dont-just-check-errors-handle-them-gracefully">振る舞いによるエラーハンドリング</a>で下げられます。
サービス運用で現実の複雑さと戦っているひとは、このような方針を取り入れてみると楽になるかもしれません。</p>
<p>おわり。</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn:1">
<p>エラーにエラー対応のメソッドを生やせばいいと気づいたのは私にとって目からウロコでした。<a href="https://blog.golang.org/errors-are-values">Errors are values</a>は偉大。 <a class="reversefootnote" href="#fnref:1" title="return to body"> ↩</a></p>
</li>
<li id="fn:2">
<p>私の関わっているシステムではエラーが発生するとTrelloにカードが作られる仕組みがあります。そのまま対応者アサインなどに繋げられるのでオススメ。 <a class="reversefootnote" href="#fnref:2" title="return to body"> ↩</a></p>
</li>
</ol>
</div>deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-17882115459128951382021-12-04T00:00:00.006+09:002021-12-07T15:02:55.104+09:00Clojureで行列計算を実装したときに考えたトリック<p>これは<a href="https://qiita.com/advent-calendar/2021/clojure">Clojureのアドベントカレンダー2021</a>、4日目の記事です。</p><p><br /></p><p>趣味でディープニューラルネットワークのフレームワークをClojureでゼロから実装しています。</p><p>
「ゼロから」とは行列計算から。</p>
<p><a href="https://github.com/deltam/neuro">deltam/neuro: Deep Neural Network written in Clojure from scratch</a></p>
<p>そのときに行列計算についてあるトリックを思いついて実装したら早くなったのでそれを紹介してみます。関数的プログラミングっぽい発想で、ほかにも応用が効くかもしれない。Clojureのデータ構造の勘所もすこし分かるかも。</p>
<p>注意:完全なる趣味の行いなので単に行列計算したいだけならそれ用のライブラリを使うほうが100倍かしこい。<br />
実用的な知識というよりちょっとしたトリックを面白がってくれればありがたい。</p>
<p>ニューラルネットの学習では行列の転置をよく使うんですが、プロファイルを取ってみたらそこが遅かったので何とかしたいといろいろやって思いついたトリックです。<br />
思ったより応用が効きました。</p>
<a name='more'></a>
<h2 id="最初の実装">最初の実装</h2>
<h3 id="行列の表現">行列の表現</h3>
<p>
$$
\begin{pmatrix}
1 & 2 & 3 \\\\
4 & 5 & 6
\end{pmatrix}
$$
</p>
<p>上の行列を表現するには行・列のサイズ(shape)と中身の値を持っておく必要があります。</p>
<p>行列は素朴に考えると二次元配列だけど、入れ子の配列を操作するのは面倒なので一次元にしてます。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn mat [col row v]
{:shape [col row]
:vec (vec v)})
(def m1 (mat 2 3 [1 2 3 4 5 6]))
</code></pre>
<p>つぎに行列の要素を取り出す関数を書きたい。そのためには行・列から<code>:vec</code>のインデックスに変換する関数が必要。<br />
両方をあわせてこのように書いておく。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn cr->i [v c r]
(let [[_ row] (:shape v)]
(+ (* c row) r)))
(defn mget [m c r]
(let [i (cr->i m c r)]
(nth (:vec m) i)))
</code></pre>
<p>コードを書いてると行と列がごっちゃになって混乱するので表示する関数も書いておくと便利です。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn show [m]
(let [[col row] (:shape m)]
(doseq [c (range col), r (range row)]
(printf " %d " (mget m c r))
(if (= r (dec row))
(println)))))
;mat1=> (show m1)
; 1 2 3
; 4 5 6
</code></pre>
<h3 id="転置とベンチマーク">転置とベンチマーク</h3>
<p>さてこれで行列の表現と値を取り出す操作が用意できた。これを使って基本的な行列演算である転置を書いてみる。</p>
<p>転置はある行列を対角線に沿って反転させる操作です。</p>
<p>例</p>
<p>
$$
\begin{eqnarray}
A = \left(
\begin{array}{ccc}
1 & 2 & 3 \\\\
4 & 5 & 6
\end{array}
\right)
\end{eqnarray}
$$
$$
\begin{eqnarray}
A^{ \mathrm{ T } } = \left(
\begin{array}{ccc}
1 & 4 \\\\
2 & 5 \\\\
3 & 6 \\\\
\end{array}
\right)
\end{eqnarray}
$$
</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn transpose [m]
(let [[col row] (:shape m)
v (for [r (range row), c (range col)]
(mget m c r))]
(mat row col v)))
;mat1=> (def m1 (mat 2 3 [1 2 3 4 5 6]))
;#'user/m1
;mat1=> (show m1)
; 1 2 3
; 4 5 6
;nil
;mat1=> (show (mat1/transpose m1))
; 1 4
; 2 5
; 3 6
</code></pre>
<p>素朴なベンチマークとして指定回数だけ転置を繰り返す関数を作った。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn bench [lim]
(let [m (mat 100 100 (range 10000))]
(dotimes [n lim]
(do (transpose m)))))
;mat1=> (time (bench 10000))
;"Elapsed time: 26856.948132 msecs"
</code></pre>
<p>10000回でも結構時間がかかっている。</p>
<h2 id="トリック1-転置フラグ">トリック1: 転置フラグ</h2>
<p>よく考えると転置は行・列と実際の配列インデックスの紐付けを変更するだけの処理です(<code>(i,j) -> (j,i)</code>)。「インデックスを計算するとき転置させたか判断してうまく変換してやれば<code>:vec</code>を書き換えなくてもOKなのでは?」と思いつきました。</p>
<p>そこで転置済みかのフラグ<code>:transposed?</code>を追加してみた。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn mat [col row v]
{:shape [col row]
:vec (vec v)
:transposed? false})
(defn cr->i [v c r]
(let [[col row] (:shape v)]
(if (:transposed? m)
(+ c (* r col))
(+ (* c row) r))))
</code></pre>
<p>転置は以下のように<code>:shape</code>と<code>:transposed?</code>を反転させるだけ。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn transpose [m]
(-> m
(update :shape reverse)
(update :transposed? not)))
;mat2=> (def m1 (mat 2 3 [1 2 3 4 5 6]))
;#'user/m1
;mat2=> m1
;{:shape [2 3], :vec [1 2 3 4 5 6], :transposed? false}
;mat2=> (transpose m1)
;{:shape (3 2), :vec [1 2 3 4 5 6], :transposed? true}
;mat2=> (show m1)
; 1 2 3
; 4 5 6
;nil
;mat2=> (show (mat2/transpose m1))
; 1 4
; 2 5
; 3 6
;nil
</code></pre>
<p><code>:vec</code>の内容は変わらないけど、転置行列として扱うことができます。</p>
<p>最初と同じ<code>bench</code>を使って簡易ベンチマークを取ってみた。</p>
<pre class="language-clojure"><code class="prism : language-clojure">mat2=> (time (bench 10000))
"Elapsed time: 7.434236 msecs"
</code></pre>
<p>やった! <strong>クッソ早い!</strong></p>
<h3 id="clojureのpersistentmap">ClojureのPersistentMap</h3>
<p>なんでこんなに早くなったのか。それにはClojureのMapの実装が関係しています。</p>
<p>Clojureでは値は不変(Immutable)なので、Mapを書き換える関数は新たなMapを生成して返します。しかし本当に全部コピーして新たなMapを作っていると非効率なので変更されていないKey-Valueは元の値と共有されています。そのようなデータ構造を永続データ構造(Persistent Data Structure)<sup class="footnote-ref"><a href="#fn1" id="fnref1">1</a></sup>と言うらしい。</p>
<p>最初の実装では<code>:vec</code>を次々書き換えていくため、共有されるValueが少なく新たに作られるMapの負荷が大きかった。二番目の<code>:transposed?</code>を使う実装だと変更後との差分が少なくPersistentMapの特性とマッチしていて効率的にMap作成が行うことができた(<code>:vec</code>を新たに作る処理も省略できた)。直感に反するけども、サイズの大きいValueについては編集せずそのままコピーしたほうが効率的なようです。</p>
<p>Clojureの永続データ構造の振る舞いについては以下の解説記事が参考になります。<br />
PersistentVectorについての解説だけどPersistentMapの理解にも役立つ。</p>
<ul>
<li><a href="https://hypirion.com/musings/understanding-persistent-vector-pt-1">Understanding Clojure’s Persistent Vectors, pt. 1</a></li>
<li><a href="https://hypirion.com/musings/understanding-persistent-vector-pt-2">Understanding Clojure’s Persistent Vectors, pt. 2</a></li>
</ul>
<p>Clojure設計者のRich Hickey自身が解説している講演のTranscriptも参考になる。</p>
<p><a href="https://github.com/matthiasn/talk-transcripts/blob/master/Hickey_Rich/AreWeThereYet.md">talk-transcripts/AreWeThereYet.md at master · matthiasn/talk-transcripts</a></p>
<h2 id="トリック2-関数リテラルをもたせる">トリック2: 関数リテラルをもたせる</h2>
<p>DNNフレームワークでもう一つ重たい処理がありました。学習データを一つの巨大な行列として作って、それを行ごとに切り分けてミニバッチという単位にして学習に使うのだけど、その切り分けに時間がかかっていました。</p>
<p>上記のトリックと永続データ構造の特性を考えていて新たなトリックを閃いた。</p>
<p><strong>「データ構造にインデックス変換の関数それ自体を持たせれば良いのでは?」</strong></p>
<p>転置行列用のフラグを用意するのではなく、インデックス変換関数それ自体を持たせて転置のときはそれをWrapすればいい。切り分けるのもそれで対応できそう。</p>
<p>つまり行列の表現を次のように書き換えます。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn mat [col row v]
{:shape [col row]
:vec (vec v)
:posf (fn [c r] (+ (* c row) r))})
(defn cr->i [m c r]
((:posf m) c r))
</code></pre>
<p><code>:posf</code>がインデックス変換の関数。これを値として持たせてしまう。<br />
転置はこのように書ける。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn transpose [m]
(let [f (:posf m)]
(-> m
(update :shape reverse)
(assoc :posf (fn [c r] (f r c)))))) ; 引数の順番を入れ替えるだけ
</code></pre>
<p>さらにこの方法だと行ごとに切り分ける関数も同じトリックでいける。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn slice [m start end]
(let [[col row] (:shape m)
size (- end start)
f (:posf m)]
(-> m
(assoc :shape [size row])
(assoc :posf (fn [c r]
(f (+ c start) r))))))
;mat3=> (def m3 (mat 3 2 [1 2 3 4 5 6]))
;#'user/m3
;mat3=> (show m3)
; 1 2
; 3 4
; 5 6
;nil
;mat3=> (show (mat3/slice m3 1 3))
; 3 4
; 5 6
;nil
</code></pre>
<p>同じように転置についてベンチマークを取ってみた。</p>
<pre class="language-clojure"><code class="prism : language-clojure">mat3=> (time (bench 10000))
"Elapsed time: 12.941026 msecs"
</code></pre>
<p><code>:transposed?</code>フラグを使う方法と同じくらい早い。だが応用範囲はこっちのほうが広い。</p>
<h3 id="応用1-ランダムシャッフル">応用1: ランダムシャッフル</h3>
<p>転置行列、行列の切り分けで説明したが、こんな処理も書ける。</p>
<p>行をランダムシャッフルする関数。行のインデックスをシャッフルしたシーケンスを関数リテラルの中に持たせている。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn shuffle-col [m]
(let [[col _] (:shape m)
rs (shuffle (range col))
f (:posf m)]
(assoc m :posf (fn [c r]
(f (nth rs c) r)))))
;mat3=> (show m3)
; 1 2
; 3 4
; 5 6
;nil
;mat3=> (show (shuffle-col m3))
; 5 6
; 1 2
; 3 4
</code></pre>
<h3 id="応用2-one-hot-ベクトルの表現">応用2: One-Hot ベクトルの表現</h3>
<p>機械学習ではあるデータがカテゴリに属していることを表すのにOne-Hotベクトルというものを使います。これは特定の列だけ1でそれ以外は0のベクトル。<br />
このトリックを使うとほとんどメモリを使わずに表現できる。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn one-hot [size hot-idx]
{:shape [1 size]
:vec [0 1]
:posf (fn [_ r]
(if (= r hot-idx)
1
0))})
;mat3=> (show (one-hot 10 3))
; 0 0 0 1 0 0 0 0 0 0
</code></pre>
<h3 id="応用3-ブロードキャスト">応用3: ブロードキャスト</h3>
<p>同じ行を指定数だけ増やす関数も書ける。numpyではこれを自動でやってくれてるブロードキャスト機能というものがある。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn broadcast-row [m-row col-size]
(let [[_ row] (:shape m-row)
f (:posf m-row)]
(-> m-row
(assoc :shape [col-size row])
(assoc :posf (fn [_ r]
(f 0 r))))))
;mat3=> (def m4 (mat 1 4 [1 2 3 4]))
;#'user/m4
;mat3=> (show m4)
; 1 2 3 4
;nil
;mat3=> (show (broadcast-row m4 3))
; 1 2 3 4
; 1 2 3 4
; 1 2 3 4
</code></pre>
<h3 id="応用4-組み合わせ">応用4: 組み合わせ</h3>
<p>関数をWrapしているだけなので組み合わせても問題ない。レキシカルクロージャなのでその時点でのrow,colを保存しておけるという利点が効いている。</p>
<pre class="language-clojure"><code class="prism : language-clojure">mat3=> (def m3 (mat 3 2 [1 2 3 4 5 6]))
#'user/m3
mat3=> (show m3)
1 2
3 4
5 6
nil
mat3=> (-> m3
(slice 1 2) ; 2行目を切り出し
(transpose) ; 転置する
(show))
3
4
mat3=> (-> (one-hot 10 3) ; OneHotベクトルを生成
(broadcast-row 3) ; 3行に増やす
(transpose) ; 転置する
(show))
0 0 0
0 0 0
0 0 0
1 1 1
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
</code></pre>
<p>このトリックはかなり応用が効く。</p>
<h2 id="弱点">弱点</h2>
<p>このトリックには一つ弱点があります。<strong>変更に弱い</strong>ことです。</p>
<p>行列の一部を変更する関数をこのように定義してみる。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn mput [m c r v]
(let [i (cr->i m c r)]
(assoc-in m [:vec i] v)))
</code></pre>
<p>ふつうの行列については正しく動く。</p>
<pre class="language-clojure"><code class="prism : language-clojure">mat3=> (def m1 (mat 2 3 [1 2 3 4 5 6]))
#'mat3/m1
mat3=> m1
{:shape [2 3], :vec [1 2 3 4 5 6], :posf #object[mat3$mat$fn__148 0x1021f6c9 "mat3$mat$fn__148@1021f6c9"]}
mat3=> (show m1)
1 2 3
4 5 6
mat3=> (show (mput m1 0 0 10)) ; 左上を10に変更
10 2 3
4 5 6
</code></pre>
<p>しかしトリックを組み合わせた行列にそのまま適用するとおかしなことになる。表示される行列は見かけのものであり、実態は2つの要素<code>[0 1]</code>だけだから。</p>
<pre class="language-clojure"><code class="prism : language-clojure">mat3=> (def m4 (-> (one-hot 10 3)
(broadcast-row 3)))
#'mat3/m4
mat3=> (show m4)
0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
nil
mat3=> (show (mput m4 0 0 99)) ; 左上を99に置き換える -> 失敗
99 99 99 1 99 99 99 99 99 99
99 99 99 1 99 99 99 99 99 99
99 99 99 1 99 99 99 99 99 99
nil
</code></pre>
<p>これを回避するために見かけの行列を反映したコピーを作る関数を用意する。</p>
<pre class="language-clojure"><code class="prism : language-clojure">(defn clone [m]
(let [[col row] (:shape m)
v (for [c (range col), r (range row)]
(mget m c r))]
(mat col row v)))
;mat3=> (show (mput (clone m4) 0 0 99)) ; 左上を99に置き換える -> 成功
; 99 0 0 1 0 0 0 0 0 0
; 0 0 0 1 0 0 0 0 0 0
; 0 0 0 1 0 0 0 0 0 0
;nil
</code></pre>
<p>行列をファイル出力するときなどもcloneは必要でしょう。</p>
<p>ニューラルネット学習では更新する必要があるのは全結合層の重み行列です。これは逆伝播のたびに全要素を更新していくのでこのトリックを使う余地はなく問題なく更新できる。One-hotベクトルのトリックは学習データに使っているがこれは入力データなので更新されない。</p>
<p>たまたまだがこのトリックは用途にベストマッチしていた。</p>
<p>最終的にやった実装がこれ<sup class="footnote-ref"><a href="#fn2" id="fnref2">2</a></sup>。</p>
<p><a href="https://github.com/deltam/neuro/blob/master/src/neuro/vol.clj">neuro/vol.clj at master · deltam/neuro</a></p>
<h2 id="まとめ">まとめ</h2>
<p>データ構造に関数リテラルをもたせると柔軟な表現が可能になります。<br />
そのトリックはClojureのPersistentMapの特性とも合致していて効率化も果たせました。<br />
関数型っぽい行列計算の実装ができ、趣味プロジェクトが進んで満足。</p>
<p>だけど趣味ではないコードで行列演算が必要な場合は自分で書かずにライブラリを探しましょう(令和の時代に行列掛け算のバグに泣かされるべきでない)。</p>
<p>おわり。</p>
<hr class="footnotes-sep" />
<section class="footnotes">
<ol class="footnotes-list">
<li class="footnote-item" id="fn1"><p>永続データ構造自体については<a href="https://en.wikipedia.org/wiki/Persistent_data_structure">英語版Wikipedia</a>がわかりやすい。Clojureでどのように使われているかも触れられている。 <a class="footnote-backref" href="#fnref1">↩︎</a></p>
</li>
<li class="footnote-item" id="fn2"><p>余談:numpyも同じようなことをやっているのかとコードや記事を読んでみたが違うみたいだった。汎用的に効率のいいコードは大変だー。<a href="https://codezine.jp/article/detail/11211">NumPyで使われる多次元配列のデータ構造「ndarray」とは?:CodeZine(コードジン)</a> <a class="footnote-backref" href="#fnref2">↩︎</a></p>
</li>
</ol>
</section>
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-70700398032173021862020-12-01T21:48:00.016+09:002021-12-15T13:42:07.652+09:00Bangle.js を購入した<p><a href="https://banglejs.com/">Bangle.js</a> というスマートウォッチを買いました。JavaScriptでアプリが作れる Hackable Smart Watch です。</p>
<blockquote class="twitter-tweet"><p lang="en" dir="ltr">my new gear... <a href="https://t.co/jY9FxXx14N">pic.twitter.com/jY9FxXx14N</a></p>— deltam (@deltam) <a href="https://twitter.com/deltam/status/1327187400062246912?ref_src=twsrc%5Etfw">November 13, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
<a name='more'></a>
<p>値段は 58.3ポンド(8,100円ぐらい)です。ついでにクレードル 9.9ポンドも付けて送料込みで 80.55ポンド(11,200円ぐらい)でした。PayPalで払えました。<br>
コロナのせいで届くまで時間がかかるらしいと聞いてましたが、注文してから my new gear… するまで8日程度でした。</p>
<p>開発環境はブラウザのみで整います。<a href="https://www.espruino.com/ide/">Web IDE</a> の左上の黄色い□を押すと Web Bluetooth の接続画面が出てきて、コンソールを叩くとそのままスマートウォッチを操作できます。すごく簡単でびっくりしました。</p>
<p>技術的な詳細は作者自身がプレゼンしているこの動画で見れます。コンソール背景にウェブカムで Bangle.js を映してデモやるのかっこいいですね。</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/fq753pg5wRo" allowfullscreen=""></iframe>
<p>通っている市民プールでスマートウォッチが解禁になり、せっかくなら自分でプログラムを書いてデータを取りたいなと思っていて物色していました。<br>
FitBitはAPIで加速度計の生データが取れないっぽい/Android Wear OS の端末は種類少なくて高価な上になんかゴツいなどの Pros/Cons を考慮し、最終的に「JavaScriptが動く腕時計はなんかかっこいい」という冷静な判断を下し購入しました。</p>
<p>梱包を開けて1時間もしないうちに Hello World できるのは素晴らしい。加速度計記録アプリはサクッと作れてもうプールで試してきました。良い判断だったと思ってます。</p>
<p>(今度はデータ解析がんばらないとなー)</p>
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">自作の加速度計レコーダアプリをBangle.jsに入れて近所の公営プールで泳いできた。グラフ見ただけだと何もわからん。 <a href="https://t.co/WpYVyqUKd3">pic.twitter.com/WpYVyqUKd3</a></p>— deltam (@deltam) <a href="https://twitter.com/deltam/status/1328939695896735746?ref_src=twsrc%5Etfw">November 18, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-64810622593011581532019-12-01T00:00:00.003+09:002021-12-15T13:43:11.940+09:002つの操作のみで全順列を列挙する:対称群のグラフ上のハミルトン路にもとづく順列生成の紹介と実装<p><a href="https://qiita.com/advent-calendar/2019/str">データ構造とアルゴリズム Advent Calendar 2019</a>の1日目の記事です。<br />
2日目は<a href="https://qiita.com/yurahuna">@yurahuna</a>さんによる「<a href="https://qiita.com/yurahuna/items/cf6b309e9c984d036d64">三角形分割の数え上げとランダムサンプリング</a>」です。</p><p>6月に<a href="https://deltam.blogspot.com/2019/06/blog-post.html">グレッグ・イーガン氏のHPで見つけた順列生成アルゴリズム</a>についてブログを書きました。<br />
そのあとに元ネタの論文<sup class="footnote-ref"><a href="#fn1" id="fnref1">1</a></sup>を読んでいたのですが、おもしろい順列生成アルゴリズムを含んでいたのでGoでライブラリ化してみました。</p><p><a href="https://github.com/deltam/perm">deltam/perm: Permutation generator based on group theory written in Go</a></p><p>自分のベンチマークでは再帰関数で実装したナイーブなアルゴリズムより<a href="https://github.com/deltam/perm#performance">33%ほど早い</a>ですが、高速さが売りというよりも「順列への最小限の操作セットのみを駆使して順列生成できないか?」という研究の流れから出てきた副産物的なアルゴリズムです。</p><p>ただその最小限の操作セットを駆使するアイデアが面白く、最終的に出来るルールが非常にシンプルで実装も短くできるのでアドベントカレンダーに乗じて紹介しようと思います。</p><p>まずアルゴリズムの背景となる論文の内容を紹介し、その結果をルール化して順列生成のプログラムを作ります。</p><br />
<br />
<a name='more'></a>
<h2 id="順列の群とグラフとその経路">順列の群とグラフとその経路</h2><p>元ネタはこのAaron Williams氏の論文です。</p><p><a href="https://arxiv.org/abs/1307.2549">Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 … n) and τ = (1 2)</a></p><p>(同著者の若干読みやすい別の文書<sup class="footnote-ref"><a href="#fn2" id="fnref2">2</a></sup>もあります。グレッグ・イーガン氏が<a href="https://ja.wikipedia.org/wiki/%E8%B6%85%E7%BD%AE%E6%8F%9B">最小超置換</a>に関連して解説している記事<sup class="footnote-ref"><a href="#fn3" id="fnref3">3</a></sup>もあります)</p><p>この論文は順列の集合に次の2つの関数を定義して群としたものを対象としています。論文ではギリシャ文字で書いてますがこの記事ではsigma,tauと表記します(入力が面倒だった…)。</p><pre class="code"><code class="plaintext">sigma: (1,2,...,n) -> (2,3,...,n,1) // ローテーション
tau: (1,2,...,n) -> (2,1,...,n) // 先頭2つのスワップ
</code></pre><p>sigmaは順列をひとつずつローテーションしていくのでn回やると元に戻ります。tauは2回でもとに戻ります。</p><p>ふたつを組み合わせると任意の連続した2つの記号をスワップすることができるので、ある順列が与えられればすべての順列をsigma, tauで作り出すことが出来ます。順列の集合とsigma/tauを合わせたものは<a href="https://ja.wikipedia.org/wiki/%E5%AF%BE%E7%A7%B0%E7%BE%A4">対称群(Symmetric Group)</a>になります。</p><p>さらにこの対称群の順列を頂点、sigma/tauで移り変わる関係を辺として有向グラフにします。このように群から作ったグラフを<a href="https://ja.wikipedia.org/wiki/%E3%82%B1%E3%82%A4%E3%83%AA%E3%83%BC%E3%82%B0%E3%83%A9%E3%83%95">ケーリーグラフ(Cayley graph)</a>というそうです。</p><p>n=4の順列でケーリーグラフを作って図にしてみました。実線がsigmaで点線がtauです。</p><div align="center"><img alt="n=4 all edges" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5y60gqB0r1DDHE9FAlIiUPK8FY1-fPYHwaVIXSevy94sZtof6oZqDLcXk83CJm7oQCdQzDhPtO9xejjJNNKr6Dd7uXq9OmGBQhE64ltAyNXDottYO7VUxZCdILV6eqtwCAi0W/s1600/68528738-1693e880-033a-11ea-9441-845d1e0ea57b.png" width="100%" /> <p>図1 順列n=4のケーリーグラフ</p></div><p>このグラフ上に <strong>「すべての頂点を一度だけめぐる経路は存在するのか?」</strong> というのがこの論文の解決したい問題(通称 <i>Sigma-Tau Path Problem</i> <sup class="footnote-ref"><a href="#fn2" id="fnref2:1">2</a></sup>)です。グラフの言葉でいうと<a href="https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E8%B7%AF">ハミルトン路(Hamilton path)</a>は存在するのか?ということです。</p><p>ハミルトン路が存在するなら「ある順列から始めてsigma/tauのどちらかの操作を繰り返すことにより毎回違う順列にするような操作の順序が存在する」ということがわかります。</p><p>この論文は <strong>「すべての n についてハミルトン路は存在する」</strong> ということを証明しました。それを生成するためのシンプルなルールも提示しています。</p><p>これはたとえばトランプの山札に対して「一番上の1枚を一番下に移動する」と「上から1枚目と2枚目を入れ替える」のどちらかを $52!$ 回繰り返して毎回違う順番にすることができるということで、なんだか不思議な結果に思えますね。</p><p>余談ですが、論文ではさらに「 n が奇数ならハミルトン閉路(Hamilton cycle, 始点と終点がつながる)が存在する」ということも証明しています(偶数なら存在しないことは <em>Rankin’s Campanological Theorem</em> からわかっているそうです<sup class="footnote-ref"><a href="#fn4" id="fnref4">4</a></sup>)。</p><p>「 $n \geq 3$ の奇数のケーリーグラフにはいつでもハミルトン閉路が存在するか」という問題はクヌース先生の<i>The Art of Computer Programming</i>でも最高難度(48/50)の問題として挙げられているもので(4巻 7.2.1.2 問題7<sup class="footnote-ref"><a href="#fn4" id="fnref4:1">4</a></sup>)、この論文はそれを解決しました(でも順列生成にはハミルトン路だけで十分なのでハミルトン閉路生成について詳しくは解説しません!)。</p><br />
<br />
<h3 id="輪っかとジグザグ">輪っかとジグザグ</h3><p>論文では上記のようなケーリーグラフには「<strong>ちょうど2つの共通部分を持たないなサイクルカバーが存在する</strong>」ということを証明し、2つのサイクルをつなぎ合わせることでハミルトン路を構成して証明しました。</p><p><a href="https://en.wikipedia.org/wiki/Vertex_cycle_cover">サイクルカバー(cycle cover)</a>はグラフ上のループで同じ頂点を2回以上通らないものです。(正式には <i>vertex-disjoint cycle cover</i> , 日本語だと<a href="https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96">閉道</a>というらしいですが慣れていないのでサイクルカバーと表記します)</p><p>全部の辺を表示すると煩雑なのでsigma辺だけ表示するとこのようなグラフになります。</p><div align="center"><img alt="n=4 sigma edges" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpvyZsvK2xPKM0Rph3HsETOHzibNX1FD8F198tAIJ1-u-T3bfBOAYK6bztP0GQvsOy_MG2ysPb1RhPkJohjSxquV9VlSJCfVcPCIJc-fopwTOS_0K5job48uAgsn77XuS4jr_Q/s1600/sigma4_rot.png" width="100%" /> <p>図2 順列n=4のsigmaサイクル</p></div><p>この図2と最初の図1を見ると次のことがわかります。</p><ul><li>sigma辺はローテーションなので n 回でもとに戻るサイクルカバーを作る(<strong>sigmaサイクル</strong>と呼ぶことにする)</li>
<li>tau辺は異なるsigmaサイクルにつながっている</li>
<li>すべての頂点はsigma,tau辺が2つずつあり、それぞれ出発する方向と到着する方向がひとつずつである</li>
</ul><p>どうにかsigmaサイクル同士をtau辺で繋いで大きなサイクルにする手順が考えられないか。</p><p>そこでこのようなルートを考えます。まず適当な頂点から始めてtau辺を通り、つぎにsigma辺を<strong>逆に</strong>たどるのを繰り返します(「有向グラフなのに逆に進んでOKなの?」と思うかもしれませんが、最終的に逆方向の辺は消去されます)。</p><p>4321から始めるとこのように移動します。</p><pre class="code"><code class="plaintext">4321 tau-> 3421
sigma<- 1342
tau-> 3142
sigma<- 2314
tau-> 3214
sigma<- 4321 (最初に戻る)
</code></pre><p>図2の上半分のレイアウトに合わせて描くとこんなかんじ。</p><div align="center"><img alt="ac4 one" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2DKgEso1R1gS6YzM9uiNxRhHxvW3NFq6sRtW-Cq6uoNjGHFEiSI3sH_AlYr-rBFm362Q5cOw90CVHILClWjMGMRdVybTRSqrbvwQiOz4NDfIOOZycYLhL-ocW2oncd-0wcVQi/s1600/ac4_one.png" width="100%" /> <p>図3 4321を始点とする交互サイクル</p></div><p>このルートがサイクルをつなげる鍵で、論文では <strong>交互サイクル(alternating-cycle)</strong> と呼ばれています。これを接しているsigmaサイクルと合成してみます。</p><div align="center"><img alt="n=4 sigma edges" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9-3-icdETSmNMTtMD7d7fidUrgtpGqhnynGWRrByKEJ3bxjvlkG8nuTFkkTqptXqtd_4Ubq-vBndmnfy8udK0oiJYLdldX5eEt3mGAYA7oC9d3CfrphMNHlfr7LQ907nkE8AQ/s1600/sigma4_ac4_one.png" width="100%" /> <p>図4 交互サイクルとsigmaサイクルの和</p></div><p>二重になっている辺を削除するとこうなります。</p><div align="center"><img alt="cycle one" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgemb2zi8gE124JmP-D8JtWFyJP1-N256IlfwCA2Q8UyFYEwU3H8DDfYbCMQ7aoYN_1VTUjZ2iVwdFfdkt04AKhaBPFzSyyZKM9EUy5uOcmhPWqkn4qyxjupsPQdV_a9xytyHU-/s1600/cc4_one.png" width="100%" /> <p>図5 交互サイクルとsigmaサイクルの対称差</p></div><p>3つのsigmaサイクルがつながって大きなサイクルになりました。</p><p>このように<strong>sigmaサイクルと交互サイクルの<a href="https://ja.wikipedia.org/wiki/%E5%AF%BE%E7%A7%B0%E5%B7%AE">対称差(symmetric difference)</a>を取ったものもまたサイクルカバー</strong>になります。 なぜでしょう?</p><p>サイクルカバーの頂点の持つ辺の向きを考えてみます。頂点をちょうど一度だけ通るのだから到着する方向と出発する方向の二本を持っているはずです。</p><p>交互サイクルの辺の向きも見てみましょう。図3のレイアウトを変えたものが以下です。</p><div align="center"><img alt="alternating-cycle" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhyUVDKjZ3HvI8PF43CZaCEUu0VLI0_9gTzwHOBQ0J7k1lF2_VwbxWANwY8P4CCSCU_JemN08tI0QjgDKsx5X4XetdPN3RoWpyUO4vQcc8AvQxMAXbfq2L76KGlzRHtF35JUeyw/s1600/68669697-80a4cb80-058e-11ea-83d1-a3a5c77e7ba3.png" width="40%" /> </div><p>交互サイクルはそれぞれ二本の辺を持ちますが、両方とも到着する方向 or 出発する方向のどちらかです。そして二本のどちらか一方だけsigma辺です。</p><p>sigmaサイクルと対称差を取った場合、sigmaサイクルのある頂点は到着する or 出発する方向のsigma辺を失いますが、同時に同じ方向のtau辺を得ます。つまり<strong>それぞれの頂点は持っている辺の個数と方向だけ見ると変わっていません。</strong></p><p>頂点の持つ辺の方向というサイクルカバーの特性が変わらずtau辺によって異なるsigmaサイクル同士がつながるので、大きなサイクルカバーを作ることができるという仕組みです。</p><p>論文によると対称差をつかう手法は17世紀から知られていたそうですが、交互サイクルという形にして絶妙に使いこなしたことがこの論文の<strong>最大のハック</strong>だと思います。</p><br />
<br />
<h3 id="交互サイクルの始点">交互サイクルの始点</h3><p>sigmaサイクルと交互サイクルで大きなサイクルカバーができるのはわかりましたが、上記の例は3つのsigmaサイクルを繋げただけです。できるだけ多くつなげるにはどうしたらいいでしょう? 辺や頂点がかぶらない作り方をしたいですね。</p><p>まずは交互サイクルの特性をもうすこし調べてみましょう。以下は4321から始まる交互サイクルの頂点を並べたものです。</p><p>4 <strong><u>3</u></strong> 2 1<br />
<strong><u>3</u></strong> 4 2 1<br />
1 <strong><u>3</u></strong> 4 2<br />
<strong><u>3</u></strong> 1 4 2<br />
2 <strong><u>3</u></strong> 1 4<br />
<strong><u>3</u></strong> 2 1 4</p><p><code>4321</code>から<code>3</code>の位置は最初と二番目を行ったり来たりしています。3を取り去るとそれ以外の並びは<code>421</code>とローテーションで一致します。始点の二番目の文字とそれ以外の循環的な並びが違うなら交互サイクルも頂点や辺が共有されることはありません。</p><p>$nmr…$ という順列の並びを考えます。nを先頭に固定して $nmr$ で始まる順列の集合を表したものです。これを交互サイクルの始点にすると最初と二番目を交互に移動する数字が m になり、循環的な並びは $nr…$ になります。</p><p>じつはこの $(r,m)$ の組みを次のように選ぶとsigmaサイクルを全部つなげることができます<sup class="footnote-ref"><a href="#fn5" id="fnref5">5</a></sup>。</p><p>$$<br />
(1,2), (2,3), … , (n-2, n-1), (n-1,1)<br />
$$</p><p>$$<br />
\begin{equation}<br />
\therefore m = (r \bmod{n-1}) +1 \tag{1}<br />
\end{equation}<br />
$$</p><p>$n=4$ の場合は次の3つの始点から交互サイクルを作ればOKです。</p><pre class="code"><code class="plaintext">(1,2) => 4213
(2,3) => 4321
(3,1) => 4132
</code></pre><div align="center"><img alt="alternating-cycle from 4213,4321,4132" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9tk87SC5dqhTFvBbf3Re9-KcNAFqGyw6CIxHvj33UyK-yUjQKTUvHvDMJ58nU5lPMtnezil4Nt2k8QRejNhcuhlUA4NG7znHHdw7nVJgZnmX6KPh-iyynd94IubIShq_uf03m/s1600/68528767-7b4f4300-033a-11ea-88e5-e1723762fd7d.png" width="100%" /> <p>図6 4213,4321,4132から始まる交互サイクル</p></div><p>sigmaサイクルと対称差を取ると灰色の辺が消えて大きな2つのサイクルになっています!</p><div align="center"><img alt="2 cycle cover" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnCDLyqHqj7ecNT1JNHmw0-Dfg-hfB2_eWfGkD3Q2SOwjVNG-1MkgWlHQo5sQIhnkNgVafRrpkK_jbe1x4lV3IhzyRs4Mme5Img34b21UfKF7Lyn81Ahc-MU_CC7WzqNKI4BRm/s1600/cc4_rot.png" width="100%" /> <p>図7 交互サイクルとsigmaサイクルから作った2つのサイクルカバー</p></div><br />
<br />
<h3 id="cycle-rule">2-Cycle Rule</h3><p>上記の交互サイクルの選び方をするとかならず長さ $2(n-1)$ の Small Cycle とそれ以外全部の Large Cycle になるそうです。なぜそうなるのかと説明したいところなのですが、論文では組合せ論の<a href="https://en.wikipedia.org/wiki/Rotation_system"><i>Rotation system</i></a>というものを使って証明していて、私にはよく分かりませんでした…<sup class="footnote-ref"><a href="#fn6" id="fnref6">6</a></sup></p><p>掴んだニュアンスだけでふんわりと説明すると交互サイクル同士はsigmaサイクルを経由してつながる木構造のような形になるのですが、式(1)の選び方だと根の部分にhubと呼ばれるサイクルができてしまいそれが Small Cycle になるようです。</p><p>さて図7のところまで来ました。式(1)の関係で交互サイクルを作っていて交互サイクルのsigma辺は消えていることを考えると、図7を作るためのルールが考えられます。ルールはある頂点からsigma辺、tau辺のどちらの進むかを決めることができればサイクルカバーを作れるのでOKです。</p><p>ある順列の二番目の数字を $m$ とし、循環的に $n$ の右隣にある数字を $r$ とします( $n$ が最後尾にある場合はrは最初の数字)。ただし $r=m$ だったら $m$ を抜かして三番目の数字を $r$ とします。そう決めると図7の2つのサイクルを作るルールを次のように書けます。</p><p>$$\begin{eqnarray}<br />
cycle(p) = \begin{cases}<br />
tau(p) & \text{if} \quad m = (r \bmod{n-1})+1 \\<br />
sigma(p) & \text{else}<br />
\end{cases} \tag{2}<br />
\end{eqnarray}$$</p><br />
<br />
<h3 id="小さい輪と大きい輪をつなげるポイント">小さい輪と大きい輪をつなげるポイント</h3><p>ふたつのサイクルカバーを作るルールが得られましたが、それだけでは全体の順列生成に使えません。どこかで切って繋げてひとつながりの経路にしたいですね。</p><p>さて上記の(2)のルールを逆順に並べた順列に対して適用してみましょう(n=4なら 4321 )。実は逆順の順列は必ず Small Cycle に属します。</p><pre class="code"><code class="plaintext">4321: m=3, r=2 -> tau -> 3421
3421: m=n -> sigma -> 4213
4213: m=2, r=1 -> tau -> 2413
2413: m=n -> sigma -> 4132
4132: m=1, r=3 -> tau -> 1432
1432: m=n -> sigma -> 4321 (最初に戻る)
</code></pre><p>見ての通り、逆順<code>4321</code>から始まる Small Cycle は n の位置が最初か2番めでそれ以外はn-1の逆順のローテーションになり、長さが $2(n-1)$ になります。 $n!$ 個の頂点の中の $2(n-1)$ 個のサイクルなのでSmall Cycleと名付けられているわけです。</p><p>Small Cycle では 4321 からtau辺をたどるのですが、そこでsigma辺に進むと 4 の位置関係が崩れるので Large Cycle に移動します。論文でもここを切り分けて繋げるポイントにしていますが、実装上でも逆順判定をする処理をSmall Cycle、Large Cycle両方の終了を判定に使えるので都合がいいです。</p><p>4321 から 3214 へのsigma辺を足してひとつながりにしたものが以下です。4321 で切り分けるため経路の始点を $tau(4321)=3421$ にしています。</p><div align="center"><img alt="hamilton path" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhH29Gl5r_RjbFiPq15nmIaWn0EkxwjUt6-E9hYbnGRrW2z35yR2ycopUzb47hDaqPlSXHRDu4Fmzu0LUPug3Pn644zz106B-koSTOsAfip9ZysEOILZPEl30SrQP0TgYlWgNCU/s1600/68540207-2c082180-03d1-11ea-8c40-33042464b988.png" width="100%" /> <p>図8 n=4のハミルトン路(Hamilton Path)</p></div><br />
<br />
<h3 id="順列生成ルール">順列生成ルール</h3><p>切り分けポイントを含めた最終的なルールをまとめます。</p><p>$$<br />
\begin{eqnarray}<br />
path(p) = <br />
\begin{cases}<br />
tau(p) & \text{if} \quad m = (r \bmod{n-1})+1 \land p \ne n,n-1,…,2,1 \\<br />
sigma(p) & \text{else}<br />
\end{cases} \tag{3}<br />
\end{eqnarray}<br />
$$<br />
</p><p>論文では <em>Definition 3.</em> と書いているものと同等のものです(論文では記述の簡潔さのためか逆順ルートで生成するルールになっている)。</p><br />
<br />
<h2 id="実装">実装</h2><p>ルール(3)をGoで実装してみたのが以下です<sup class="footnote-ref"><a href="#fn7" id="fnref7">7</a></sup>。ブラウザで動作確認したい場合は<a href="https://play.golang.org/p/r9-_63FxQmg">Go Playground</a>をどうぞ。</p><br />
<pre class="code"><code class="go">package main
import "fmt"
const N = 4
func main() {
p := make([]int, N)
all := 1
for i := 0; i < N; i++ {
p[i] = N - i
all *= i + 1
}
tau(p)
fmt.Println(p)
for i := 1; i < all; i++ {
if ruleCycle(p) && !isSmallCycleEnd(p) {
tau(p)
} else {
sigma(p)
}
fmt.Println(p)
}
}
func sigma(p []int) {
f := p[0]
copy(p[0:N-1], p[1:N])
p[N-1] = f
}
func tau(p []int) {
p[0], p[1] = p[1], p[0]
}
func ruleCycle(p []int) bool {
r, i := 0, 0
for p[i] != N {
i++
}
if i == 0 {
r = p[2]
} else {
r = p[(i+1)%N]
}
return p[1] == r%(N-1)+1
}
func isSmallCycleEnd(p []int) bool {
for i := 0; i < N; i++ {
if p[i] != N-i {
return false
}
}
return true
}
</code></pre><p>出力される順列にかぶりがないか確認します。</p><pre class="code"><code class="shell">$ go run main.go
[3 4 2 1]
[4 2 1 3]
[2 4 1 3]
[4 1 3 2]
[1 4 3 2]
[4 3 2 1]
[3 2 1 4]
[2 1 4 3]
[1 2 4 3]
[2 4 3 1]
[4 3 1 2]
[3 1 2 4]
[1 3 2 4]
[3 2 4 1]
[2 3 4 1]
[3 4 1 2]
[4 1 2 3]
[1 2 3 4]
[2 1 3 4]
[1 3 4 2]
[3 1 4 2]
[1 4 2 3]
[4 2 3 1]
[2 3 1 4]
$ go run main.go|sort
[1 2 3 4]
[1 2 4 3]
[1 3 2 4]
[1 3 4 2]
[1 4 2 3]
[1 4 3 2]
[2 1 3 4]
[2 1 4 3]
[2 3 1 4]
[2 3 4 1]
[2 4 1 3]
[2 4 3 1]
[3 1 2 4]
[3 1 4 2]
[3 2 1 4]
[3 2 4 1]
[3 4 1 2]
[3 4 2 1]
[4 1 2 3]
[4 1 3 2]
[4 2 1 3]
[4 2 3 1]
[4 3 1 2]
[4 3 2 1]
$ go run main.go |sort|uniq|wc -l
24
</code></pre><p>順列生成できました!</p><p>2018年の論文<sup class="footnote-ref"><a href="#fn2" id="fnref2:3">2</a></sup>にはC言語による実装も載っているので気になる方はチェックしてみてください。</p><br />
<br />
<h3 id="ライブラリでの実装">ライブラリでの実装</h3><p>もともと最小超置換探索のアルゴリズムを理解するためにClojureコードを書いてました。そこでグレッグ・イーガン氏の記事<sup class="footnote-ref"><a href="#fn3" id="fnref3:1">3</a></sup>に上記アルゴリズムをアレンジしたものが <em>The Williams Construction</em> として紹介されていたので興味本位で実装してみました(<code>superperm.williams</code>)。</p><p><a href="https://github.com/deltam/clj-superpermutation">deltam/clj-superpermutation: Clojure library for finding minimal superpermutation</a></p><p>Clojureには集合リテラルがあるので数学的な処理を書くのに便利です。REPLも試行錯誤して理解を深めるのに助かりました。実はこの記事の図もこのClojurerコードとGraphvizで作っています。</p><p>おもしろいアルゴリズムだったのでGoのライブラリに切り出してみました。Goの実装はベンチマーク、プロファイリングなど取って出来る限り高速化してます。</p><p><a href="https://github.com/deltam/perm">deltam/perm: Permutation generator based on group theory written in Go</a></p><p>上記の実装コードでは1…nの順列でしたが、配列のインデックスにそのまま使えるようにライブラリでは0…n-1の順列にしています。配列を与えて順列のイテレータっぽく使えるようにも作ってあります(詳しくは <a href="https://github.com/deltam/perm#usage">Usage</a> を読んでください)。</p><p>ライブラリでは上記コードのように $n!$ 個を出力してストップするのではなく順列の並びから終了判定しています。これによりたとえ $1000!$ 個の順列でも桁あふれすることなく生成し続けることができます。現在の順列を保存しておけばそこからすぐに生成を再開できるのも良いところですね。</p><p>ローテーション操作を多用するので例えば「先頭が <code>1,2,..</code> の順列だけスキップする」のようなことは出来ません。生成順序に癖があるので実用的かどうかは分かりません(そもそも順列生成ってどこで実用されるのか?)</p><p>より良い実装としてはsigma/tauが高速になるようなデータ構造を選ぶというのが考えられます。そこでローテーションが多用されるならリストをつかったほうが早いのではと思い<a href="https://golang.org/pkg/container/list/">container/list</a>で書き換えてみたのですが、逆に遅くなってしまいました。ビルトイン関数の copy が思ったより早かったようです。あとはビット列で表現するとsigmaがビットシフトで出来るので早くなりそうと思いましたが、そこまでは高速化に情熱が持てなかったのでこちらは試してません。</p><p>なにか面白いアイデアありましたら issue / PullReq をください!</p><br />
<br />
<h2 id="余談">余談</h2><h3 id="taocpでの言及">TAOCPでの言及</h3><p>紹介した論文が発表される前に書かれた <i>The Art of Computer Programming, Volume 4, p.333, 少数の生成器の使用</i> ではsigma-tauのやり方を次のように紹介しています。</p><blockquote><p>Ruskey, Jiang, Weston [Discrete Applied Math. 57(1995), 75-83] は, n=5のσーτを全数探索することによって5つの本質的に異なるHamiltonグラフが存在することと, そのうちの1つ「最も美しい」図22(a)に示すものを発見した。(中略)残念なことに, 彼らが発見した解には, はっきりとした論理的な構造を持たない。演習70にいくらか複雑さが少ない経路を述べるけれども, その経路でさえ単純であるとは言い難い。したがって, σ-τをのやり方は, もっと n が大きな値の場合には, 新しい構成方法が見つからない限り, あまり本気で使う気にはならない。</p></blockquote><p>今回紹介した順列生成アルゴリズムは「論理的な構造」を持つ「新しい構成方法」ではないでしょうか。 おそらく改訂版に載るのでは?</p><br />
<h3 id="順列リボンの比較">順列リボンの比較</h3><p>TAOCPでは順列生成で数字が移動する様子を折れ線グラフでリボンのように可視化する見せ方をしています。同じようにこのアルゴリズムでの移動を可視化してみました<sup class="footnote-ref"><a href="#fn8" id="fnref8">8</a></sup>。比較用に順列を辞書式順序に並べたリボンもつくってみました。</p><div align="center"><img alt="hamilton path n=4" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZZdnmDh-hoSOxkCxsw8gZOzLQTvzcn-PicG2iwMzCIBOZpZ19c7N83pQjqSjiFfKr3pGxBREbIRCnGXn3NEJXlax0q5aVsobMO_3Po1OrOaWRaA0Yhua3JBvdXOc1NphAHFt7/s1600/69159525-68532480-0b2b-11ea-94b7-bf095d1411aa.png" width="100%" /><br />
<img alt="rec perm n=4" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhcM9_r22zBtZBrsuGlA1_-FApFpn9iy-YfeI-3AUjTmTPgnFYO5KCFQP-tNsB28v9HxtB3ExbKPRsSId-D2E_6qfm8jpZ6g6_-P_Ij1QuWXwLsMyE2sJgk32k5lmDQynfxRZr/s1600/69159544-70ab5f80-0b2b-11ea-9099-8352b3ce85e8.png" width="100%" /> <p>図8 n=4のハミルトン路(上)、辞書式順序の順列(下)</p></div><p>sigmaサイクルをたどっているところは斜めのラインが続いていてストライプ模様になっていてきれいな気がします。<strong>クリスマスの飾り付け</strong>っぽいリボンになりましたね(無理やりなアドベントカレンダー要素)</p><h2 id="まとめ">まとめ</h2><p>順列とsigma/tau操作による群をグラフ化してそこにハミルトン路が存在するということを証明した論文を紹介しました。ハミルトン路の生成ルールは簡潔に書くことが可能で、実装もおこないました。</p><p>Goのライブラリにしたので使ってみてください!</p><p>おわり。</p><br />
<br />
<br />
<hr class="footnotes-sep" /><section class="footnotes"> <ol class="footnotes-list"><li class="footnote-item" id="fn1"><p><a href="https://arxiv.org/abs/1307.2549">Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 … n) and τ = (1 2)</a> <a class="footnote-backref" href="#fnref1">↩︎</a></p></li>
<li class="footnote-item" id="fn2"><p><a href="https://www.researchgate.net/publication/322218107_A_Hamilton_Path_for_the_Sigma-Tau_Problem">A Hamilton Path for the Sigma-Tau Problem</a> <a class="footnote-backref" href="#fnref2">↩︎</a> <a class="footnote-backref" href="#fnref2:1">↩︎</a> <a class="footnote-backref" href="#fnref2:2">↩︎</a> <a class="footnote-backref" href="#fnref2:3">↩︎</a></p></li>
<li class="footnote-item" id="fn3"><p><a href="https://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html">Superpermutations — Greg Egan, The Williams Construction</a> <a class="footnote-backref" href="#fnref3">↩︎</a> <a class="footnote-backref" href="#fnref3:1">↩︎</a></p></li>
<li class="footnote-item" id="fn4"><p><a href="https://amzn.to/2QiO7qB">The Art of Computer Programming Volume 4A Combinatorial Algorithms</a> <a class="footnote-backref" href="#fnref4">↩︎</a> <a class="footnote-backref" href="#fnref4:1">↩︎</a></p></li>
<li class="footnote-item" id="fn5"><p>$n \ge 3$ の奇数の場合、 $(1,2), (2,3), …, (n-2,n-1), (n-1,2)$ と $1,n,2,3,…,n-2,n-1$ を交互サイクルの始点に選ぶとハミルトン閉路になるそうです。 <a class="footnote-backref" href="#fnref5">↩︎</a></p></li>
<li class="footnote-item" id="fn6"><p>同著者の2018年の論文<sup class="footnote-ref"><a href="#fn2" id="fnref2:2">2</a></sup>の最後の一文にRotation systemを使って証明に対して <code>"Our future work is to simplify the proof in [10] using the approach taken in this paper."</code> とあるので今後に期待したい。 <a class="footnote-backref" href="#fnref6">↩︎</a></p></li>
<li class="footnote-item" id="fn7"><p>ハミルトン閉路バージョンのルールのGo実装もつくりました <a href="https://play.golang.org/p/4AXSw0NEYMJ">Go Playground</a> <a class="footnote-backref" href="#fnref7">↩︎</a></p></li>
<li class="footnote-item" id="fn8"><p>n=5のハミルトン閉路のリボンもつくってみた </p><div align="center"><img alt="hamilton cycle n=5" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-yX0eAuDqMT-jCDCbWxNWx3M8WkfW6BoOhICFdM_TAzLo7RI_IE80w8KEr8MhpF8-nsE922q2UMbzEP6K0O-tfMxC5RFs0GTm30fMythRwquHXpyXsBdcMva7chDhG6UXtgiJ/s1600/69158321-96d00000-0b29-11ea-8aef-cf96afea651f.png" width="100%" /></div><a class="footnote-backref" href="#fnref8">↩︎</a><p></p></li>
</ol></section> <span><!--more--></span>deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-5616675586196242072019-06-29T17:55:00.003+09:002020-05-28T18:11:46.952+09:00グレッグ・イーガン経由で知った順列生成アルゴリズム<p>SF作家のグレッグ・イーガンさんは最小超置換文字列の<a href="http://www.supermutations.net/ChaffinMethodResults/" target="_blank">分散探索プロジェクト</a>を主催しています。それ自体も興味深いんですが、<a href="https://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html" target="_blank">解説ページ</a>で紹介されていた副産物の順列を列挙するアルゴリズムが面白かったので紹介&実装してみます。</p><p>(<a href="https://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html#LOCAL" target="_blank">Local Rule</a>のセクションで解説されている内容の紹介です。)</p><p>(追記:順列生成アルゴリズムをライブラリ化しました <a href="https://github.com/deltam/perm">deltam/perm: Permutation generator based on group theory written in Go.</a>)</p><h2 id="順列生成アルゴリズム">順列生成アルゴリズム</h2><p>まず順列の順番を入れ替える写像sigma、deltaを次のように定義します。</p><pre class="code"><code class="plaintext">sigma: (2,3,4,...,n-1,n,1)
delta: (3,4,5,...,n-1,n,2,1)
</code></pre><p>始点の順列を<code>(n-2, n-3, ..., 3, 2, n, 1)</code>として、それに対して次のルールAを繰り返し適用します。</p><p><strong>ルールA</strong><br />
以下の条件をすべて満たすなら現在の順列にdeltaを適用し、そうでないならsigmaを適用する。</p><ol><li>左端の数字がnではない。</li>
<li>順列中のnの右隣の数字をrとする(nが右端なら左から2番めをrとする)。左端の数字をfとし、r が 1+(f-2) mod (n-1) と等しい。</li>
<li>現在の順列が<code>(1, n, n-1, ..., 3, 2)</code>ではない。</li>
</ol><p>(2番めの条件が分かりにくいので具体例を挙げると、順列<code>(3, 1, 2, 4)</code> ならf=3かつr=1で、1+(3-2) mod (4-1) = 1+1 = 2なので r = 1 ≠ 2となります)</p><p>始点からルールAを繰り返し適用した系列は<strong>すべての順列が一回だけ登場する</strong>ものになっています。</p>
<h2 id="実験">実験</h2>
<a name='more'></a>
<p>n=3の順列で実験してみます。まず始点は<code>(2,3,1)</code>です。</p><pre class="code"><code class="plaintext">(2,3,1) : ルールA 1.OK 2.OK 3.OK -> delta
(1,3,2) : ルールA 1.OK 2.OK 3.NG -> sigma
(3,2,1) : ルールA 1.NG -> sigma
(2,1,3) : ルールA 1.OK 2.OK 3.OK -> delta
(3,1,2) : ルールA 1.NG -> sigma
(1,2,3) : 終了
</code></pre><p>全順列が出てきました。<br />
4以上だと手計算が面倒なのでGoで書いてみました。</p><p><a href="https://play.golang.org/p/hjt_iTAJWPo" target="_blank">https://play.golang.org/p/hjt_iTAJWPo</a></p><pre class="code"><code class="shell">$ go run perm_gen.go |head
[3 2 4 1]
[2 4 1 3]
[1 3 4 2]
[3 4 2 1]
[2 1 4 3]
[1 4 3 2]
[4 3 2 1]
[3 2 1 4]
[1 4 2 3]
[4 2 3 1]
$ go run perm_gen.go | wc -l
24
$ go run perm_gen.go |sort|uniq|wc -l
24
</code></pre><p>うまくいってますね。<code>(4,3,2,5,1)</code>から始めると5の全順列120個が出てくるので適当に書き換えて試してみてください。</p><p>イーガン先生が書いたJavaScriptによる実装も<a href="https://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html#LOCAL" target="_blank">解説ページ</a>にリンクがあります(Supermutate.jsというやつ)。ページトップの文字がぐるぐる動いているのはそれで文字の全順列を表示しているみたいです。</p><h2 id="なぜうまくいくのか?">なぜうまくいくのか?</h2><p>グレッグ・イーガン先生は最小超置換の長さの上界を証明するためにAaron Williams氏の論文の結果を使っています。</p><p><a href="https://arxiv.org/abs/1307.2549" target="_blank">[1307.2549] Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 … n) and τ = (1 2)</a></p><p>この論文では順列と2つの写像による群を<a href="https://ja.wikipedia.org/wiki/%E3%82%B1%E3%82%A4%E3%83%AA%E3%83%BC%E3%82%B0%E3%83%A9%E3%83%95" target="_blank">ケイリーグラフ</a>というグラフ構造に変換したものの上に、ハミルトン路を構成しそれが必ず存在するということを証明しています。<br />
<a href="https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E8%B7%AF" target="_blank">ハミルトン路</a>とはグラフのすべての頂点をそれぞれ一回だけ通る経路のことです(終点→始点にならない場合もある)。頂点=順列なのでそのような経路を生成するアルゴリズムは順列生成アルゴリズムになります。上で紹介したアルゴリズムはイーガン先生が論文から少しアレンジしたものです。</p><p>上記の論文ではハミルトン路の存在以外にも次のことが証明されています。</p><ul><li>論文が対象としているケイリーグラフにはちょうど2つのサイクルカバーが存在し、すべての頂点はそのどちらか一方に含まれる</li>
<li>サイクルカバーを生成するアルゴリズムが存在する</li>
</ul><p><a href="https://ja.wikipedia.org/wiki/%E9%96%89%E8%B7%AF%E3%82%B0%E3%83%A9%E3%83%95" target="_blank">サイクルカバー</a>とはグラフ上の各頂点を一回だけ通るループのことです(すべての頂点を巡るものは<a href="https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E8%B7%AF" target="_blank">ハミルトンサイクル</a>と呼ばれる)。この順列生成アルゴリズムはまず片方のサイクルカバーを生成し、始点に戻る直前の頂点でもう一方のサイクルカバーに移動して全頂点をめぐります。<br />
</p><p>サイクルカバーの次の頂点を生成するためのルールがルールAの1.2.です。3.は最初のサイクルカバーの終点を判別し、もう一方のサイクルカバーに移動するためのルールです。</p><p>普通の順列生成なら<code>(1,2,3)</code>から始めたいところですが、サイクルの終点を明確にするために<code>(2,3,1)</code>から始めてるんですね。ルールAを調整すれば<code>(1,2,3)</code>を始点に出来るかもしれないですが、出力するときに変換をかますほうが楽かも。</p><p>ケイリーグラフ上のハミルトン路の存在証明は上記の論文が初めてではないようですが、すでに知られているものよりかなりシンプルになったそうです。Goで書いたものも70行ほどなので素晴らしいですね。<br />
(追記:今まで知られていたのは逆方向の移動を許すものや全数探索で見つけたもので、すべての n について構成法はこれが初めてのようです)</p><h2 id="最小超置換との関わり">最小超置換との関わり</h2><p>元論文ではdeltaは先頭二文字を入れ替える<code>(2,1,3,4,...,n-1,n)</code>写像になっています。イーガン先生がさらに二文字を後ろに持っていくようにしたのは超置換文字列を作るためです。<br />
<a href="https://ja.wikipedia.org/wiki/%E8%B6%85%E7%BD%AE%E6%8F%9B" target="_blank">超置換</a>はnの順列がすべて部分列として含まれる文字列のことです。sigma、deltaで順列を変換すると前の順列と先頭n-1、n-2文字が共通になります。変換するごとに1,2文字を追加していけばそれは超置換文字列になります。</p><p>上記のGoプログラムのmainをこんなふうに書き換えれば超置換を出力します。</p><pre class="code"><code class="go">func main() {
p := []int{2, 3, 1}
for i := 0; i < len(p); i++ {
fmt.Print(p[i])
}
add := 0
for i := 0; i < 6-1; i++ {
if ruleCheck(p) {
delta(p)
add = 1
} else {
sigma(p)
add = 2
}
for i := len(p) - add - 1; i < len(p); i++ {
fmt.Print(p[i])
}
}
}
// Output: 2313232121312123
</code></pre><p>この方法で作った超置換は部分列に重複が多く、残念ながら最小にはなりません。n=3の最小超置換は<code>123121321</code>です。<br />
ただしこれによって数学的に証明された超置換を生成するアルゴリズムを作ることができて、超置換の長さの上界を示すことができます。</p><p>最小超置換問題の全体的な説明はこちらの記事が参考になります。イーガン先生の貢献も解説されています。<br />
<a href="https://qiita.com/kgoto/items/884b04b636de90136014" target="_blank">ハルヒ問題(最小超置換問題)の紹介 - Qiita</a></p><h2 id="(おまけ)イーガン先生による最小超置換の分散探索プロジェクト紹介">(おまけ)イーガン先生による最小超置換の分散探索プロジェクト紹介</h2><p><a href="http://www.supermutations.net/ChaffinMethodResults/" target="_blank">Distributed Chaffin Method Results</a></p><p>いまアマチュア数学者業界で最小超置換が熱い! 単純な予想を覆す複雑さを持ち、なんか新発見できるんではという希望があります。<br />
イーガン先生は現在n=6の超置換を全探索してすでに知られたものが本当に最小か追試しています。</p><p>最小超置換の探索アルゴリズムの<a href="https://github.com/superpermutators/superperm/wiki/Chaffin-method" target="_blank">Chaffin Method</a>(これも考え方が興味深いので解説書きたい)を複数台のコンピュータで実行できるようにしたのがDistributed Chaffin Methodです。サーバもクライアントもイーガン先生が書いてます。</p><p><a href="https://github.com/superpermutators/superperm/tree/master/DistributedChaffinMethod" target="_blank">superperm/DistributedChaffinMethod at master · superpermutators/superperm</a></p><p>クライアントはCとJavaのものがあります。チーム名を決めて実行するとプロジェクトページに実績が載るので誘い合わせて参加するといいかも(私はぼっちチームですが…)。</p><p>現在のところ最小超置換を見つけることの実用的意味はまったくありませんが、すこしでも面白そうと思ったならクライアントを動かしてみませんか?</p><p>イーガン先生の熱情がどこから来るのか不明ですが、このような著作があるのと関係あるのかもしれません。(もしくは短編『<a href="https://amzn.to/2RIL6OY">ルミナス</a>』のように数論の<不備>を発見しようとしているのかも?)</p><iframe frameborder="0" marginheight="0" marginwidth="0" scrolling="no" src="//rcm-fe.amazon-adsystem.com/e/cm?lt1=_blank&bc1=000000&IS2=1&bg1=FFFFFF&fc1=000000&lc1=0000FF&t=deltam-22&language=ja_JP&o=9&p=8&l=as4&m=amazon&f=ifr&ref=as_ss_li_til&asins=B00RKN4876&linkId=f16346b9a1ccfff58c2ba148caf0db9c" style="height: 240px; width: 120px;"></iframe><br />
<iframe frameborder="0" marginheight="0" marginwidth="0" scrolling="no" src="//rcm-fe.amazon-adsystem.com/e/cm?lt1=_blank&bc1=000000&IS2=1&bg1=FFFFFF&fc1=000000&lc1=0000FF&t=deltam-22&language=ja_JP&o=9&p=8&l=as4&m=amazon&f=ifr&ref=as_ss_li_til&asins=B00RKN4880&linkId=3f72580f38df2b394874267ee49f9506" style="height: 240px; width: 120px;"></iframe><br />
<br />
<h2 id="コード全体">コード全体</h2><pre class="code"><code class="go">// permutation generator
// author @deltam
package main
import "fmt"
func main() {
p := []int{3, 2, 4, 1}
for i := 0; i < 24; i++ {
fmt.Println(p)
if ruleCheck(p) {
delta(p)
} else {
sigma(p)
}
}
}
// 2 3 4 ... n-1 n 1
func sigma(p []int) {
n := len(p)
f := p[0]
copy(p[0:n-1], p[1:n])
p[n-1] = f
}
// 3 4 5 ... n-1 n 2 1
func delta(p []int) {
n := len(p)
f0 := p[0]
f1 := p[1]
copy(p[0:n-2], p[2:n])
p[n-2] = f1
p[n-1] = f0
}
func ruleCheck(p []int) bool {
n := len(p)
// 1.
if p[0] == n {
return false
}
pos := 0
for i := 0; i < n; i++ {
if p[i] == n {
pos = i
break
}
}
pos++
if pos == n {
pos = 1
}
// 2.
if p[pos] != 1+(p[0]-2+n-1)%(n-1) {
return false
}
// 3.
for i := 0; i < n; i++ {
if p[(i+1)%n] != n-i {
return true
}
}
return false
}
</code></pre><p>おわり。</p><br />
<p>(訂正 2019-06-30:ハミルトンサイクルとサイクルカバーの用語の意味を取り違えてたので修正)</p>deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-83632444044882765642018-10-10T18:18:00.003+09:002021-12-07T15:03:33.604+09:00カスタマイズしやすい重み付きレーベンシュタイン距離ライブラリをGoで書きました<a href="https://github.com/deltam/go-lsd-parametrized">deltam/go-lsd-parametrized: Weighted Leveshtein Distance and its extended interfaces written in Go.</a><br />
<br />
重み付き<a href="https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2">レーベンシュタイン距離(編集距離)</a>のライブラリを書きました。文字ごとに追加・削除・置換のコストが指定できます。文字列の長さによる正規化や複数の文字列から近いものを選ぶ関数も含まれてます。<br />
<br />
エラーメッセージをラフに分類したいという動機から作り始めました。類型的で機械学習が必須なわけでない分類タスクにお役立てください。<br />
詳しい使い方はGitHubの<a href="https://github.com/deltam/go-lsd-parametrized/blob/master/README.md">README</a>を見てください。<br />
<br />
<pre class="code"><code>go get -u github.com/deltam/go-lsd-parametrized</code></pre><br />
<h1 id="カスタマイズ">カスタマイズ</h1><br />
<a name='more'></a>
重みの調整でだいたいの用途は足りるかなーと思います。編集方法ごとに重みを付ける場合は<a href="https://godoc.org/github.com/deltam/go-lsd-parametrized#Weights">lsdp.Weights</a>構造体、さらに文字ごとに重みを付けたい場合は<a href="https://godoc.org/github.com/deltam/go-lsd-parametrized#ByRune">lsdp.ByRune()</a>を使います。<br />
<br />
<pre class="code"><code class="go"> // weighted
wd := lsdp.Weights{Insert: 0.1, Delete: 1, Replace: 0.01}
fmt.Println(wd.Distance(a, b))
// Output:
// 0.22
// weighted by rune
wr := lsdp.ByRune(&lsdp.Weights{1, 1, 1}).
Insert("g", 0.1).
Insert("h", 0.01).
Replace("k", "s", 0.001).
Replace("e", "i", 0.0001)
fmt.Println(wr.Distance(a, b))
// Output:
// 0.1111
</code></pre><br />
調整するときに分類精度を評価するのが面倒なので<a href="https://godoc.org/github.com/deltam/go-lsd-parametrized/tools#Evaluate">tools.Evaluate()</a>というのも作りました。<a href="https://godoc.org/github.com/deltam/go-lsd-parametrized/tools#EvaluateByCSV">tools.EvaluateCSV()</a>ならCSVでテストデータを用意できるので便利。<br />
<br />
もっと細かく調整したい場合は<a href="https://godoc.org/github.com/deltam/go-lsd-parametrized#DistanceMeasurer">lsdp.DistanceMeasurer</a> インターフェイスを実装する必要があります。<br />
ただロジック的な変更のみでパラメータが無い場合はいちいち構造体を定義するのも面倒なので、こちらの記事を参考に直接関数で指定できるようにしてみました。<br />
<br />
<a href="https://qiita.com/ruiu/items/85b72bc94e08d192d90b">Goのメソッドは構造体以外にでも定義できるしそれが便利なこともよくある - Qiita</a><br />
<br />
<pre class="code"><code class="go">// 長さの差を距離とする
func lenDiff(a, b string) float64 {
d := utf8.RuneCountInString(a) - utf8.RuneCountInString(b)
return math.Abs(float64(d))
}
func main() {
var d lsdp.DistanceFunc = lenDiff
fmt.Println(d.Distance("kitten", "shitting"))
// Output:
// 2
group := []string{"", "a", "ab", "abc"}
s, dist := lsdp.Nearest(d, "xx", group)
fmt.Println(s, dist)
// Output:
// ab 0
}
</code></pre><br />
<br />
<h1 id="goで書いた感想">Goで書いた感想</h1><br />
Goでライブラリを書く経験はそれほどなかったのでいろいろ勉強になりました。<br />
<br />
<h2 id="interfaceの使い方">interfaceの使い方</h2><br />
<a href="https://golang.org/doc/effective_go.html">Effective Go</a>でこんな一節があったので<a href="https://godoc.org/github.com/deltam/go-lsd-parametrized#Normalized">Normalized()</a>の実装で実践してみました。<br />
<br />
<blockquote>Generality<br />
If a type exists only to implement an interface and will never have exported methods beyond that interface, there is no need to export the type itself.<br />
<br />
<a href="https://golang.org/doc/effective_go.html#generality">Effective Go - The Go Programming Language</a></blockquote><br />
構造体を作ってInterfaceとして返すようにしておけば実装の詳細を隠せるのであとで変更しやすいです。Go moduleだと後方互換性が大事なのでこうしておくとのちのち楽です。<br />
<br />
<h2 id="ベンチマークテストたのしい">ベンチマークテストたのしい</h2><br />
Goの標準ライブラリのコミットログを見てるとベンチマークテストの結果が貼り付けられたものがあります(例:<a href="https://github.com/golang/go/commit/23093f86eebbefb0cf11298c45513da360d2b48d">string</a>)。効果が分かりやすいし、なんかかっこいいので真似することにしました。<br />
<br />
<a href="https://mattn.kaoriya.net/software/lang/go/20161019124907.html">Big Sky :: golang でパフォーマンスチューニングする際に気を付けるべきこと</a><br />
<br />
単純な比較なら<a href="https://godoc.org/golang.org/x/tools/cmd/benchcmp">benchcmp</a>というのもあります。入力をランダム生成して複数回試行するようなベンチマークなら<a href="https://godoc.org/golang.org/x/perf/cmd/benchstat">benchstat</a>のほうが良さそう。<br />
<br />
<br />
<h1 id="アルゴリズム的なやつ">アルゴリズム的なやつ</h1><br />
<h2 id="コスト計算を工夫してメモリ削減">コスト計算を工夫してメモリ削減</h2><br />
レーベンシュタイン距離のアルゴリズム(<a href="https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm">解説</a>)では文字列1、2の先頭からの部分列に対して段階的にコストを計算する方法を使います。空行から文字列全体なので文字列1,2がそれぞれN文字、M文字ならば N+1行 M+1列の表を作ります。<br />
<br />
詳しい説明は省きますが、現在の行を計算するのに必要なのは一つ前の行の値だけなので実際に必要な記憶領域は(N+1)*2だけです。レーベンシュタイン距離の実装を見てみるとN+1の配列2つを互い違いに使うことで表の代用をする方法が多いです。<br />
<br />
ベンチマークテストを追加した影響でもっと効率化できないか考えるようになりメモリ削減のアイデアを思いつきました。表のあるコスト(i, j)の計算に必要なコストは左(i-1, j)、左上(i-1, j-1)、上(i, j-1)の3つだけです。コスト(i, j)の計算が終わったら次は(i+1, j)に移るので、実は左上(i-1, j-1)の値はもう参照しません。だったら左(i-1, j)の値で上書きしちゃえばいいのでは?というが思いついたアイデア。これによって記憶領域はN+2で済みます。<br />
<br />
たぶん既出アイデアだと思うけどそこそこ高速化できたので気分がいい。<br />
<br />
<a href="https://github.com/deltam/go-lsd-parametrized/commit/61be4fe4677600d5c0d6acb0a0d057fc8ffa0af9">Performance improvement for accumulateCost() · deltam/go-lsd-parametrized@61be4fe</a><br />
<br />
ベンチマークテスト万歳!<br />
<br />
<h2 id="重み付き〜の定義">重み付き〜の定義</h2><br />
最初かんぜんに勘違いしてた、はずかしい…<br />
<br />
<a href="https://ja.stackoverflow.com/questions/44583/%e9%87%8d%e3%81%bf%e4%bb%98%e3%81%8d%e3%83%ac%e3%83%bc%e3%83%99%e3%83%b3%e3%82%b7%e3%83%a5%e3%82%bf%e3%82%a4%e3%83%b3%e8%b7%9d%e9%9b%a2%e3%81%ae%e5%ae%9a%e7%be%a9%e3%81%ab%e3%81%a4%e3%81%84%e3%81%a6">アルゴリズム - 重み付きレーベンシュタイン距離の定義について - スタック・オーバーフロー</a><br />
<br />
勘違いの副産物で削除・挿入・置換ごとの最短回数を集計する関数ができました(通常のレーベンシュタイン距離はコストは全部合計するため編集種別ごとの回数は分からない)。<br />
<a href="https://godoc.org/github.com/deltam/go-lsd-parametrized#CountEdit">lsdp.CountEdit()</a><br />
<br />
<br />
<br />
<br />
<br />
なんかあったらissue、PullReq投げてくださいー。<br />
<br />
おわり。deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-22877130911127532542018-03-13T15:19:00.004+09:002024-01-23T12:26:25.961+09:00FitDesk X-2.0を修理した<a href="http://amzn.to/2DhYwZH" target="_blank">FitDesk X-2.0</a>というエアロバイクを愛用してます。<br />
<br />
<br />
デスクが付いているので運動しながら読書をしたりPC作業をしたり便利です。<br />
もう2年以上ほぼ毎日使っているのですが、すこし前からペダリングに違和感を覚えるようになりました。音がうるさくなりペダル回転も引っかかるような感触がします。<br />
<br />
エアロバイクの故障について調べてみたら故障の原因はだいたいが<b>ベルトかベアリングの破損</b>のようです。私のFitDeskの保証期間はすでに切れていたので何とか自分で修理できないか試すことにしました(安くない買い物だったし)。<br />
<br />
検索してみると<a href="https://www.youtube.com/user/fitdeskbikedesk/" target="_blank">FitDesk製造元のYoutubeチャンネル</a>にギアボックスを分解するための手順の解説動画があります。<br />
<br />
<a name='more'></a>
<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/ghLWx1353dA" width="560"></iframe><br />
<br />
<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/zuSHE30KiTY" width="560"></iframe><br />
<br />
<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/ebu73qds5_A" width="560"></iframe><br />
<br />
<br />
どうやらクランクを外さないとギアボックスは開けない、クランクを外すには自転車の専用工具がいるらしい。<br />
しょうがないので必要な工具を用意しました。<br />
<br />
<br />
<h2>
修理に必要な工具リスト</h2>
<ul>
<li>クランク抜き工具</li>
<ul>
<li>この商品はFitDeskのクランクに合いました(共通規格なのかな?)</li>
<li><a href="https://amzn.to/42b1tIH" target="_blank">Amazon | SUPER B(スーパービー) コッタレスクランク 抜き 6610 | スーパービー(SUPER B) | 工具(単品)</a>
</li>
</ul>
<li>ゴム製ハンマー</li>
<ul>
<li><a href="https://www.amazon.co.jp/dp/B00GRS30GA" target="_blank">Amazon | 大五郎 ゴムハンマー 1P | ゴムハンマー</a>
</li>
</ul>
<li>ソケットレンチ</li>
<ul>
<li>クランク抜きに必要なのはサイズ13のみ</li>
<li>固く締まっていたので力が込めても痛くなさそうな柄のやつがいいです</li>
<li><a href="https://amzn.to/3S9Fe19" target="_blank">Amazon.co.jp: WORKPRO ソケットレンチセット W003024A 差込角:12.7mm 12点 1セット : DIY・工具・ガーデン</a>
</li>
</ul>
<li>モンキーレンチ</li>
<ul>
<li>ペダルも外すのに力がいるので柄が長いほうがいいです</li>
<li><a href="https://amzn.to/3HuqLrx" target="_blank">Amazon | ケンオー(KENOH) モンキーレンチ 300mm 24043 | モンキーレンチ</a>
</li>
</ul>
<li>プラスドライバー</li>
<ul>
<li>カバーを外すのに必要</li>
<li><a href="https://amzn.to/3ScPc1s" target="_blank">Amazon | サンフラッグ テクニカルドライバー No.5800 本体 +1/+2 | ドライバー</a>
</li>
</ul>
</ul>
<div>
<br />
<br />
<br /></div>
<h2>
ギアボックスを開く</h2>
<div>
<br />
クランクを外す→前の接地部を外す→カバーを外すの手順でいきます(バランスが悪いのでカバーを外した後に接地部を戻して軽く固定してます)。</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwrGmc9ME-9YhSySSCuKXBwszbUyZK028GrQC6DuV7r5Ki7AxsxHKs4zEd1FQ4D_nloCMg4oRqir9Kl5CKqCz8tqI_Xi6d_IasvxPJql4xNaoe4YBQqIZ7kETXrverbLPt3dQo/s1600/gearbox1.jpg" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1200" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwrGmc9ME-9YhSySSCuKXBwszbUyZK028GrQC6DuV7r5Ki7AxsxHKs4zEd1FQ4D_nloCMg4oRqir9Kl5CKqCz8tqI_Xi6d_IasvxPJql4xNaoe4YBQqIZ7kETXrverbLPt3dQo/s320/gearbox1.jpg" width="240" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2LBpAMfWJhs-QHYHp4i1tA3jKkEWHyVJAQib3x5Sn1BAPIGMxBn2B6JSjurBSN6cTjj1hlw-Grh4v-DkYa_5e-877maxcYvBdJ8q8MXazw9CI32QMiwEYeQ1TsmJQf2rNtunt/s1600/gearbox2.jpg" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1200" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2LBpAMfWJhs-QHYHp4i1tA3jKkEWHyVJAQib3x5Sn1BAPIGMxBn2B6JSjurBSN6cTjj1hlw-Grh4v-DkYa_5e-877maxcYvBdJ8q8MXazw9CI32QMiwEYeQ1TsmJQf2rNtunt/s320/gearbox2.jpg" width="240" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
ギアボックスを開くと中に黒い金属の玉が落ちてました。ベアリングが壊れて中のボールが落ちてきたみたいです。</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjF2ZjJJ2tFo3w2UrFqTgohZvdNJ_u9L0PLdr6ggthyphenhyphendHUwtiY9Z5Smw6qpocGdzxtMP491v-9GObg013EUG56pXZPSwLYOLuRaPWxPm-1yrRztOW6rlIZt9zs9fSd00EESfc8x/s1600/bearing_ball.jpg" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="915" data-original-width="1600" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjF2ZjJJ2tFo3w2UrFqTgohZvdNJ_u9L0PLdr6ggthyphenhyphendHUwtiY9Z5Smw6qpocGdzxtMP491v-9GObg013EUG56pXZPSwLYOLuRaPWxPm-1yrRztOW6rlIZt9zs9fSd00EESfc8x/s320/bearing_ball.jpg" width="320" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
実際ギアボックスも分解してホイールやベルトを取り出してみると、ベルトを裏から抑えているベアリングがこんなふうに壊れてました。</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihzrV48TNUs22S6ULfhNsmAbZHoLsVHa53FL65-IkHahmlzaw_u7vI6pTCtuU-7h98LyDXxfKGY6BRT6MRVm_ubX-NX8455pyNBqgPZSL2HVxSUFvcUGH3ACqVLhnNwejb_UrH/s1600/break_bearing.jpg" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1002" data-original-width="1600" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihzrV48TNUs22S6ULfhNsmAbZHoLsVHa53FL65-IkHahmlzaw_u7vI6pTCtuU-7h98LyDXxfKGY6BRT6MRVm_ubX-NX8455pyNBqgPZSL2HVxSUFvcUGH3ACqVLhnNwejb_UrH/s320/break_bearing.jpg" width="320" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
他の部分に異常はなさそうなのでこのベアリングを交換すればOKだと判断しました。</div>
<div>
<br /></div>
<div>
<br />
<br /></div>
<h2>
ベアリングを交換して修理完了</h2>
<div>
<div>
<br /></div>
<div>
保証期間過ぎてるけどダメ元で販売代理店の<a href="http://www.pod-e.com/" target="_blank">株式会社POD</a>に連絡してみると送料のみで譲っていただけることに。感謝です!</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJFVLD2BkxnF6vHl02971g131wxvp9PR-MGrQGxjOwAm4GRgut1-vxadGAs8lE2AHDaOQQ5U-mREaFuWia8bdyq7Xll9IqUVzC_nYC3g4-t-5SAdrev22Mw-cuJj9yXYpx3fvr/s1600/new_bearing.JPG" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJFVLD2BkxnF6vHl02971g131wxvp9PR-MGrQGxjOwAm4GRgut1-vxadGAs8lE2AHDaOQQ5U-mREaFuWia8bdyq7Xll9IqUVzC_nYC3g4-t-5SAdrev22Mw-cuJj9yXYpx3fvr/s320/new_bearing.JPG" width="320" /></a></div>
<div>
<br /></div>
<div>
さっそく交換して元通りになりました。</div>
<div>
<br /></div>
<div>
<br /></div>
<h3>
自前でベアリングを用意して交換する場合</h3>
<div>
<br /></div>
<div>
ベアリングは消耗品らしいので今度また壊れたらこんなふうに直そうと思ってます。</div>
<ul>
<li>サイズを調べて同じベアリングを購入して差し替える</li>
<ul>
<li>マニュアルの部品リストには「<b>Bearing 6200ZZ</b>」と書いてあるのでこれで大丈夫そう</li>
<ul>
<li><a href="https://amzn.to/3S6jWRX" target="_blank">Amazon.co.jp: イースタン ウレタンベアリングBタイプ 硬度90 U104090 : DIY・工具・ガーデン</a>
</li>
</ul>
<li>ボルトにローラーベアリングがくっついた構造なので取り外すのにまた専用工具がいる……</li>
<ul>
<li><a href="https://amzn.to/4964dt8" target="_blank">Amazon | HFS(R) ワイパーアームプーラー 6-28mm バッテリーリムーバー 車用 ボルト脱着 分解用ツール | ワイパー用ツール | 車&バイク</a>
</li>
</ul>
</ul>
</ul>
<div>
<br /></div>
</div>
<div>
<br /></div>
<h2>
故障を予防するために</h2>
<div>
<br /></div>
<div>
マニュアルには「<b>30分毎に20分の休憩を</b>」と書いてありますが、健康上の理由だけでなくベアリングやベルトが熱を持ちすぎないようにとの理由があるそうです。ダイエットのためとしても連続で漕ぎ続けるのは膝にもエアロバイクにも良くないみたいですね。</div>
<div>
<br />
<br />
<br />
<br />
<h2>
【参考リンク】</h2>
<a href="http://orangain.hatenablog.com/entry/2015/02/24/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%97%E3%81%AA%E3%81%8C%E3%82%89%E9%81%8B%E5%8B%95%E3%81%A7%E3%81%8D%E3%82%8B%E3%82%A8%E3%82%A2%E3%83%AD%E3%83%90%E3%82%A4%E3%82%AF_Fi" target="_blank">プログラミングしながら運動できるエアロバイク FitDesk X-2.0を買った - orangain flavor</a><br />
私が購入したきっかけはこの記事。しかし振動があるので入力作業はあまりしてません。難しいドキュメントやソースコードを読むときなどは眠くならなくて超捗る。</div>
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com9tag:blogger.com,1999:blog-9245921.post-63149148187080653372015-08-27T21:21:00.001+09:002020-05-28T18:14:10.504+09:00SICP問題1.45の回答と説明(SICP1.3.4, ex1.45)<b>この記事の対象読者:『計算機プログラムの構造と解釈』を読んだことがあって、問題1.45に納得がいってないひと</b><br />
<br />
<br />
<br />
<a href="http://sicp.iijlab.net/fulltext/x134.html#ex145">1.3.4 値として返される手続き (計算機プログラムの構造と解釈 第二版)</a><br />
<br />
SICPの読んでたときにけっこう苦労した練習問題。<br />
n乗根を求めるための平均緩和法の適用回数を「実験して確かめよ」って書いてあるけど、たぶん実験だけでは分からない。回答自体はカンニング(検索)して見つけたけど、なぜそうなのかをちゃんと説明しているのを見つけられなかったので、この記事で説明してみる。<br />
<br />
<br />
<h2>平均緩和法、不動点探索の復習</h2><br />
回答のまえに平均緩和法や不動点探索についておさらいしておきます。<br />
<a name='more'></a>
<br />
不動点探索(fixed-point)ではx=f(x)となる点をみつけます。y=f(x)を計算してさらにf(y)を計算して、というのを繰り返す。図解すると次の赤線のような軌道を描きます。<br />
<div><br />
</div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicRXp5VZGTI6zB7pP12G4JfO94lcN78jeOK1fIUQewRCI8azvYhJUWo9dQFRXschmrgQsgtl44emrgl6TPRkvBHPl0UQ69FiY1CTz0RukoLRS3gX-JcTL3iedeNentythjkI2q/s1600/01_fixed-point-process.jpg"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicRXp5VZGTI6zB7pP12G4JfO94lcN78jeOK1fIUQewRCI8azvYhJUWo9dQFRXschmrgQsgtl44emrgl6TPRkvBHPl0UQ69FiY1CTz0RukoLRS3gX-JcTL3iedeNentythjkI2q/s320/01_fixed-point-process.jpg" /></a><br />
<br />
ところがこの方法では上手くいかない場合がある。次のようにy=xを軸として対称な曲線だと同じ軌道をグルグルしてしまい不動点に行き着かない。<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZzfnfBmHchsZadJAW7NoFeL1nshB2CSplp8GVU6ogG_KJkEB2D_IdF1foau9uKv7QO4KYiy0nwtg9TaQuslnOsvq0AyXWLF0-2nzTjYkVSyaWsuklG8MpP_-DA_EDUIPIG01z/s1600/02_root-fixed-point.jpg"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZzfnfBmHchsZadJAW7NoFeL1nshB2CSplp8GVU6ogG_KJkEB2D_IdF1foau9uKv7QO4KYiy0nwtg9TaQuslnOsvq0AyXWLF0-2nzTjYkVSyaWsuklG8MpP_-DA_EDUIPIG01z/s320/02_root-fixed-point.jpg" /></a><br />
<br />
このようなときに平均緩和法を適用するといい具合に非対称に歪めてくれる。この変形のおかげで不動点探索がうまくいくようになります。<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiOpMgKr9s7JoYN4AxLXz3pSaUC6oxqyvU9QR1Tx14pr5gP8VOw_tVonlbMXp5Irr57pLVVr6591jnZkXtN-iVe0GNYBhqNnFP3vJHj3tM5Exk-Yty_wu6e7O-iyXF208fL9EI8/s1600/03_root-average-damp-diff.jpg"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiOpMgKr9s7JoYN4AxLXz3pSaUC6oxqyvU9QR1Tx14pr5gP8VOw_tVonlbMXp5Irr57pLVVr6591jnZkXtN-iVe0GNYBhqNnFP3vJHj3tM5Exk-Yty_wu6e7O-iyXF208fL9EI8/s320/03_root-average-damp-diff.jpg" /></a><br />
<br />
<br />
<br />
<h2>四乗根を平均緩和法で求める</h2><br />
<blockquote>平均緩和の不動点として立方根を見つけることが出来る. 困ったことに, この方法は四乗根には使えない. </blockquote><br />
問題文にはこう書いてあるけど、実際やってみると<b>四乗根を見つけることはできます</b>。見つけられないのは(上で説明したとおり)y=xの軸に対称な場合ですが、平均緩和法を適用すれば非対称になるはずなので見つけられるということです。<br />
でもこれをコーディングして実行すると三乗根に比べてだいぶ遅いです。<br />
<br />
<pre class="code">;;; 安全に計算の動きをおうため、計算回数の上限を指定できるように改造した
(define (fixed-point-limited f first-guess limit)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess count)
(let ((next (f guess)))
;; 計算過程を表示する
(display count) (display ": ") (display next) (newline)
(if (or (= count limit) (close-enough? guess next))
(list count next) ; 計算回数も一緒に返す
(try next (+ count 1)))))
(try first-guess 1))
;;; 平均緩和法1回での4乗根計算手続き
(define (root4-ad1 x limit)
(fixed-point-limited
(average-damp (lambda (y) (/ x
(* y y y))))
1.0
limit))
(root4-ad1 16 10)
; (10 1.8597959434977196)
(root4-ad1 16 100)
; (100 1.9364452032204889)
(root4-ad1 16 1000)
; (1000 1.9781656271972445)
;(time (root4-ad1 81 0))
; real 176.408
; user 175.530
; sys 0.380
; (449999982 3.000050001249936)
</pre><br />
81の四乗根を求めるのに4億回も計算して176秒も掛かっている。<br />
<br />
<br />
<br />
<h2>なぜ四乗根の計算は遅い?</h2><br />
四乗根の不動点探索の様子を見てみましょう。平均緩和法を一回適用したグラフはこのようになります。その上での不動点を求める軌道はこのように螺旋を描きます。<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBKKa2fe1v_t0YoiXtNfROPdE3aFWPYGlDhZMCKbFxc7CXXFC94mmXA4uaiRG5i7MH6u0kHI5lG98I5yL1zFjPtFTwNTSgdaqpOYQmAJyL7pT5iw_YsUFN47vrlaoLMoKLgx2b/s1600/root4-average-damp-1-arrow.jpeg"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBKKa2fe1v_t0YoiXtNfROPdE3aFWPYGlDhZMCKbFxc7CXXFC94mmXA4uaiRG5i7MH6u0kHI5lG98I5yL1zFjPtFTwNTSgdaqpOYQmAJyL7pT5iw_YsUFN47vrlaoLMoKLgx2b/s320/root4-average-damp-1-arrow.jpeg" /></a><br />
<br />
比べて、平均緩和法を2回適用した場合は、このようにまっすぐに不動点に向かう軌道になります。<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhi3ulbOT58UHXYm6an9GR5HL9-Wfk2P-EO2xCoCtiBEr-0GPB0CsTxoT0BHfbU_T51RPZ6704z1LRzxXQW7nYIvSGlgCsT-Vk2IcRKnxYo-lJvdAASSUh4zSKQtS9i5sbIk7do/s1600/root4-average-damp-2-arrow.jpeg"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhi3ulbOT58UHXYm6an9GR5HL9-Wfk2P-EO2xCoCtiBEr-0GPB0CsTxoT0BHfbU_T51RPZ6704z1LRzxXQW7nYIvSGlgCsT-Vk2IcRKnxYo-lJvdAASSUh4zSKQtS9i5sbIk7do/s320/root4-average-damp-2-arrow.jpeg" /></a><br />
<br />
直感的に上より下のほうが早く不動点に行き着きそうですよね。<br />
<br />
<br />
<h2>不動点探索に向いた曲線とその求め方</h2><br />
不動点探索に向いた曲線、早く探索が収束するための曲線ってどんなのでしょう。上のふたつのグラフを比較してみると、<b>グラフの最下点の位置</b>が重要そうに思えます。<br />
最下点が不動点の位置より<b>右</b>だと、探索軌道が螺旋を描いてしまう。最下点が不動点より<b>左</b>だとまっすぐな探索軌道を描く。<br />
最下点と不動点のx軸上の位置関係が、<b>最下点<=不動点</b>となっていると良さそうです。<br />
<br />
<br />
ということで平均緩和法を複数回適用した場合に、その最下点がどうなるか調べてみれば良さそうですね。<br />
調べやすくするために平均緩和法を適用した数式を変形してみます。<br />
<br />
・準備<br />
定数mのn乗根を求めるための不動点探索用関数を以下のように定義する。<br />
\[g_{n}(x)=\frac{m}{x^{n-1}}\]<br />
<br />
$g_{n}(x)$に平均緩和法をk回適用した関数をつぎのように定義する<br />
\[<br />
\begin{eqnarray}<br />
f_{n,k}(x) & = & \frac{1}{2} (x+ \frac{1}{2} (x+\ldots \frac{1}{2} (x+ g_n(x) )\ldots)) \nonumber \\<br />
& = & \frac{1}{2} (x+\frac{1}{2} (x+ \ldots \frac{1}{2} (x+ \frac{m}{x^{n-1}} ) \ldots )) \nonumber \\<br />
& = & (\frac{1}{2} + \frac{1}{2^2}+ \frac{1}{2^3}+ \ldots + \frac{1}{2^k})x + \frac{1}{2^k} \frac{m}{x^{n-1}} \nonumber \\<br />
& = & \frac{2^k-1}{2^k}x + \frac{1}{2^k} \frac{m}{x^{n-1}} \nonumber \\<br />
& = & \frac{1}{2^k}((2^k-1)x+ \frac{m}{x^{n-1}})<br />
\end{eqnarray}<br />
\]<br />
<br />
$f_{n,k}$の最下点を調べたい。そのため式(1)を微分して0になる点を調べる。<br />
\[<br />
Df_{n,k}(x)= \frac{1}{2^k}(2^k-1+(1-n) \frac{m}{x^n})<br />
\]<br />
\[<br />
\begin{eqnarray}<br />
Df_{n,k}(x) & = & 0 \nonumber \\<br />
\frac{1}{2^k}(2^k-1+(1-n) \frac{m}{x^n}) & = & 0 \nonumber \\<br />
2^k-1+(1-n) \frac{m}{x^n} & = & 0 \nonumber \\<br />
\frac{m}{x^n} & = & \frac{1-2^k}{1-n}<br />
\end{eqnarray}<br />
\]<br />
<br />
さて$f_{n,k}$の不動点は$\sqrt[n]{m}$である。不動点にあるとき式(2)の左辺は1になる。<br />
\[<br />
\begin{eqnarray}<br />
1 & = & \frac{1-2^k}{1-n} \nonumber \\<br />
1-n & = & 1-2^k \nonumber \\<br />
n & = & 2^k \nonumber \\<br />
\log_2 n & = & \log_2 2^k \nonumber \\<br />
& = & k \log_2 2 = k \nonumber \\<br />
\log_2 n & = & k<br />
\end{eqnarray}<br />
\]<br />
<br />
<br />
<h2>回答</h2><br />
ようやく求める平均緩和回数がわかりそうだ。式(3)の k は整数にしないと回数にならないので、左辺を切り上げるか切り捨てるかしないといけない。<br />
<br />
<ul><li>切り上げ:式(2)の右辺は1より大きくなる。左辺のxは不動点より小さい値でなくてはならない</li>
<li>切り捨て:式(2)の右辺は1より小さくなる。左辺のxは不動点より大きい値でなくてはならない</li>
</ul><br />
不動点と最下点xの位置関係は「最下点x<=不動点」が良いってことはグラフを描いて分かってました。なので式(3)は切り上げのほうが良さそうです。<br />
まとめると平均緩和法の適用回数kはつぎの式になります。<br />
<br />
\[ k= \lceil \log_{2}{n} \rceil \]<br />
<br />
<br />
<br />
<pre class="code">;;; n乗根を探す手続き
(define (root-n x n)
(fixed-point
((repeated average-damp
;; 回数:2を底とするlog nの小数点以下切上げ
(ceiling (/ (log n) (log 2))))
(lambda (y) (/ x
(expt y (- n 1))))) ; exptはべき乗
1.0))
;; test
(root-n 2 2)
; 1.4142135623746899
(root-n 27 3)
; 3.0000234260125787
(root-n 256 8)
; 2.0000000000039666
(root-n 65536 16)
; 2.000000000076957
</pre><br />
<h3>参考リンク</h3><br />
切り捨てが多いけど理由説明は特にないんですよね。上のグラフの議論から切り上げのほうが良いと私は考えてます。<br />
<br />
<ul><li><a href="http://science.kinokoru.jp/sicp-1-3-4-exercise-1-40-1-46-memo/">[SICP 1.3.4] Exercise 1.40-1.46 Memo | Nisei Kimura's Blog</a></li>
<ul><li>この回答だと$\log_{2}{n}$を切り捨て(floor)している</li>
</ul><li><a href="http://snufkon.hatenablog.com/entry/2013/06/21/112209">SICP 孤読書会 - 1.3 高階手続きによる抽象 (1.3.1 〜 1.3.4) - プログラミング的な何か、あと自転車日本一周とか</a></li>
<ul><li><a href="https://github.com/snufkon/SICP/blob/master/ch1/1-45.scm">回答コード</a>だとやっぱりfloorしてる。しかしよくみんな$\log_2{n}$だと気づくなー。</li>
</ul><li><a href="http://d.hatena.ne.jp/tetsu_miyagawa/20130320/1363781534">SICP 1.3.4 Procedures as Returned Values - プログラミング再入門</a></li>
<ul><li>こちらはceiling</li>
</ul><li><a href="https://ivanovivan.wordpress.com/2010/08/22/sicp-exercises-section-1-3-4/">SICP Exercises Section 1.3.4 | Ivan Ivanov's Weblog</a></li>
<ul><li>floor</li>
</ul><li><a href="http://www.serendip.ws/archives/491">問題1.45 – SICP(計算機プログラムの構造と解釈)その23 : Serendip - Webデザイン・プログラミング</a></li>
<ul><li>四捨五入(round)は新しいパターン</li>
</ul><li><a href="https://sicp.g.hatena.ne.jp/n-oohira/20090207/1233979052">問題1.45 - n-oohiraのSICP日記 - sicp</a></li>
<ul><li>floor、たぶん上リンクのようなのを参考にした結果</li>
</ul><li><a href="http://www.zhihu.com/question/28838814">SICP 1.45证明? - 数学 - 知乎</a></li>
<ul><li>中国語ですが上と同じような議論で証明してあります。結論は$m \geq \log_{2}{n}$で、切り上げです!</li>
</ul></ul>deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com3tag:blogger.com,1999:blog-9245921.post-71842484435506547822015-05-26T20:10:00.004+09:002024-01-23T13:15:26.372+09:00『コンピュータシステムの理論と実装』第5章 CPUを作ったよ 個人的に進めてる<a href="http://www.oreilly.co.jp/books/9784873117126/" target="_blank">『コンピュータシステムの理論と実装』</a>の実装メモを書きますよ。<br />
今回はCPUを作るのが山場でした。<br />
<br />
「第5章 コンピュータアーキテクチャ」では<b>Hackコンピュータ</b>というこの本オリジナルのコンピュータを作ります。前章まででALU、レジスタやプログラムカウンタなんかは作ってあるので、それらを組合せてなんとかします。<br />
<br />
命令メモリ、CPU、データメモリを合体させるとHackコンピュータになるらしい(P.105、5.3.3)。メモリは前章のRAMを利用すればすぐ作れるので、問題はCPUを作ることです。<br />
<br />
<br />
P.102に概略図が載ってるのでそのとおりに作るんですが、詳細が省かれてるので実際にHDLで書こうとすると大変でした。この本は実践に重きを置いているので、詳細を省いているのはたぶん意図的です。実装を通じて学んで欲しいということでしょう。<br />
<br />
下に私の考えた実装コードを載せますけど、本の思想に忠実に自分で考えたいというひとは<b>ネタバレ注意</b>です。(GW中にやったけどハマった部分があって3日ぐらいかかってしまったw)<br />
<a name='more'></a>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
HDLコード<br />
<a href="https://github.com/deltam/nand2tetris/blob/master/projects/05/CPU.hdl">nand2tetris/CPU.hdl at master · deltam/nand2tetris</a><br />
<script src="https://gist.github.com/deltam/a9475124afd9d289ebfa.js"></script><br />
<br />
<br />
<br />
苦労したところはジャンプ命令のパースでした。ぜんぶ論理回路でやらないといけないので慣れないとどこから手を付ければいいのか分からないです。<br />
ジャンプ命令パース部分の論理回路を部分的に書いてみました。<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyyPl_CTxMvAynz-w9XNjOIalHKJkAHt6OnIUzZP4fNozxbo3sd3wg84jV_g0ba2tnqjlqOgrEJcbkKdLf84ScROq1rMUARiwjn8H_reeo6e9G2uVX1A5bnSBDZiR-RkaCXBgt/s1600/CPU_jmp_parse.jpg"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyyPl_CTxMvAynz-w9XNjOIalHKJkAHt6OnIUzZP4fNozxbo3sd3wg84jV_g0ba2tnqjlqOgrEJcbkKdLf84ScROq1rMUARiwjn8H_reeo6e9G2uVX1A5bnSBDZiR-RkaCXBgt/s400/CPU_jmp_parse.jpg" /></a><br />
<br />
まず命令コードのジャンプ命令部分をデマルチプレクサのselに入力して何の命令なのかはっきりさせます(該当するジャンプ命令のビットだけ1が立つ)。<br />
ALUなどの論理回路を作ったときの経験から学んだコツとして<b>"必要な値は最初に全部作っておいて、必要なときに組み合わせる"</b>というのがあります。<br />
ジャンプ命令はALUの出力値の大小によって分岐するので、条件判断に必要な次の値とその否定を全部作っておきます。<br />
<br />
<ul><li>zr − ALUの出力が0と等しい</li>
<li>ng − ALUの出力が0未満</li>
<li>gt − ALUの出力が0より大きい(zrとngから作る)</li>
</ul><br />
つぎにそれぞれのジャンプ命令に必要な論理回路を作って条件判断させておきます。<br />
最後にデマルチプレクサの出力値とAndして(該当命令の条件判断だけが残る)、全体をORでまとめればジャンプ命令がパースできたことになります。<br />
<br />
このロジックというか、考え方を思いつくのに苦労しました。CPU作るのって大変ですねー。<br />
<br />
<br />
<br />
苦労したけど、エミュレータでサンプルコードがちゃんと動くのを確認できたときはかなりの達成感でした。<b>「やったぜ! 俺はコンピュータを作ったぞ!」</b>www<br />
<br />
<br />
次の第6章はこのHackコンピュータ用のアセンブラを実装します。ここから先はソフトウェアの世界になるので少し楽になるんじゃないかなーと思ってます(コンパイラ、OSの実装とかあるけど)。<br />
<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-7352867040518080542015-04-19T17:17:00.001+09:002015-04-19T17:55:43.070+09:00AND、ORだけではNOT回路は作れないのか<a href="http://deltam.blogspot.jp/2015/04/2.html">「コンピュータシステムの理論と実装」読書会</a>のときの疑問を追っかけて考えてみました。<br />
<br />
NotとAnd/Orからならすべての論理回路が作れることは分かりました。<b>ではAnd、OrのみからNot回路は作れないのでしょうか?</b><br />
直感的に「作れない」って感じるんですが、きちんと論理的に説明するのはけっこう難しい気がします。<br />
<br />
ではどうやったら説明できるか。<br />
<br />
Notは1入力1出力の回路です。まずは入力をaとおきます。最初の入力の可能性としてはa、定数0、定数1のどれかしかありません。<br />
最初の入力から次の出力の可能性は次の表の通りです。やっぱりa,0,1のどれかになってしまいます。<br />
<br />
<table><thead>
<tr> <th>入力1</th> <th>入力2</th> <th>And出力</th> <th>Or出力</th> </tr>
</thead> <tbody>
<tr> <td>a</td> <td>0</td> <td>0</td> <td>a</td> </tr>
<tr> <td>a</td> <td>1</td> <td>a</td> <td>1</td> </tr>
<tr> <td>a</td> <td>a</td> <td>a</td> <td>a</td> </tr>
<tr> <td>0</td> <td>0</td> <td>0</td> <td>0</td> </tr>
<tr> <td>0</td> <td>1</td> <td>0</td> <td>1</td> </tr>
<tr> <td>1</td> <td>1</td> <td>1</td> <td>1</td> </tr>
</tbody> </table><br />
<br />
つぎに1出力ってことを考えます。And、Orのみで回路を作るならケーブルをまとめる最後の素子はAndまたはOrのどっちかになります。そして回路の最初の入力も次の出力もa,0,1になってるので、最後の出力もやっぱりa,0,1になってしまう。<br />
雑に図解するとこんな感じ。<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZBe3e9uEGfNXvTSsKkB68kbXeZzTiKxdz_LK5INlFTKPafejzZG5VLvNUbsZSOURj3daDnjwKRZ_0VeC4iODiADNlgETMU1IXRYo2CLCyN7c8jc_4552EIGlNjq0ySUhtOvP5/s1600/20150419170558.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZBe3e9uEGfNXvTSsKkB68kbXeZzTiKxdz_LK5INlFTKPafejzZG5VLvNUbsZSOURj3daDnjwKRZ_0VeC4iODiADNlgETMU1IXRYo2CLCyN7c8jc_4552EIGlNjq0ySUhtOvP5/s320/20150419170558.png" /></a></div><br />
途中の回路がどんな複雑でもAnd/Orのみなら中間出力も変わらないので、最後の論理素子の入力も変わらない。だから最後までNot aを作ることはできない。<br />
<br />
<br />
……という説明を考えてみたけど、なんだかすっきりしない。背理法か何かでさっぱりと証明する方法はないのかなー。<br />
<br />
<br />
<br />
<br />
追記:ツイートしたら<a href="https://twitter.com/chiral">@chiral</a>さんが速攻で返信くれました。だいぶすっきりした!<br />
<br />
<blockquote class="twitter-tweet" lang="ja"><p><a href="https://twitter.com/deltam">@deltam</a> それを実現する段数が最小の回路をXとしましょう。いま、出力が1だとすると、出力の手前の素子Yへの入力は(Xの段数最小性より)全てゼロのはずです。するとYがANDでもORでも入力が全てゼロなら出力は決して1にならないので矛盾。 Q.E.D.</p>— ITコンサルタント (@chiral) <a href="https://twitter.com/chiral/status/589707999360331776">2015, 4月 19</a></blockquote><script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-6718234639748951152015-04-17T02:13:00.002+09:002020-05-28T18:15:35.273+09:00#nandris コンピュータシステムの理論と実装 読書会(2) に参加してきました<a href="http://www.oreilly.co.jp/books/9784873117126/">「コンピュータシステムの理論と実装」</a>は論理回路から順を追ってコンピュータの仕組みを知ろうという教科書です。<br />
Nand回路から初めて論理回路、加算器から機械語、OSや高級言語のコンパイラを経てテトリスを作っちゃおうという、デアゴスティーニでやりそうな構成。<br />
<br />
この本の内容はNand2Tetrisというオンライン学習コースで、私はこのTED Talksで知りました。<br />
<br />
<a name='more'></a>
<a href="http://www.aoky.net/articles/shimon_schocken/the_self_organizing_computer_course.htm">独習コンピュータ教程</a><br />
<iframe allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/7G9CPYskKxE" width="560"></iframe><br />
<br />
<br />
Nandからテトリスまでつなぎ目無く作っていくというのは、なんとなく冒険心を刺激されるものがありますね。<br />
学習コースでは資料全部、ハードウェアシミュレータのようなツールも全部公開されてるので本当に独習できるんですが、全部英語なのが難点でした。<br />
いつかやろうと思って放置してましたが日本語訳が出たというなら、今でしょッ! ということでちょうどよく開催されていた読書会に参加!<br />
<br />
<a href="http://nandris.connpass.com/event/13752/">コンピュータシステムの理論と実装 読書会(2) - connpass</a><br />
<br />
<br />
<br />
第2回は主に論理回路とブール代数でした。ここらへんは情報系工業高校に通った身なので死ぬほどやったところ。すごく懐かしかったです。<br />
論理回路のキモはNand回路が一種類があればAnd、Or、Notがすべて構成できるってこと。さらにそれらを使ってつくる<a href="http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%83%81%E3%83%97%E3%83%AC%E3%82%AF%E3%82%B5">マルチプレクサ</a>なども作れます。<br />
<br />
書いたHDLをハードウェアシミュレータで動かしてみることもできます。ハードウェアシミュレータ+今後必要なツールはここからダウンロードできます。<br />
<br />
<a href="http://www.nand2tetris.org/software.php">The Elements of Computing Systems / Nisan & Schocken</a><br />
<br />
<br />
<br />
NandかNorから他の論理素子を作れることは分かったけど、別のものを元に論理素子を作ることは出来ないのかな? ということでマルチプレクサからAndとNotを作ってみました。<br />
Andは $out = b \cdot sel$。<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilSel9DSRr7fHp1nO2bnimyJrJ0yERPsDmUJE_YZ6f3-4sAmcWmeJlF23-lQRYDoANvOVM7cTMn1Sa_kcwRIsIIrscXFx3-fsZpIpzo7Vx4bP-dLxkM4FsJQk4TCJVG2Jr7G7E/s1600/20150417011459.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilSel9DSRr7fHp1nO2bnimyJrJ0yERPsDmUJE_YZ6f3-4sAmcWmeJlF23-lQRYDoANvOVM7cTMn1Sa_kcwRIsIIrscXFx3-fsZpIpzo7Vx4bP-dLxkM4FsJQk4TCJVG2Jr7G7E/s320/20150417011459.png" /></a></div><br />
Notは $out = \overline{sel} $。<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj6jMap3aLO-54dINw4sPr6T23MANFs_HxEnGMkVtj7HURRp5nw_g0S_K0Ds-Gkg6WxVY-4jsMpX2ROcgRsEyPj3xLidFiOcIv5igdwxdXBN_s36eXqXrDUiXupZkcq69Xc7e2m/s1600/20150417011558.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj6jMap3aLO-54dINw4sPr6T23MANFs_HxEnGMkVtj7HURRp5nw_g0S_K0Ds-Gkg6WxVY-4jsMpX2ROcgRsEyPj3xLidFiOcIv5igdwxdXBN_s36eXqXrDUiXupZkcq69Xc7e2m/s320/20150417011558.png" /></a></div><br />
HDLのコードで書くとこんな感じ(HDLでは1,0はtrue,falseで表すらしい)。<br />
<br />
<pre class="code">CHIP Not {
IN in;
OUT out;
PARTS:
Mux (a=true, b=false, sel=in, out=out);
}
CHIP And {
IN a, b;
OUT out;
PARTS:
// Put your code here:
Mux (a=false, b=a, sel=b, out=out);
}
</pre><br />
元になる論理素子からNotが作れればなんとかなりそうですね。<br />
And、OrだけじゃNotは作れないだろうけど、そのことってどうやって証明するんだろうなー。<br />
<br />
<br />
<br />
<br />
ブール算術の章は2の補数のところまでで今回は終了。<a href="http://ja.wikipedia.org/wiki/2%E3%81%AE%E8%A3%9C%E6%95%B0">2の補数</a>は2進数でマイナスの数を表す約束事ですが、これを採用すれば足し算回路だけで引き算も表現できるので超重要です。使わないと引き算回路も別に作らないといけなくなって不経済。<br />
1の補数というのもあるのですが、これだと−0と+0が出来てしまって効率的じゃないのです。途中で<a href="https://twitter.com/yshigeru">@yshigeru</a>さんが紹介してくれた式変形が、1の補数から2の補数への変化をわかりやすく表現していて良かったです。<br />
<br />
\[ a + \overline{a} = -1 \]<br />
\[ \overline{a} + 1 = -a \]<br />
<br />
<br />
<br />
次回はちょっと長めですがそのぶんゆっくりできるでしょう。興味ある人はどうぞ。<br />
<a href="http://nandris.connpass.com/event/14194/">コンピュータシステムの理論と実装 読書会(3) 休日編 - connpass</a><br />
<br />
<br />
<iframe frameborder="0" marginheight="0" marginwidth="0" scrolling="no" src="http://rcm-fe.amazon-adsystem.com/e/cm?lt1=_blank&bc1=000000&IS2=1&bg1=FFFFFF&fc1=000000&lc1=0000FF&t=deltam-22&o=9&p=8&l=as4&m=amazon&f=ifr&ref=ss_til&asins=4873117127" style="height: 240px; width: 120px;"></iframe><br />
<br />
<br />
<br />
<br />
【おまけ】Nandのみで作ったAnd,Or,NotのHDLコード<br />
<a href="https://gist.github.com/deltam/640dd4965246c99f6bd2">NandOnly.hdl</a><br />
<script src="https://gist.github.com/deltam/640dd4965246c99f6bd2.js"></script>deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-56973479475369023802014-12-31T23:55:00.001+09:002020-05-28T18:16:02.412+09:00 素数腕立て伏せ Advent Calendar まとめ #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
<br />
ACの経過を一覧表にまとめました。リンク集としてお使いくださいませ。<br />
けっきょく全体の勝率は<b>3割2分</b>でした。<br />
<br />
<a name='more'></a>
<style type="text/css">
div.inner > table { border: solid 2px black; border-collapse: collapse;}
div.inner > table > thead > tr > th { border: solid 1px black; padding: 4px; border-collapse: collapse;}
div.inner > table > tbody > tr > td { border: solid 1px black; padding: 4px; border-collapse: collapse;}
</style><br />
<br />
<div class="inner"><table><thead>
<tr> <th align="right" style="width: 10%;"> 日数 </th> <th align="right" style="width: 15%;"> 腕立て回数</th> <th align="left" style="width: 10%;"> 勝敗</th> <th> メモ</th> </tr>
</thead> <tbody>
<tr> <td align="right"> <a href="http://deltam.blogspot.jp/2014/12/adventcalendar-1-primenumpushups.html">1日</a></td> <td align="right"> 28 </td> <td align="left">負け </td> <td>28は3通りの方法で4つの平方数の和で表せる最小の数字。だけど3つの平方数の和で表すのは不可能。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/adventcalendar-2-primenumpushups.html">2日</a></td> <td align="right"> 37</td> <td align="left"> <strong>勝ち</strong> </td> <td> 37は原子ピタゴラス数の斜辺。<a href="http://www.mathjax.org/">MathJax</a>を導入して数式をキレイに表示できるようになるが、同時に<b>TeX記法を覚えるという苦行</b>が始まる。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/adventcalendar-3-primenumpushups.html">3日</a></td> <td align="right"> 30</td> <td align="left"> 負け</td> <td> 30は2つの平方数の和では表せないけど3つならOK。<b>ロッキーのテーマ</b>が筋トレBGMに最適だと気づく。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-4-primenumpushups.html">4日</a></td> <td align="right"> 32</td> <td align="left"> 負け</td> <td> <a href="https://twitter.com/haruyama">@haruyama</a>さんに3つの平方数の和で表せる数の条件を教えてもらう。<b>0を平方数に含めるか</b>でちょっと混乱する。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-5-primenumpushups.html">5日</a></td> <td align="right"> 28</td> <td align="left"> 負け</td> <td> 4日目を引きずって自然数に0を含めるか考えていたらメガネをしたまま素数腕立て伏せを始めてしまいビビる。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-6-primenumpushups.html">6日</a></td> <td align="right"> 55</td> <td align="left"> 負け</td> <td> 2セット(33、22)の合計。素数腕立て伏せACの勧誘メッセージなど書いてみるが、<b>PVは依然二桁</b>。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-7-primenumpushups.html">7日</a></td> <td align="right"> 29</td> <td align="left"> <strong>勝ち</strong></td> <td> 0時を越えてしまったが「始めからインド標準時使ってたし」という<b>小学生並みの言い訳</b>で乗り切る。二平方和定理の1文証明を紹介。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-8-primenumpushups.html">8日</a></td> <td align="right"> 37</td> <td align="left"> <strong>勝ち</strong></td> <td> 記録回数を<b>平方数の和で表すのがクセ</b>になりはじめる。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-9-primenumpushups.html">9日</a></td> <td align="right"> 31</td> <td align="left"> <strong>勝ち</strong></td> <td> 記録が伸びなくて飽きてきたので次から2セット方式にすることに。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-10-primenumpushups.html">10日</a></td> <td align="right"> 62</td> <td align="left"> 負け</td> <td> 2セット(36、26)の合計。合計値が素数か脳内判定が難しくなってくる。<a href="https://oeis.org/?language=japanese">オンライン整数列大辞典</a>の存在を知る。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-11-primenumpushups.html">11日</a></td> <td align="right"> 63</td> <td align="left"> 負け</td> <td> 2セット(41、22)の合計。<a href="http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86">フェルマーの小定理</a>と<a href="http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0">メルセンヌ数</a>の復習をする。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-12-primenumpushups.html">12日</a></td> <td align="right"> 35</td> <td align="left"> 負け</td> <td> 飲み会帰りだったので途中で気持ち悪くなり自重する。35は5通りの方法で3つの異なる素数の和で表せる最小の数字。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-13-primenumpushups.html">13日</a></td> <td align="right"> 32</td> <td align="left"> 負け</td> <td> 2通りの方法で2つの異なる素数の和で表せる最小の数字ってなんだろか、と考えて<a href="http://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AD%90%E7%B4%A0%E6%95%B0">双子素数予想</a>へ行き着く。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-14-primenumpushups.html">14日</a></td> <td align="right"> 46</td> <td align="left"> 負け</td> <td> 46は18の分割数と同じ。素数以外にも魅力ある数が多くて浮気しそうになるが<b>素数腕立てニスト</b>として気を引き締め直す。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-15-primenumpushups.html">15日</a></td> <td align="right"> 47</td> <td align="left"> <strong>勝ち</strong></td> <td> <b>アウトドア素数腕立て伏せ</b>というアイデアを思いつくが未実行。あとの経過を見るとやらんでよかった。あと47は<a href="http://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%A5%E3%82%AB%E6%95%B0">リュカ数</a>。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-16-primenumpushups.html">16日</a></td> <td align="right"> 43</td> <td align="left"> <strong>勝ち</strong></td> <td> ついにインド標準時でもカバーできなくなり「<b>イラン標準時だし</b>」という言い訳を始める。「<b>そもそも地球時間とか相対論的効果とかさー</b>」と面倒くさいことを言い出す。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-17-primenumpushups.html">17日</a></td> <td align="right"> 52</td> <td align="left"> 負け</td> <td> 52は5番目の<a href="http://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E6%95%B0">ベル数</a>。だんだん素数間隔が増えてきてキツくなってくる</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-18-primenumpushups.html">18日</a></td> <td align="right"> 31</td> <td align="left"> <strong>勝ち</strong></td> <td> この頃に風邪を引いたみたい。熱があったらしく筋肉痛っぽい症状がでる。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-19-primenumpushups.html">19日</a></td> <td align="right"> 33</td> <td align="left"> 負け</td> <td> 本格的に<b>熱がでて寝込む</b>がヤケクソで素数腕立て伏せは続ける。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-20-primenumpushups.html">20日</a></td> <td align="right"> 37</td> <td align="left"> <strong>勝ち</strong></td> <td> 平熱に戻ったので心置きなく素数腕立て伏せをする。<a href="http://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%8C%E3%83%BC%E3%82%A4%E6%95%B0">ベルヌーイ数</a>をしらべて<a href="http://ja.wikipedia.org/wiki/%E9%96%A2%E5%AD%9D%E5%92%8C">関孝和</a>の偉大さを知る。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-21-primenumpushups.html">21日</a></td> <td align="right"> 50</td> <td align="left"> 負け</td> <td> <b>素数腕立て伏せ健康法</b>により全快。2通りの方法で2つの平方数の和で表せる数についていろいろ計算する</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-22-primenumpushups.html">22日</a></td> <td align="right"> 29</td> <td align="left"> <strong>勝ち</strong></td> <td> <a href="http://deltam.blogspot.jp/2014/12/advent-calendar-21-primenumpushups.html">21日目</a>の2通り2平方和について確認した事実をメモる。記録はイマイチ伸びていない。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-23-primenumpushups.html">23日</a></td> <td align="right"> 46</td> <td align="left"> 負け</td> <td> ここまでの勝率を集計。3割9分。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-24-primenumpushups.html">24日</a></td> <td align="right"> 49</td> <td align="left"> 負け</td> <td> イブの日付を一桁数字にバラして平方和を取ると25になるという<b>神秘的事実</b>を発見して<b>イブどころじゃない</b>。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-25-primenumpushups.html">25日</a></td> <td align="right"> 38</td> <td align="left"> 負け</td> <td> クリスマスだけど特に関係なく素数腕立て伏せ。あと$12^2+25=13^2$という<b>意味深な関係を発見</b>。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-26-primenumpushups.html">26日</a></td> <td align="right"> 48</td> <td align="left"> 負け</td> <td> <b>正48角形</b>は定規とコンパスで作図可能。<a href="http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E6%95%B0">フェルマー素数</a>とか調べる。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-27-primenumpushups.html">27日</a></td> <td align="right"> 50</td> <td align="left"> 負け</td> <td> 大掃除をしてピカピカの床で素数腕立て伏せができて<b>幸せ</b>。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-28-primenumpushups.html">28日</a></td> <td align="right"> 27</td> <td align="left"> 負け</td> <td> 腕立て中に<b>カーチャン</b>に話しかけられて混乱して潰れる。素数腕立て伏せにはメンタルも重要だと認識。</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-29-primenumpushups.html">29日</a></td> <td align="right"> 43</td> <td align="left"> <strong>勝ち</strong></td> <td> 素数腕立て伏せ<b>ダイエット本</b>が出せないか企む</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-30-primenumpushups.html">30日</a></td> <td align="right"> 33 </td> <td align="left"> 負け </td> <td><a href="http://ja.wikipedia.org/wiki/%E3%82%B4%E3%83%BC%E3%83%AB%E3%83%89%E3%83%90%E3%83%83%E3%83%8F%E3%81%AE%E4%BA%88%E6%83%B3">ゴールドバッハ予想</a>についてちょっと調べる</td> </tr>
<tr> <td align="right"><a href="http://deltam.blogspot.jp/2014/12/advent-calendar-31-primenumpushups.html">31日</a></td> <td align="right"> 58 </td> <td align="left"> 負け</td> <td>負けだが2セット形式を除けば過去最高記録でフィニッシュ! <a href="http://en.wikipedia.org/wiki/Idoneal_number">idoneal number</a>という新たな敵が現れる...!!</td> </tr>
</tbody> </table></div>deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-35516278006856255472014-12-31T23:38:00.000+09:002014-12-31T23:38:06.004+09:00素数腕立て伏せ Advent Calendar 31日目(最終回) #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
最終回じゃー!<br />
<br />
<b>31日目<br />
58回で負け(合成数)</b><br />
<br />
<br />
負けだけど連続での素数腕立て伏せでは最高の回数だ。30ぐらいでもまだ余裕があったので「イケるかな?」と思ってガンバった。<br />
欲を言えば59(素数)までやって勝ちで終わりたかったけど、まぁいいや。<br />
$ 58 = 3^2 + 7^2 $<br />
<br />
Alphaちゃんによると58は<b>Idoneal number</b>だとのこと。<br />
<br />
<blockquote>58 is an idoneal number.<br />
<a href="http://www.wolframalpha.com/input/?i=58">58 - Wolfram|Alpha</a><br />
</blockquote><br />
日本語でなんていうのか分からなかったけど英語版Wikipediaによるとこんな数らしいです。<br />
<br />
<blockquote>In mathematics, Euler's idoneal numbers (also called suitable numbers or convenient numbers) are the positive integers D such that any integer expressible in only one way as x^2 ± Dy^2 (where x^2 is relatively prime to Dy^2) is a prime, prime power, or twice one of these.<br />
</blockquote>(relatively prime=互いに素)<br />
<br />
うーむ、こういうことかな。<br />
正整数Dがidoneal numberであるならば、整数x,yによって<br />
<br />
\[n = x^2 \pm Dy^2 \]<br />
<br />
と書いたとき(ただし$x^2$と$Dy^2$は互いに素)、値nを<b>素数</b>か<b>素数のべき乗</b>および<b>それらの2倍</b>にできる。<br />
(定義が複雑でよく分からん。これで正しいのか?)<br />
<br />
<br />
$ 3^2 + 58*1^2 = 67 $で素数ですね。他に適当にemacs lispで計算してみると($58=2*29$なのでxを2の倍数にすると互いに素にならないのでNG)、<br />
<br />
<pre class="code">(defun idoneal (d x y)
(list (+ (* x x) (* d y y))
(- (* x x) (* d y y))))
(idoneal 58 3 2)
(241 -223) ; 241 素数
(idoneal 58 5 1)
(83 -33) ; 83 素数
(idoneal 58 5 2)
(257 -207) ; 257 素数
(idoneal 58 7 1)
(107 -9) ; 107 素数
</pre><br />
あれ、なんかすごくないこれ? Wikipediaによるとこの系列には無限個の素数を含んでいるそうです。<br />
<a href="http://ja.wikipedia.org/wiki/%E7%AE%97%E8%A1%93%E7%B4%9A%E6%95%B0%E5%AE%9A%E7%90%86">算術級数定理</a>と似てるけど等差数列にはならないから違いますね。<br />
<br />
<br />
idoneal numberは意外にも有限みたいです。<br />
カール・ガウスとオイラーによって今まで65個のidoneal numberが発見されていて、それで全部だと予想されていると。<br />
<br />
<blockquote>The 65 idoneal numbers found by Carl Friedrich Gauss and Leonhard Euler and conjectured to be the only such numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, and 1848 (sequence A000926 in OEIS). Weinberger proved in 1973 that at most one other idoneal number exists, and that if the generalized Riemann hypothesis holds, then the list is complete.<br />
<a href="http://en.wikipedia.org/wiki/Idoneal_number">Idoneal number - Wikipedia, the free encyclopedia</a><br />
</blockquote><br />
なんかリーマン予想とも関係あるらしいけど、もう追い切れないので切り上げる!<br />
<br />
<br />
<u>素数腕立て伏せ一言コメント</u><br />
とうとうACをやり遂げました(インド標準時とかイラン標準時とか知らんもーん)。<br />
<a href="http://deltam.blogspot.jp/2014/12/adventcalendar-1-primenumpushups.html">12月1日</a>に比べると明らかに腕力が付きました。あといろんな自然数の性質に触れて楽しかった。<br />
最後の最後にidoneal numberなんていうよく分からない数も出てきて、「<b>俺たちの素数腕立て伏せはこれからだ!</b>」と打ち切りエンドっぽく盛り上がりました(自分の中では)。<br />
各記事の<b>PVは二桁</b>なんですが、2015年も素数腕立て伏せニストとして普及に努めていきまーす。(来年はQiitaを使おう)<br />
<br />
<br />
あと2014年中に今までのまとめ一覧表をアップしまーす。<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-49721026844453274592014-12-30T20:38:00.001+09:002014-12-30T20:39:55.168+09:00 素数腕立て伏せ Advent Calendar 30日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
これまでのまとめ記事を書こうと思ったけどクソメンドイっすね、書くけど。<br />
<br />
<b>30日目<br />
33回で負け(合成数)</b><br />
<br />
あと10回は行けたはず。TV見ながらやるのは止めよう。<a href="http://deltam.blogspot.jp/2014/12/advent-calendar-19-primenumpushups.html">19日目</a>の38.7度の熱を出してた時と同じ記録なのはアカン。<br />
<br />
<blockquote>33 is the smallest number with 9 representations as a sum of 3 primes:<br />
33 = 2+2+29 = 3+7+23 = 3+11+19 = 3+13+17 = 5+5+23 = 5+11+17 = 7+7+19 = 7+13+13 = 11+11+11<br />
<a href="http://www.wolframalpha.com/input/?i=33">33 - Wolfram|Alpha</a><br />
</blockquote><br />
33は9通りの方法で3つの素数の和として表せる最小の数だと。<br />
素数の和といえば「4以上のすべての偶数は2個の素数の和で表せる」という<a href="http://ja.wikipedia.org/wiki/%E3%82%B4%E3%83%BC%E3%83%AB%E3%83%89%E3%83%90%E3%83%83%E3%83%8F%E3%81%AE%E4%BA%88%E6%83%B3">ゴールドバッハの予想</a>が有名ですね。<br />
もともとゴールドバッハさんが述べたのは「<b>5より大きな任意の自然数は3つの素数の和で表せる</b>」という命題だったそうです。<b>3素数の和で表せたとして、そのパターン数を求める定理</b>は無いのかな?<br />
<br />
<br />
ほかにWikipediaにある数学的性質ではこれが面白かった。<br />
<br />
<blockquote>33 = 1! + 2! + 3! + 4!<br />
<a href="http://ja.wikipedia.org/wiki/33">33 - Wikipedia</a><br />
</blockquote><br />
<br />
<u>素数腕立て伏せ一言メモ</u><br />
明日で素数腕立て伏せACは終わりです。できれば53以上の素数で終わりたいなぁ(フラグ)。<br />
<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com1tag:blogger.com,1999:blog-9245921.post-51972624241006695722014-12-29T21:16:00.000+09:002014-12-29T21:16:28.725+09:00素数腕立て伏せ Advent Calendar 29日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
コタツはあれか、催眠ビームでも出してんのけ?<br />
<br />
<b>29日目<br />
43回で勝ち(素数)</b><br />
<br />
53越えを目指してたのでイマイチ不満。うーむ、腕のポジションが安定して無かった気がするなー。<br />
43は41と双子素数ですね。そういや29と31も双子素数だ。<br />
<br />
<blockquote>41 and 43 form a twin prime pair.<br />
<a href="http://www.wolframalpha.com/input/?i=43">43 - Wolfram|Alpha</a><br />
</blockquote><br />
<br />
<u>素数腕立て伏せ一言メモ</u><br />
お餅が美味しいのでつい食べ過ぎちゃったが、素数腕立て伏せのおかげで筋肉量が増えてるはずなのでたぶん大丈夫なはず。たぶん。deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-53066301731191436552014-12-28T22:35:00.001+09:002014-12-28T22:35:26.995+09:00素数腕立て伏せ Advent Calendar 28日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
寒い!<br />
<br />
<b>28日目<br />
27回で負け(合成数)</b><br />
<br />
素数腕立て伏せの途中で話しかけられると記録が伸びないということが分かりました。<br />
やはり精神統一と脳内カウントが大事みたいっすねー。<br />
<br />
<blockquote>27 is the smallest number with 2 representations as a sum of 3 positive squares:<br />
27 = 1^2+1^2+5^2 = 3^2+3^2+3^2<br />
<a href="http://www.wolframalpha.com/input/?i=27">27 - Wolfram|Alpha</a><br />
</blockquote><br />
<br />
<u>素数腕立て伏せ一言メモ</u><br />
今度はロッキーのテーマをiPodで聞きながら素数腕立て伏せします。deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-14327475086870385412014-12-28T22:28:00.000+09:002014-12-28T22:28:25.536+09:00素数腕立て伏せ Advent Calendar 27日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
大掃除してたらこれを書くの忘れてしまった。腕立て自体はちゃんとやったよ!<br />
<br />
<b>27日目<br />
50回で負け(合成数)</b><br />
<br />
53を目指してたので残念。49でかなり限界にきてて+1回で力尽きた。<br />
50は<a href="http://deltam.blogspot.jp/2014/12/advent-calendar-21-primenumpushups.html">21日</a>から2回めですね。2通りの方法で2つの平方数の和で表せる最小の数字。ただし0も平方数に含めると25が最小です($25 = 0^2 + 5^2 = 3^2 + 4^2$)。<br />
<br />
<br />
<u>素数腕立て伏せ一言メモ</u><br />
大掃除すると素数腕立て伏せしたときに床がピカピカで気分いいですよ!<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-72959058131499594162014-12-27T11:08:00.000+09:002015-01-01T12:13:32.546+09:00素数腕立て伏せ Advent Calendar 26日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
忘年会に出て年を忘れてたら筋トレの習慣も忘れてたわ〜(かなり大爆笑)<br />
<br />
<b>26日目<br />
48回で負け(合成数)</b><br />
<br />
またしても53まで行かなかった。スポーツ的な面もあるから今度は精神統一してからやろう。掛け声とかも。<br />
$ 48 = 4^2 + 4^2 + 4^2$、ゾロ目でキレイ。<br />
<br />
<br />
WolframさんとこのAlphaちゃんに訊いたところ<b>正48角形は定規とコンパスで作図可能</b>だとのことです。<br />
<br />
<blockquote>A regular 48-gon is constructible with straightedge and compass.<br />
<a href="http://www.wolframalpha.com/input/?i=48">48 - Wolfram|Alpha</a><br />
</blockquote><br />
<blockquote>ガウスはさらに1801年に出版した『整数論の研究』において、正 n 角形が作図可能であるための必要十分条件が、n が2の冪と相異なるフェルマー素数の積、すなわち<br />
n = 2^mFaFb…Fc(Fa , Fb , … ,Fc は全て異なるフェルマー素数、m は非負整数)<br />
の形であることを示した[6]。<br />
<a href="http://ja.wikipedia.org/wiki/%E5%AE%9A%E8%A6%8F%E3%81%A8%E3%82%B3%E3%83%B3%E3%83%91%E3%82%B9%E3%81%AB%E3%82%88%E3%82%8B%E4%BD%9C%E5%9B%B3">定規とコンパスによる作図 - Wikipedia</a><br />
</blockquote><br />
フェルマー素数は $ p = 2^{2^m} + 1 $ と書ける素数のこと。<br />
<br />
うーんと、$ 48 = 2^4 * 3 = 2^4 * (2^{2^0} + 1) $ か。たしかに条件は満たしてますね。<br />
<br />
ところでWikipediaにあった<a href="http://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%BC%E3%83%AB-%E3%83%9E%E3%82%B9%E3%82%B1%E3%83%AD%E3%83%BC%E3%83%8B%E3%81%AE%E5%AE%9A%E7%90%86">モール-マスケローニの定理</a>が気になるぞ(内容と語感がいい)。<br />
<br />
<br />
<br />
<br />
<br />
<u>素数腕立て伏せ一言メモ</u><br />
素数腕立て伏せに必要不可欠となってきているWolframAlphaですが、Wolframおじさんの孫娘Alphaちゃんと考えると非常に癒やされることに気づきました。<br />
「WolframAlpha 萌え擬人化」で検索しても出てこないから誰か描いちゃってもいいのよ。<br />
ちなみにMathematicaは個人的には<a href="http://www.hyuki.com/girl/">数学ガール</a>のミルカさんのイメージ。<br />
<br />
<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-10054324956132746662014-12-26T01:37:00.001+09:002014-12-27T08:06:34.131+09:00素数腕立て伏せ Advent Calendar 25日目 #prime_num_pushups<br />
<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
<br />
<blockquote> クリスマスというものに、最近の犀川は何も感じない。十二月二十五日だから、1、2、2、5の数字を全部足すとちょうど10になる、というくらいの印象しかない。<br />
<a href="http://www.amazon.co.jp/gp/product/4061819275/ref=as_li_ss_tl?ie=UTF8&camp=247&creative=7399&creativeASIN=4061819275&linkCode=as2&tag=deltam-22">笑わない数学者</a><br />
</blockquote><br />
クリスマス=チキンとケーキが安く買える日になりつつある。<br />
そういや$12^2 + 25 = 13^2$ですね(深い意味は無い)。<br />
<br />
<b>25日目<br />
38回で負け(合成数)</b><br />
<br />
別のことを考えながらやり始めたら、なんかタイミングがおかしくなった。<br />
手のポジション、タイミング、スピードなどをいつもどおりにしないと調子が狂うなぁ。<br />
$38 = 2^2 + 3^2 + 5^2$<br />
<br />
<br />
<u>素数腕立て伏せアナウンス</u><br />
<a href="http://deltam.blogspot.jp/2014/12/adventcalendar-1-primenumpushups.html">1日目</a>に書きましたが、25って数字が気に食わないのでアドベントカレンダーだけど<b>31日</b>まで続けます。<br />
PVの少なさもなんのその、カーズ様だって言ってます<b>「頂点に立つものは 常にひとり!」</b>。(このセリフ、使い勝手よくて好き)<br />
<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-29897022700576776742014-12-25T00:20:00.003+09:002014-12-25T00:20:53.067+09:00素数腕立て伏せ Advent Calendar 24日目 #prime_num_pushups<br />
<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
さっき気づいたけど$ 1^2 + 2^2 + 2^2 + 4^2 = 25 = 5^2 $だ、すごくね?<br />
イブ? なんですかそれ。<br />
<br />
<b>24日目<br />
49回で負け(合成数)</b><br />
<br />
30ぐらいまでは調子良かったんだけど、45からの踏ん張りが効かなかった。<br />
$ 49 = 7^2 = 2^2 + 3^2 + 6^2 $<br />
<br />
<br />
<u>素数腕立て伏せ一言メモ</u><br />
続けてるといろんな数の性質について敏感になるみたいです。<br />
「あの数を平方和で表すとー」とか無意識に考えてしまう。<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com1tag:blogger.com,1999:blog-9245921.post-41509341151900066842014-12-24T01:42:00.000+09:002014-12-24T01:42:40.029+09:00素数腕立て伏せ Advent Calendar 23日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
あまりにも穏やかな1日過ぎて忘れるとこだった。<br />
<br />
<b>23日目<br />
46回で負け(合成数)</b><br />
<br />
50は越えると思ったんだけど勢いが途切れてしまった。素数日数は勝ちたかったなー。<br />
$ 46 = 1^2 + 3^2 + 6^2 $<br />
<br />
<br />
<u>素数腕立て伏せACミニ集計</u><br />
1日から23日までの素数腕立て伏せでは、<br />
<b>勝ち9回<br />
負け14回</b><br />
で、勝率は3割9分です。<br />
残りは8日間。安全勝ちを狙わず常に攻めの勝ちを目指す所存であーる。<br />
<br />
<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-13560583266498129872014-12-23T01:34:00.000+09:002014-12-23T01:34:34.076+09:00素数腕立て伏せ Advent Calendar 22日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
ねむい!<br />
<br />
<b>22日目<br />
29回で勝ち(素数)</b><br />
<br />
いつもよりゆっくり目に腕立て伏せをしてみたらこんな記録になってしまった。<br />
普段は勢いに任せてやってたところもあったみたい。<br />
<br />
<br />
ところで<a href="http://deltam.blogspot.jp/2014/12/advent-calendar-21-primenumpushups.html">昨日の2通りの方法で2つの平方数の和で表せる数</a>についてごりごり計算して考えてみました。<br />
<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj49ku4epdxTAWSUxnKLAxDV7mP6FQ6wTycseuT31qa8ba4JQZzs4faljVagouwf0wQvG7XEvMA9g1ojzZ_C6LHwDx7Afpvhuc42LyBpJY6wT_lKj0YUgQBjLAtTy-lPfs370VK/s1600/IMG00752_noexif.jpg" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj49ku4epdxTAWSUxnKLAxDV7mP6FQ6wTycseuT31qa8ba4JQZzs4faljVagouwf0wQvG7XEvMA9g1ojzZ_C6LHwDx7Afpvhuc42LyBpJY6wT_lKj0YUgQBjLAtTy-lPfs370VK/s320/IMG00752_noexif.jpg" /></a><br />
<i>(本屋のブックカバーを広げてミウラ折りにしておくと計算用紙として便利。ほどほどに大きい)</i><br />
<br />
<br />
<b>結局よくわかんなーい</b>、だったですが途中まで確認した事実をアウトプットしておきましょう。自分でも忘れそうだし。<br />
<br />
$ x = a^2 + b^2 = c^2 + d^2$ とします。まずはそれぞれの大小関係を考えてみます。<br />
<br />
$ a \le b かつ c \le d $としておいて、b,dを考えます。b=d はありえない(2通りじゃなくて1通りになるから)。なので b<d とできる(逆でもいいけど分かりやすい順にした)。<br />
それでこんなふうに式変形してみると c<a ってこともわかる。<br />
<br />
\[<br />
\begin{eqnarray}<br />
a^2 + b^2 = c^2 + d^2 \nonumber \\<br />
a^2 - c^2 = d^2 - b^2 \nonumber<br />
\end{eqnarray}<br />
\]<br />
<br />
b<d から右辺は正数、左辺も同様なので $a^2 - c^2 > 0 $ から c<a がわかるという寸法です。<br />
これらの条件を組み合わせると次の大小関係がわかります(ねむい、tex調べながら書くのだるい)。<br />
<br />
\[<br />
\begin{equation}<br />
c < a \le b < d<br />
\end{equation}<br />
\]<br />
<br />
これで大小関係はひとまず分かった。つぎは、、、最初の式をもう少し変形してみようかな。<br />
<br />
\[<br />
\begin{eqnarray}<br />
a^2 + b^2 & = & c^2 + d^2 \nonumber \\<br />
a^2 - c^2 & = & d^2 - b^2 \nonumber \\<br />
(a - c) ( a + c ) & = & (d-b)(d+b) \nonumber \\<br />
\frac{a + c}{d - b} & = & \frac{ d + b} {a -c} <br />
\end{eqnarray}<br />
\]<br />
<br />
(2)は、、、なんかこれからもう少し何か言えそうなんだけど。<br />
あと平方数同士の差って連続する奇数の和と等しいから、<b>異なる範囲の連続する奇数の和が等しくなる条件は何かって問題は同値</b>だよなぁ、とか思ったけどなむい。今日はここまでだ。<br />
<br />
<br />
あとオンライン整数列大辞典で50,65,85を検索したらいくつか登録されてましたね。これとかそのまま。<br />
<a href="https://oeis.org/A118882">A118882 Numbers which are the sum of two squares in two or more different ways.</a><br />
<br />
<br />
<u>素数腕立て伏せ一言メモとかどうでもいいや</u><br />
ねむいdeltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-16728801304177268282014-12-22T01:49:00.000+09:002014-12-27T19:18:06.755+09:00素数腕立て伏せ Advent Calendar 21日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
風邪を引いても熱が出ても構わず素数腕立て伏せやってて結局治ったわけだから、素数のお陰で全快したと言えまいか。<br />
素数腕立て伏せ健康法、イケまいか。<br />
<br />
<b>21日目<br />
50回で負け(合成数)</b><br />
<br />
体力も戻ってきたみたいです。59を目指してたけど53にも届かなかったよ。<br />
<br />
<br />
ところで50は2通りの方法で2つの平方数の和に表せす最小の数字らしいですね。(smallestttってバグってるのかななな)<br />
<br />
<blockquote>50 is the smallesttt number with 2 representations as a sum of 2 squares:<br />
50 = 1^2+7^2 = 5^2+5^2<br />
<a href="http://www.wolframalpha.com/input/?i=50">50 - Wolfram|Alpha</a><br />
</blockquote><br />
では<b>この条件に叶う2番めに小さい数字</b>ってなんだろう?<br />
まず$ x = a^2 + b^2 = c^2 + d^2 $として、a,b,c,dはそれぞれ異なる数でないといけない。<b>(←追記:コレ違う)</b><br />
では50のときは$ a = 1, b = 7 $ だったから$ a = 2 $ で幾つか計算してみよう。<br />
2つの数の組合せを計算しないといけないけど、奇偶を考えればチェックする数が減らせますね。<br />
<br />
\[<br />
\begin{eqnarray}<br />
2^2 + 7^2 & = & 53 \nonumber \\<br />
3^2 + 6^2 & = & 45 (ダメ) \nonumber \\<br />
5^2 + 6^2 & = & 61 (ダメ) \nonumber \\<br />
4^2 + 5^2 & = & 41 (ダメ) \nonumber<br />
\end{eqnarray}<br />
\]<br />
<br />
うーん、だめだった。では次は和の大きさも考えて候補を減らそう。和の大きい順に抑えていって目標の数より下回ったら終わりということ。<br />
<br />
\[<br />
\begin{eqnarray}<br />
2^2 + 8^2 & = & 68 \nonumber \\<br />
5^2 + 7^2 & = & 74 (最大の組合せはダメ) \nonumber \\<br />
3^2 + 7^2 & = & 58 (残ってる組合せで最大の組合せもダメ) \nonumber<br />
\end{eqnarray}<br />
\]<br />
<br />
これもダメすね。はい次!<br />
<br />
\[<br />
\begin{eqnarray}<br />
2^2 + 9^2 & = & 85 \nonumber \\<br />
7^2 + 8^2 & = & 113 (最大の組合せはダメ) \nonumber \\<br />
6^2 + 7^2 & = & 85 (残ってる中で最大の組合せはビンゴ!)\nonumber <br />
\end{eqnarray}<br />
\]<br />
<br />
<br />
おぉ、85が2番めに小さな(省略)な数らしいぞ!<br />
たまには地道に計算してみるのもいいものだね〜。<br />
<br />
念のため、プログラムで検算してみよう(もちろん使うのはClojure)。<br />
<br />
<pre class="code">user> (def squares (map (fn [x] (* x x)) (range 1 10)))
#'user/squares
user> (filter (fn [[k v]] (>= (count v) 4))
(apply merge-with concat
(for [x squares, y squares :while (<= y x)] {(+ x y) [x y]})))
([65 (49 16 64 1)] [50 (25 25 49 1)] [85 (49 36 81 4)])
</pre>
あれれ、85は正しいけど3番目だったみたいだ。(1,7)から(2,7)じゃなくて、(1,6)を調べれば65に行き当たってたのになー。
ということで、<b>2通りの方法で2つの平方数の和で表せる2番めに小さい自然数は65</b>でした(ついでに3番めは85)。<br />
<br />
<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0tag:blogger.com,1999:blog-9245921.post-37196201041194412562014-12-20T23:49:00.000+09:002014-12-22T00:06:33.506+09:00 素数腕立て伏せ Advent Calendar 20日目 #prime_num_pushups<i>素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。<br />
<a href="http://deltam.blogspot.jp/2010/09/blog-post.html" target="_blank">素数腕立て伏せについて : サルノオボエガキ</a></i><br />
<br />
平熱に戻ったし素数腕立て伏せすんぞオラ!<br />
<br />
<b>20日目<br />
37回で勝ち(素数)</b><br />
<br />
病み上がりだからセーブしただけだし。別にパワーダウンしてないし。<br />
<br />
37ってベルヌーイ数に関係があるみたいですね。<br />
<br />
<blockquote>37 is an irregular prime, since it divides the numerator of the Bernoulli number B_32 = -7709321041217/510.<br />
<a href="http://www.wolframalpha.com/input/?i=37">37 - Wolfram|Alpha</a><br />
</blockquote><br />
<br />
そういえば昔にべき乗和の公式を調べてたときにベルヌーイ数を初めてみたんだったなぁ(その時は意味不明でしたが)。<br />
<br />
<br />
<blockquote>ベルヌーイ数は、もともと、連続する整数のべき乗和を定式化する際に、展開係数として導入された。<br />
<br />
(中略)<br />
<br />
一方、日本ではベルヌーイとほぼ同時期に関孝和がべき乗和を定式化し、ベルヌーイ数を発見していた[6]。 そのため、ベルヌーイ数を関・ベルヌーイ数と書いている文献[7]もある。<br />
<a href="http://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%8C%E3%83%BC%E3%82%A4%E6%95%B0#.E3.81.B9.E3.81.8D.E4.B9.97.E5.92.8C.E3.81.AB.E3.82.88.E3.82.8B.E5.B0.8E.E5.85.A5">ベルヌーイ数 - Wikipedia</a><br />
</blockquote><br />
関孝和も同時期に同じ結果を出していたらしい。関さんパネェ。<br />
<br />
<br />
<u>素数腕立て伏せ一言メモ</u><br />
素数腕立て伏せは回数が増えるほど勝ちが困難になるという特徴があるが、裏を返せば回数が少ないほど勝ちが多くなる。<br />
体力が落ちてツライときは無理せず、少ない回数で勝ちを取って気力を得よう。<br />
ハングリー精神は健康になるまで取っておけ!<br />
<br />
<br />
<br />
素数腕立て伏せとは関係ないけど、マンガ版<a href="http://www.amazon.co.jp/gp/product/4063880028/ref=as_li_ss_tl?ie=UTF8&camp=247&creative=7399&creativeASIN=4063880028&linkCode=as2&tag=deltam-22">『天地明察』七巻</a>に出てきた関孝和は意外なキャラで面白かったです。和算がパズルとほぼ同じ時代に代数を考えていた関さんの異才は、同時代の主人公からすればまさに龍のごとしでしょう。<b>(追記:勘違い、七巻じゃまだ関さんは出てこなかった、たぶん八巻で出る)</b><br />
<br />
<iframe src="http://rcm-fe.amazon-adsystem.com/e/cm?lt1=_blank&bc1=000000&IS2=1&bg1=FFFFFF&fc1=000000&lc1=0000FF&t=deltam-22&o=9&p=8&l=as4&m=amazon&f=ifr&ref=ss_til&asins=4063880028" style="width:120px;height:240px;" scrolling="no" marginwidth="0" marginheight="0" frameborder="0"></iframe><br />
<br />
deltamhttp://www.blogger.com/profile/00949008221129941620noreply@blogger.com0