1/x を、乗算器しかないDSPなどで演算するアルゴリズムについて
お教え願えないでしょうか?
おぼろげな記憶では、0<x≦1 などのように正規化して、
バタフライ演算を行って求めるアルゴリズムがあったと記憶しますが、
正確な事がわかりません。
宜しくお願いします。

A 回答 (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桁以上減らせます。メモリやキャッシュの隅っこに十分収まってしまいますね。
    • good
    • 0
この回答へのお礼

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月号に、全く同じアルゴリズムで
除算器を構成する方法が記載されていました。

お礼日時:2001/11/06 13:42

固定小数点演算なのか、浮動小数点演算なのか。


除算器を作ろうとしてるのか、ソフトウェアで計算したいのか。

とかの情報も書いた方がいいですよ。

浮動小数点演算をソフトウェアで実装するなら、
stomachman さんの方法でいいと思います。
    • good
    • 0
この回答へのお礼

cherry_moonさま、お世話になります(^^)
情報はなるべく多いほうが良いというわけですね。
ありがとうございます。

状況を説明しますと、
1 固定小数点で良い
2 ハードウェア(FPGA)で除算器もどきを実装したい
3 単純に引いた回数をカウントしたのでは間に合わない
4 大雑把にいうと10万/100 程度の演算です。
5 4の整数解が得られれば良い
6 実は精度も0.1%(10bit)程度で良い
なので、最も適した回路を模索しているところです。

stomachmanさんの説明のアルゴリズムから大雑把に規模・スピードを見積もりましたが、
結構小規模で速度・精度が得られそうです。

お礼日時:2001/11/06 11:18

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]を求めるのに使うのも良い方法です。
    • good
    • 0
この回答へのお礼

はじめまして、stomachmanさま。ありがとうございます。
成る程、これは使えそうです。
あまえついでなのですが、
f[n+1]=f[n](2-xf[n])
特性方程式? はどうやって導くのでしょうか?
初歩的な数値計算法の本をいくつかあさってみましたが
恥ずかしながら判りませんでした。

お礼日時:2001/11/06 11:21

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q【数学】逆数の母数って1固定ですか? 逆数の逆数は左右辺が同等という意味になる?

【数学】逆数の母数って1固定ですか?

逆数の逆数は左右辺が同等という意味になる?

Aベストアンサー

何の逆数ですか?
 小学校の6年で学ぶ逆数は、掛け合わせると1になる数
・3の逆数は1/3である。
・ある数にその数の逆数をかければ1になる
・割り算と、割る数の逆数をかけることは同じ結果になる
 5÷3 = 5×1/3 
をまなびましたね。

この逆数は二項演算( https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%A0%85%E6%BC%94%E7%AE%97 )がなりたつ群・・グルーフの要素

【数学】逆数の母数って1固定ですか?

逆数の逆数は左右辺が同等という意味になる?

質問の意味が分かりませんが、ある数の逆数は一意に決まります。(決まる群での話)
逆数の逆数は元の数になります。
0.5の逆数は2
2+iの逆数は、1/(2+i) = (2 - i)/3
 その逆数は、一意で元の数になる。

逆数と半数(加えてoになる数)を考えることで、二項演算の交換、分配、結合が常に成り立つようになる。--中学一年で学ぶ。

QX-Y平面の領域D={(x,y)|0≦x≦1,x-1≦y≦x+1}を、

X-Y平面の領域D={(x,y)|0≦x≦1,x-1≦y≦x+1}を、x/y=u,y=vとして、U-V平面での領域で表したいのですが、どうにもできません。誰か教えてください。

Aベストアンサー

定義域をどう変換したら良いかわからないという意味の質問と捉えるならば、(<、>の下の等号は省略)
0<x<1 より両辺を足したり引いたりすれば、
1<x+1<2
-1<x-1<0
よってx-1<y<x+1 は -1<y<2 となり、 -1<v<2
また、x/y=uより0<x<1は0<uy<1
これから両辺に(題意としてy=v=0は定義されないので)1/yを掛ければ
0<u<1/y=1/v となりvの定義域から1/vの定義域の上限は無限大なので
0<uのみとなる。
結果、-1<v<2、0<uが領域の変換後の回答です。


 

Qなぜ逆数?

ちょっと疑問があります.理科の時間に教わった抵抗の求め方で,「並列の場合はそれぞれの抵抗値の逆数をとり,全部を合計したあとで,また逆数にする」とありますが,なぜ並列のときだけ,逆数にするのでしょうか?「逆数にする」意味を教えてください.

Aベストアンサー

抵抗の逆数は、いわば、電気の通り道の太さ、言い換えれば、ホースの太さです。
同じ力(電圧)でも、ホースが太ければ太いほど、それに比例して電気が沢山通るようになります。
逆にホースが細ければ、通りにくくなります。

1/R=1/R1+1/R2 という式は、電気が通る道が2つに枝分かれしているときに流れる電気の量は、2つの道の太さを合体した太さを流れる電気の量という同じ、という、当たり前のことを表わしている式です。

