Skip to content

Instantly share code, notes, and snippets.

@bellbind

bellbind/dft.mjs

Last active April 24, 2019 12:55
Show Gist options
  • Save bellbind/fee0ef8fd376a4b56cf4e2510baf45f1 to your computer and use it in GitHub Desktop.
Save bellbind/fee0ef8fd376a4b56cf4e2510baf45f1 to your computer and use it in GitHub Desktop.
Download ZIP
[jupyter][JavaScriot][Japanese] Understanding FFT
Raw
dft.mjs
// complex number arithmetic for DFT/FFT
function expi(theta) {return [Math.cos(theta), Math.sin(theta)];}
function iadd([ax, ay], [bx, by]) {return [ax + bx, ay + by];}
function imul([ax, ay], [bx, by]) {
return [ax * bx - ay * by, ax * by + ay * bx];
}
function idivr([x, y], r) {return [x / r, y / r];}
function isum(cs) {return cs.reduce((s, c) => iadd(s, c), [0, 0]);}
// DFT
function dftc(c, T) {
return [...Array(c.length).keys()].map(i => isum(
c.map((cn, n) => imul(cn, expi(T * n * i)))
));
}
export function dft(f) {
const N = f.length, T = -2 * Math.PI / N;
return dftc(f, T);
}
export function idft(F) {
const N = F.length, T = 2 * Math.PI / N;
return dftc(F, T).map(z => idivr(z, N));
}
Raw
fft-rec.js
// complex number arithmetic for DFT/FFT
function expi(theta) {return [Math.cos(theta), Math.sin(theta)];}
function iadd([ax, ay], [bx, by]) {return [ax + bx, ay + by];}
function isub([ax, ay], [bx, by]) {return [ax - bx, ay - by];}
function imul([ax, ay], [bx, by]) {
return [ax * bx - ay * by, ax * by + ay * bx];
}
function idivr([x, y], r) {return [x / r, y / r];}
// FFT: Cooley-Tukey FFT
function fftrec(c, T, N = c.length) {
if (N === 1) return c;
const l = fftrec(c.filter((_, i) => i % 2 === 0), T, N / 2);
const r = fftrec(c.filter((_, i) => i % 2 === 1), T, N / 2);
const re = r.map((ri, i) => imul(ri, expi(T / N * i)));
const laddr = l.map((li, i) => iadd(li, re[i]));
const lsubr = l.map((li, i) => isub(li, re[i]));
return laddr.concat(lsubr);
}
function fft0(f) {return fftrec(f, -2 * Math.PI);}
function ifft0(F) {return fftrec(F, 2 * Math.PI).map(z => idivr(z, F.length));}
// ordering
{
function reorder(c, N = c.length) {
if (N === 1) return c;
const l = reorder(c.filter((_, i) => i % 2 === 0), N / 2);
const r = reorder(c.filter((_, i) => i % 2 === 1), N / 2);
return l.concat(r);
}
function toBin(k) {
return n => n.toString(2).padStart(k, "0");
}
console.log([0,1,2,3].map(toBin(2)));
console.log(reorder([0,1,2,3]).map(toBin(2)));
console.log([0,1,2,3,4,5,6,7].map(toBin(3)));
console.log(reorder([0,1,2,3,4,5,6,7]).map(toBin(3)));
console.log([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15].map(toBin(4)));
console.log(reorder([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]).map(toBin(4)));
}
// example
{
const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2,3];
const f0 = fr0.map(r => [r, 0]);
const F = fft0(f0);
const f1 = ifft0(F);
const fr1 = f1.map(([r]) => r);
console.log("fr0:", fr0);
console.log("F:", F);
console.log("f1:", f1);
console.log("fr1:", fr1.map(Math.round));
}
Raw
fft.mjs
// complex number arithmetic for DFT/FFT
function conj([x, y]) {return [x, -y];}
function expi(theta) {return [Math.cos(theta), Math.sin(theta)];}
function iadd([ax, ay], [bx, by]) {return [ax + bx, ay + by];}
function isub([ax, ay], [bx, by]) {return [ax - bx, ay - by];}
function imul([ax, ay], [bx, by]) {
return [ax * bx - ay * by, ax * by + ay * bx];
}
function idivr([x, y], r) {return [x / r, y / r];}
// bit operations for FFT
function revBit(k, n0) {
if (k === 1) return n0;
const s1 = ((n0 & 0xaaaaaaaa) >>> 1) | ((n0 & 0x55555555) << 1);
if (k === 2) return s1;
const s2 = ((s1 & 0xcccccccc) >>> 2) | ((s1 & 0x33333333) << 2);
if (k <= 4) return s2 >>> (4 - k);
const s3 = ((s2 & 0xf0f0f0f0) >>> 4) | ((s2 & 0x0f0f0f0f) << 4);
if (k <= 8) return s3 >>> (8 - k);
const s4 = ((s3 & 0xff00ff00) >>> 8) | ((s3 & 0x00ff00ff) << 8);
if (k <= 16) return s3 >>> (16 - k);
const s5 = ((s4 & 0xffff0000) >>> 16) | ((s4 & 0x0000ffff) << 16);
return s5 >>> (32 - k);
}
function isPowerOf2(n) {return (n & (n - 1)) === 0;}
function nextPowerOf2(n) {
return isPowerOf2(n) ? n : 1 << (32 - Math.clz32(n));
}
// FFT: Cooley-Tukey FFT
function fftin1(c, T, N = c.length) {
const k = Math.log2(N);
const rec = c.map((_, i) => c[revBit(k, i)]);
for (let Nh = 1; Nh < N; Nh *= 2) {
T /= 2;
for (let s = 0; s < N; s += Nh * 2) {
for (let i = 0, li = s, ri = s + Nh; i < Nh; i++, li++, ri++) {
const l = rec[li], re = imul(rec[ri], expi(T * i));
[rec[li], rec[ri]] = [iadd(l, re), isub(l, re)];
}
}
}
return rec;
}
function fft1(f) {return fftin1(f, -2 * Math.PI);}
function ifft1(F) {return fftin1(F, 2 * Math.PI).map(z => idivr(z, F.length));}
// FFT: Blustein's algorithm
function fftin2(c, T, N = c.length) {
const Nd = N * 2;
const bc = c.map((_, n) => expi(T * n * n / Nd));
const b = bc.map(conj);
const a = c.map((cn, n) => imul(cn, bc[n]));
const N2 = nextPowerOf2(Nd - 1);
const a2 = a.concat(Array(N2 - N).fill([0, 0]));
const b2 = b.concat(Array(N2 - Nd + 1).fill([0, 0]), b.slice(1).reverse());
const A2 = fft1(a2);
const B2 = fft1(b2);
const AB2 = A2.map((A2n, n) => imul(A2n, B2[n]));
const ab2 = ifft1(AB2);
return bc.map((bcn, n) => imul(bcn, ab2[n]));
}
export function fft(f) {
const N = f.length, T = 2 * Math.PI;
const fftin = isPowerOf2(N) ? fftin1 : fftin2;
return fftin(f, -2 * Math.PI);
}
export function ifft(F) {
const N = F.length, T = 2 * Math.PI;
const fftin = isPowerOf2(N) ? fftin1 : fftin2;
return fftin(F, T).map(z => idivr(z, N));
}
Raw
main-large.mjs
// $ node --experimental-modules main.mjs
import {fft, ifft} from "./fft.mjs";
{
// 15 elements example
const fr0 = [...Array(1024 * 1024).keys()].map(i => Math.sin(i) * i);
const f0 = fr0.map(r => [r, 0]);
console.time("fft-ifft");
const F = fft(f0);
const f1 = ifft(F);
console.timeEnd("fft-ifft");
const fr1 = f1.map(([r]) => r);
}
Raw
main.mjs
// $ node --experimental-modules main.mjs
import {dft, idft} from "./dft.mjs";
import {fft, ifft} from "./fft.mjs";
{
// 15 elements example
const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2];
const f0 = fr0.map(r => [r, 0]);
const F = dft(f0);
const f1 = idft(F);
const fr1 = f1.map(([r]) => r);
console.log("fr0:", fr0);
console.log("F:", F);
console.log("f1:", f1);
console.log("fr1:", fr1.map(Math.round));
}
{
// 15 elements example
const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2];
const f0 = fr0.map(r => [r, 0]);
const F = fft(f0);
const f1 = ifft(F);
const fr1 = f1.map(([r]) => r);
console.log("fr0:", fr0);
console.log("F:", F);
console.log("f1:", f1);
console.log("fr1:", fr1.map(Math.round));
}
Display the source blob
Display the rendered blob
Raw
understanding-fft.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 高速フーリエ変換FFTを理解する\n",
"\n",
"この文書は、離散フーリエ変換DFTの理解をもとに、高速フーリエ変換FFTの振る舞いを理解することを目標とするものです。\n",
"\n",
"はじめにDFTが何をするものかを簡単に説明し、そのDFT処理をJavaScriptコードに書き下し、FFT実装の検証対象となる具体例でのDFT実行結果を示します。\n",
"そして、再帰版FFT実装を天下り的に提示し、具体例を用いてFFTの中で何が行われるかを解析します。\n",
"最後に、この解析結果にもとづいて、ループ版FFTを導出します。\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. 離散フーリエ級数(DFT)\n",
"\n",
"**離散フーリエ変換(Discrete Fourier Transform, DFT)** は、一定期間の時系列の数値列を、その期間を周期的に繰り返す**合成波**とみなし、その周波数成分の**複素数**値の列(低周波数から高周波数の順)を算出する仕組みです。\n",
"\n",
"各周波数における複素数値のうち、実数成分が偶関数であるcos波の係数であり、虚数成分が奇関数であるsin波の係数となります。\n",
"この**係数の量**が、時系列データの分析のために用いることができます。たとえば、一番大きい係数の周波数を取り出して音階を算出する、などが行えます。\n",
"\n",
"離散フーリエ変換では、**時系列データがN個**な場合、区間Nで1/2周期とする周波数を基本に、0倍(定数成分)からN-1倍までの**N個の周波数成分**を算出します。\n",
"時系列データを$f(t), t = 0 \\dots N-1$、周波数成分を$F(k), k=0 \\dots N-1$とすると、この関係は数式で以下のようになります。\n",
"\n",
"$$\n",
"\\begin{align}\n",
"F(k) = & \\sum^{N-1}_{n=0} f(n) \\exp(\\frac{-2 \\pi i}{N} n k) \\\\\n",
"f(t) = & \\frac{1}{N} \\sum^{N-1}_{n=0} F(n) \\exp(\\frac{2 \\pi i}{N} n t) \\\\\n",
"\\end{align}\n",
"$$\n",
"\n",
"$f$も$F$も**N要素の複素数値配列**として、前者の右辺の計算で$F(k)$計算することを「**離散フーリエ変換(IFT)**」、\n",
"後者の右辺の計算で$f(t)$を計算することを、「**逆離散フーリエ変換(Inverse DFT,IDFT)**」と呼びます。\n",
"\n",
"右辺にある$\\exp(i\\theta)$の部分は複素数であり、オイラーの公式$\\exp(i\\theta) = cos{\\theta} + i sin{\\theta}$となります。\n",
"離散フーリエ変換のプログラミングでは、計算でsinやcosを使い、実数成分と虚数成分のペアとして、各成分ごとにコーディングすることも多いです。\n",
"この場合、複素数の足し算と掛け算を、以下のように、各成分ごとに行います。\n",
"\n",
"$$\n",
"\\begin{align}\n",
"a + b = & (a_x + i a_y) + (b_x + i b_y) \\\\\n",
" = & (a_x + b_x) + i(a_y + b_y) \\\\\n",
"a \\times b = & (a_x + i a_y) \\times (b_x + i b_y) \\\\\n",
" = & (a_x \\times b_x - a_y \\times b_y) + i(a_x \\times b_y + a_y \\times b_x) \\\\\n",
"\\end{align}\n",
"$$\n",
"\n",
"この実数虚数成分を分けての計算の場合には、さらに「時系列データは実数値のみ」として、以下のように虚数部の計算を省くこともあります(ただし、ここではこの実数限定な実装は行いません)。\n",
"\n",
"- DFT: $f(t)$の虚数部が0であることから、$exp(i)$の複素数との積は、実数部虚数部ともに$f(t)$をかけるだけにする\n",
"- IDFT: $f(t)$の実部側($a_x \\times b_x - a_y \\times b_y$)のみ計算する"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. JavaScriptでのDFT実装コード\n",
"\n",
"まず、数値２要素`Array`を複素数として、複素数計算のヘルパーを用意します。\n",
"$\\exp(i\\theta)$は、実数`theta`を引数に取り、複素数を返す関数`expi(theta)`として用意します。\n",
"$\\sum$に対応するものとして、複素数配列`cs`の総和を取る関数`isum(cs)`も用意します。"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"function expi(theta) {return [Math.cos(theta), Math.sin(theta)];}\n",
"function iadd([ax, ay], [bx, by]) {return [ax + bx, ay + by];}\n",
"function isub([ax, ay], [bx, by]) {return [ax - bx, ay - by];}\n",
"function imul([ax, ay], [bx, by]) {return [ax * bx - ay * by, ax * by + ay * bx];}\n",
"function isum(cs) {return cs.reduce((s, c) => iadd(s, c), [0, 0]);}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"複素数の時系列データ`f`を受け取り、複素数の周波数成分配列を返すDFT関数`dft(f)`は、以下のようになります:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"function dft(f) {\n",
" const N = f.length, T = -2 * Math.PI / N;\n",
" return [...Array(N).keys()].map(k => isum(\n",
" f.map((fn, n) => imul(fn, expi(T * n * k)))\n",
" ));\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"複素数の周波数成分配列`F`を受け取り、複素数の時系列データを返すIDFT関数`idft(F)`は、以下のようになります:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"function idft(F) {\n",
" const N = F.length, T = 2 * Math.PI / N;\n",
" return [...Array(N).keys()].map(t => isum(\n",
" F.map((Fn, n) => imul(Fn, expi(T * n * t)))\n",
" )).map(([r, i]) => [r / N, i / N]);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"以下、実数値の時系列データ`fr0`を用意し、複素数化した`f0`を用いて、DFT，IDFTを行う実行例です:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"fr0: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2, 3 ]\n",
"F: [ [ 107, 0 ],\n",
" [ 23.295891661412693, 51.72985580737281 ],\n",
" [ -53.54772721475247, 42.96194077712561 ],\n",
" [ -49.21391810443097, -25.674384455895552 ],\n",
" [ -7.869471018244225e-14, -59 ],\n",
" [ 49.79970454205781, -24.2601708935226 ],\n",
" [ 35.54772721475254, 48.96194077712551 ],\n",
" [ -19.8816780990393, 53.14406936974603 ],\n",
" [ -63, 9.583546756334772e-14 ],\n",
" [ -19.881678099039497, -53.14406936974596 ],\n",
" [ 35.54772721475236, -48.961940777125726 ],\n",
" [ 49.799704542057995, 24.260170893522123 ],\n",
" [ 2.3608413054732673e-13, 58.99999999999999 ],\n",
" [ -49.21391810443097, 25.67438445589565 ],\n",
" [ -53.54772721475294, -42.96194077712513 ],\n",
" [ 23.29589166141229, -51.72985580737299 ] ]\n",
"f1: [ [ 0.9999999999999822, -7.993605777301127e-15 ],\n",
" [ 2.9999999999999187, 3.68594044175552e-14 ],\n",
" [ 4.000000000000027, 6.17284001691587e-14 ],\n",
" [ 2.0000000000000044, 1.9095836023552692e-14 ],\n",
" [ 5.000000000000019, -8.659739592076221e-15 ],\n",
" [ 5.999999999999996, -1.509903313490213e-14 ],\n",
" [ 1.9999999999999831, 2.2426505097428162e-14 ],\n",
" [ 3.999999999999982, 3.907985046680551e-14 ],\n",
" [ -1.2434497875801753e-14, 8.704148513061227e-14 ],\n",
" [ 1.000000000000095, 1.9539925233402755e-14 ],\n",
" [ 3.0000000000000027, -1.865174681370263e-14 ],\n",
" [ 4.000000000000051, -1.9539925233402755e-14 ],\n",
" [ 5.000000000000107, -1.2212453270876722e-14 ],\n",
" [ 61.99999999999999, -2.816635813474022e-13 ],\n",
" [ 1.9999999999999196, -3.6415315207705135e-14 ],\n",
" [ 3.000000000000007, -1.3766765505351941e-14 ] ]\n",
"fr1: [ 1, 3, 4, 2, 5, 6, 2, 4, -0, 1, 3, 4, 5, 62, 2, 3 ]\n"
]
}
],
"source": [
"{\n",
" const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2,3];\n",
" const f0 = fr0.map(r => [r, 0]);\n",
" \n",
" const F = dft(f0);\n",
" const f1 = idft(F);\n",
" const fr1 = f1.map(([r]) => r);\n",
" \n",
" console.log(\"fr0:\", fr0);\n",
" console.log(\"F:\", F);\n",
" console.log(\"f1:\", f1);\n",
" console.log(\"fr1:\", fr1.map(Math.round));\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"DFTしたものをIDFTし誤差を丸めた`fr1`は、もとの値`fr0`の値にもどっているのが確認できました(ただし、0の符号を除く)。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. DFTとIDFTの計算部分の共通化\n",
"\n",
"DFTとIDFTの処理の違いは、`expi`に渡す`T`の符号が違う部分と、IDFTの最後のNで割る部分だけです。\n",
"\n",
"この共通部分のコードを`dftc(c, T)`としてまとめると、以下のようになります。\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"function dftc(c, T) {\n",
" return [...Array(c.length).keys()].map(i => isum(\n",
" c.map((cn, n) => imul(cn, expi(T * n * i)))\n",
" ));\n",
"}\n",
"\n",
"function dft(f) {\n",
" const N = f.length, T = -2 * Math.PI / N;\n",
" return dftc(f, T);\n",
"}\n",
"function idft(F) {\n",
" const N = F.length, T = 2 * Math.PI / N;\n",
" return dftc(F, T).map(([r, i]) => [r / N, i / N]);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"FFTでも逆変換との計算部分の共通化をしたものとして、プログラムを考えていきます。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. 高速フーリエ変換(FFT)\n",
"\n",
"高速フーリエ変換は、要素数に制限を加えることによって可能となった、離散フーリエ変換の計算量の少ない実装です。\n",
"時系列データから周波数成分列データへの変換を「**高速フーリエ変換(FFT)**」、その逆変換を「**逆高速フーリエ変換(Inverse FFT, IFFT)**」と呼びます。\n",
"\n",
"離散フーリエ変換DFTやその逆変換IDFは、ともに結果の各成分ごとに、N回の複素数の積を取りその総和を計算するため、その計算量はO(N^2)となります。\n",
"高速フーリエ変換(Fast Fourier Transform, FFT)では、**Nが2のべき乗**のときに使える手法で、変換と逆変換の計算量をともに**O(NlogN)**に抑える事ができます。\n",
"たとえばN=8のとき、DFTでは8x8=64回計算するところを、FFTでは8 x log2(8) = 8x3 = 24回の計算でできるようになります。\n",
"\n",
"ここでは、先に再帰関数によるFFT関数の実装を与え、その**実行結果を分析する**ことによって、FFTではどういう計算方法になっているのかについて理解していきます。\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. JavaScriptでの再帰版FFT実装コード\n",
"\n",
"FFTとIFFTの共通部分を再帰関数`fftrec(c, T, N, s, w)`で実装します。\n",
"再帰呼び出しでは、データ列を二分させて呼び出します。つまり、log2(N)段再帰され、各段のトータルはN回の計算になることで、O(NlogN)の計算になります。\n",
"\n",
"- cとTはDFTのときと同じ、データ列とexpiに渡す定数です。Tは再帰呼び出しで2倍にしていきます。\n",
"- Nは、その再帰ステップで処理するデータ列の要素数(2のべき乗の数)で、再帰呼出しで半減させていきます。\n",
"- sは、その最期ステップで扱うcでの先頭インデックスです。\n",
"- wは、2の再帰段数乗(1 => 2 => 4 => 8 => ...)です。再帰の終端(N=1)のときに、インデックスsとs+wを隣り合わせにし、計算させます(たすき掛けの相手)。\n",
"\n",
"sとwは、データ列cでのインデックスでの、演算で使う２つの複素数を取り出すためのデータであり、コードではわかりにくいものとなります。\n",
"このあとで説明するように、具体的なデータを使って実行した結果を見れば、これが何をするためのコードだったかについては、すぐわかるかと思います。\n",
"\n",
"まずは、再帰版FFT実装コードを提示します。FFT関数を`fft0(f)`、IFFT関数を`ifft0(F)`にします。"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"function fftrec(c, T, N, s = 0, w = 1) {\n",
" if (N === 1) return [c[s]];\n",
" const Nh = N / 2, Td = T * 2, wd = w * 2;\n",
" const rec = fftrec(c, Td, Nh, s, wd).concat(fftrec(c, Td, Nh, s + w, wd));\n",
" for (let i = 0; i < Nh; i++) {\n",
" const l = rec[i], re = imul(rec[i + Nh], expi(T * i));\n",
" [rec[i], rec[i + Nh]] = [iadd(l, re), isub(l, re)];\n",
" }\n",
" return rec;\n",
"}\n",
"\n",
"function fft0(f) {\n",
" const N = f.length, T = -2 * Math.PI / N;\n",
" return fftrec(f, T, N);\n",
"}\n",
"function ifft0(F) {\n",
" const N = F.length, T = 2 * Math.PI / N;\n",
" return fftrec(F, T, N).map(([r, i]) => [r / N, i / N]);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"複素数計算は、forループ部分でのみ行っています。\n",
"各再帰関数内では`Nh`回計算します。\n",
"`Nh`は最初はNで、再帰ごとに半減します。一方再帰呼び出しでは2回再帰呼び出しをするので、最初の1つから始まって再帰ごとに2倍の数になっていきます。\n",
"この結果、各再帰段でトータルすると、結局はどの段でもN回複素数の計算していることになります。\n",
"\n",
"再帰段数はlog2(N)なので、計算量がO(NlogN)なコードとなっていることがわかるでしょう。\n",
"\n",
"この`fft0`と`ifft0`を、DFTと同じ、16要素の時系列データ`fr0`で実行してみます。"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"fr0: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2, 3 ]\n",
"F: [ [ 107, 0 ],\n",
" [ 23.29589166141268, 51.729855807372815 ],\n",
" [ -53.5477272147525, 42.961940777125584 ],\n",
" [ -49.21391810443094, -25.67438445589562 ],\n",
" [ 3.6127080574846916e-15, -59 ],\n",
" [ 49.799704542057846, -24.260170893522517 ],\n",
" [ 35.54772721475249, 48.96194077712559 ],\n",
" [ -19.8816780990396, 53.14406936974591 ],\n",
" [ -63, 0 ],\n",
" [ -19.881678099039586, -53.14406936974591 ],\n",
" [ 35.5477272147525, -48.961940777125584 ],\n",
" [ 49.799704542057846, 24.260170893522528 ],\n",
" [ -3.6127080574846916e-15, 59 ],\n",
" [ -49.21391810443094, 25.67438445589561 ],\n",
" [ -53.54772721475249, -42.96194077712559 ],\n",
" [ 23.295891661412693, -51.729855807372815 ] ]\n",
"f1: [ [ 1, 0 ],\n",
" [ 3.000000000000001, -1.3877787807814457e-15 ],\n",
" [ 3.999999999999999, -1.0143540619928357e-16 ],\n",
" [ 2, -3.0531133177191805e-16 ],\n",
" [ 5, 0 ],\n",
" [ 6, -1.7763568394002505e-15 ],\n",
" [ 2, 4.592425496802574e-17 ],\n",
" [ 3.9999999999999996, -2.498001805406602e-16 ],\n",
" [ 0, 0 ],\n",
" [ 0.9999999999999991, 1.3877787807814457e-15 ],\n",
" [ 3.000000000000001, 9.586896263232085e-18 ],\n",
" [ 4.000000000000001, 3.608224830031759e-16 ],\n",
" [ 5, 0 ],\n",
" [ 62, 1.7763568394002505e-15 ],\n",
" [ 2, 4.592425496802574e-17 ],\n",
" [ 2.9999999999999996, 1.942890293094024e-16 ] ]\n",
"fr1: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2, 3 ]\n"
]
}
],
"source": [
"{\n",
" const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2,3];\n",
" const f0 = fr0.map(r => [r, 0]);\n",
" \n",
" const F = fft0(f0);\n",
" const f1 = ifft0(F);\n",
" const fr1 = f1.map(([r]) => r);\n",
" \n",
" console.log(\"fr0:\", fr0);\n",
" console.log(\"F:\", F);\n",
" console.log(\"f1:\", f1);\n",
" console.log(\"fr1:\", fr1.map(Math.round));\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"DFTのときとほぼ同様の結果となりました。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. 再帰版FFTの実行結果を分析する\n",
"\n",
"この再帰実装FFTの`fftrec`は、再帰呼び出しの前後で、別々の処理を行っています:\n",
"\n",
"- 前半: データの並べ替えをする\n",
"- 後半: 複素数の計算を行う\n",
"\n",
"まず、前半のデータの並べ替えを解析します。\n",
"\n",
"### 6.1. FFT前半部: 並べ替え部分の実行結果を分析する\n",
"\n",
"`fftrec`の並び替えの部分だけを切り出したものを`reorder`として切り出したものは、以下のようになります:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[ 0, 2, 1, 3 ]\n",
"[ 0, 4, 2, 6, 1, 5, 3, 7 ]\n",
"[ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 ]\n"
]
}
],
"source": [
"function reorder(c, N = c.length, s = 0, w = 1) {\n",
" if (N === 1) return [c[s]];\n",
" const Nh = N / 2, wd = w * 2;\n",
" const rec = reorder(c, Nh, s, wd).concat(reorder(c, Nh, s + w, wd));\n",
" return rec;\n",
"}\n",
"console.log(reorder([0,1,2,3]));\n",
"console.log(reorder([0,1,2,3,4,5,6,7]));\n",
"console.log(reorder([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]));"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"この結果の`[0,2,1,3]`というのは、r`reorder`によって`[c[0], c[2], c[1], c[3]]`になった、ということを意味しています。\n",
"\n",
"この並びは一見わかりにくい結果ですが、数値を２進数で表現することで、その意味がすぐわかるようになります。\n",
"整数をk桁２進数文字列にする関数`toBin(k)(n)`は、以下の通りになります。"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"function toBin(k) {\n",
" return n => n.toString(2).padStart(k, \"0\");\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"これを使って`reorder`するものと、した結果をそれぞれ２進数で表示してみます。"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[ '00', '01', '10', '11' ]\n",
"[ '00', '10', '01', '11' ]\n",
"[ '000', '001', '010', '011', '100', '101', '110', '111' ]\n",
"[ '000', '100', '010', '110', '001', '101', '011', '111' ]\n",
"[ '0000',\n",
" '0001',\n",
" '0010',\n",
" '0011',\n",
" '0100',\n",
" '0101',\n",
" '0110',\n",
" '0111',\n",
" '1000',\n",
" '1001',\n",
" '1010',\n",
" '1011',\n",
" '1100',\n",
" '1101',\n",
" '1110',\n",
" '1111' ]\n",
"[ '0000',\n",
" '1000',\n",
" '0100',\n",
" '1100',\n",
" '0010',\n",
" '1010',\n",
" '0110',\n",
" '1110',\n",
" '0001',\n",
" '1001',\n",
" '0101',\n",
" '1101',\n",
" '0011',\n",
" '1011',\n",
" '0111',\n",
" '1111' ]\n"
]
}
],
"source": [
"console.log([0,1,2,3].map(toBin(2)));\n",
"console.log(reorder([0,1,2,3]).map(toBin(2)));\n",
"\n",
"console.log([0,1,2,3,4,5,6,7].map(toBin(3)));\n",
"console.log(reorder([0,1,2,3,4,5,6,7]).map(toBin(3)));\n",
"\n",
"console.log([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15].map(toBin(4)));\n",
"console.log(reorder([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]).map(toBin(4)));"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"このように、`reorder`の再帰処理でやってることは、インデックスを**２進数での前後を逆転**させた位置に移したものだったのです。\n",
"\n",
"次に、再帰実装ではなく、k桁２進数の順序逆転関数`revBit(k, n)`を実装し、それによって、`reorder`を再帰なしで実装してみます。"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"function revBit(k, n) {\n",
" let r = 0;\n",
" for (let i = 0; i < k; i++) r = (r << 1) | ((n >>> i) & 1);\n",
" return r;\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"function reorder(c, N = c.length) {\n",
" const k = Math.log2(N);\n",
" console.assert(Number.isInteger(k), \"c.length should be power of 2\");\n",
" return c.map((_, i) => c[revBit(k, i)]);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"このコードで、再帰関数のときと同様の結果が、`map`(ループ)によって得られます。\n",
"\n",
"整数が32bitであることを前提にすると、ビット操作で`revBit`をループなしで以下のように実装できます。"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"function revBit(k, n0) {\n",
" if (k === 1) return n0;\n",
" const s1 = ((n0 & 0xaaaaaaaa) >>> 1) | ((n0 & 0x55555555) << 1);\n",
" if (k === 2) return s1;\n",
" const s2 = ((s1 & 0xcccccccc) >>> 2) | ((s1 & 0x33333333) << 2);\n",
" if (k <= 4) return s2 >>> (4 - k);\n",
" const s3 = ((s2 & 0xf0f0f0f0) >>> 4) | ((s2 & 0x0f0f0f0f) << 4);\n",
" if (k <= 8) return s3 >>> (8 - k);\n",
" const s4 = ((s3 & 0xff00ff00) >>> 8) | ((s3 & 0x00ff00ff) << 8);\n",
" if (k <= 16) return s3 >>> (16 - k);\n",
" const s5 = ((s4 & 0xffff0000) >>> 16) | ((s4 & 0x0000ffff) << 16);\n",
" return s5 >>> (32 - k);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"これは、\"ab cd ef gh\"を1つづつ入れ替えると\"ba dc fe hg\"になり、次に2つづつで入れ替えると\"dcba hgfe\"となり、\n",
"最後に4つで入れ替えると\"hgfe dcba\"となるのと同じやり方です。そして、返す直前にk桁に切り詰めています。\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 6.2. FFT後半部: 複素数計算部分の実行結果を分析する\n",
"\n",
"ここでは、要素数N=8での計算について考えていきます。\n",
"\n",
"まず、DFTでの計算について、N=8のときで確認します:\n",
"\n",
"$$\n",
"F(k) = f(0) \\exp(\\frac{-2\\pi i}{8} 0 k) + f(1) \\exp(\\frac{-2\\pi i}{8} 1 k) + \n",
" f(2) \\exp(\\frac{-2\\pi i}{8} 2 k) + f(3) \\exp(\\frac{-2\\pi i}{8} 3 k) +\n",
" f(4) \\exp(\\frac{-2\\pi i}{8} 4 k) + f(5) \\exp(\\frac{-2\\pi i}{8} 5 k) +\n",
" f(6) \\exp(\\frac{-2\\pi i}{8} 6 k) + f(7) \\exp(\\frac{-2\\pi i}{8} 7 k)\n",
"$$\n",
"\n",
"ここで、$E(n) = \\exp(\\frac{-2\\pi i}{8} n)$とすると、$\\exp(\\frac{-2\\pi i}{8} t k)$は短く、`E(t * k)`とかけます。\n",
"このとき、$F(k)$は以下のようになります:\n",
"\n",
"```\n",
"F(k) = E(0 * k)f(0) + E(1 * k)f(1) + E(2 * k)f(2) + E(3 * k)f(3) + E(4 * k)f(4) + E(5 * k)f(5) + E(6 * k)f(6) + E(7 * k)f(7)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"まず、この係数`E(n * k)`に着目し、表にすると以下のようになっています:\n",
"\n",
"| F\\f | f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) |\n",
"|----------|-------|-------|-------|-------|-------|-------|-------|-------|\n",
"| **F(0)** | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) |\n",
"| **F(1)** | E(0) | E(1) | E(2) | E(3) | E(4) | E(5) | E(6) | E(7) |\n",
"| **F(2)** | E(0) | E(2) | E(4) | E(6) | E(8) | E(10) | E(12) | E(14) |\n",
"| **F(3)** | E(0) | E(3) | E(6) | E(9) | E(12) | E(15) | E(18) | E(21) |\n",
"| **F(4)** | E(0) | E(4) | E(8) | E(12) | E(16) | E(20) | E(24) | E(28) |\n",
"| **F(5)** | E(0) | E(5) | E(10) | E(15) | E(20) | E(25) | E(30) | E(35) |\n",
"| **F(6)** | E(0) | E(6) | E(12) | E(18) | E(24) | E(30) | E(36) | E(42) |\n",
"| **F(7)** | E(0) | E(7) | E(14) | E(21) | E(28) | E(35) | E(42) | E(49) |"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"`E(n)`はべき乗でもあるから、`E(n)E(m) = E(n + m)`です。\n",
"\n",
"また、$\\exp(-2\\pi i) = \\exp(\\frac{-2\\pi i}{8} 8) = 1$、$\\exp(-\\pi i) = \\exp(\\frac{-2\\pi}{8} 4) = -1$といった関係があります。\n",
"これは`E(0) = E(8) = 1`、`E(4) = -1`になるので、`E(n + 8) = E(n)E(8) = E(n)`、`E(n + 4) = E(n)E(4) = -E(n)`という関係を持ちます。\n",
"\n",
"`E(n + 8) = E(n)`から、先の表の`E(n)`の`n`を8で割った余りにすると以下のようになります:\n",
"\n",
"| F\\f | f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) |\n",
"|----------|------|------|------|------|------|------|------|------|\n",
"| **F(0)** | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) |\n",
"| **F(1)** | E(0) | E(1) | E(2) | E(3) | E(4) | E(5) | E(6) | E(7) |\n",
"| **F(2)** | E(0) | E(2) | E(4) | E(6) | E(0) | E(2) | E(4) | E(6) |\n",
"| **F(3)** | E(0) | E(3) | E(6) | E(1) | E(4) | E(7) | E(2) | E(5) |\n",
"| **F(4)** | E(0) | E(4) | E(0) | E(4) | E(0) | E(4) | E(0) | E(4) |\n",
"| **F(5)** | E(0) | E(5) | E(2) | E(7) | E(4) | E(1) | E(6) | E(3) |\n",
"| **F(6)** | E(0) | E(6) | E(4) | E(2) | E(0) | E(6) | E(4) | E(2) |\n",
"| **F(7)** | E(0) | E(7) | E(6) | E(5) | E(4) | E(3) | E(2) | E(1) |"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"この表に、先に調べた、前半でのビット前後反転した順でのデータ列の入れ替え`[ 0, 4, 2, 6, 1, 5, 3, 7 ]`を行うと、以下のようになります:\n",
"\n",
"| F\\f | f(0) | f(4) | f(2) | f(6) | f(1) | f(5) | f(3) | f(7) |\n",
"|----------|------|------|------|------|------|------|------|------|\n",
"| **F(0)** | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) |\n",
"| **F(1)** | E(0) | E(4) | E(2) | E(6) | E(1) | E(5) | E(3) | E(7) |\n",
"| **F(2)** | E(0) | E(0) | E(4) | E(4) | E(2) | E(2) | E(6) | E(6) |\n",
"| **F(3)** | E(0) | E(4) | E(6) | E(2) | E(3) | E(7) | E(1) | E(5) |\n",
"| **F(4)** | E(0) | E(0) | E(0) | E(0) | E(4) | E(4) | E(4) | E(4) |\n",
"| **F(5)** | E(0) | E(4) | E(2) | E(6) | E(5) | E(1) | E(7) | E(3) |\n",
"| **F(6)** | E(0) | E(0) | E(4) | E(4) | E(6) | E(6) | E(2) | E(2) |\n",
"| **F(7)** | E(0) | E(4) | E(6) | E(2) | E(7) | E(3) | E(5) | E(1) |\n",
"\n",
"ここで、E(n)のnだけ並べてみます。\n",
"\n",
"| F\\f | 0 | 4 | 2 | 6 | 1 | 5 | 3 | 7 |\n",
"|-------|---|---|---|---|---|---|---|---|\n",
"| **0** | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\n",
"| **1** | 0 | 4 | 2 | 6 | 1 | 5 | 3 | 7 |\n",
"| **2** | 0 | 0 | 4 | 4 | 2 | 2 | 6 | 6 |\n",
"| **3** | 0 | 4 | 6 | 2 | 3 | 7 | 1 | 5 |\n",
"| **4** | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 |\n",
"| **5** | 0 | 4 | 2 | 6 | 5 | 1 | 7 | 3 |\n",
"| **6** | 0 | 0 | 4 | 4 | 6 | 6 | 2 | 2 |\n",
"| **7** | 0 | 4 | 6 | 2 | 7 | 3 | 5 | 1 |\n",
" \n",
"この並び替えによって、F(０)とF(4)のあいだなどで、共通部分のあるパターンがなんとなく見えてきたかもしれません。\n",
"次は、このパターンについて見ていきます。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"先に示した`E(n + 8) = E(n)`、`E(n + 4) = -E(n)`より、`E(n)`には:\n",
"\n",
"- `-E(0) = E(4)`\n",
"- `-E(1) = E(5)`\n",
"- `-E(2) = E(6)`\n",
"- `-E(3) = E(7)`\n",
"\n",
"かつ:\n",
"\n",
"- `-E(4) = E(0)`\n",
"- `-E(5) = E(1)`\n",
"- `-E(6) = E(2)`\n",
"- `-E(7) = E(3)`\n",
"\n",
"の関係があります。つまりE(n)のnには、0と4、1と5、2と6、3と7は、互いにマイナスをかけた関係にあります。\n",
"\n",
"ここからたとえば、F(0)とF(4)は、F(0)の前側の0426部分をL0、後ろ側の1537部分をR0とすると、\n",
"\n",
"- `F(0) = L0 + R0`\n",
"- `F(4) = L0 - R0 = L0 + E(4)R0`\n",
"\n",
"という関係になっています。同様に、\n",
"\n",
"- `F(1) = L1 + R1`\n",
"- `F(5) = L1 - R1`\n",
"- `F(2) = L2 + R2`\n",
"- `F(6) = L2 - R2`\n",
"- `F(3) = L3 + R3`\n",
"- `F(7) = L3 - R3`\n",
"\n",
"ともなっています。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"最後に、このLRの計算を、再帰の一番奥の段から、足し合わせていくときの計算ステップを具体的に並べていきます。\n",
"\n",
"再帰版FFTの後半の計算コードは、同一段数の再帰処理でまとめることで、各再帰段ごとで全要素を1回づつ更新しています。\n",
"(実際の動作では、葉がN要素な二分木での深さ優先の帰りがけ順で、各段としてはバラバラに計算されます。\n",
"しかし、二分木のそれぞれの枝での計算範囲は完全に分割されているので、幅優先で処理しても同じ結果になります。)\n",
"N=8では、Nを半減させてN=1になるまで、3段の(2回づつの)再帰呼び出しが、再帰関数中で行われることになります。\n",
"\n",
"以下は、この再帰段数を一度に巻き戻すことの順に、計算される内容と結果を列挙したものです。\n",
"入力値の時系列データの値は、それぞれ`f(0) = f0`、`f(1) = f1`、 ...、`f(7) = f7`と記述します。\n",
"\n",
"#### 再帰段3\n",
"\n",
"前半の入れ替え直後の初期値です。\n",
"\n",
"- `F0(0) = f0`\n",
"- `F0(1) = f4`\n",
"- `F0(2) = f2`\n",
"- `F0(3) = f6`\n",
"- `F0(4) = f1`\n",
"- `F0(5) = f5`\n",
"- `F0(6) = f3`\n",
"- `F0(7) = f7`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"#### 再帰段2\n",
"\n",
"Nhが1、つまりループはi = 0のみで、ループ中の複素数計算は:\n",
"\n",
"- `L1 = L0 + E(i*4)R0 = E(0)L0 + E(i*4+0)R0`\n",
"- `R1 = L0 - E(i*4)R0 = E(0)L0 + E(i*4+4)R0`\n",
"\n",
"より、以下の計算が行われます:\n",
"\n",
"- s = 0, i = 0\n",
" - `F1(0) = F0(0) + F0(1) = E(0)f0 + E(0)f4`\n",
" - `F1(1) = F0(0) - F0(1) = E(0)f0 + E(4)f4`\n",
"- s = 2, i = 0\n",
" - `F1(2) = F0(2) + F0(3) = E(0)f2 + E(0)f6`\n",
" - `F1(3) = F0(2) - F0(3) = E(0)f2 + E(4)f6`\n",
"- s = 4, i = 0\n",
" - `F1(4) = F0(4) + F0(5) = E(0)f1 + E(0)f5`\n",
" - `F1(5) = F0(4) - F0(5) = E(0)f1 + E(4)f5`\n",
"- s = 6, i = 0\n",
" - `F1(6) = F0(6) + F0(7) = E(0)f3 + E(0)f7`\n",
" - `F1(7) = F0(6) - F0(7) = E(0)f3 + E(4)f7`\n",
"\n",
"この結果の値を順に並べると:\n",
"\n",
"- `F1(0) = E(0)f0 + E(0)f4`\n",
"- `F1(1) = E(0)f0 + E(4)f4`\n",
"- `F1(2) = E(0)f2 + E(0)f6`\n",
"- `F1(3) = E(0)f2 + E(4)f6`\n",
"- `F1(4) = E(0)f1 + E(0)f5`\n",
"- `F1(5) = E(0)f1 + E(4)f5`\n",
"- `F1(6) = E(0)f3 + E(0)f7`\n",
"- `F1(7) = E(0)f3 + E(4)f7`\n",
"\n",
"となります。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"#### 再帰段1\n",
"\n",
"Nhが２，つまりループはi = 0,1で、ループ中の複素数計算は:\n",
"\n",
"- `L2 = L1 + E(i*2)R1 = E(0)L1 + E(i*2)R1`\n",
"- `R2 = L1 - E(i*2)R1 = E(0)L1 + E(i*2+4)R1`\n",
"\n",
"より、以下の計算が行われます:\n",
"\n",
"- s = 0, i = 0\n",
" - `F2(0) = F1(0) + E(0)F1(2) = E(0)f0 + E(0)f4 + E(0)f2 + E(0)f6`\n",
" - `F2(2) = F1(0) - E(0)F1(2) = E(0)f0 + E(0)f4 + E(4)f2 + E(4)f6`\n",
"- s = 0, i = 1\n",
" - `F2(1) = F1(1) + E(2)F1(3) = E(0)f0 + E(4)f4 + E(2)f2 + E(6)f6`\n",
" - `F2(3) = F1(1) - E(2)F1(3) = E(0)f0 + E(4)f4 + E(6)f2 + E(2)f6`\n",
"- s = 4, i = 0\n",
" - `F2(4) = F1(4) + E(0)F1(6) = E(0)f1 + E(0)f5 + E(0)f3 + E(0)f7`\n",
" - `F2(6) = F1(4) - E(0)F1(6) = E(0)f1 + E(0)f5 + E(4)f3 + E(4)f7`\n",
"- s = 4, i = 1\n",
" - `F2(5) = F1(5) + E(2)F1(7) = E(0)f1 + E(4)f5 + E(2)f3 + E(6)f7`\n",
" - `F2(7) = F1(5) - E(2)F1(7) = E(0)f1 + E(4)f5 + E(6)f3 + E(2)f7`\n",
"\n",
"この結果の値を順に並べると:\n",
"\n",
"- `F2(0) = E(0)f0 + E(0)f4 + E(0)f2 + E(0)f6`\n",
"- `F2(1) = E(0)f0 + E(4)f4 + E(2)f2 + E(6)f6`\n",
"- `F2(2) = E(0)f0 + E(0)f4 + E(4)f2 + E(4)f6`\n",
"- `F2(3) = E(0)f0 + E(4)f4 + E(6)f2 + E(2)f6`\n",
"- `F2(4) = E(0)f1 + E(0)f5 + E(0)f3 + E(0)f7`\n",
"- `F2(5) = E(0)f1 + E(4)f5 + E(2)f3 + E(6)f7`\n",
"- `F2(6) = E(0)f1 + E(0)f5 + E(4)f3 + E(4)f7`\n",
"- `F2(7) = E(0)f1 + E(4)f5 + E(6)f3 + E(2)f7`\n",
"\n",
"となります。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"#### 再帰段0\n",
"\n",
"Nhが4、つまりループはi = 0,1,2,3で、ループ中の複素数計算は:\n",
"\n",
"- `L3 = L2 + E(i*1)R2 = E(0)L2 + E(i*1)R2`\n",
"- `R3 = L2 - E(i*1)R2 = E(0)L2 + E(i*1+4)R2`\n",
"\n",
"より、以下の計算が行われます:\n",
"\n",
"- s = 0, i = 0\n",
" - `F3(0) = F2(0) + E(0)F2(4) = E(0)f0 + E(0)f4 + E(0)f2 + E(0)f6 + E(0)f1 + E(0)f5 + E(0)f3 + E(0)f7`\n",
" - `F3(4) = F2(0) - E(0)F2(4) = E(0)f0 + E(0)f4 + E(0)f2 + E(0)f6 + E(4)f1 + E(4)f5 + E(4)f3 + E(4)f7`\n",
"- s = 0, i = 1\n",
" - `F3(1) = F2(1) + E(1)F2(5) = E(0)f0 + E(4)f4 + E(2)f2 + E(6)f6 + E(1)f1 + E(5)f5 + E(3)f3 + E(7)f7`\n",
" - `F3(5) = F2(1) - E(1)F2(5) = E(0)f0 + E(4)f4 + E(2)f2 + E(6)f6 + E(5)f1 + E(1)f5 + E(7)f3 + E(3)f7`\n",
"- s = 0, i = 2\n",
" - `F3(2) = F2(2) + E(2)F2(6) = E(0)f0 + E(0)f4 + E(4)f2 + E(4)f6 + E(2)f1 + E(2)f5 + E(6)f3 + E(6)f7`\n",
" - `F3(6) = F2(2) - E(2)F2(6) = E(0)f0 + E(0)f4 + E(4)f2 + E(4)f6 + E(6)f1 + E(6)f5 + E(2)f3 + E(2)f7`\n",
"- s = 0, i = 3\n",
" - `F3(3) = F2(3) + E(3)F2(7) = E(0)f0 + E(4)f4 + E(6)f2 + E(2)f6 + E(3)f1 + E(7)f5 + E(1)f3 + E(5)f7`\n",
" - `F3(7) = F2(3) - E(3)F2(7) = E(0)f0 + E(4)f4 + E(6)f2 + E(2)f6 + E(7)f1 + E(3)f5 + E(5)f3 + E(1)f7`\n",
"\n",
"この結果の値を順に並べると:\n",
"\n",
"- `F3(0) = E(0)f0 + E(0)f4 + E(0)f2 + E(0)f6 + E(0)f1 + E(0)f5 + E(0)f3 + E(0)f7`\n",
"- `F3(1) = E(0)f0 + E(4)f4 + E(2)f2 + E(6)f6 + E(1)f1 + E(5)f5 + E(3)f3 + E(7)f7`\n",
"- `F3(2) = E(0)f0 + E(0)f4 + E(4)f2 + E(4)f6 + E(2)f1 + E(2)f5 + E(6)f3 + E(6)f7`\n",
"- `F3(3) = E(0)f0 + E(4)f4 + E(6)f2 + E(2)f6 + E(3)f1 + E(7)f5 + E(1)f3 + E(5)f7`\n",
"- `F3(4) = E(0)f0 + E(0)f4 + E(0)f2 + E(0)f6 + E(4)f1 + E(4)f5 + E(4)f3 + E(4)f7`\n",
"- `F3(5) = E(0)f0 + E(4)f4 + E(2)f2 + E(6)f6 + E(5)f1 + E(1)f5 + E(7)f3 + E(3)f7`\n",
"- `F3(6) = E(0)f0 + E(0)f4 + E(4)f2 + E(4)f6 + E(6)f1 + E(6)f5 + E(2)f3 + E(2)f7`\n",
"- `F3(7) = E(0)f0 + E(4)f4 + E(6)f2 + E(2)f6 + E(7)f1 + E(3)f5 + E(5)f3 + E(1)f7`\n",
"\n",
"となります。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"このE(n)を表にすると、\n",
"\n",
"| F3\\ft | f0 | f4 | f2 | f6 | f1 | f5 | f3 | f7 |\n",
"|-----------|------|------|------|------|------|------|------|------|\n",
"| **F3(0)** | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) | E(0) |\n",
"| **F3(1)** | E(0) | E(4) | E(2) | E(6) | E(1) | E(5) | E(3) | E(7) |\n",
"| **F3(2)** | E(0) | E(0) | E(4) | E(4) | E(2) | E(2) | E(6) | E(6) |\n",
"| **F3(3)** | E(0) | E(4) | E(6) | E(2) | E(3) | E(7) | E(1) | E(5) |\n",
"| **F3(4)** | E(0) | E(0) | E(0) | E(0) | E(4) | E(4) | E(4) | E(4) |\n",
"| **F3(5)** | E(0) | E(4) | E(2) | E(6) | E(5) | E(1) | E(7) | E(3) |\n",
"| **F3(6)** | E(0) | E(0) | E(4) | E(4) | E(6) | E(6) | E(2) | E(2) |\n",
"| **F3(7)** | E(0) | E(4) | E(6) | E(2) | E(7) | E(3) | E(5) | E(1) |\n",
"\n",
"となり、先の表と同じ値となっていることがわかります。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 7. JavaScriptによるループ版FFT実装コード\n",
"\n",
"上述の再帰段数ごとの計算を、要素数が任意の２のべき乗数Nとして、ループによって直接的に実装したものが、ループ版FFTとなります。\n",
"\n",
"FFTとIFFTの共通処理部分を`fftin1(c, T, N)`としました。ただし、引数Tの値は再帰版と違い、Nで割っていません。\n",
"\n",
"最内ループ内のコードでの変数(i, Nh, l, re)は、再帰版FFTでのループ処理での変数と合わせてあります。\n"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"function fftin1(c, T, N) {\n",
" const k = Math.log2(N);\n",
" const rec = c.map((_, i) => c[revBit(k, i)]);\n",
" for (let Nh = 1; Nh < N; Nh *= 2) {\n",
" T /= 2;\n",
" for (let s = 0; s < N; s += Nh * 2) {\n",
" for (let i = 0; i < Nh; i++) {\n",
" const l = rec[s + i], re = imul(rec[s + i + Nh], expi(T * i));\n",
" [rec[s + i], rec[s + i + Nh]] = [iadd(l, re), isub(l, re)];\n",
" }\n",
" }\n",
" }\n",
" return rec;\n",
"}\n",
"\n",
"function fft1(f) {\n",
" const N = f.length, T = -2 * Math.PI;\n",
" return fftin1(f, T, N);\n",
"}\n",
"function ifft1(F) {\n",
" const N = F.length, T = 2 * Math.PI;\n",
" return fftin1(F, T, N).map(([r, i]) => [r / N, i / N]);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"最外ループでは、Nhを倍々にしていくことから、log2(N)回実行されます。\n",
"その中のループは２つ合わせて、中の計算部分をN/2回実行するものとなります。\n",
"\n",
"この実装で、再帰版FFTのときと同じ`fr0`を使って計算してみましょう。"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"fr0: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2, 3 ]\n",
"F: [ [ 107, 0 ],\n",
" [ 23.29589166141268, 51.729855807372815 ],\n",
" [ -53.5477272147525, 42.961940777125584 ],\n",
" [ -49.21391810443094, -25.67438445589562 ],\n",
" [ 3.6127080574846916e-15, -59 ],\n",
" [ 49.799704542057846, -24.260170893522517 ],\n",
" [ 35.54772721475249, 48.96194077712559 ],\n",
" [ -19.8816780990396, 53.14406936974591 ],\n",
" [ -63, 0 ],\n",
" [ -19.881678099039586, -53.14406936974591 ],\n",
" [ 35.5477272147525, -48.961940777125584 ],\n",
" [ 49.799704542057846, 24.260170893522528 ],\n",
" [ -3.6127080574846916e-15, 59 ],\n",
" [ -49.21391810443094, 25.67438445589561 ],\n",
" [ -53.54772721475249, -42.96194077712559 ],\n",
" [ 23.295891661412693, -51.729855807372815 ] ]\n",
"f1: [ [ 1, 0 ],\n",
" [ 3.000000000000001, -1.3877787807814457e-15 ],\n",
" [ 3.999999999999999, -1.0143540619928357e-16 ],\n",
" [ 2, -3.0531133177191805e-16 ],\n",
" [ 5, 0 ],\n",
" [ 6, -1.7763568394002505e-15 ],\n",
" [ 2, 4.592425496802574e-17 ],\n",
" [ 3.9999999999999996, -2.498001805406602e-16 ],\n",
" [ 0, 0 ],\n",
" [ 0.9999999999999991, 1.3877787807814457e-15 ],\n",
" [ 3.000000000000001, 9.586896263232085e-18 ],\n",
" [ 4.000000000000001, 3.608224830031759e-16 ],\n",
" [ 5, 0 ],\n",
" [ 62, 1.7763568394002505e-15 ],\n",
" [ 2, 4.592425496802574e-17 ],\n",
" [ 2.9999999999999996, 1.942890293094024e-16 ] ]\n",
"fr1: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2, 3 ]\n"
]
}
],
"source": [
"{\n",
" const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2,3];\n",
" const f0 = fr0.map(r => [r, 0]);\n",
" \n",
" const F = fft1(f0);\n",
" const f1 = ifft1(F);\n",
" const fr1 = f1.map(([r]) => r);\n",
" \n",
" console.log(\"fr0:\", fr0);\n",
" console.log(\"F:\", F);\n",
" console.log(\"f1:\", f1);\n",
" console.log(\"fr1:\", fr1.map(Math.round));\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"結果は、再帰版FFTのときと同じ値になりました。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 8. まとめ\n",
"\n",
"DFTの実装の理解を前提に、再帰版FFTの実装を提示し、再帰版FFTの振る舞いを具体例で解析することで、FFTの仕組みを解明し、最後にその仕組をループで直接実行したループ版FFTを作成しました。\n",
"\n",
"再帰版FFTの前半部の解析では、インデックスの2進数表現を用いました。\n",
"\n",
"内部で２度自身を呼び出す再帰関数は、O(NlogN)な処理として、葉がN要素の完全二分木のデータ構造への処理を行っているとみなせます。\n",
"この隠れた二分木を表出させるのが、再帰で扱う数値の２進数表現になります。\n",
"\n",
"たとえば、ハノイの塔は、この内部で二度自身を呼び出す再帰関数になります。\n",
"これも２進数表現化を応用することで、固定段のループによって実装させることができます。\n",
"\n",
"- https://gist.github.com/bellbind/9f8948f74f1b8ecc06f359d0430b5863\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 付録: 任意長データのためのFFT\n",
"\n",
"２のべき乗のFFT/IFFTを用いて、任意長のデータを扱うFFTを作ることができます。\n",
"この任意長FFTは、[Bluestein's algorithm](https://en.wikipedia.org/wiki/Chirp_Z-transform#Bluestein's_algorithm)と呼ばれています。\n",
"\n",
"２つの数列(関数)をかけ合わせて総和(積分)を取ることを、畳み込み(convolution)といいます。\n",
"フーリエ変換やラプラス変換は、べき乗タイプ($\\exp(C x)$)の数列(関数)との畳み込みを行っています。\n",
"このタイプの畳み込みによる変換では、２つの数列(関数)に対して、変換した後同士の積をとり、その逆変換をすると、**もとの2数列(関数)の畳み込みになっている**、という性質があります。\n",
"\n",
"Bluestein's algorithmでは、DFTの$\\exp(\\frac{-2\\pi i}{N}n k)$を分解して、その畳み込みに変形します。\n",
"この変形後の畳み込みは、2のべき乗長にデータを拡大するのに適した形になります。\n",
"\n",
"まずDFTの畳み込みの式が、リンク先での$a_n$と$b_n$との畳込みの式へと変換されます。\n",
"そこから、この$a_n$と$b_n$を、2のべき乗長に拡大します。\n",
"$a_n$は後ろを単に０で埋めるだけですが、$b_n$のほうは後ろ側に$b_n$を反転したものを入れます。\n",
"これは元からの$a_n$との畳み込みがされる範囲を埋めています。\n",
"(先頭の畳込みは$ab_0 = a_0 b_0 + a_1 b_{-1} + a_2 b_{-2} + \\dots + a_{N-1} b_{1-N}$であり、この$b_{-1} \\dots b_{1-N}$が拡大した$b_n$の後ろ側に必要)。\n",
"\n",
"この２のべき乗長に拡大された$a_n$と$b_n$の畳み込みを、2のべき乗長のFFTとIFFTを使って行い、その結果から、先頭からもとの長さだけ切り出し、$b$の複素共役とかけることで、DFTでの結果とほぼ同じものになる、という仕組みです。\n",
"\n",
"---\n",
"\n",
"このBluestein's algorithmのコードは以下のようになります(`fft2(f)`、`ifft2(F)`):"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"function conj([x, y]) {return [x, -y];}\n",
"\n",
"function fftin2(c, T, N) {\n",
" const Nd = N * 2;\n",
" const bc = c.map((_, n) => expi(T * n * n / Nd));\n",
" const b = bc.map(conj);\n",
" const a = c.map((cn, n) => imul(cn, bc[n]));\n",
" \n",
" //const N2 = 1 << Math.ceil(Math.log2(Nd - 1));\n",
" const N2 = 1 << (32 - Math.clz32(Nd - 1));\n",
" const a2 = a.concat(Array(N2 - N).fill([0, 0]));\n",
" const b2 = b.concat(Array(N2 - Nd + 1).fill([0, 0]), b.slice(1).reverse());\n",
" const A2 = fft1(a2);\n",
" const B2 = fft1(b2);\n",
" const AB2 = A2.map((A2n, n) => imul(A2n, B2[n]));\n",
" const ab2 = ifft1(AB2);\n",
" return bc.map((bcn, n) => imul(bcn, ab2[n]));\n",
"}\n",
"\n",
"function fft2(f) {\n",
" const N = f.length, T = -2 * Math.PI; \n",
" return fftin2(f, T, N);\n",
"}\n",
"function ifft2(F) {\n",
" const N = F.length, T = 2 * Math.PI;\n",
" return fftin2(F, T, N).map(([x, y]) => [x / N, y / N]);\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"fr0: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2 ]\n",
"F: [ [ 104.00000000000001, 1.4210854715202004e-14 ],\n",
" [ 40.113068713053366, 40.536802661213386 ],\n",
" [ -16.938440097404285, 64.08647185352932 ],\n",
" [ -47.041019662496865, 29.02599135062092 ],\n",
" [ -57.94588444305084, -15.35101781191083 ],\n",
" [ -35.500000000000064, -52.82754963085073 ],\n",
" [ 20.04101966249682, -49.09166758334534 ],\n",
" [ 52.77125582740197, -26.917243683390566 ],\n",
" [ 52.771255827401916, 26.91724368339068 ],\n",
" [ 20.041019662496826, 49.091667583345306 ],\n",
" [ -35.49999999999999, 52.82754963085077 ],\n",
" [ -57.94588444305086, 15.351017811910662 ],\n",
" [ -47.04101966249681, -29.02599135062106 ],\n",
" [ -16.938440097404428, -64.08647185352933 ],\n",
" [ 40.11306871305353, -40.53680266121326 ] ]\n",
"f1: [ [ 1.0000000000000246, -8.763360407707903e-15 ],\n",
" [ 3.0000000000000235, -1.4092430925908654e-14 ],\n",
" [ 4.000000000000012, -6.158037043254202e-15 ],\n",
" [ 2.000000000000004, 6.2764608325475514e-15 ],\n",
" [ 4.999999999999981, 5.921189464667502e-15 ],\n",
" [ 5.999999999999992, -2.0368891758456206e-14 ],\n",
" [ 2.0000000000000098, -8.052817671947802e-15 ],\n",
" [ 4.000000000000021, 9.473903143468002e-16 ],\n",
" [ 1.1817018103590317e-14, 9.119920035791959e-15 ],\n",
" [ 0.9999999999999932, 1.0835776720341527e-14 ],\n",
" [ 2.9999999999999916, -1.4210854715202004e-14 ],\n",
" [ 3.999999999999985, 5.8027656753741514e-15 ],\n",
" [ 4.9999999999999964, 8.763360407707903e-15 ],\n",
" [ 62.00000000000001, 7.579122514774402e-15 ],\n",
" [ 2.000000000000005, 1.4802973661668755e-14 ] ]\n",
"fr1: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2 ]\n"
]
}
],
"source": [
"{\n",
" // 15 elements example\n",
" const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2];\n",
" const f0 = fr0.map(r => [r, 0]);\n",
" \n",
" const F = fft2(f0);\n",
" const f1 = ifft2(F);\n",
" const fr1 = f1.map(([r]) => r);\n",
" \n",
" console.log(\"fr0:\", fr0);\n",
" console.log(\"F:\", F);\n",
" console.log(\"f1:\", f1);\n",
" console.log(\"fr1:\", fr1.map(Math.round));\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"比較対象に、同じデータのDFTでの結果も載せておきます:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"fr0: [ 1, 3, 4, 2, 5, 6, 2, 4, 0, 1, 3, 4, 5, 62, 2 ]\n",
"F: [ [ 104, 0 ],\n",
" [ 40.1130687130533, 40.53680266121345 ],\n",
" [ -16.93844009740454, 64.08647185352929 ],\n",
" [ -47.04101966249686, 29.02599135062094 ],\n",
" [ -57.945884443050794, -15.351017811910953 ],\n",
" [ -35.49999999999983, -52.827549630850896 ],\n",
" [ 20.041019662496918, -49.09166758334529 ],\n",
" [ 52.771255827402115, -26.917243683390264 ],\n",
" [ 52.77125582740182, 26.917243683390836 ],\n",
" [ 20.041019662496755, 49.09166758334532 ],\n",
" [ -35.50000000000034, 52.82754963085049 ],\n",
" [ -57.94588444305084, 15.351017811910584 ],\n",
" [ -47.04101966249679, -29.025991350621084 ],\n",
" [ -16.938440097404428, -64.08647185352936 ],\n",
" [ 40.113068713053934, -40.536802661212924 ] ]\n",
"f1: [ [ 1.0000000000000286, 1.0894988614988204e-14 ],\n",
" [ 3.000000000000027, 1.8947806286936004e-14 ],\n",
" [ 4.000000000000055, 1.5158245029548804e-14 ],\n",
" [ 2.0000000000000298, -6.015928496102182e-14 ],\n",
" [ 5.000000000000037, -8.052817671947802e-15 ],\n",
" [ 6.000000000000018, -5.6369723703634616e-14 ],\n",
" [ 1.9999999999999796, -6.987003568307652e-14 ],\n",
" [ 3.9999999999999383, -3.789561257387201e-15 ],\n",
" [ -1.7289873236829103e-14, -1.5158245029548804e-14 ],\n",
" [ 0.9999999999999837, -1.8947806286936004e-14 ],\n",
" [ 2.999999999999985, 1.8000415972589204e-14 ],\n",
" [ 3.999999999999993, 3.600083194517841e-14 ],\n",
" [ 5.000000000000014, -1.3026616822268503e-14 ],\n",
" [ 62, -2.2737367544323207e-14 ],\n",
" [ 1.999999999999967, -1.3263464400855204e-14 ] ]\n",
"fr1: [ 1, 3, 4, 2, 5, 6, 2, 4, -0, 1, 3, 4, 5, 62, 2 ]\n"
]
}
],
"source": [
"{\n",
" // 15 elements example\n",
" const fr0 = [1,3,4,2, 5,6,2,4, 0,1,3,4, 5,62,2];\n",
" const f0 = fr0.map(r => [r, 0]);\n",
" \n",
" const F = dft(f0);\n",
" const f1 = idft(F);\n",
" const fr1 = f1.map(([r]) => r);\n",
" \n",
" console.log(\"fr0:\", fr0);\n",
" console.log(\"F:\", F);\n",
" console.log(\"f1:\", f1);\n",
" console.log(\"fr1:\", fr1.map(Math.round));\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"\n",
"データ列の長さが2のべき乗のときは`fftin1`を呼び、そうでない場合のみ`fftin2`を呼ぶようにした`fft`/`ifft`は以下のようになります。"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"function isPowerOf2(n) {return (n & (n - 1)) === 0;}\n",
"function fft(f) {\n",
" const N = f.length, T = -2 * Math.PI;\n",
" const fftin = isPowerOf2(N) ? fftin1 : fftin2;\n",
" return fftin(f, T, N);\n",
"}\n",
"function ifft(F) {\n",
" const N = F.length, T = 2 * Math.PI;\n",
" const fftin = isPowerOf2(N) ? fftin1 : fftin2;\n",
" return fftin(F, T, N).map(([x, y]) => [x / N, y / N]);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 参考: このドキュメントの編集環境\n",
"\n",
"このドキュメントは、[jupyter-notebook](https://jupyter.org/)形式で記述したもので、[ijavascript](https://github.com/n-riesco/ijavascript)カーネルを用いて、nodejsによってドキュメント内のコードが実行できます。\n",
"エディタ環境として、ブラウザを用いる[JupyterLab](https://github.com/jupyterlab/jupyterlab)を使いました。\n",
"\n",
"jupyterインストール:\n",
"\n",
"```shell\n",
"$ pip3 install --upgrade jupyter\n",
"```\n",
"\n",
"ijavascriptインストールとnodejsカーネルのインストール(macの場合):\n",
"\n",
"```shell\n",
"$ brew install zeromq\n",
"$ npm install -g ijavascript --zmq-external\n",
"$ ijsinstall\n",
"```\n",
"\n",
"注: zeromqのネイティブモジュールを含むので、nodejsを更新した場合、再度`npm install`する必要がでるかもしれません。\n",
"\n",
"JupyterLabインストールと実行:\n",
"\n",
"```shell\n",
"$ pip3 install --upgrade jupyterlab\n",
"$ jupyter-lab\n",
"```\n",
"\n",
"成功すればブラウザタブが開き、ipynbファイルの編集を行えます。\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 追加: ipynbからqiitaのmarkdownにしてqiitaへ貼り付ける\n",
"\n",
"この本文を記述したipynbは以下のgistへ置いてあります。\n",
"\n",
"- https://gist.github.com/bellbind/fee0ef8fd376a4b56cf4e2510baf45f1\n",
"\n",
"`jupyter-nbconvert`コマンドを使えば、ipynb形式のファイルをmarkdwon形式のファイルへ変換できます:\n",
"\n",
"```shell\n",
"$ jupyter-nbconvert --to markdown understanding-fft.ipynb\n",
"[NbConvertApp] Converting notebook understanding-fft.ipynb to markdown\n",
"[NbConvertApp] Writing 25680 bytes to understanding-fft.md\n",
"```\n",
"\n",
"macosでは、このmarkdownファイルをpbcopyコマンドでクリップボードに載せ、ブラウザ上で貼り付けられます:\n",
"\n",
"```shell\n",
"$ cat understanding-fft.ipynb | pbcopy\n",
"```\n",
"\n",
"ただし、いくつかの点でqiitaとjupyter-notebookでのmarkdownには、解釈に違いがあります:\n",
"\n",
"- 改行の解釈: qiitaは改行ごとに折り返されるが、jupyter-notebookは空行で改段落になる\n",
"- 表の解釈: qiitaでは行頭の`|`の前に空白を入れられない(装飾可能なテキストブロック扱いになる)が、jupyter-notebookでは行頭の`|`の前に空白を入れても表として処理される\n",
"- `$$`な数式ブロックの解釈: qiitaでは`$$`なブロックでは`\\begin{align}`環境は解釈されず数式扱いもされなくなるが、jupyter-notebookでは解釈される\n",
"\n",
"この対応のために、ipynbのmarkdownで使った`$$`な数式ブロック部分は、`math`コードブロックに書き換えるなど、の後処理が必要となるでしょう。\n",
"\n",
"ここではさらに、javascriptコードブロックに、qiitaのコードファイル名表示機能を使って、実行順の`:[0]`をつけておきました。\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Javascript (Node.js)",
"language": "javascript",
"name": "javascript"
},
"language_info": {
"file_extension": ".js",
"mimetype": "application/javascript",
"name": "javascript",
"version": "11.14.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment