医学英単語は，分解すると覚えやすい！【語源学習法のすゝめ】

全国の医学生のみなさんは，様々な医学用語を英語で覚えることも多いでしょう．その理由は，大学の試験に出題されるからだったり，英語で書かれた論文を読むためだったりします．

医学用語を英語で覚えることに損はありません．一般的に，和訳によって作られた日本語の単語より，英単語の方が体系的にできていることが多いと言われます．

「でも，日本語ですら既に覚えることが多いのに，それにくわえて英語も覚えるとなると大変……」

そう感じている人も多いのではないでしょうか？

そんなあなたに朗報です！

医学英単語の多くは，基本的なパーツを組み合わせてできています．そのため，まずはパーツを知り，そのあとは語源に基づいて単語を学んでゆくことで覚えやすくなります！

例を見てみましょう．

ヘモグロビン hemoglobin の先頭の hemo- は，「血」を意味します．血の赤い色を作っている大事なタンパク質ですから，イメージしやすいですね．

一方，-stasis という接尾辞は，何かをとどめることを意味します．これは，生理学の重要な概念であるホメオスタシスという単語で知られていると思います．

では問題です．hemostasis という単語はどんな意味でしょうか？

答え
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

そうです，「止血」です！

このように，hemo- と -stasis を組み合わせて hemostasis という単語ができていることが分かれば，覚えやすいですね．

ちなみにイギリス英語では haemostasis です．アメリカとイギリスで綴りがちょっとくらい違うのは，仕方ないですね．

別の例も見てみましょう．

コレステロール cholesterol の先頭の chole- は，「胆汁」のことです．英語では，胆汁に関係する単語に chole- が付きます．

では問題です．胆汁が通る管である「胆管」を英語では何というでしょうか？

答え
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

そうです，「bile duct」です！

胆汁は英語で bile と言いますね．これを通す管 duct なので，bile duct です．

続けてもう 1 問いってみましょう．肝臓で作られた胆汁を貯めておく場所である「胆嚢」を英語では何というでしょうか？

答え
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

そうです，「gallbladder」です！

胆汁のことを英語では gall と言います．これを貯めておく場所なので gallbladder です．

いかがだったでしょうか？いくつかの基本的な「パーツ」を覚えておけば，そこから色々な英単語の意味が推測できることが分かりますね！

この「語源学習法」が，全国の医学生のみなさんの助けになれば幸いです✨

ではまた！

論理的思考に基づいて繁栄する生物

風呂に入りながらぼーっと考えていた，この地球とは別のどこかの星にいるかもしれない生き物の話をしたい．

彼らは，生まれたときから器用な手と論理的な思考力，そして脳内に自分の"設計図"データをもっている．

生後しばらくはまず様々なことを体験し，それを論理的に解釈することで自分たちの住む星について多くを理解してゆく．

そして時が経つと，生まれもった自分の設計図データをもとに，器用な手で次の世代（子）を作り出す．このとき，設計図をそのまま用いるとは限らない．その星の環境は必ず変化する．論理的思考に基づいて設計図を修正し，変化に合った子を産む．子にはもちろん，自分（親）ではなく子自身の設計図データを載せる．

会話

彼らは，近くにいる相手の思考を覗くことができる．これにより，ある者が設計図データの大きな改善を発見したら，周囲の者もそれを取り入れることができる．広い星の中，あちらこちらで設計図が書き換わっていけば，いずれ思考のインターフェースも変わってしまい，互いに覗けなくなるかもしれない．そうしたら，それが「種」の定義となるだろう．

群れ

種によっては群れを作るかもしれない．活動したり次の世代を作ったりするのに必要な物質やエネルギーを互いに分け与えれば，より効率的に繁栄できるだろう．

バグ

突然バグった思考が蔓延することで，ある種が全員子孫を残さず自殺したらちょっと面白い．

[[likely]]が役立った話