勿論オームの法則からでも、全く同じことが言えます。
E=R1i1 → i1/E=1/R1
E=R2i2 → i2/E=1/R2
E=Ri → i/E=1/R
ところが、i=i1+i2(2つの経路の電流の足し算)なので
1/R=1/R1+1/R2
いっちょあがり。



(以上は、下記参考URLの私の回答のコピーです)
http://oshiete1.goo.ne.jp/kotaeru.php3?q=899194

参考URL:http://oshiete1.goo.ne.jp/kotaeru.php3?q=899194

抵抗の逆数は、いわば、電気の通り道の太さ、言い換えれば、ホースの太さです。
同じ力(電圧)でも、ホースが太ければ太いほど、それに比例して電気が沢山通るようになります。
逆にホースが細ければ、通りにくくなります。

1/R=1/R1+1/R2 という式は、電気が通る道が2つに枝分かれしているときに流れる電気の量は、2つの道の太さを合体した太さを流れる電気の量という同じ、という、当たり前のことを表わしている式です。

勿論オームの法則からでも、全く同じことが言えます。
E=R1i1 → i1/E=1/R1...続きを読む

QD={(x,y)|0≦x≦1,x≦y≦1}

D={(x,y)|0≦x≦1,x≦y≦1}
∬[D](e^y)^2dxdy
初歩的な問題なんですがこれ答えは(e/2)-(1/2)であってますか?どなたか頼みます。

Aベストアンサー

>積分範囲がxは0からy、yは0からyにになるのがわからないです。0≦x≦1,x≦y≦1がなんでその積分範囲になるのでしょうか?

重積分する場合は、積分領域をxy座標平面にプロットして確認します。
その積分領域全体をカバーするように積分変数を1つずつ順に変化させていくことで、各変数の積分範囲が決まります。それが逐次積分法です。

今の問題の場合

∫[0,1]{∫[x,1] f(x,y)dy}dx

∫[0,1]{∫[0,y] f(x,y)dx}dy

どちらの順序で逐次積分しても、積分領域全体をカバーできます。
必ず積分領域をプロットして、積分をどの順序で行っているか確認
してください(そうすれば重積分が怖くなくなりますよ)。

なので、どちらでも積分でき同じ積分値が得られます。
しかし、積分のしやすさ(難易度)に差が出ますので、簡単に積分できる方を選んでやります。
したがって、どちらの逐次積分の順序もマスターしておき、より簡単に積分できる方を選ぶことがポイントになります。

Qtanθの逆数??

今数学の参考書をやってて(高一レベル)答えのところに
tanθ+1/tanθ=sinθ/cosθ+cosθ/sinθ・・・略と書いてあり
                     ↑のcosθ/sinθのとこに
tanθの逆数と書いてあったのですが逆数なんて初めてで意味がわかりません、なんでこの式になるのか教えてください。
tanθがsinθ/cosθになるのはわかります。

Aベストアンサー

逆数の意味を理解していないのでしょうか?
tanθに限らず、
2の逆数は1/2 等、分子と分母を逆にした数字です。
tanθ=sinθ/cosθより、tanθの逆数はcosθ/sinθとなります。

QD={(x,y)|0≦x≦1,0≦y≦x}とする。

D={(x,y)|0≦x≦1,0≦y≦x}とする。
∬{(4x^2)-(y^2)}^1/2dxdyを求めよ。
但し、d/dt[t/2{(4a^2)-t^2}^(1/2)+(2a^2)sin^-1(t/2a)]={(4a^2)-t^2}^1/2
答えに逆関数は残ってしまいますか?
一応答えも載せて頂けるとありがたいです。

Aベストアンサー

int[y:0,x]dy/root{4x^2-y^2}=arcsin(x/2x)-arcsin(0,2x)=π/6.

int[x:0,1]π/6dx=π/6.

間違ってる?

Q逆数

自然対数をとって計算しやすくすることがありますが、逆数をとって計算しやすくすることもあるのでしょうか?
「逆数をとる」というのはどんなときにするものですか?

Aベストアンサー

例えば、数列の問題で、a_1=2,a_(n+1)=a_n/(a_n+3)
という数列{a_n}があったら,
a_1=2からa_n>0 (n=1,2,…)
でこのとき、両辺の逆数をとって
    1/a_(n+1)=1+3/a_n
1/a_n=b_nとおいて
      b_(n+1)=3b_n+1
という式(この式に持ち込めばもう解けますよね。)を得たり、また、
     3/2=5/x
という方程式があったら逆数をとって
         2/3=x/5
という式を得たり。

Qx(x-y)≦0とかで、なんでx^2≦xy, x≦

x(x-y)≦0とかで、なんでx^2≦xy, x≦yみたいに計算してしまっては、片方(?)の答えしか出てこないのはなぜですか。
他のでは、x^2-6x=0なども、x^2=6xで計算してしまうとx=6だけしか出てこないのは、なんか、なんとなく不思議です。理屈を教えて下さい。

Aベストアンサー

#2のものです。

>x=0では、やはり0では割ってはいけないルールでダメなんですよね…不思議です。

