- ベストアンサー
除算アルゴリズムについて
stomachmanの回答
- stomachman
- ベストアンサー率57% (1014/1775)
1/xの近似値をf[0]とします。その相対誤差をe（|e|<1)とすると f[0] = (1+e)/x という関係になっています。 次に f[1]=f[0](2-xf[0]) を計算する。 2-xf[0]= 2-(1+e) = (1-e) ですから、 f[1]=f[0](2-xf[0]) = (1-e)(1+e)/x = (1-e^2)/x 従って誤差はeだったものがe^2に改良されました。これを f[n+1]=f[n](2-xf[n]) のように繰り返せば、誤差はe→e^2→e^4→e^8…とどんどん小さくなり、有効桁数が繰り返しの度に倍になっていきます。 例えばx=0.1の逆数を求めるのに出発値として1/x ≒ f[0] =2-xを使ったとすると、 f[0]=1.9 f[1]=3.439 f[2]=5.6953279 f[3]=8.146979811 f[4]=9.656631618 f[5]=9.988209815 f[6]=9.999986099 どのぐらいの範囲のXが入ってくるかによって、前処理の方法がいろいろあり得ます。また必要な答の精度が荒くて良いのなら表を引く(table lookup)、表を引いてから２次補間する、などの方法でも十分ですし、表を出発値f[0]を求めるのに使うのも良い方法です。
関連する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](2-xf[n]) 特性方程式？ はどうやって導くのでしょうか？ 初歩的な数値計算法の本をいくつかあさってみましたが 恥ずかしながら判りませんでした。