タグ

関連タグで絞り込む (1)

タグの絞り込みを解除

algorithmとmathに関するemonkakのブックマーク (10)

  • 小数第四位までの小数を10000倍して整数に直せるのか - Pixel Pedals of Tomakomai

    数値が小数第四位まで与えられるとする。例えば、 1234.5678 のような形式である。 それらの数値を使って計算をしたいのだが、何も考えないと計算機上ではこれらの数値は double 型などで保持され、誤差が発生することは有名だろう。 >>> 1001.0000 * 1.1000 == 1101.1000 False >>> 1001.0000 * 1.1000 1101.1000000000001 誤差が発生するのは嫌なので、入力を 10000 倍して整数として扱いたくなる。例えば、 1234.5678 は 12345678 に変換したい。 しかし、この操作にも注意が必要である。 https://qiita.com/mod_poppo/items/910b5fb9303baf864bf7 で解説されている通り、 10000 倍したり、 int を取ったりするだけではうまくいかない。 >

    小数第四位までの小数を10000倍して整数に直せるのか - Pixel Pedals of Tomakomai
  • GitHub - google/double-conversion: Efficient binary-decimal and decimal-binary conversion routines for IEEE doubles.

    You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert

    GitHub - google/double-conversion: Efficient binary-decimal and decimal-binary conversion routines for IEEE doubles.
  • 円周率の16進数表現100億桁目を求めてみた! ― 円周率の世界記録をどのように検証するか ― - プログラムモグモグ

    あなたは円周率を何桁言えますか。3.14159…という、あの数字です。 円周率の小数部分は無限に続き、循環することもありません。 古来より、数学者は円周率の値を様々な幾何学的な近似や公式を用いて計算してきました。 その桁数は計算機の発明により飛躍的に伸び、収束の速い公式の発見や効率の良いアルゴリズムの発明などによって加速してきました *1。 5年前、私がまだ学生だった頃、円周率1億桁の計算に挑んだことがありました。 私にとって高精度計算の初めての挑戦で、様々な試行錯誤で苦労したのをよく覚えています。 itchyny.hatenablog.com 2017年現在、円周率計算の世界記録は22兆桁です。 円周率計算の歴史をご覧いただくとよく分かると思いますが、近年の円周率計算の世界記録からは次のような特徴が読み取れます。 2002年に1兆を超え、最新の記録 (2016年) は22兆桁 (10進数

    円周率の16進数表現100億桁目を求めてみた! ― 円周率の世界記録をどのように検証するか ― - プログラムモグモグ
  • 整数の公式でフィボナッチ数列を求める | POSTD

    (注:2020/10/01、2017/6/10、いただいたフィードバックを元に翻訳を修正いたしました。) 次のコードを用いると、なんとフィボナッチ数列が生成できます。 def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) この記事では、その導き方と振る舞いを説明しましょう。 具体的な説明に入る前に、背景としてフィボナッチ数列の概要と計算方法を駆け足で紹介します。すでに数学の専門知識がある方は、導入部分はほとんど飛ばして、「母関数」のセクションをざっと読んでから、「整数の公式」に進んでいただいて構いません。 概要 フィボナッチ数列とは、言わずと知れた以下の数列です。 \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\] この数列の \(n\) 番目

    整数の公式でフィボナッチ数列を求める | POSTD
  • Island Life - 2進小数の10進桁での丸め

    About 南の島のプログラマ。 たまに役者。 Practical Schemeの主。 WiLiKi:Shiro 最近のエントリ 無限cxr高校受験Defense振り返ってみると2019年は色々学んで楽...覚えるより忘れる方が難しい(こともある)眼鏡のつると3DプリンタIris Klein Acting ClassSAG-AFTRA conservatory: Voice Acting創作活動って自分を晒け出さねばならないと...ループを使わずに1から100までMore... 最近のコメント shiro on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/14)1357 on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/01)ベアトリーチェ on ハイポハイポハイポのシューリンガン (2022/04/02)ベアトリーチ

    Island Life - 2進小数の10進桁での丸め
  • PHPのround関数とは一体なんだったのか - hnwの日記

    (7/3 14:05追記)Javaに関する記述について誤認があったので盛大に書き換えました。Java 6、Java 7、Java 8それぞれで実装が変わっていたようです。 (7/13 23:55追記)記事中ではroundを四捨五入と言い切ってしまっています。これは筆者がC99のroundを基準に考えているためですが、言語によっては偶数丸めになっているround関数も珍しくありません。ご注意ください。 PHPのround関数について、ネット上で次のような記述を見つけました。 PHP 四捨五入の計算を間違える唯一の言語として畏れられていましたが、そのバグは治っているかもしれません(治ってないかもしれません) 主要なプログラミング言語8種をぐったり解説 - 鍋あり谷あり 各言語を面白おかしく紹介する内容とはいえ、ずいぶん雑な理解だなーという印象です。ゆるふわな話だけでPHPがdisられ続けるの

    PHPのround関数とは一体なんだったのか - hnwの日記
  • Island Life - 誤差が生じるとき

    About 南の島のプログラマ。 たまに役者。 Practical Schemeの主。 WiLiKi:Shiro 最近のエントリ 無限cxr高校受験Defense振り返ってみると2019年は色々学んで楽...覚えるより忘れる方が難しい(こともある)眼鏡のつると3DプリンタIris Klein Acting ClassSAG-AFTRA conservatory: Voice Acting創作活動って自分を晒け出さねばならないと...ループを使わずに1から100までMore... 最近のコメント shiro on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/14)1357 on 歳を取ると時間が速く過ぎるのは、新しいことに挑戦しないから? (2023/03/01)ベアトリーチェ on ハイポハイポハイポのシューリンガン (2022/04/02)ベアトリーチ

    Island Life - 誤差が生じるとき
  • 平方数かどうかを高速に判定する方法 - hnwの日記

    平方数とは、ある整数の平方(=二乗)であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します(PHPでもgmp_perfect_square関数として利用できます)。稿ではこの実装

    平方数かどうかを高速に判定する方法 - hnwの日記
  • カラツバ法 - Wikipedia

    カラツバ法(カラツバほう)とは、主に多倍長乗算の乗算アルゴリズム(英語版)において、乗算の回数を4分の3にするアルゴリズムである。 加減算の回数は増加するが、乗算コストはそれより遥かに大きいため、結果として演算コストそのものもほぼ4分の3となる。 発見者のAnatolii Alexeevitch Karatsuba(Карацуба Анатолий Алексеевич)の名前を取ってKaratsuba法(Karatsuba-algorithm)、あるいは単にKaratsubaとも呼ばれる。 従来の乗算はだったが、Karatsuba法の再帰的適用により、(≒1.585)まで計算コストが抑えられる。 アルゴリズム[編集] 単純な例として、被乗数と乗数の積を求める()。 まず、被乗数と乗数をそれぞれ上位・下位の2つに分割する。 分割の基数を(例えば3桁ずつに分割するなら)とすると、 この乗算

  • 万能数値表現法 URR

    ━─────────────────────────────────── アセンブラ講座(番外編) 《万能数値表現法 URR》 鎌田 誠 ──────────────────────────────────── IEEE 754 で規格化されている浮動小数点数の表現方法は符号と指数部と仮数 部に整然と分けられていてわかりやすく、実装も容易なのですが、指数部と仮数 部を区切る位置を固定してしまったために、大きな数を扱いたい技術者には指数 部の範囲が狭すぎ、精度を要求する技術者には仮数部のビット数が少なすぎると いう問題点があります。 しかし、かつて日人によって IEEE 754 よりも算術的に優れている浮動小数 点数の表現方法が考案されていたことを知る人はほとんどいないでしょう。その 数値表現法は考案された当時の技術では実装が困難だったために規格化されなか ったようですが、非常に興味深い数

  • 1