0で割ると式そのものが成り立たなくなります。

例えば
x=2x
の解はx=0ですが、もとの方程式をxで割ることを許してしまうと
x/x=2x/2x → 1=2
となってしまいます。

どのような式(例え絶対に等しくないことが明らかなもの)でも両辺に0をかければ等しくなります。そのため、そのように作られた方程式や不等式の両辺を"0"で割ったからといってその式が成り立つとは限らないのです。

Qエクセルで任意の数の逆数のとりかた

エクセル2011である適当な数字20個のそれぞれの逆数を求めるにはどうすればいいのでしょうか。調べてみても逆数の合計とか逆関数とか関係ないものばかり出て来て全く分かりません。そもそも演算の仕方が分からないです。。。

Aベストアンサー

>「B1=1/A1」という式をどこにペーストすればいいのかが分かりません・・・
B1というセルに=1/A1を書き込むんですよ

Q∬sin(x+y)dxdy;0≦x,0≦y,x^2+y^2≦1

∬_S sin(x+y)dxdyの解を求めよ。
ただしS:={(x,y);x≧0,y≧0,x^2+y^2≦1}とする。

と言う問題ですが、検索したところ類似問題の答えを見つけました。
以下をご覧ください。
--------------------------------------------------------------
この先生http://www.math.meiji.ac.jp/new/35.htmlの
http://www.math.meiji.ac.jp/~mk/lecture/kaisekigairon-2/exercise1.pdf
の中の2.の(5)の答えは"2"になっております。
------------------------------------------------
さて、ちょっとややこしいのですが、上記二者は全く同じ問題ではないので、こことは別なあるご相談サイトで前者の問題
∬_S sin(x+y)dxdy;0≦x,0≦y,x^2+y^2≦1・・・・・について質問したところ、次のような回答がありました。

その回答の抜粋;”私も積分値が何なのかは知りませんが、積分領域の S の面積がπ/4 で、sin(x+y)≦1 なので積分値はπ/4 以下になります。”
あとで気づいたのですが、この記述は、
http://www.math.meiji.ac.jp/~mk/lecture/kaisekigairon-2/exercise1.pdf
の答えと矛盾するような気がしますが、どうでしょうか?
当方独学の部分が多いため、わからなくなって困っております。宜しくお願い致します。

∬_S sin(x+y)dxdyの解を求めよ。
ただしS:={(x,y);x≧0,y≧0,x^2+y^2≦1}とする。

と言う問題ですが、検索したところ類似問題の答えを見つけました。
以下をご覧ください。
--------------------------------------------------------------
この先生http://www.math.meiji.ac.jp/new/35.htmlの
http://www.math.meiji.ac.jp/~mk/lecture/kaisekigairon-2/exercise1.pdf
の中の2.の(5)の答えは"2"になっております。
------------------------------------------------
さて、ちょっとややこしいのです...続きを読む

Aベストアンサー

∫[S] sin(x)cos(y)+cos(x)sin(y)dxdy
=∫[0,1]{sin(x)∫[0,√(1-x^2)]cos(y)dy+cos(x)∫[0,√(1-x^2)]sin(y)dy}dx
=∫[0,1]{sin(x)sin√(1-x^2)-cos(x)[cos√(1-x^2)-1]}dx
=∫[0,1]cos(x)dx-∫[0,1] cos{x+√(1-x^2)}dx
=sin(1)-∫[0,1] cos{x+√(1-x^2)}dx …(◆)
≒0.8414709848-0.2793082485
≒0.5621627363
(◆)の第二項の定積分は解析的に行えませんので数値計算(ガウス数値積分法その他→参考URL参照)で計算します。

積分そのものは以下のサイトで数値積分してくれます。
ttp://www10.wolframalpha.com/input/?i=integrate%28integrate%28sin%28x%2By%29%2Cy%2C0%2Csqrt%281-x%5E2%29%29%2Cx%2C0%2C1%29
integrate(integrate(sin(x+y),y,0,sqrt(1-x^2)),x,0,1)

参考URL:http://homepage3.nifty.com/gakuyu/suti/sekibun/gauss-int.html

∫[S] sin(x)cos(y)+cos(x)sin(y)dxdy
=∫[0,1]{sin(x)∫[0,√(1-x^2)]cos(y)dy+cos(x)∫[0,√(1-x^2)]sin(y)dy}dx
=∫[0,1]{sin(x)sin√(1-x^2)-cos(x)[cos√(1-x^2)-1]}dx
=∫[0,1]cos(x)dx-∫[0,1] cos{x+√(1-x^2)}dx
=sin(1)-∫[0,1] cos{x+√(1-x^2)}dx …(◆)
≒0.8414709848-0.2793082485
≒0.5621627363
(◆)の第二項の定積分は解析的に行えませんので数値計算(ガウス数値積分法その他→参考URL参照)で計算します。

積分そのものは以下のサイトで数値積分してくれます。
ttp://www10.wolframalpha.com/input/?i...続きを読む


人気Q&Aランキング

おすすめ情報