超高速！！多倍長整数の計算手法 - Qiita
こんにちは、年齢 3X 歳の peria です。 6月に @square1001 さんの「超高速！多倍長整数の計算手法」シリーズ(前編 / 後編) が投稿された際、Constants コンテスト で数年前に得点していたことを思い出しつつ、今だともう少し書けるかな、というノリだけで色々コーディングしていたら総合2位まで来たのでザックリ何したかを書いていこうと思います。 注意点としては、あくまでコンテスト用に書いたコードなので全てを公開するわけではありません。また、実際に私が選んだアルゴリズムを曖昧にする意味でも、見えていない最適化があるかもしれないという意味でも、いくつかの選択肢を書いていることが多々あると思います。また、あくまで上記シリーズに付け加える二次創作・アフターストーリー的なものなので「超高速！多倍長整数の計算手法」シリーズは読破しているものとして書いていきます。 保存形式の工夫
有理数同士の大小比較
JAG の ICPC 模擬地区予選 2015 の最中に, ジャッジルームで思いついたこと. イントロ 誤差を避けるために有理数を使うとき, オーバーフローするボトルネックは, 多くの場合, 有理数同士の大小比較になる. (逆に, 有理数同士の大小比較がボトルネックにならないときは, 別のテクニックで誤差を避けられることがある) そこで, 有理数の分母分子自体はオーバーフローしていないときに, 有理数同士の比較を, なるべくオーバーフローさせずに行う方法を見る. つまり, 次のような sgn 関数を作りたい. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39template<class Int> struct Fraction{
kuuso on Twitter: "超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 https://t.co/mQ68pGe6hG #Qiita 大作だった．いい記事．"
数値計算の落とし穴
数値計算の落とし穴 Last modified: この前計算機室にいたら，学生が「long ではなくて float を使うのかな」などと話しておりました。 # float より double を使ってくれ... コンピュータが用いる数の精度 コンピュータの内部で使用される数は，2進数で表される。 以下のプログラムを考えてみよう。 #include <stdio.h> #include <math.h> void put_float(char *string, float z); #define N 100 int main(void) { float x, sum; int i; sum = 0.0; x = 1.0/N; /* (1) */ for (i = 0; i < N; i++) { /* (2) */ sum += x; } put_float("sum = ", su
浮動小数点数について - komiyamの日記
はじめに この記事はCompetitive Programming Advent Calendar12月10日分の記事です。 誤差が原因でWAになる問題が嫌いな人は決して少なくないと思います。「こんなのは本質的なことではない」という人もいるでしょう。誤差を回避することが本質となるような問題がコンテストに出てもきっと人気は出ないでしょう。自分も以前は誤差死の起きうる問題は嫌いでしたが、最近はそれを回避するのも面白さだと感じるになってきました。 しかし面白いとかつまらないとか好きとか嫌いとか以前に非ACは悔しいものです。なので今回は、誤差死などを回避するために地味なネタである浮動小数点数について書こうと思います。 A+B problem とりあえず、いろんなオンラインジャッジで最初の1問目として見ることの多いA+B problemを解いてみましょう。よくあるのは整数の和を出力させる問題ですが、
浮動小数点数の丸め処理を見比べてみる - hnwの日記
各種プログラミング言語には、切り上げ・切り捨て・四捨五入など浮動小数点数を丸める関数が何種類もあります。こうした丸め処理を利用する際、「ceilとfloorどっちがどっちだっけ？」「マイナスの数が来た時の挙動って大丈夫なんだっけ？」などと不安になることはないでしょうか。 僕が丸め関数を使うときは、バグが無いかどうか他の場所以上に警戒します。というのも、これらの関数は境界値ピッタリだった場合の挙動とマイナスの数に対する挙動がそれぞれ違っており、勘違いや考え漏れから境界値バグを作り込みやすいためです。僕と同じ感覚の人も多いのではないでしょうか。 本稿では、こうした関数の挙動が一目でわかる便利なグラフを紹介します。このグラフは『WEB+DB PRESS Vol.57』に掲載いただいた僕の記事「PHP転ばぬ先の杖 第2回 数値の正しい扱い方 ― 浮動小数点数、巨大な整数」でも紹介したものです。以下
How to calculate binomial probabilities
Suppose you’re doing something that has probability of success p and probability of failure q = 1 − p. If you repeat what you’re doing m+n times, the probability of m successes and n failures is given by Now suppose m and n are moderately large. The terms (m+n)! and m! n! will be huge, but the terms pm and qn will be tiny. The huge terms might overflow, and the tiny terms might underflow, even tho
hnwの日記 - PHPの奇妙なround関数
(2012/11/01追記) 4年ほど前の記事「PHP5.3.0alpha3のround関数の実装がPHP5.2.6と変わった - hnwの日記」でお伝えした通り、PHP 5.3.0から別の実装が採用されており、本ページで指摘しているような挙動のPHPは既に絶滅危惧種です。念のため。 さて、プログラミングの話題もたまには書いてみます。今回はPHPのround関数の挙動が変だ！という話題です。 round()は浮動小数点数を四捨五入する関数で、大抵の言語に同じ名前で実装されているかと思います。ではPHPのround関数の何が問題なのか、ちょっと試してみましょう。 $ uname -sro Linux 2.6.9-42.0.10.plus.c4smp GNU/Linux $ php --version PHP 5.1.6 (cli) (built: Feb 23 2007 06:56:38)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Hiroki Tanaka on Twitter: "新しい「数値計算の常識」のPDFを見つけた https://t.co/PJ27tYds6v"
浮動小数点数オタクが AtCoder Beginner Contest 169 のC問題をガチで解説してみる - Qiita
高速な倍精度指数関数expの実装
How to calculate general binomial coefficients
Probability approximations
How to compute log factorial