この記事はstackoverflowで質問した内容の結論をまとめたものです．

正直， [[likely]] attribute なんて今まで一度も使ったことなかったです．

こんなコードを書いた

#include <stdio.h>
#define N 19

int main(void){
    int a[N];
    int ans = 0;

    for(int i = 0; i < N; ++i){
        a[i] = 0;
    }
    for(;;){
        int i;
        ++ans;
        for(i = N - 1; a[i] == 2; --i){
            if(i == 0){
                printf("%d\n", ans);
                return 0;
            }else{
                a[i] = 0;
            }
        }
        ++a[i];
    }
}

これは， 0 以上 3 未満の整数から重複を許して 19 個選ぶやり方 通りを，ループで数え上げて出力するコードです．

これを， gcc でコンパイルして実行時間をはかります．このとき， -O1 オプションを付けた場合と， -O2 オプションを付けた場合の 2 通りためしてみます．

すると，結果は次のようになりました（単位はすべて秒）：

オプション	1回目	2回目	3回目	4回目	5回目	平均
-O1	0.70	0.71	0.69	0.71	0.68	0.70
-O2	1.13	1.11	1.10	1.11	1.09	1.11

-O2 の方が遅い！！びっくりして stackoverflow で質問を投げたら， -O2 で有効になる最適化のうち，-falign-functions -falign-jumps -falign-labels -falign-loopsがどうやら悪い方に働いていると言われました．さらに [[likely]] attribute を付けることも提案されました．

[[likely]] [[unlikely]] って？

[[likely]] は，実行される確率の高い文に付けます．[[unlikely]] は，実行される確率の低い文に付けます．

付けてみた

今回，for(;;)文で無限ループを書いていて， 回はループが回ります． break されるのは最後の一回だけなので，この for 文は「ループが終了する確率より，続く確率の方がはるかに高い」ということになります．

そこで，次のように[[likely]]を付けてみます．

#include <stdio.h>
#define N 19

int main(void){
    int a[N];
    int ans = 0;

    for(int i = 0; i < N; ++i){
        a[i] = 0;
    }
    for(;;) [[likely]] {
        int i;
        ++ans;
        for(i = N - 1; a[i] == 2; --i){
            if(i == 0){
                printf("%d\n", ans);
                return 0;
            }else{
                a[i] = 0;
            }
        }
        ++a[i];
    }
}

すると……

オプション	1回目	2回目	3回目	4回目	5回目	平均
-O1	0.65	0.65	0.66	0.66	0.66	0.66
-O2	0.66	0.65	0.66	0.65	0.66	0.66

おお！ -O2 も速くなった！！

結論

[[likely]]でこんな影響が出ることも，あるんだなぁ

エモいコードについてのメモ

これはキャス（1枠目，2枠目）で話した内容を文字にしたものです．

メジャーの中にマイナー，マイナーの中にメジャー

メジャーキーの曲の中にマイナーコードを一瞬混ぜる，あるいはその逆をすると，エモくなります

例 1：ちいさい秋みつけた
E minor の曲ですが，「めかくし鬼さん手のなる方へ」と「よんでる口笛もずの声」の二箇所で平行調の G major が混ざります．もの寂しい秋の中にわずかな人の温もりが感じられる一瞬を映し出しているようにも感じられます．

例 2：ブラームス，ハイドンの主題による変奏曲
これは逆に B♭ major の曲に平行調の G minor が出てきます．一瞬だけ出てきてそのあとすぐに戻っちゃうあたりが推しポイントです．

例 3：Simon and Garfunkel - Bridge Over Troubled Water
多分他にも同じ進行は多くあると思いますがパッと思いついたのがこれでした， 2 番と 3 番の間の間奏（動画内 3 分くらいのところ）の A♭→A♭m→E♭です．曲の中で一回だけ使うとエモくなるというのが自分の中のイメージです．

