Smoothed-particle hydrodynamics - Wikipedia
Schematic view of an SPH convolution Flow around cylinder with free surface modelled with SPH. See[1] for similar simulations. Smoothed-particle hydrodynamics (SPH) is a computational method used for simulating the mechanics of continuum media, such as solid mechanics and fluid flows. It was developed by Gingold and Monaghan[2] and Lucy[3] in 1977, initially for astrophysical problems. It has been
Designing a Tree Diff Algorithm Using Dynamic Programming and A* - Tristan Hume
During my internship at Jane Street1, one of my projects was a config editing tool that at first sounded straightforward but culminated in me designing a custom tree diffing algorithm using dynamic programming, relentlessly optimizing it and then transforming it into an A* accelerated path finding algorithm. This post is the story of the design and optimization of the algorithm, of interest to any
malloc.c を読む (malloc / free)
このシリーズではこれらの関数が内部でどのように処理されるのかを調べていきます。 malloc.c を読む (malloc / free) malloc.c を読む (bins) malloc.c を読む (arena) 今回は malloc() free() の全体像を紹介します。 注意としてここでの目的は全体を俯瞰して、詳細を詰めずとも各 bins の役割を理解し、攻撃手法を理解できるようにすることです。それに合わないマルチスレッドや最適化などにおける緻密なトリックやコーナーケースなどは暗黙的に実装されていると仮定します。その詳細についてはソースコードや他の資料を参考にしていただきたいです。 ここで扱う glibc のバージョンは v2.38 です。また glibc のソースコードはブラウザ上で読むことができます。 https://elixir.bootlin.com/glibc/lat
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倍精度浮動小数点
You (Probably) Shouldn't use a Lookup Table - Speculative Branches
Thoughts on software, hardware, performance, math, and similar topics I have been working on another post recently, also related to division, but I wanted to address a comment I got from several people on the previous division article. This comment invariably follows a lot of articles on using math to do things with chars and shorts. It is: “why are you doing all of this when you can just use a lo
githublog/2024/5/10/cordic.md at main · francisrstokes/githublog
This post is an adaptation of a twitter thread I put together a few days ago. CORDIC is an algorithm for computing trig functions like sin, cos, tan etc on low powered hardware, without an FPU (i.e. no floating point) or expensive lookup tables. In fact, it reduces these complex functions to simple additions and bit shifts. I'll cut right to the chase and tell you why I love this algorithm so much
詰将棋に対するdf-pnアルゴリズムの解説 | コウモリのちょーおんぱ
長手数の詰将棋の探索に用いられるdf-pnアルゴリズムについて、その概要と実用上の課題を解説する。 概要 #詰め将棋において、各局面の平均着手可能数は5.8手程度と言われている1。単純にこれを全探索することを考えると、\(n\) 手詰を解くためには \(5.8^n\) 局面を調べることになる。例えば、現時点で最長の詰将棋であるミクロコスモス（1525手詰）を解くためにはざっくり \(10^{1164}\) 局面を調べることになってしまう。このように、愚直な全探索では長手数の詰将棋を現実的な時間内で解くことはできないことが分かる。 しかし、ある局面が詰むことを示すだけならここまで膨大な探索は必要ない。例えば以下の局面を考える。 この局面の合法手は63金打、53金打など全部で9通りあるが、この局面が詰みであることを示すためには次の手順だけ探索できていればよい。 この探索結果より、玉方がどのよう
詰将棋アルゴリズムdf-pnのすべて | やねうら王 公式サイト
将棋AIで用いている詰将棋ルーチンにdf-pnというアルゴリズムがある。 これは、proof number(証明数)、disproof number(非証明数)を用いて効率的に探索を行い、その局面が詰むか、詰まないかを判定できるとても強力なアルゴリズムである。 将棋ファンなら『脊尾詰』と言う「ミクロコスモス」(1525手詰)を解く詰将棋専用ソフトについて一度ぐらいは聞いたことぐらいあるだろう。これは、脊尾さんが大学時代に作成されたプログラムである。そこに使われていたのが脊尾さんが考案されたdf-pnというアルゴリズムである。 df-pnに関しては、脊尾さん自身の論文(1998年)があるものの、要点しか書かれておらず、いまのようにGitHubにソースコードがあるわけでもなく、その詳細については長らく謎に包まれたままであった。(この脊尾さんの論文では、証明数のみを用いており、非証明数は陽には出
Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping
While Transformers have enabled tremendous progress in various application settings, such architectures still trail behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks. This is accomplished by training an encoder-decoder Transformer model to predict the search dynamics of the $A^*$ se
XXmallocのメモリ管理アルゴリズムについてわかりやすい記事 - Qiita
dlmalloc, tcmalloc, jemallocについて，以下の各記事を読めば各mallocのアルゴリズムはわかるはず． dlmalloc Linuxの一部やAndroidのDalvik VMで利用されている．シンプルながらうまく考えられている． チャンク(連続空き領域1つ)の境界と構造体の境界が違う所が罠． http://g.oswego.edu/dl/html/malloc.html http://mkosaki.blog46.fc2.com/blog-entry-241.html にわかりやすい講演資料が，と思ったら動画がprivateになってる… tcmalloc thread-caching malloc. Googleで利用されている． スレッドがキャッシュ持つのでfreeしてもメモリ利用量が減らない!のが罠． http://goog-perftools.sourcef
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 along several generalized means. In mathematics, the arithmetic–geometric mean of two positive real numbers x and y is the mutual limit of a sequence of arithmetic means and a sequence of geometric means: Begin the sequences
CORDIC - Wikipedia
CORDIC (coordinate rotation digital computer), Volder's algorithm, Digit-by-digit method, Circular CORDIC (Jack E. Volder),[1][2] Linear CORDIC, Hyperbolic CORDIC (John Stephen Walther),[3][4] and Generalized Hyperbolic CORDIC (GH CORDIC) (Yuanyong Luo et al.),[5][6] is a simple and efficient algorithm to calculate trigonometric functions, hyperbolic functions, square roots, multiplications, divis
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Interval parsing grammars for file format parsing (2023) | Hacker News
A brief introduction to interval arithmetic
GitHub - facebookresearch/searchformer: Official codebase for the paper "Beyond A* Better Planning with Transformers via Search Dynamics Bootstrapping".
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?