高速フーリエ変換
先日, 調和解析の器械のことを調べていて, フーリエ変換をやってみる必要があった. データの個数の少い例なので, プログラムは簡単に書ける. 書きなが, 学生のころ(1953年ころ)に計算させられたことを思い出した. あの時に比べるといまは極楽だな. ところで高速フーリエ変換(FFT)というのがあって, 私は30年も前に, 高橋秀俊先生の追悼文を「コンピュータソフトウェア」誌に寄稿したときに, 高橋先生がFFTのプログラミングに熱中されていたことにも触れた. (この記事はCiNiiで探すと見つかる.) 当時の雑誌を取り出してみると, そのプログラムが掲載されている. もとは東大大型計算機センターのライブラリプログラムだからFortranで書かれれていたのを, 私が当時使っていたFranz Lispに書き直したものであった. 添字の名前などにはいかにもFortranという気分が残っているが.
素因数探し
大きい数が素数かどうか知りたいことがある. 素数と分かればそれでよし. 素数でなければ, 素因数が知りたくなるのが人情だ. 素数であるかは素数性のテストがあるので, それによればよい. 素因数探しはそれに較べ困難である. Knuth先生のTAOCP第2巻の4.5.4項は素因数に分解する話題である. 最初のアルゴリズム4.5.4Aは2,3,5,...と順に割ってみる方法である. 素数を全部覚えているわけにもいかぬから, 2,3,5のあとは4,2,4,2,...と足して疑似素数を発生する. この辺はもう少し凝れるが, とりあえずはここまで. その後にあるアルゴリズム4.5.4Cはちょっと面白いので, 今回はその話にしよう. TAOCPによると, この方法は1643年にFermatが使ったものらしい. 分解したい奇数nが与えられた時, このアルゴリズムは下の図の左上のように, 正の整数aとbにつ
正方化長方形
Tne New Martin Gardner Mathematical Libraryの2冊目にSquaring the Squareという話題があった. 正方化正方形とでもいおうか. 正方形を相異る正方形で埋め尽す問題である. 同じ正方形で埋め尽すなら22が4とか33が9とかに分割すれば出来るが, 相異るとなると出来るかどうか不明である. 本書によると1936年頃, ケンブリッジ大学の4名の学生が挑戦したらしい. 周囲が正方形なら非常に困難だが, 相異る正方形で長方形を敷き詰めるのは, 比較的容易らしい. 下の図の左がその一例で, 横61, 縦69の長方形が相異る正方形で敷き詰めてある. 正方形の中の数が, 正方形の辺の長さで, 最小のは2と書いてある. こういう図形を正方化長方形(squared rectangle)という. 例えばこの上に61掛ける61の正方形, 横に69掛ける69の
Dijkstraのプログラム
オランダの計算機科学者 Edsger W. Dijkstra は, ものを書くのが好きで, BachのBWVにならってEWD何番というドキュメントが沢山ある. (http://www.cs.utexas.edu/~EWD/ ) それを眺めていたら, EWD221に Raw code for computing DeBruijn-sequence というのがあった. 例えば00011101がB(2,3)で, 最初のパラメータ2は, 記号が0と1の2種類ということ, 後のパラメータ3は, 3個ずつとると, 全てのパターンが得られるということである. つまり先頭から1ビットずつずらしながら, 3ビットとると 000 001 011 111 110 101 010 100 (最後の2つは, 3ビットとれないので, 始めに循環している)つまり上から順に0, 1, 3, 7, 6, 5, 2, 4とす
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
再帰曲線