例 4：ショパン，遺作
これは短調の曲の最後でフッと長調にして終わるやつです．ずーっと C♯minor で悲しい雰囲気が続く曲ですが，最後の最後で C♯ major になって終わります．このパターンは最近の曲でもよくあると思います．

解決前の属和音に色々な音を重ねる

A minor の曲で E→Am という解決をするとき， E のコードに D の音を付け加えて E7 にするのは割とよくやると思います．ここにさらに F とか C とか A の音を付けてみるとちょいエモくできます．どうせ属音の圧倒的な解決力がどうにかしてくれるので，いくらでも汚くして遊べます．

主音を引きずりまくる

まず右手だけで Am→E→Am という簡単なコードを弾いてみます．次にここに，左手で主音 A を重ねてみます．右手が属和音 E を弾いている間，左手の主音 A が残り続けていると，少し深みが生まれます．こんな風に，コードが進行している間主音を残し続けることでエモが作れます．

曲の最後の和音で遊ぶ

曲の最後を単に主和音で終わらせてしまうとつまらないな，と感じたときには，この主和音の上に別の音を重ねて遊んで見るのも良いでしょう．このときにピタゴラス音階（ 5 度ずつ重ねるやつ）とかが使いやすかったりします．

音を減らす

主和音の 3 つの音から 1 個抜きます．すると単純ながらも印象に残りやすい響きになったりします．

同じメロディーに違うコード

例 1：灼熱スイッチ（灼熱の卓球娘 op 曲）
アニメ放送当時，コード進行がヤバすぎると話題になった op 曲ですね．コード使いがテクニカルなのでなかなか真似できないんですが，この中で真似しやすいところを挙げるとすれば，曲の後半の方に出てくるサビ直前の「夕陽あびてこぶしを高くあげて明日も頑張るとかたく誓うんだ」のコードが，それまでのサビ直前と変わっているところです．メロディーは変わっていないのにコードだけが変わっています．こういうのが好きなんだってばよ！！！

他（汎用性は低い）

• A minor の中の B♭．入れ方は複数ありますが， F→G→Am と来そうなところで F→G→B♭とするのが割と好きだったりします．
• A minor の属和音は E ですが， E→Am の代わりに Em7→Am とするのもうまく使うとめちゃくちゃエモくなります．
• ラフマニノフのヴォカリーズの中の，歌詞で言うと「アアアアーーアアーーー，アーアーーーアーァァアーーー」のところ（どこだよ）．E minor に F の音を混ぜてるところは，本当に何を食って生きてたらそんな音が生めるんだって感じがします．

無料で PDF ファイルが編集できる強力ツール「PDFtk」について

PDF の編集にはお金がかかると思っていませんか？

確かに，たとえば Adobe Acrobat のような有料のソフトウェアも出回っています．しかし， PDF なんて中身はただ /Type /Page とか /Font << /F3 212 0 R >> とか書かれてるだけのファイルに過ぎないのですから，無料の編集ソフトが存在しないわけがありません．そこで今回紹介するのが， PDFtk という無料ソフトです． PDF の結合や分割，重ね合わせなどができます．

インストール方法

ここから，自分の OS に合ったインストーラをダウンロードします*1(Windows 10 は存在しないので代わりに Windows XP/Vista/7/8 を選択します)．インストーラを起動して，言われるがままに「Next」を押し続けると……あれ？インストールが完了したのに PDFtk が起動しないし，デスクトップを見てもそれらしいアイコンがありません．どうしたのでしょう．

実は， PDFtk はコマンドラインツールです(GUI のものは有料です)． Mac/Linux ならターミナル， Windows なら PowerShell を起動して，

$ pdftk --version

と打ち込んでみましょう(最初の「$」は，シェルが入力を受け付けていることを表すもので，あなたが入力するのは「pdftk」以降です．環境によっては「$」ではなく「>」だったり「%」だったりするかもしれません)．インストールに成功していれば，ここで

pdftk 2.02 a Handy Tool for Manipulating PDF Documents
Copyright (c) 2003-13 Steward and Lee, LLC - Please Visit: pdftk.com
This is free software; see the source code for copying conditions. There is
NO warranty, not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE

のようなメッセージが出力されるはずです．もしここで

用語 'pdftk' は、コマンドレット、関数、スクリプト ファイル、または操作可能なプログラムの名前として認識されません。

や

command not found: pdftk

といったエラーが出力されていれば，インストールに失敗しています．

パソコンの中にある PDF ファイルをコマンドラインから見る方法

シェルの扱いに慣れていない人のための項目です，普段から使っている人は読み飛ばしてください．

シェルには，カレントディレクトリという概念が存在します．コンピュータの中にはファイルの階層構造が形成されていて，たとえば Pictures というディレクトリ(フォルダともいいます)の中に写真が入っていたり， Downloads というディレクトリの中にダウンロードしたファイルが入っていたりします．シェルを使うとき，あなたは常に，何らかのディレクトリを基点として，その中や外にあるファイルを操作することになります．今操作の基点となっているディレクトリのことを，カレントディレクトリといいます．

今あなたがどのディレクトリにいるのかは，

$ pwd

と入力することで知ることができます(繰り返します，「$」自体は入力しないでください)． Windows であれば「C:」， Mac/Linux であれば「/」から始まるパスが表示されたはずです．そこがあなたが今いる場所です．

PDF ファイルを操作するときには，そのファイルが含まれるディレクトリまで移動したい(カレントディレクトリを移動させたい)です．これには 2 つの方法があります．

まず 1 つ目(この方法は Windows の場合しか知らないのですが，他でも多分可能です)． Windows ではフォルダをクリックするとエクスプローラが開き，フォルダ内のファイル一覧が表示されると思います．その状態で，左上の「ファイル」から「Windows PowerShell を開く」をクリックすると， PowerShell が開くでしょう．その状態で $ pwd と打つと，今度はエクスプローラで開いていたディレクトリがカレントディレクトリになっているはずです．

2 つ目は， cd を使う方法です．たとえば，カレントディレクトリ直下にある Documents というディレクトリに移動したければ，

$ cd Documents

と打つと移動できます．また， C:\Users\example\Documents\ というディレクトリに移動したければ，

$ cd C:\Users\example\Documents\

と打っても移動できます．

さて，こうして 2 通りのやり方のいずれかでカレントディレクトリを移動できたら，

$ ls

と打ってみてください．ディレクトリ直下にあるファイルの一覧が表示されるはずです．この一覧の中にあなたが編集したい PDF ファイルが含まれているかどうかを，

$ ls (ファイル名)

で確認しましょう．

PDFtk の使用例

まずはいくつか例を紹介します． a.pdf と b.pdf を結合して c.pdf にしたければ

$ pdftk a.pdf b.pdf cat output c.pdf

とします．逆に， 100 ページある a.pdf を 1 ページの PDF ファイル 100 個に分割したければ，

$ pdftk a.pdf burst output bursted_

とします(bursted_pg_0001.pdf から bursted_pg_0100.pdf までのファイルが作られます)．

PDFtk の詳細な用法は少々複雑ですが，たいていは

$ pdftk (入力元ファイル) (操作) output (出力先ファイル)

だけで事足ります．上の 2 つの例では，「(操作)」の部分がそれぞれ「cat」，「burst」だったわけです．

cat

cat は実はもう少し高機能です．複数個の PDF ファイルを連結するだけでなく，複数個の PDF ファイルの「好きなページ範囲を」「好きな順番で」連結できます．そのためには， cat の直後に範囲の指定を続けます．

まず， a.pdf が 20 ページの PDF ファイルだったとき，

$ pdftk a.pdf cat 5 output b.pdf

