高速ゼータ変換について - Qiita
これは データ構造とアルゴリズム Advent Calendar 2018 の 25 日目の記事です。 突然ですが 次の問題を解いてみましょう。 整数 $N$ と $A_0, A_1, A_2, ... A_{2^N-1}$ が与えられます。 $s, t$ に対して $s\ AND\ t=t$ の時、$t \subset s$ と表記することにします。 $0≦i<2^N$ を満たす整数 $i$ について、$j \subset i$ を満たす整数 $j$ についての $A_j$ の総和をそれぞれ求めなさい。 ただし、$a\ AND\ b$ は $a$ と $b$ のbitごとの論理積を求める演算とします。 $1≦N≦10$ $1≦A_i≦10^9\ (0≦i<2^N)$ 実行時間制限 2秒 問題文にある $s\ AND\ t=t$ が何を言っているのかちょっと分かりにくいかもしれませんが、こ
ゲルファント変換入門 - p進大好きサークル
趣旨 競技プログラミングでは非常に多くの畳み込みとゲルファント変換が登場するのですが、ゲルファント変換という名称が競技プログラミング界隈ではあまり有名ではないようなので簡素な解説を書いてみます。どうせ$n$番煎じかもしれませんが、現状としてあまり有名でない以上はまだまだこういう記事が増えることで調べ物の助けになる人もいるかと思いますので、あまり気にせず書いてみることにします。毎回ネタを思いついてはどうせ$n$番煎じと思ってやめちゃうのですが、たまには許してもらえますよね。 まず競技プログラマーなら以下の用語に聞き覚えがある人も多いのではないでしょうか？ 累積和 部分集合上のゼータ変換 約数ゼータ変換 倍数ゼータ変換 離散フーリエ変換（DFT） アダマール変換 これらは全部ゲルファント変換です。それぞれの原理を一々別個に勉強した覚えのある人も多いのではないでしょうか？ ゲルファント変換を知っ
物理学者ニュートンが300年前に考案して現代でも実用されるアルゴリズム「ニュートン法」がアップデートされる
by Alexander Borek 約300年前に物理学者のアイザック・ニュートンが考案した「ニュートン法」は、現代でも物流や金融工学、コンピュータビジョン、純粋数学など多岐にわたる分野で重要な役割を果たしているアルゴリズムです。これまでさまざまな数学者がこのニュートン法の改良に苦心しており、近年の研究でついにアップデートされたと科学系ニュースサイトのQuanta Magazineが紹介しています。 Implementable tensor methods in unconstrained convex optimization | Mathematical Programming https://link.springer.com/article/10.1007/s10107-019-01449-1 Three Hundred Years Later, a Tool from Isaa
FFT:NTT
2020/07/13 HCPC 2020/07/13 HCPC /46 !2 2020/07/13 HCPC /46 f(x) n − 1 ζn 1 n 𝒪(n2 ) 𝒪(n log n) !3 ̂ f(t) = n−1 ∑ i=0 f(ζi n)ti 2020/07/13 HCPC /46 !4 2020/07/13 HCPC /46 (x + x2 + x4 )(x3 + x6 + x10 + x15 )[x7 ] = 2 f(x)[xa ] := xa !5 2020/07/13 HCPC /46 f(x), g(x) n m f(x)g(x) n + m − 1 f(x) = (1 + 2x) g(x) = (3 + x + 4x2 ) f(x)g(x) = 3 + 7x + 6x2 + 8x3 !6 2020/07/13 HCPC /46 !7 f(x), g(x) n m
NTT(数論変換)のやさしい解説 - Senの競技プログラミング備忘録
この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな なんで$ 10 ^ 9 + 7 $じゃダメなのか 原始根って何？ とかについてもこれを見ればわかります。 前提知識としては、Fast Fourier Translation(高速フーリエ変換)が必要です。 kaage大先生のQiita記事とかは中高生にもわかりやすく書かれています。 下に一応自分の勉強ノートを載せます。(上の記事の行間を埋めた感じです) では、数論変換について説明したいと思います。 高速フーリエ変換の弱点 高速フーリエ変換は正しいですが、弱点として精度が足りないというのがあります。 なぜならば、複素数の1の$ 2 ^ m $乗根は計算上ではれっきとした64bit倍精度浮動小数点
Arithmetic–geometric mean - Wikipedia
This article is about the particular type of mean. For the similarly named inequality, see Inequality of arithmetic and geometric means. Plot of the arithmetic–geometric mean among several generalized means. In mathematics, the arithmetic–geometric mean (AGM or agM[1]) of two positive real numbers x and y is the mutual limit of a sequence of arithmetic means and a sequence of geometric means. The
CORDIC - Wikipedia
CORDIC, short for coordinate rotation digital computer, is a simple and efficient algorithm to calculate trigonometric functions, hyperbolic functions, square roots, multiplications, divisions, and exponentials and logarithms with arbitrary base, typically converging with one digit (or bit) per iteration. CORDIC is therefore an example of a digit-by-digit algorithm. The original system is sometime
超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 - Qiita
1. はじめに ～メインを読むための準備～ まず、大きな数の計算の話をする前に、少しコンピューターと計算回数について話しましょうか。 コンピューターは、現代ではソフトウェアやアプリケーションの開発に使われていますが、これには重要な背景があります。これは「計算がめっちゃ速いこと」です！人間なんかと比べたら、圧倒的な計算スピードを誇ります。 1-1. 人間の計算速度はどのくらい？ まず人間はどのくらいの速度で計算できるでしょうか？速い人も遅い人もいると思います。 例えば、$628 \times 463$ の計算を、今やってみましょう。10 秒以内で計算できたらかなり速い方でしょう。この計算では、次のように「単純計算」を合計 28 回もしていることになります。 9 回の 1 桁 × 1 桁の掛け算 6 回の 1 桁 × 1 桁の足し算 13 回の繰り上がり計算 もし $628 × 463$ が
AlphaTensor :強化学習を利用した高速な行列積演算アルゴリズムの発見 - Qiita
1. はじめに 本記事では、2022年10月にNatureに掲載されたAlphaTensor[1]および関連分野を紹介します。AlphaTensorは「AIが行列積演算の新しいアルゴリズムを発見した」といううたい文句のもとSNSを中心に大きな話題となりました。具体的には、[1]でAIが”発見”したアルゴリズムのひとつでは2進数上の4×4の行列の積を47回の掛け算で計算することができ、これは[1]以前の最速49回(Strassenのアルゴリズム)を上回ったことになります。なお、Strassenのアルゴリズムの49回はその発見から[1]まで約50年間破られていませんでした。 「AIが新しいアルゴリズムを発見した」という広告ですが、実際は 「あるテンソルのよい分解方法を強化学習を利用して探索した」 といった方が正しいです。この 「あるテンソル」はその分解方法と「行列積のアルゴリズム」が自然と対応
「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443
「無限に都市が生成されるアルゴリズム」で生成された都市を自由に歩き回ってみた - GIGAZINE
波動関数とは「物体の状態そのもの」が波動で表されるという関数であり、時にはゲーム内の物理シミュレーションなどに利用されることもあります。そんな波動関数がある1つの固有の状態に収縮することを波動関数の崩壊と呼び、そんな波動関数の崩壊を用いた「無限に都市が生成されるアルゴリズム」を作り出す猛者が登場。実際にどのような都市生成ツールになっているのか、実際にダウンロードして試してみました。 Wave Function Collapse by marian42 https://marian42.itch.io/wfc GitHub - mxgmn/WaveFunctionCollapse: Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics. https://g
Kalman Filter, Extended Kalman Filter, Unscented Kalman Filter
The second term of Self-Driving Car Engineer Nanodegree devotes Robotics. Therefore, the first two projects we spend on learning Kalman filter (KF) and its variations. We implemented three different versions of KF suitable for SDC and I decided to write and overview which describe key differences. The first question is why we need KF at all. Why can’t we rely on measurement we receive from our sen
Scalaで型レベル”だけ”でクイックソート | POSTD
Scalaの型システムが先進的であることは、皆さんもご存じのことかと思います。この投稿では、Scalaの型システムのみを使った クイックソート アルゴリズムの実装方法をご紹介したいと思います。なお、ここで紹介するデモの完全なコードは こちら をご覧ください。 自然数 まずは準備から。ソートアルゴリズムを実装するには、ソートする対象が必要ですよね。ここでは自然数を用います。もちろん、Scalaの型システムには利用可能な自然数はありません。そんなわけで、全ての自然数の型を作る必要があります。 型を無限に作るというのは、恐らく時間の浪費になるでしょうから、ここはもう少し賢い手を考えます。そう、数学を使いましょう。 ペアノの公理 ペアノの公理とは、自然数を形式的に定義するためのシンプルな方法のことです。 0 は特別なものとする。 0 は自然数である。 全ての自然数 n には、それに続くもう1つ別の
最大エントロピーモデル - DO++
自分の復習も含め、最大エントロピーモデルについて勉強会で発表しました。発表資料 [ppt] [pdf] 今年のACLやICMLなどでの発表などを解説してます。論文中になかった式導出とかもしてみてます。 発表中では結構口頭で補足した部分があって、この資料だけでは不十分だと思います。適宜引用先などを参照してください。 最大エントロピーモデルは高次元の確率分布推定に適していて自然言語処理や、最近だと動植物がどのように分布しているかなどの推定等、広い分野で使われている確率モデルです。 ＃修正＋質問・回答スライドを追加しました
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://cr.yp.to/arith/logagm-20030717-retypeset20220327.pdf
https://cr.yp.to/lineartime/multapps-20080515.pdf
Full page fax print
What algorithm is used by computers to calculate logarithms?