【Python】プログラムでフーリエ変換を理解しよう！【FFT, 標本化定理, ナイキスト周波数】 | Raccoon Tech Blog [株式会社ラクーンホールディングス 技術戦略部ブログ]
こんにちは。早く業務に慣れたい開発チーム入社１年目の髙垣です。 急ですが皆さん。ふと、音をフーリエ変換したい時ってありませんか？ ありますよね。 でも、「フーリエ変換って学校で計算式で習ったけど、結局は何をしているんだ？」となることありませんか？ そこで今回は計算式なんてほっといて、Pythonを使ってフーリエ変換が何をやっているのか体験してみましょう！ 環境構築 下記リポジトリをクローンしてください https://github.com/takaT6/fft-tutorial クローンができたら下記のライブラリをインストールしてください↓ pip install numpy matplotlib japanize_matplotlib japanize_matplotlib はmatplotlibに日本語を書き込めるようにするライブラリです。 日本語化をするにはフォントを入れたり、設定フ
![【Python】プログラムでフーリエ変換を理解しよう！【FFT, 標本化定理, ナイキスト周波数】 | Raccoon Tech Blog [株式会社ラクーンホールディングス 技術戦略部ブログ]](https://cdn-ak-scissors.b.st-hatena.com/image/square/62c624e35ea268ce332a1d128f27738a882d3e03/height=288;version=1;width=512/https%3A%2F%2Ftechblog.raccoon.ne.jp%2Fwp-content%2Fuploads%2F2023%2F11%2Fman-5572871_1280.jpg)
UUID(v4) がぶつかる可能性を考えなくていい理由 - Qiita
お手軽にランダムなIDを取得したい時にUUIDはとても重宝します。 でもたまに、 「このID(UUID)ってぶつかることない？対策しなくて大丈夫？」 と聞かれることがあります。 それに対して、 「ウィキペディア先生がぶつからねえって言ってたから大丈夫だよ！（＃ﾟДﾟ）」 で切り抜けるのもそろそろ限界のような気がするのでちゃんと調べました。 (もちろんウィキペディア先生を頼りました！) 2つの理論 UUIDの衝突確率について考える上で次の2つの理論が重要になります。 鳩の巣原理 誕生日のパラドクス 鳩の巣原理 鳩の巣原理とは、 m個の入れ物にn個のものを入れるとき、n > m ならば少なくとも1個の箱には2個以上のものが入る 9個の巣箱に10羽の鳩が入る場合、必ずどれかの巣箱には2羽以上入ることになるということです！(ウィキペディア先生) 考えれば当たり前のことですが同様にして考えれば、 「
カルマンフィルタの使い方 - Qiita
はじめに 書かれていること この記事では具体例を示しながらカルマンフィルタとは何か、何が出来るのかをついて解説します。カルマンフィルタについては、様々な方が既に解説記事・書籍を投稿しておりますが、初学者（特に組み込み技術者）にとって「じゃあ具体的にどう解釈すればよいの？どう実装すればいいの？」といったところが弱い気がして、もったいないと感じたため、その辺を補完する記事が書ければと思っています。 さて、この記事は下記の順で解説します。 カルマンフィルタとは何か なぜカルマンフィルタを使うのか 具体的な実装例 応用例 自分のモチベーションとしては、最近カルマンフィルタを勉強して、「なんて便利な道具なんだ！」と感じたため、それを共有する目的で記載しております。すこしでも「便利だなあ」と感じていただければ幸いです。また、この記事は、組み込み技術者としての私の視点から見た解釈で記載しております。もし
楕円同士の接触判定と衝突判定
ググっても出てこなかったので。 2つの楕円が接している（内接 or 外接）かどうか判定する方法についてです。ついでに衝突判定もできます。 衝突判定だけしたい方 以下で説明する方法でも判定自体はできますが、非常に非効率です。悪いことは言いません。GJK法などを使いましょう。凸同士なので簡単にできます。 どうしても接触を判定したい方 心して読み進めてください。 事の発端 まだそんなにバズってないけど宣伝していいらしいので． AI でも普通のプログラマーでもない優秀なプログラマーたる皆さんは，もちろん楕円が接するか判定する方法を知っていますよね？ 私は一昨日実装しました．各位の解法に興味があります．よろしくお願いいたします． — 青い楕円形のぜろ (@0_uda) October 4, 2022 もちろん楕円が接するか判定する方法を知っているので、書くことにしました。 楕円の表現方法 楕円とはい
しっかり学ぶ数理最適化 ヒューリスティック編 - Qiita
これはどんな記事? 本記事は、私がヒューリスティック関連の知識をまとめることになった際に作成したJupyter Notebookを、Qiitaの記事へと改変したものです。 前提としてこれは梅谷俊治先生の「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」という本(以下、教科書と表記)の内容に準拠しています。 そしてその内容の多くは、ありがたいことにネット上の様々な形で公開されており、梅谷先生によるスライド1やスライド2、日本オペレーションズ・リサーチ学会(以下、ORと表記)での記事1や記事2、そしてORの他の方の記事1や記事2などでも類似した内容を見ることが可能です。 (そしてそれ故に、本記事を公開させて頂いています。流石に本家の方がネット上で公開されていない内容を書くのは、例え権利的に問題がないとしても気が引けるので……) また、この記事は、それらの内容を踏まえた上で、私がネット上の様
グラフィック系アルゴリズムに役立つ「計算幾何学」の入門用ノートPDF （Computational Geometry） - 主に言語とシステム開発に関して
講義ノートの目次へ CGやゲーム開発にも役立つ計算・幾何学（けいさん・きかがく）の教科書。 点・線分などの図形を数値計算する時に必要なアルゴリズムを勉強できる。 プログラミングにすごく役立つ。 複雑な図形どうしの関係を，三角形や木構造を使ってシンプルに考えられるようになり面白い。 たとえば… 平面上に，たくさんの点が存在する。点の分布にしたがって領域を分割し，境界線を描画したい。勢力図やテリトリーを生成したい。（＝ボロノイ図） 複雑な形の部屋で，監視カメラで全体を見渡す。部屋中をもれなく監視するには，どこにいくつカメラを置けばいいか？（＝美術館問題，領域の三角形分割） 地図上で，川が国境をまたぐのはどこ？（＝線分の交差問題） 点とエリアの「当たり判定」をしたい。地図上の１点を選んだとき，その点がどの国に属するのかを高速に求めたい（＝点位置決定問題） 平面上に，たくさんの点が存在する。すべて
アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
衝突判定 2D編 - Qiita
はじめに 衝突判定2Dの記事まとめです。 Canvasを使って動くグラフなどを用意しており、Qiitaの記事としては投稿できない内容なので外部サイトにまとめています。 主に形状毎の衝突判定の考え方、計算方法、及びサンプルプログラム(TypeScript)を記載しています。 記事を追加次第更新していきます。 ※また個人の勉強として作成している側面もあるため、もっと効率の良い方法があればここのコメントで教えていただけると喜びます。 ※LGTMすると記事更新速度が上がります。 新着記事 線分やカプセルの衝突で必要となる直線と直線の最短距離に関する記事を追加しました。 直線と直線の最短距離 簡易版 直線と直線の最短距離 本気① 直線と直線の最短距離 本気② ※直線とカプセルの衝突は、判定できたのでページを用意していますが解説はまだ書けていません。 基本事項 衝突判定をしよう 衝突判定用の図形定義
再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに 再帰関数は初めて学ぶときに壁になりがちで なんとなくわかった...けれど どんな場面で使えるのだろう...いい感じの例を探したい！ という気持ちになりがちです。再帰関数は、なかなかその動きを直感的に想像することが難しいため、掴み所が無いと感じてしまいそうです。 そこで本記事では 再帰関数の動きを追いまくることで、再帰関数自体に慣れる 再帰的なアルゴリズムの実例に多数触れることで、世界を大きく広げる！ ことを目標とします。特に「再帰関数がどういうものかはわかったけど、使いどころがわからない」という方のモヤモヤ感を少しでも晴らすことができたら嬉しいです。なお本記事では、ソースコード例に用いるプログラミング言語として C++ を用いておりますが、基本的にはプログラミング言語に依存しない部分についての解説を行っています。 追記 1. 再帰関数とは 再帰の意味はとても広いです。自分自
UX最強のベジェ曲線「κ-Curves」を完全に理解する - Qiita
TL;DR 全てのユーザ制御点上を通り、 全ての曲率極大点がユーザ制御点上にある そんな超便利なのにあまり知られていないパラメトリック曲線こと「κ-Curves」。 Adobe ResearchとテキサスA&M大学のYan氏らがSIGGRAPH 2017で発表した研究で、Adobe Illustratorに実装されており、Adobeが特許を取っています（無断の商用利用はNG）。 新しめなせいか、検索しても情報があまり出てきません。 この論文と同じ流れを、前提知識や行間を補いつつ日本語で追っていきます。 C#で実際に実装もしていきます。 論文に忠実に実装するとちょっとバグるので、それについても少し。 ※本記事では、上記論文から一部画像や式を引用しています。 これは論文から引用した図で、他の様々なパラメトリック曲線とκ-Curvesの比較。 左から順に、Interpolatory subdiv
FFT（高速フーリエ変換）を完全に理解する話 - Qiita
となります。 この $C_i$ を、$0\leq i\leq 2N$ を満たすすべての $i$ について求めるのが今回の目標です。 それぞれ愚直に求めると、$f,g$ の全項を組み合わせて参照することになるので、 $O(N^2)$ です。これをどうにかして高速化します。 多項式補間 愚直な乗算は難しそうなので、$C_i$ の値を、多項式補間を用いて算出することを考えます。 多項式補間とは、多項式の変数に実際にいくつかの値を代入し、多項式を計算した値から、多項式の係数を決定する手法です。 たとえば、$f(x)=ax+b$ という $1$ 次関数があるとします。 $a$ と $b$ の値は分かりませんが、$f(3)=5,f(7)=-3$ がわかっているものとします。 実際に $3,7$ を代入してみると、 $3a+b=5$ $7a+b=-3$ と、連立方程式が立ち、$a,b$ の値が求められま
乱数について本気出して考えてみる｜TechRacho by BPS株式会社
プログラミングをやっていると、様々な乱数に出会います。乱数に関しては大勢の研究者が色々な研究結果を出しているため、種類も増え、いったいどれを使えばいいのかと悩む原因にもなります。 大勢が研究し利用している分野ですから、私以外でも大勢が乱数に関する記事を書いているため、あえて新しい記事を書く価値は高くないかもしれません。まあ、既に理解している人はここで記事を閉じるか、暇つぶし程度の感覚で読んでいただくと良いかと思います。 真乱数と疑似乱数 プログラミングの世界の中でいわゆる "乱数" として扱われることが多いのは擬似乱数です。疑似、と付くからには、これは実のところ乱数ではないと言えます。とは言え、擬似乱数を乱数でないと言ってしまうと話が終わってしまうので、疑似乱数を含む乱数を広義の乱数とします。この記事で扱うのは広義の乱数です。逆に、狭義の乱数、本物の乱数は真乱数と言います。 本物と言いまし
楕円曲線暗号アルゴリズムを理解する｜TechRacho by BPS株式会社
お久しぶりです。yoshiです。みなさん、夏を満喫していますか？ 私は溶けそうです。日本の夏はとってもあつい。 覚えている方がいるかどうかは分かりませんが、以前私はRSA公開鍵暗号アルゴリズムを理解するという記事を書きました。今回はその続編（？）です。 楕円曲線について 楕円曲線、という言葉を事前知識無しで見ると、 多分こんな画像が脳裏に浮かぶと思います。違います。 楕円曲線の楕円は楕円積分から現れた言葉で、楕円積分は文字通り楕円の弧長などを求める方法なので全くの無関係とは言えませんが、少なくとも楕円曲線と楕円は別の図形です。楕円のことは忘れましょう。 実際の楕円曲線は、例を示すと以下のような曲線です。 一般化すると (ただし または ) という式で表されるこのような曲線をワイエルシュトラス型楕円曲線と呼びます。ワイエルシュトラス型、と付いているのは他のパターンもあるからで、 こんな形の楕
Lerpで作るアニメーション(easing)を解析する - Qiita
Lerpの引数に自身のpを入れているのがポイント。これだけで次の値をゲットでき、上のような動きを作れます。0.1f を変更すると、どのぐらい急に移動するかを調整できます。（大きいほど急に動く。経験上、どんな状況でもまず0.1を入れておいて様子を見るのがいいです） 一般項 なぜ一般項？ 先ほどの実装は、数学的に言えば「漸化式」と呼ばれるものでした。ほとんどの場合これで問題はないのですが、 ・任意の時刻の状態を得たい ・逆再生したい のような状況では漸化式での対応が難しくなります。一般項ならそういったことも解決できるわけです。 Mathf.LerpのLerpはLinear Interpolationの略で、ようするに線形補間です。 $a$ と $b$ をパラメータ$t$で線形補間すると $result=(1-t)a + tb$ となり、$t$が０〜１の間で変化すれば結果は$a$と$b$の間に収
一般的なRPGの経験値を計算してみる - Qiita
レベルアップを重ねていくゲームがあったとしたら、そのレベル間の努力は均一にしたい、という要求が生まれますよね。今回はその要素となる経験値の計算をしてみましょう。 経験値の要件 よくあるRPGの例として。レベルアップによりプレイヤーは強くなるのですが、例えば 「レベル３からレベル４に上がるために必要な努力」 と、 「レベル30からレベル31に上がるために必要な努力」 を同じにしたい、と考えます。レベルをひとつ上げる努力をずっと同じにしないと、レベルアップの頻度を一定に保てませんから。（この時点で、単純な足し算引き算では値が出せないことに気がつきます） また、ここではその努力を「戦闘」とし、戦闘で得られる報酬を「経験値」とします。 そして戦闘に勝利した際に 「自分のレベルより敵のレベルが低いときには経験値は少なめに」 「自分のレベルより敵のレベルが高いときには経験値は多めに」 もらえるものとし
浮動小数点数の限界を把握する - Qiita
いまやあらゆるプログラムで浮動小数点数が使われていますが、ここで改めてその性質を確認してみましょう。 フォーマットのおさらい 浮動小数点数には単精度(float)と倍精度(double)がありますが、例えばゲームプログラムであれば使用頻度が高いのはfloatでしょう。 floatのフォーマットはIEEE754という規格で 符号部：1bit 指数部：8bit 仮数部：23bit と定められています。 指数部には負の値が欲しいので（数値の符号とは別に）、あらかじめ127を加算した値を指数部に格納します。（追記：コメントに議論あり、規格策定の歴史的経緯に言及しているわけではありません） よって指数部にゼロ乗を格納したい場合は上の図のように 01111111 が入ります（という規格です）。 仮数部は1.0を基準に考えたいので、あらかじめ1.0を減算した値を格納します。 よって仮数部に1.0を格納し
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
[0.0, 1.0) の乱数を得るための“本当の”方法
数理最適化ことはじめ / Introduction to Mathematical Optimization
「フーリエ級数」から「高速フーリエ変換」まで全部やります！【2019.07.20更新】