とすると， b.pdf は a.pdf から 5 ページ目を切り出した 1 ページの PDF ファイルになります．

$ pdftk a.pdf cat 5-10 output c.pdf

とすると， c.pdf は a.pdf から 5-10 ページを切り出した 6 ページの PDF ファイルになります．

$ pdftk a.pdf cat 5-10 15-20 output d.pdf

とすると， d.pdf は a.pdf の 5-10 ページと 15-20 ページを連結した計 12 ページの PDF ファイルになります． 20 ページ目は a.pdf の最後のページなので，

$ pdftk a.pdf cat 5-10 15-end output d.pdf

としても同じです．

次に，複数個の PDF ファイルについてこれを行います．このためには，入力元ファイルを指定するときに，一時的に名前を付けてやります．たとえば

$ pdftk A=hoge.pdf B=fuga.pdf C=piyo.pdf (操作) output (出力ファイル)

とすると， 3 つの PDF ファイル hoge.pdf，fuga.pdf，piyo.pdf に対し，それぞれ一時的に A，B，C という名前が付けられ，「(操作)」の部分で用いることができるようになります．

これを使って， hoge.pdf の 1-2 ページ目， fuga.pdf の 3-4 ページ目， piyo.pdf の 5-6 ページ目をつなげて全 6 ページの PDF ファイルを作るには，

$ pdftk A=hoge.pdf B=fuga.pdf C=piyo.pdf cat A1-2 B3-4 C5-6 output out.pdf

とします．

練習問題：100 ページの hoge.pdf と， 1 ページの fuga.pdf があります． hoge.pdf の 30 ページ目を fuga.pdf で差し替え，新たに 100 ページの PDF ファイルを作るにはどうすれば良いでしょうか．

cat には他にもいくつか機能があります．ページ範囲が「10-5」のように逆転していれば，「10 9 8 7 6 5」とページが逆順になります．ページ範囲を指定するところで「5-11odd」や「2-10even」のように odd/even を付けると，奇数ページ目/偶数ページ目だけが選択され，それぞれ「5 7 9 11」と「2 4 6 8 10」のようになります．「1-10south」のように範囲指定の後に north/south/east/west/left/right/down を付けると，ページが回転します*2．

burst

burst は， PDF ファイル全体を 1 ページずつに分割します．分割された PDF ファイルの名前は，デフォルトで末尾に pg_(ページ番号).pdf が付きますが， C 言語の printf と同じ形式で指定することもできます．たとえば

$ pdftk a.pdf burst output bursted%02d.pdf

とすると， bursted01.pdf ， bursted02.pdf ，…という名前になります．

background/multibackground/stamp/multistamp

これらのコマンドを使うと， 1 つの PDF ファイルの前面/背面に別の PDF ファイルを重ね合わせることができます．

$ pdftk (入力ファイル) background (重ねるファイル) output (出力ファイル)

のように，直後に重ねる PDF ファイルの名前を続ける必要があります．たとえば，全ページにハンコを押さなければいけない書類 a.pdf と，スキャンされたハンコのデータ b.pdf があったとき，

$ pdftk a.pdf stamp b.pdf output c.pdf

とすると，全ページにハンコが押された書類 c.pdf が完成します．

background/multibackground を使うと，重ねるファイルが入力ファイルの背面に置かれます．逆に stamp/multistamp を使うと重ねるファイルが入力ファイルの前面に置かれます．

background/stamp を使うと，重ねるファイルの 1 ページ目が，入力ファイルの全ページに重ねられます．一方 multibackground/multistamp を使うと，重ねるファイルの 1, 2, 3, …ページ目が，それぞれ入力ファイルの 1, 2, 3, …ページ目に重ねられます．

help

以上で大体基本的な使い方は網羅していると思います．もっと詳細な使い方を見るには，

$ pdftk --help

とすると，英語のヘルプが表示されます．

無料でもちゃんとできる！

