- ベストアンサー
除算アルゴリズムについて
stomachmanの回答
No.1のコメントに対する回答です。 f[1]=f[0](2-xf[0]) = (1-e)(1+e)/x = (1-e^2)/x というのはつまり、誤差eの１次の項をうち消すようにしてやればよいのです。「簡単に計算できる関数の逆関数」あるいは一般に「簡単に計算できる検算法がある関数」を計算するときに広く使えます。 この漸化式はニュートン法から導くこともできます。 g(f)=x-1/f とおいて、方程式 g(f)=0 を解く。ニュートン法を使うと、 g'(f) = dg/df = 1/(f^2) を用いて f[n+1]=f[n]-g(f[n])/g'(f[n]) = f[n]-(x-1/f[n])/(1/(f[n]^2)) = f[n]-(x(f[n]^2)-f[n]) = 2f[n]-x(f[n]^2) = f[n](2-xf[n]) この場合は旨く行きましたが、ニュートン法がわり算なしの漸化式になるとは限りません。そういうときは、わり算なしで誤差|e|が繰り返しの度に単調減少するような計算を何らか工夫してやることになります。 なお、実際の応用においてはtable lookupは馬鹿にならない性能を発揮します。10bitの精度で1/100をやるんだったら、高々数百個の要素を持つテーブルを用意すれば十分で、２次あるいは３次のラグランジュ補間を使えば要素をさらに１桁以上減らせます。メモリやキャッシュの隅っこに十分収まってしまいますね。
関連するQ&A
- 乗算回数最小の冪乗アルゴリズム
断面ｎ次モーメントを計算するプログラムを書いていてふと思ったのですが， X^n を乗算の繰り返しで計算する場合，一般の自然数ｎについて乗算回数最小の アルゴリズムって存在するんでしょうか？ たとえばｎが２の冪乗の場合，２乗を繰り返すと１回ごとに X → X^2 → X^4 → X^8 → X^16 → … となるので，X^n は log2(n) 回の乗算で計算でき，たぶんこれが最小だと思います． その他のｎについてはどうでしょうか？ ｎの素因数分解とか使えばうまくいくんでしょうか？
- ベストアンサー
- 数学・算数
- マイクロコンピュータ 乗算演算について
マイクロコンピュータで、８ビット演算回路の乗算演算を行ったのですが、その際、乗数の０、１パターンに応じて被乗数を左シフトさせ加算していくロジックで演算をするというアルゴリズムを組み立てて実行しました。 乗算演算をより高速化させるには、この他にどのような手段が考えられるのか教えていただけないでしょうか？ お願いいたします。
- 締切済み
- 数学・算数
- 信号処理に関する質問です。
FFT（高速フーリエ変換）の計算アルゴリズムを 簡単に説明するとしたら、バタフライ演算図を描けば いいですか？他にも方法がありましたら教えて下さい。
- ベストアンサー
- 物理学
- [2進数 シフト演算 除算について]
[2進数 シフト演算 除算について] シフト演算について勉強中です。ご協力お願い出来たら幸いです。 乗算について例えば『1010』（符号ビットを考えず)を2倍 4倍 8倍（2のn乗）した場合 ビットを2倍であれば1つ、4倍であれば2つ・・・左に シフトすれば良いというのは理解しました。 また3倍 5倍などのケースも、 3倍であれば1ケタ左にシフトした数＋1010で求まる事も理解しました。 問題は除算です。他の質問を探ってみたのですが、考え方は一緒という回答で・・・詰まっています 除算は右シフトとの事ですが 先ほどの例である『1010』(10)ですがこれを1/2、つまり2で割ると 1つ右にシフトし1010→0101 となり 1010を1/4する場合右に2ビットシフトし 1010→0010.10 となり理解は出来ます。 しかし1/3 、1/5といった場合の計算の仕方が分かりません。 余りを出さないという考えで（近似値になると思いますが） 解き方をご教授願えたらと思います。
- 締切済み
- 数学・算数
- Cプログラミングの関数電卓のアルゴリズムについてですが、
Cプログラミングの関数電卓のアルゴリズムについてですが、 標準入力からの文字列式を、トークンに区切り、先頭から配列型スタックに格納して、計算を行う処理を考えていて、 a-b-cという処理のアルゴリズムに困っています。 どういった解決策があるのか教えて頂けませんか？？ お願いします！！ フローチャートを書くほどの事でも無いと思うので、僕が考えていたアルゴリズムを、文で記載しますが、できれば、このアルゴリズムからどうすれば解決できるかを考えて頂けたらとても助かります！！ １． 別のスタックを用意して、元々のをstack1,コピー用をstack2とし、stack1のトップからstack2に格納。（スタックの構造は二次元文字型配列） この場合、cからstack2に格納される。 ２． 演算子を見つけると、その前後の数字をその演算子によって処理。 この場合なら、c-bという処理。 ３． 計算結果を、cが格納されていた、演算子の前に格納。 ４．引き続き、この操作を繰り返す。 これを考えてたんですが、実行すると、(c-b)-aという式になり、違う答えが出てしまいます。加算ならば影響はでません。 きちんと（-c-b)+a の処理をさせるにはどうしたら良いかがわからないです。 お願いします!! ※返事が多少遅れるかもしれませんが、すみません!!
- ベストアンサー
- C・C++・C#
- 素数判定アルゴリズム内の剰余計算
今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか？
- 締切済み
- その他（プログラミング・開発）
- 数のサイズのO記法について
代数学の勉強をしています。O記法についてわからないところがあります。 「a,b∈N,a,b≦nとしk:=[log(n)]+1とする。 加法a+bの計算に対するビット演算の数はO(k)で 乗法a・bに対してはO(k^2)である。 もし高速乗算アルゴリズムが使用されれば、乗法 はO(klog(k))にまで改良することができる。」 とあるのですが、加法がO(k)、乗法がO(k^2)と表せるのはO記法の考え方からわかりました。 しかし、「高速乗算アルゴリズムが使用されれば、乗法はO(klog(k))にまで改良することができる」 というところがどうしてそうなるのかがわかりません。 ※logの底は2です。
- ベストアンサー
- 数学・算数
- 引き放し法による除算アルゴリズムについて
突然の質問失礼いたします。 現在私は学校で引き戻し法・引き放し法といった除算のアルゴリズムについて学んでいるのですが、そのうちの引き放し法について質問したく投稿しました。 引き放し法について自分で勉強しようと思い、いろいろ調べていたのですが、商と余りを出す引き放し法は見つかっても、小数点以下にわたってまで商を求める引き放し法がまったく見つかりませんでした。 (例えば5÷2=2あまり1と結果を出すのではなく、5÷2=2.5と結果を出す引き放し法のことです。) 少数点以下にわたってまで商を求める引き放し法は商と余りを出す引き放し法で表現できるのでしょうか？ もしよろしければ教えていただけると幸いです。また、参考にすべきインターネットサイト等もあれば教えていただけると助かります。
- ベストアンサー
- その他（プログラミング・開発）
- 乗積 Π のアルゴリズム
はじめまして。 質問内容が表題と多少ズレる事をご承知下さい。 アルゴリズムを教えて頂きたいと思っています。 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ Π(2x-1) ,x=1～m 上式においてm=3とすると、総数は15となります。 今、A～Fまで6つのアルファベットがあります。 このうち2つをペアにしてグループを作ります。 上式により、グループ総数は15となります。 ペアの組み方は以下のようになります。 ＜例＞ (1) A-B、 C-D、 E-F (2) A-B、 C-E、 D-F (3) A-B、 C-F、 D-E ・ ・ ・ (14) A-F、 B-D、 C-E (15) A-F、 B-E、 C-D ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ このような取り方をプログラムしようと思うのですが どこから手をつけてよいかわかりません。 是非アドバイスをお願いします。
- ベストアンサー
- Visual Basic
- 2進アルゴリズムの時間計算量
ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは k<=(2*log(n))-1 となっていました。
- ベストアンサー
- その他（プログラミング・開発）
お礼
stomachmanさま、お世話になってます。 成る程～～ 反復法やニュートンラフソン法 の最初のところに f[n+1]=f[n]-g(f[n])/g'(f[n]) が載っていますね（＾＾；） g(f)=x-1/f を fx-1 と変形してしまったために 代入すると全部消えてしまって導けなかった（？）ようです。 実のところ、分母には高々数十種類（6bitで充分）の整数と決まっているので 全部テーブル引きでも良いのです（実際、テーブルを小さくしてラグランジュ補間 を実装するのはかなり大変だろうと思います）が、もう少し方法はないものかと 思い、ここに投稿した次第です。 親切に解説していただき有難うございました。 また、自己レスにはなりますが、 DesignWaveマガジン 1999年12月号、2000年5月号に、全く同じアルゴリズムで 除算器を構成する方法が記載されていました。