No.3ベストアンサー
- 回答日時:
No.1のコメントに対する回答です。
f[1]=f[0](2-xf[0]) = (1-e)(1+e)/x = (1-e^2)/x
というのはつまり、誤差eの1次の項をうち消すようにしてやればよいのです。「簡単に計算できる関数の逆関数」あるいは一般に「簡単に計算できる検算法がある関数」を計算するときに広く使えます。
この漸化式はニュートン法から導くこともできます。
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をやるんだったら、高々数百個の要素を持つテーブルを用意すれば十分で、2次あるいは3次のラグランジュ補間を使えば要素をさらに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月号に、全く同じアルゴリズムで
除算器を構成する方法が記載されていました。
No.2
- 回答日時:
固定小数点演算なのか、浮動小数点演算なのか。
除算器を作ろうとしてるのか、ソフトウェアで計算したいのか。
とかの情報も書いた方がいいですよ。
浮動小数点演算をソフトウェアで実装するなら、
stomachman さんの方法でいいと思います。
cherry_moonさま、お世話になります(^^)
情報はなるべく多いほうが良いというわけですね。
ありがとうございます。
状況を説明しますと、
1 固定小数点で良い
2 ハードウェア(FPGA)で除算器もどきを実装したい
3 単純に引いた回数をカウントしたのでは間に合わない
4 大雑把にいうと10万/100 程度の演算です。
5 4の整数解が得られれば良い
6 実は精度も0.1%(10bit)程度で良い
なので、最も適した回路を模索しているところです。
stomachmanさんの説明のアルゴリズムから大雑把に規模・スピードを見積もりましたが、
結構小規模で速度・精度が得られそうです。
No.1
- 回答日時:
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)、表を引いてから2次補間する、などの方法でも十分ですし、表を出発値f[0]を求めるのに使うのも良い方法です。
はじめまして、stomachmanさま。ありがとうございます。
成る程、これは使えそうです。
あまえついでなのですが、
f[n+1]=f[n](2-xf[n])
特性方程式? はどうやって導くのでしょうか?
初歩的な数値計算法の本をいくつかあさってみましたが
恥ずかしながら判りませんでした。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 計算機科学 アルゴリズムについて 1 2023/01/01 19:43
- その他(パソコン・スマホ・電化製品) 挿入ソートとマージソートを比較すると,挿入ソートのほうが計算量は少なく,効率的なアルゴリズムである。 1 2022/11/30 17:31
- 数学 「FFTの基本は、DFTはサンプル数Nが偶数なら 2つのDFTに分解できるということ。 分解するとD 3 2022/03/31 21:01
- その他(プログラミング・Web制作) プログラミングって本来数学的な計算をする為のものではないのですか? 学校で配られたFortran90 11 2022/08/25 22:14
- 物理学 量子力学のDeutsch–Jozsaアルゴリズムについてです。 下の画像において上側の出力が|+>と 1 2022/07/13 20:15
- ノンジャンルトーク 最近アルゴリズムが悪くてねぇ 1 2022/12/16 12:51
- 数学 図はn=8の場合だけど、3段(=log[2]8)のバタフライ (3回の計算)で処理してる。と言われた 4 2022/03/24 19:41
- 新規公開株・IPO アルゴリズムについて 3 2023/01/01 19:44
- ビデオカード・サウンドカード 1つのマザボでAMD&NVIDIAを同時使用できますか? 3 2022/04/22 14:36
- 物理学 スピン 行列表示 固有状態 測定値 1 2022/08/16 18:39
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
最小二乗法は、なぜ「二乗」な...
-
プラスマイナス1.5の範囲に...
-
実験計画法、L18直交表への割り...
-
有効数字について教えて下さい...
-
誤差率 理論値が0の時
-
有効数字が整数部分の一桁で表...
-
集積公差について教えて下さい。
-
データの相対誤差について
-
古典物理学で考える永劫回帰(...
-
測量の誤差全般について
-
近似値をマクローリン展開を用...
-
除算アルゴリズムについて
-
変動係数・真度・相対誤差につ...
-
近似値の計算方法をおしえて下...
-
誤差の二乗を最小にする理由
-
測定と有効数字(乗除の場合)
-
回帰分析における「誤差の仮定」
-
正五角形の作図を何種類知って...
-
コイン2000回中、1025回が表な...
-
信頼区間の求め方が分かりません
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報