以上， PDF ファイルを編集できる無料ソフト PDFtk の紹介でした．

この記事が誰かの役に立てればこの上なく幸せです！

*1:Mac/Linux であれば， brew や apt や yum などで pdftk あるいは pdftk-java と打っても入ります．

*2:east/right は右， west/left は左に倒れ， south/down は 180 度回転します． pdftk を 2 回実行して right を 2 回かけると 180 度回転しますが， east は何度かけても右に倒れた状態のままです．すなわち， north/south/east/west は絶対的ですが， left/right/down は相対的です．ページが回転した状態の PDF ファイルは， north で元に戻すことができます．

離散フーリエ変換を O(n log n) で行うアルゴリズム

離散フーリエ変換とは，長さ の数列 から長さ の数列 への変換で，各 について次のように定義されます．

ただし は で定義され， 乗すると 1 になる虚数(の1つ)です．また，逆離散フーリエ変換はその逆変換ですが，式はよく似ています． 逆離散フーリエ変換が離散フーリエ変換の逆変換になっていることの証明は容易です．

今回はこれを任意の について で計算するアルゴリズムを考えます．

Cooley-Tukey のアルゴリズム

Cooley-Tukey のアルゴリズムは離散フーリエ変換を行う最も有名なアルゴリズムで， が合成数のときに限って使えます．例として， のときを考えます． の離散フーリエ変換 は，定義によれば次のようになります．

さて，ここで を の形に因数分解します．まず ， としてみましょう．そして，右辺にある を，添字を で割った余りで並び替えます． ここで， であることを利用すると， の肩の数字が次のように書き換えられます． この状態で式を次のようにくくると，同じ形がたくさん出てきます． であることに注意すると， は長さ の数列 の離散フーリエ変換であり， は長さ の数列 の離散フーリエ変換であり， は長さ の数列 の離散フーリエ変換であるということに気付きます．これを用いてもとの式を書き換えると となり，さらにこれを並べ替えると となります．今度は ，， であることに注意すると， は長さ の数列 の離散フーリエ変換であり， は長さ の数列 の離散フーリエ変換であるということに気付きます．つまり，長さ の数列の離散フーリエ変換が，長さ の数列の離散フーリエ変換 回と，長さ の数列の離散フーリエ変換 回によって行えるわけです．
今度は， ， としてみましょう．同様の変形により となるので， の離散フーリエ変換を とし， の離散フーリエ変換を とすると， は の離散フーリエ変換であり， は の離散フーリエ変換であり， は の離散フーリエ変換であるわけです．

以上より，長さ の数列の離散フーリエ変換は，長さ の数列の離散フーリエ変換を 回行ったあとに，長さ の数列の離散フーリエ変換を 回行うことでできることが分かりました．これを繰り返していくことで， が小さな素数の積で構成されているときに で離散フーリエ変換を行うのが，Cooley-Tukey のアルゴリズムです． の最小の素因数を としてこれを繰り返すやり方を DIF (周波数間引き)， の最小の素因数を としてこれを繰り返すやり方を DIT (時間間引き)といいます．

特に が のべき乗のときの DIT が広く知られています．

フーリエ変換の性質

さて，次に が素数のときを考えるのですが，その前に離散フーリエ変換の重要な性質について見てみます．それは「畳み込み定理」と呼ばれるものです．

長さが であるような 2 つの数列 と について，その畳み込み を次のように定義します．

ただし， は と等価とします．たとえば なら畳み込みは次のようになります． このとき， の離散フーリエ変換をそれぞれ とすると任意の について が成り立つというのが畳み込み定理です．証明は次のようにできます． (ただし途中でシグマの下の数が上の数より大きくなってしまうところはその総和の結果を とします)

2020/10/25 追記：熨斗さんからより分かりやすい証明をいただきました．
多項式同士の mod を次のように定義します．

， ， を の多項式とする．ある多項式 が存在して が の恒等式となるとき， と は を法として合同であるといい， と書く．

