3命令のCPU処理で済む高速なうるう年判定アルゴリズム - Faith and Brave - C++で遊ぼう
要約 この短いコードで、西暦102499年までのうるう年を判定できます。このマジックナンバーはz3というSMTソルバーで見つけ出されました。 bool is_leap_year_fast(uint32_t y) { return ((y * 1073750999) & 3221352463) <= 126976; } はじめに GCC (libstdc++) のうるう年判定のアルゴリズムが、以下のように変更になりました (commit)。 constexpr bool is_leap() const noexcept { - return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0; + const auto __y = static_cast<uint32_t>(_M_y) + 32800u; + return ((__y * 1073750999u)
Algorithmica
Algorithmica is an open-access web book dedicated to the art and science of computing. It is created by Sergey Slotin and the teachers and students of Tinkoff Generation — a nonprofit educational organization that trains about half of the finalists of the Russian Olympiad in Informatics. The English version of the website is a work in progress; the only useful thing you can find here is the contin
GitHub - xai-org/x-algorithm: Algorithm powering the For You feed on X
This repository contains the core recommendation system powering the "For You" feed on X. It combines in-network content (from accounts you follow) with out-of-network content (discovered through ML-based retrieval) and ranks everything using a Grok-based transformer model. Note: The transformer implementation is ported from the Grok-1 open source release by xAI, adapted for recommendation system
Xの新アルゴリズムがオープンソースで公開 「おすすめ欄」選出のメカニズムは
米Xは1月20日（現地時間、以下同）、イーロン・マスク氏の予告通り、Xの新しいアルゴリズムをオープンソースで公開した。アルゴリズムはおすすめ欄に表示する投稿を選出するもので、GitHubでソースコードを確認できる。 新たなアルゴリズムでは、GrokベースのTransformerモデル「Phoenix」を活用し、投稿がエンゲージメントを獲得する確率を予測。結果を基に投稿をスコアリングし、上位の候補をおすすめ欄に表示する。 一連の工程は大きく7ステップに分かれる。まずは投稿を閲覧するユーザーのエンゲージメント履歴やフォローリストなど取得。次にそのユーザーがフォローしているアカウントの投稿とそうでない投稿から、表示するポストの候補を選出する。 その後、各候補には属性情報を付与する。例えば投稿者のユーザー名やサブスクリプションへの加入状況、投稿がテキストのみかそうでないか、動画の場合はその長さなど
高速整数除算のメモ
a64fx SVE 1.0 に高速(近似)整数除算(逆数)ない... SVE 2.0 には urecp あるけど.. とりまここからスタートする! Gemini クンに調査させた. ただ基本は precompute なので divisor(分母)がある程度使い回せることが前提. 要素ごとに変化する場合は遅い(FPU が使えるのであれば fp -> recpe などの高速逆数命令 + newton raphson iteration が効率良いであろう) https://github.com/lemire/fast_division が更新されていないのは、そのリポジトリが提唱したアルゴリズム（LKK法: Lemire-Kaser-Kurz, 2019年）が完成された技術であり、概念実証（PoC）としての役割を終えているためです。 しかし、高速整数除算の分野はその後も発展しています。 特に2
文字列変換アルゴリズム「Burrows-Wheeler変換」についてGoogleがムービーで解説、考案者本人も出演して説明する貴重な映像
Burrows-Wheeler変換は、イギリスのコンピュータ科学者であるマイク・バロウズ氏とデビッド・ウィーラー氏によって考案された文字列変換アルゴリズムで、圧縮アルゴリズムなどで使われています。GoogleがこのBurrows-Wheeler変換を解説する動画を公開しており、その中では考案者であるバロウズ氏も登場します。 Burrows-Wheeler Transform (Ep 4, Compressor Head) Google - YouTube Burrows-Wheeler変換は、データを直接圧縮するアルゴリズムではなく、データを他の圧縮アルゴリズムがより効率的に処理できるように並べ替える、可逆的なデータ変換手法です。Linuxなどで広く利用されている圧縮ツール「bzip2」の中核技術としても知られています。 一般的な情報量の指標であるエントロピーは、データに含まれる記号の種類
「最短経路問題」の新アルゴリズム。数十年来の“理論的限界”破ったと発表【研究紹介】 レバテックラボ（レバテックLAB）
中国の清華大学、米国のスタンフォード大学、ドイツのMax Planck Instituteに所属する研究者らが発表した論文「Breaking the Sorting Barrier for Directed Single-Source Shortest Paths」は、グラフ理論の最短経路問題において、長年の理論的限界を打ち破るアルゴリズムを発見したとする研究報告である。 ▲論文のトップページ グラフ理論における単一始点最短経路問題（Single Source Shortest Path Problem）は、ある地点から他のすべての地点への最短ルートを見つける問題で、カーナビのルート検索やネットワーク設計など、幅広い応用を持つ。 コンピュータサイエンスの基礎的な問題のひとつであり、この問題を解く最も有名な方法が、1959年に考案されたダイクストラ法である。ダイクストラ法は、出発点から波紋が
なっとく！アルゴリズム 第2版 | 翔泳社
人探し、バスの乗り継ぎ、お買いもの…… 半径3メートルの身近なアルゴリズムはこんなにわかりやすい！ さまざまなアルゴリズムの背後で使われる≪木構造≫の解説を増補した第2版！ プログラミングにおいてアルゴリズムの知識は欠かせません。しかし、いざアルゴリズムの学習をはじめると、理屈の山と数式の谷間で迷子になることが少なくありません。 そんなときにおすすめなのがこの一冊。本書は、人探しやバスの乗り継ぎなど身近な例を通して、イラストとサンプルプログラムを援用しながらアルゴリズムについて平易に解説してくれます。 読み進めるには、中学レベルの代数の基礎を知っていれば大丈夫。プログラミング言語をどれか1つ知っていれば、さらに理解が深まります。 最後まで読めば、応用範囲の広い重要なアルゴリズムの数々をしっかり理解できます。 ［本書は、"Grokking Algorithms, Second Edition
高速で頑健なシェーダー乱数の比較と提案 - 屋根裏工房改
はじめに シェーダー (HLSL) で乱数を発生させたくなることがしばしばあります。 直接的にはホワイトノイズ、間接的にはパーリンノイズなどが挙げられます。 そういうシェーダーを書いたことがある方は、 frac(sin(...)) みたいな擬似乱数生成器を目にしていることでしょう。 ですが、乱数を発生させる手法は星の数ほど存在します。品質や速度もそれぞれ異なる擬似乱数生成器がたくさんあります。 本稿ではそれらのシェーダー乱数の性能比較を行っていきたいと思います。 シェーダー乱数の定義 さて、乱数とはいっても、シェーダーでよく使われる乱数は CPU ベースの (メルセンヌツイスタ とかの) 擬似乱数生成器とは設計レベルで異なることが多いです。 まず、状態を持たない、ある種のハッシュ関数のような実装をすることがほとんどです。 大抵の場合、座標を引数にとることになるでしょう。毎フレーム変化する乱
CRDTs go brrr
5000x faster CRDTs: An Adventure in Optimization July 31 2021 A few years ago I was really bothered by an academic paper. Some researchers in France put together a comparison showing lots of ways you could implement realtime collaborative editing (like Google Docs). They implemented lots of algorithms - CRDTs and OT algorithms and stuff. And they benchmarked them all to see how they perform. (Cool
世界1位取った後3年間オセロAIを作り続けたらﾅﾆﾓﾜｶﾗﾅｸなってﾁｮｯﾄﾀﾞｹﾃﾞｷﾙようになった話 - Qiita
2021年、ふとしたきっかけでオセロAIを作り始め、オセロAIコンテストに作ったAIを提出し、なんやかんやあって半年かけてそのコンテストで世界1位になりました。 それで満足…？と思いきや、全然満足せず、コンテスト関係なしにオセロAIを作って早3年。この記事ではオセロAIが色々なところに私を連れて行ってくれた話と、オセロAIが深いという話をします。 この記事は2年ほど前に書いていっぱい読んでいただけた以下の記事「ｶﾝｾﾞﾝﾆﾘｶｲｼﾀ話」の続編、みたいな立ち位置です。単体で読んでも、以下の記事と合わせて読んでも楽しめます。 世界1位からさらに高みを目指す 私が参加したオセロAIのコンテスト(CodinGame Othello)は、コンテストという特性上、かなり厳しい制約が設けられていました。例えば着手する時間です。これは1手あたり0.15秒以下でないといけません。また、コード長にも制限があり
Bloom Filters
2024-02-19 Everyone has a set of tools they use to solve problems. Growing this set helps you to solve ever more difficult problems. In this post, I'm going to teach you about a tool you may not have heard of before. It's a niche tool that won't apply to many problems, but when it does you'll find it invaluable. It's called a "bloom filter." Before you continue! This post assumes you know what a h
The Myers diff algorithm: part 1 – The If Works
If you enjoy this article, I have published a book explaining the internals of Git through implementation: Building Git. — As a programmer, you probably use a version control system such as Git, and spend an awful lot of your time looking at diffs. You use them to check over your uncommitted work in progress, to look at what changed in a single commit, to compare two branches before performing a m
Othello is Solved 論文解説 (私見) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう
DeepMindが深層強化学習を利用してアルゴリズムを改善するAI「AlphaDev」を発表、すでにソートアルゴリズムやハッシュ関数の高速化に成功
AlphaGoの開発元として有名なGoogle DeepMind社が深層強化学習を応用してさまざまなコンピューティングアルゴリズムを改善するAI「AlphaDev」を発表しました。同時に、AlphaDevを利用してソートアルゴリズムを高速化できたという論文がNatureに掲載されています。 AlphaDev discovers faster sorting algorithms https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms Faster sorting algorithms discovered using deep reinforcement learning | Nature https://doi.org/10.1038/s41586-023-06004-9 ソートアルゴリズムとは
Beautiful Branchless Binary Search
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requir
NASAが宇宙規模の通信などで発生する損失にも耐えられるよう作った画像圧縮アルゴリズム「ICER」が誰でも利用可能に
NASAは、「宇宙から地球に無線で画像を転送する」といったデータ損失の大きな状況に最適化した画像圧縮アルゴリズム「ICER」を開発しています。そんなICERをC言語のライブラリとして実装したものがGitHubで無料公開されています。 GitHub - TheRealOrange/icer_compression: Progressive, error tolerant, wavelet-based image compression algorithm https://github.com/TheRealOrange/icer_compression NASAは火星探査などのミッションで現地の様子を撮影した画像データを地球へ送信しています。異なる場所へデータを送信する際は、地球上での通信であってもデータの損失が発生しているのですが、地球と火星などの宇宙規模の通信ではデータの損失は非常に大き
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
【実践】エンジニアの基礎教養-アルゴリズムを学べる本
Raft(分散合意アルゴリズム)について
CPU/GPU高速化セミナー 浮動小数点から文字列への高速変換の論文を読んでみた / cpugpu acceleration seminar 20230201