NP-complete や NP-hard のような概念は、競プロ文脈ではあまり重要視されることがない気がします。 多項式時間で解くのが厳しそうな問題が $n\le 20$ 程度の制約で出題されることはあっても、それが実際に NP-hard であることを示す必要は別にありません（…

浮動小数点型の二分探索についてはいろいろと議論があります。 背景 本題 単純な撃墜ケース それっぽい例 他の例 まとめ おまけ あとがき おわり 背景 下記のような形式の問題を考えます。 実数に関する述語 $P\colon \R\to\{0, 1\}$ と $x_L, x_R\in\R$ が…

www.youtube.com 補足： ・N >= 1 を仮定しても構いません。 ・C言語でなくても構いません。 本題 証明 ？？？ あとがき おわり 本題 下記のコードの正当性を示していきます。 fn plus1(x: i32) -> i32 { (x as f64).sqrt().atan().cos().powi(2).recip().ro…

配列 $a = (a_0, a_1, \dots, a_{n-1}) \in \Z^n$ に対して、次の種類のクエリを処理する問題を考えます。 $\texttt{1}\; i\; x$ $a_i \gets x$ で更新する $\texttt{2}\; l\; r$ $(a_l, a_{l+1}, \dots, a_{r-1})$ の空でない連続部分列における、総和の最…

タイトルは下記の記事のパロディです。decimal に夢を見ている輩に含まれる人はぜひ見てほしいです。 qiita.com 背景 本題 除算 集合の大きさ 大小比較 等比数列の判定 余談 あとがき おわり 背景 よく、「浮動小数点型は誤差が出るので避けたい」という話が…

ABC で等比数列の判定をしたくなることはしばしばあります。 ABC 390 B ABC 413 D これに対して double で判定するとうまくいかないケースがあり、たとえば下記です。 $$ 67114657 \oslash 67114656 = 67114658 \oslash 67114657 = \texttt{1}.\texttt{00000…

codeforces.com これに触発されていろいろ調べたりがんばったりした記録です。 tl;dr: フ…上等だ…オレも一つ言っておくことがある f64 の FFT でも誤差がいい感じに収まるような気がしていたが別にそんなことはなかったぜ！ ウオオオいくぞオオオ！ ご愛読あ…

下記を書きます。 ↓ ここに書いています。 ↑ ここに書いています。 脚註を見に行くと...？*2 没パートを隠したつもりでも晒されてしまうことがあるので注意しましょう（少なくとも 1 敗）。 *1:a footnote leaks! *2:執筆時点と挙動が変わったら意味不明に…

浮には興味があるものの、ヒュにはないので見落としてしまいます。 atcoder.jp そういえばAHC048で(浮動小数使ってるのに) "なお、配布ツールもジャッジプログラムと完全に同一の挙動をするように実装されている。"って言いきってるのすごいなと思った(詳し…

人「浮動小数点数の演算なんだから環境によって結果が変わりうるのは当然だろ」 そうか...？ 前提 補足 事象 仮説と検証 仮説 1 仮説 2 仮説 3 仮説 4 調査 関数定義 実行時の処理 おまけ 補足 あとがき おわり 前提 $\gdef\libmsin#1{\operatorname{\texttt…

apple, banana, cherry, durian とかにしてほしかった... atcoder.jp 考察 立式 計算量改善 おまけ おまけのおまけ あとがき おわり 考察 コンテスト中にやった考察に沿って話を進めます。 立式 一番右の A と一番右の B に注目します。それらの間に C が含…

やりましょう。 前回、double-double や triple-double の話をしましたが、「triple-double は必要なのか？」とか「quadruple-double は不要なのか？」とかについて触れた方がいいかなと思ったので、先にそういう話をします。重要なお話です。 disclaimer: …

小さな誤差を積み重ねる操作と、積み重なった誤差に影響される操作を区別して考えましょう。 同じ符号の浮動小数点数を加算や乗算を計 $k$ 回繰り返しても、$(1+2^{-53})^k-1 \approx 2^{-53}\cdot k$ 程度の相対誤差しか生まれません。 競プロにおける演算…

倍精度浮動小数点型であるところの double ですが、現代においてはもはや double が「ふつう」になり、単精度と呼ばれている float は実質的に「半精度」のような感覚になっている気がします。 なにかしらを計算したいときに、計算結果は double だとしても…

#浮動小数点数 に関するクイズ（マジメなやつ）をつくってみた pic.twitter.com/2aYU8zcguU— 某ZR（ざんねん） (@zr_tex8r) 2025年4月8日 「反例がない気はしないんだが、具体的にぱっと構成するのは難しい」みたいなシリーズ— えびちゃん (@rsk0315_h4x) 20…

ずんだもんなのだ今日はこの解法の正当性の証明をやっていくのだ pic.twitter.com/UeXkq4BG5O— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2025年4月5日 fn solve_f64(n: f64, m: i32) -> Option<u32> { if n == 1.0 || m == 1 { (n + (m as f64) <= 1.0e9).then(|| n as u32 + m</u32>…

今回は整数を使わずに、いわゆる「数値計算」っぽいアルゴリズムで平方根を求めていきます。そういうアルゴリズムであっても correctly-rounded な値を得られるところが面白いですね。 あまくだり 例 グラフ 前提知識たち Equioscillation theorem Remez alg…

箱ティッシュとハンドソープは、それぞれ「次の要素を取得する」という操作ができます。つまりイテレータですね。 しかし、一言でイテレータと言っても両者は少し性質が違います。 箱ティッシュは、要素の取得と同時に（ユーザから観測できる形で）次の要素…

前回 は、主に自分で考えた素朴なアルゴリズムを実装・証明しましょうというスタンスの回でした。 今回は（今後は？）既存の実装をなぞる形で勉強していきます。 紹介 実装 資料 ツール おわび 本題 考察 手順 おまけ 所感 おわり 紹介 実装 LLVM のものを参…

ここにテスト用の画像を貼る ここにテスト用の画像を貼ります。

いろいろな数学関数たちの correct rounding な実装をしていこうという遊びです。 丸め方向については一旦は tiesToEven のみを考えています。 $\sin$ や $\log$ のような超越関数 (transcendental functions) は大変ではありますが、さまざまな典型テクがあ…

えびちゃんです。お気持ち表明記事です。最近「お気持ち表明」というフレーズをあまり聞かなくなった気がしますね。 出会い 整数型との対比 固定小数点型や十進浮動小数点型など 誤差 比較 数式での証明 数学関数たちについて 実務？ 所感 おわり 各章はそれ…

Rust で言うところの下記のような関数です。 fn is_square(nn: u64) -> bool { let n = (nn as f64).sqrt() as u64; n.wrapping_mul(n) == nn } fn is_square(nn: u64) -> bool { ((nn as f64).sqrt() as u64).wrapping_pow(2) == nn } これが問題ないという…

「そろそろ四則演算の誤差評価も飽きたな〜」「数学関数の計算とかもやってみてよ」という声が聞こえてきた*1ので、今日はそれをします。 導入 glibc 実装 精度？ まえおき 方針 定数の計算 近似多項式 念のためもう少し近づけておく 完成 余談 参考文献 感…

C++ で #include <limits> をして std::numeric_limits<__float128>::digits をすると 0 と返ってきました。 よって、__float128 は float にすら劣る桁数しかないことがわかりました。いかがでしたか？ コード #include <math.h> #include <stdio.h> #define MAGIC 0x7EEE #define PRECISION(F) l</stdio.h></math.h></__float128></limits>…

a / b の時点で float になって誤差が出てしまうので、$\floor{a/b}$ になってくれるとは限りません。というのがよくある説明です。 「誤差が出てしまう」と言われると、「では実際にそういうケースを構築してください」「誤差が出ない範囲を教えてください…

こんにちは。 まえがき 注意 おあそび 配列境界外参照 符号つき整数型のオーバーフロー ヌルポインタ参照 ゼロ除算 ビットシフト おまけ あとがき おわり まえがき 引用たち www.open-std.org C17 (ISO/IEC 9899:2018) の similar draft であるところの N231…

最近ツイートしたこの子です。 なんのコマンドで読んだのかお見通しなファイルちゃんできたよー pic.twitter.com/kjiMfPPqVz— えびちゃん (@rsk0315_h4x) 2025年2月19日 clairvoyance は、通常は知覚するのが不可能と考えられている情報を得る能力を指します…

なかよく（いろいろな解釈） 今日の遊び相手は glibc malloc ちゃんです。 今回はちゃんとした解説を目指した記事ではないです。 sourceware.org なかよし とりあえず malloc とりあえず free Use after free Double free tcache poisoning ふりかえり おき…