要約 この短いコードで、西暦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)

🌐 Read this post in English この記事ではOxc Minifierの変数マングル処理の仕組みを解説します。 変数マングルとは？ まず、そもそも変数マングル (mangling)が何かを説明しましょう。 変数マングルは、変数名を短いものに置き換えることでコードサイズを削減する処理で、ミニファイ(minify)の処理の一種です。 例えば、

New AI agent evolves algorithms for math and practical applications in computing by combining the creativity of large language models with automated evaluators

January 2016 boasted a Powerball jackpot of 1.5 billion dollars. This generated a lot of interest in the lottery and the Los Angeles Times released a simulator where you start with 100 dollars and play until that is gone. I had seen previous work for predicting Java’s Math.random() and thought it would be a fun project to replicate for the browser. The first step is to find the algorithm used in t

LabBaseテックカレンダー Advent Calendar 2024の12月17日分のアドベントカレンダーです。 このブログのゴール ssh-keygenしたときに出るあのキラキラの正体を突き止めて、Rustで完全再現する⭐️ 再現するだけにとどまらずオエー鳥AAで似たようなものを作る🐦‍⬛ コードはここ 出典 http://www.dirk-loss.de/sshvis/drunken_bishop.pdf https://github.com/lfam/randomart あのキラキラの正体 randomartって言う テキストベースのフィンガープリントだと人間が誤って確認するリスクがあるから、視覚的な差分が取りやすいようにAAとして可視化している アルゴリズム 公開鍵ファイルの解析 公開鍵の中身はこうなっている ssh-ed25519 AAAAC3NzaC1lZDI1NTE5A

過去のテストの実行時間を利用してテストの sharding を効率化する Tenbin というツールを作りました。 この記事では Tenbin が解決する課題と内部実装の詳細について解説します。ツールの使い方などは、リポジトリの README をぜひ読んでもらえればと思います。 Tenbin が解決する課題 テストの実行時間を削減するために、CI などではテストを sharding (分割) して実行することがあると思います。フロントエンドでよく使われる Jest、Vitest、Playwright などのツールでは、実際に sharding の機能を提供しています。 確かに sharding はテストの実行時間を削減できるのですが、分割のアルゴリズムがいまいちで shard 毎の実行時間に大きく差が出てしまった経験はないでしょうか？[1]Tenbin は、この問題を過去のテストの実行時間

2002年から約10年 IIJ技術研究所長. 年を取ってからは古い計算機や昔の計算法に興味が増し, シミュレーターを作ってそのプログラムを書いたり. 近頃はKnuthのTAOCPにあった問題のプログラムなどに挑戦したりしている. 【IIJ 2022 TECHアドベントカレンダー 12/5（月）の記事です】 クリスマスといえば, 英国王立研究所が1825年から続けている「クリスマス講演」が有名で, 岩波文庫にあるFaradayの「ロウソクの科学」はその1860年の講演だ. それに比べればまだ20年くらいだが, スタンフォード大学のKnuth教授も毎年「クリスマス講義」を続けている. しかし今回のブログはそのKnuthによる大著, The Art of Computer Programming(以後TAOCP)が話題である. 上段の左の横積みは, 英語版TAOCPの, 上から第1, 2, 3,

ID を採番するときによく使われる UUID Version 4 の課題として「順序性がなくソートしにくい」という側面があり，ULID (Universally Unique Lexicographically Sortable Identifier) を使えばソートできるようになるという記事を前に書いた． kakakakakku.hatenablog.com 関連して調査をしていたら，標準化団体 IETF (Internet Engineering Task Force) によって，UUID Version 6, 7, 8 という新しい仕様が提案（ドラフト段階）されていることを発見した❗️UUID Version 6, 7, 8 の目的を簡単にまとめると「タイムスタンプ情報を使ってソートできる ID を採番できるようにする」となり，もしこの仕様が取り込まれると，UUID を活用する幅がさ

地球の自転が高速化して｢負のうるう秒｣が来そう。Google、Amazon、Metaは猛反対2022.08.03 23:0066,411 satomi なんせ1秒減らす｢負のうるう年｣は初めて。やれる気がしません。 年末カウントダウンで午前零時を2回カウントすることで1秒加え、自転速度と協定世界時（UTC）の誤差を埋めてきた｢うるう秒｣に異変が生じ、地球自転が高速化に一転。午前零時をスキップして1秒引く調整が叫ばれるなか、｢1秒足すだけでも世界中のシステムがパニックだったのに、1秒引いたらどうなっちゃうの⁉｣という不安がIT業界に広まり、Google、Amazonに次いでMeta（メタ、旧Facebook）も｢うるう秒やめようぜ｣と言い出しています。 うるう秒は1972年以降27回行なわれていますが、地球の自転スピードが遅くなるのに合わせて毎回1秒ずつ足すのが常でした。マイナスにすると、プ

テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を

September 29, 2021 by Henning Dieterichs, @hediet_dev When dealing with deeply nested brackets in Visual Studio Code, it can be hard to figure out which brackets match and which do not. To make this easier, in 2016, a user named CoenraadS developed the awesome Bracket Pair Colorizer extension to colorize matching brackets and published it to the VS Code Marketplace. This extension became very popu

はじめに ある乱数生成器が N 個のセットのなかからランダムに一つを返すとき、その返り値をそれよりも小さな範囲に収まるようにしてから利用したい、という要件にたまに出会います。例えば、[0, 2^32) の範囲内の乱数を生成する乱数生成器を利用できる環境で、サイコロの目をランダムに計算するには、何らかの方法を使って [0, 6) の範囲の乱数に収める必要があります。このような getrandom(2) や /dev/urandom を使った乱数生成器の例以外にも、例えば Int64 のユーザー属性値を入力にしてユーザーを 10 種類に均等に分類したいという類の要件を過去にレビューしたこともあります。 ある値域をより小さい値域にマップするために、よく利用されるのは剰余（モジュロ）演算です。乱数生成器の例でいえば、その返り値を X とすると、 X % 6 を計算すれば結果は [0, 6) に収ま

曖昧検索は便利なものである。「ピテカントロプス」の綴りは難しいが、最近のGoogle検索は曖昧検索対応しているようで、「pitekantoropusu」で検索してもちゃんと直立猿人(Pithecanthropus)がみつかる。しかし「musogurusuki-」でムソルグスキーを検索できないようなので、改良の余地はあるのかもしれない。 Unix系の計算機システムやプログラミング言語では曖昧な検索を行なうために正規表現を使えるものが多い。正規表現とは検索パタンとして文字列の繰り返しや文字列の選択を指定できるもので、a*という表現で「0回以上のaの繰り返し」というパタンを指定したり、(abc|def)という表現で「abcまたはdef」を指定したり、a.cという表現で「aac, abc, acc, ...」を指定したりできる。たとえばpi.*ca.*puのような曖昧なパタンを指定すれば辞書からP

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 下記はスライドの講演の書き下しのようになっているので、スライドだけ見るんじゃなくて、スライドを見ながら文章を読み進めたい方向けです。 CRDTとは 今回は、CRDTというデータ構造について紹介します。CRDTはそもそも2011年にSSS(Stabilization, Safety, and Security of Distributed Systems)という国際会議で、INRIA(フランス国立情報学自動制御研究所)のMarc Shapiro博士によって発表された、比較的新しいモノです。 CRDTは"Conflict-free Repl

こんにちは、BASEのフロントエンドチームでエンジニアリングマネージャーをやっている松原(@simezi9)です。 私は最近ではマネージャーとしてコードを書くことよりもチームの編成や採用などをメインに業務を行っているのですが、 そんな中でチラっと書いたコードで見事に落とし穴にハマって失敗をしたのでその共有記事です まえがき BASEのフロントエンドチームは現在15名ほど（うち業務委託5名）で運営されています。 この人数は今後もどんどん増えていく予定なのですが、目下全社的にリモートワークになっている事情も手伝ってメンバー同士の関係性が希薄になってしまう懸念を持っていました。 BASEの中では常に複数のプロジェクトが走っているのですが、それぞれのプロジェクトにフロントエンドエンジニアは2〜3名ずつ配置されています。 そんななかでアサインされた人同士がフロントエンドエンジニア同士であるにも関わら

A few years ago I had the privilege of being an engineer on the Google Photos team and part of the initial launch in 2015. A lot of people contributed to the product — designers, product managers, researchers, and countless engineers (across Android, iOS, Web, and the server) to name just some of the major roles. My responsibility was the web UI, and more specifically the photo grid. We wanted to

アークシステムワークスによる対戦格闘ゲーム『GUILTY GEAR XX ΛCORE PLUS R』（以下、GGXXACPR）のSteam版において、オンライン対戦の遅延を改善する「GGPO」と呼ばれるネットコードが試験的に導入された。このパブリックテストは10月29日から開始されている。また同時期に開催されているSteamのハロウィンセールによって同作は現在80%オフの296円にて購入することが可能だ。 Early reports say that #GuiltyGear XX Accent Core Plus R runs SMOOV with its new rollback code. You know what's SMOOV-ER than that? Picking it up for $2.99 on @Steam's Fall sale.https://t.co/JTkQ