このとき，次が成り立ちます．

の多項式 ， ， が を満たすとき， であるような任意の について が成り立つ．

さて， が と の巡回畳み込みであるとき，



とおくと が成り立ちます． は を満たすので， すなわち となるわけです．

原始根

さて，突然ですが数論の話をします． を素数とし， を 以上 未満の自然数とします．このとき， を満たす最小の自然数 を， を法とした の「位数」といい， と書きます． の位数 は常に の約数です．なぜなら，フェルマーの小定理より であり，もし でないと仮定すると を で割った余り は を満たすので， ではなく が の位数となるはずだからです．

「 が の原始根である」とは， であることをいいます．

が の原始根であるとき， を で割った余りは を並べ替えたものになります．なぜなら任意の について より だからです．

が の原始根かどうかは，で判定できます．もし が原始根でない，すなわち ならば， は全て と合同になるはずです．ということは，逆に の各素因数 について を調べ上げれば，その中に必ず と合同なものが含まれるはずです．もし含まれなければ， は の原始根です．

任意の奇素数 に少なくとも 1 つ原始根が存在します．証明は難しいので省略しますが，整数 が の原始根でなければ， のいずれとも合同でない数 をとってくることで， の位数が の位数よりも大きくなります．これを繰り返すと，いつか位数が であるような数が見つかります(ただし，実際に原始根を求めるコードを書くときは， 以上 未満の自然数について順に原始根かどうか確かめていくだけで十分高速に動作します)．

Rader のアルゴリズム

離散フーリエ変換の話に戻ります．Rader のアルゴリズムは， が 以上の素数のときに使えるアルゴリズムです． は合成数なので，長さ の数列の離散フーリエ変換を長さ の数列の離散フーリエ変換で表し， Cooley-Tukey のアルゴリズムを適用します．

例として， の場合を考えます．

まず の原始根 を発見します．今回は が原始根なので とします．このとき， を で割った余りはそれぞれ なので， 〜 について次のような書き換えが可能です． 少し混乱しますが落ち着いて確認しましょう．たとえば における の係数というのはもともと で，この右肩の という値は という計算によって得られたものでした．今度はこれが ， という式で書き換えられて， になっています．こうして掛け算が指数の足し算になったところで，さらに を使うことで，最終的には となります．これはまさしく，数列 と数列 の畳み込みです．よって，これらを離散フーリエ変換して積を計算し，逆離散フーリエ変換でもとにもどしてやれば計算できます．

よって，Cooley-Turkey のアルゴリズムと Rader のアルゴリズムを組み合わせて使うことで，任意の自然数 に対して で離散フーリエ変換を計算することができます．

最後まで読んでくださってありがとうございましたm(_ _)m

デバッグ出力に役立つ ostream_joiner とは

こんにちは．

今日は C++ コンテナの中身を簡単にデバッグ出力できる ostream_joiner を紹介します．

ostream_joiner は experimental/iterator をインクルードすることで， std::experimental::ostream_joiner として使えるようになります．

#include <experimental/iterator>
#include <vector>
#include <iostream>

using namespace std;
using namespace experimental;

ostream_joiner<const char *> debug = make_ostream_joiner(cout, " ");

int main(){
	vector<int> v = {1, 2, 3, 4, 5};

	copy(v.begin(), v.end(), debug);
	cout << endl;
}

これで

1 2 3 4 5

と出力されます． make_ostream_joiner の第 2 引数で " " の代わりに ", " を指定すればカンマ区切りになります(最後の要素の後にカンマは入りません)．

set とかもいけます．

	set<int> s;
	s.insert(5);
	s.insert(2);
	s.insert(3);
	s.insert(1);
	s.insert(4);

	copy(v.begin(), v.end(), debug);
	cout << endl;

出力は同じく

1 2 3 4 5

です．

わりと便利そう．