(57)【特許請求の範囲】
【請求項１】
コンピュータシステムにおける、桁選択回路と変換器と一桁乗算器と加算器とを用いて基数がｒのときの平方根の逆数を計算する方法であって、
ｊ回の繰り返し計算後の中間結果をＳ[j]、残余をＷ[j]、演算数Ｘと中間結果Ｓ[j]との積をＰ[j]としたときに、
第１のステップにおいて、初期値Ｓ[0]、Ｗ[0]、Ｐ[0]＝Ｘ・Ｓ[0]に、−２Ｘ・Ｓ[0]ρ＋Ｘρ2＜Ｗ[0]＝１−Ｘ・Ｓ[0]2＜２Ｘ・Ｓ[0]ρ＋Ｘρ2（ρ＝ａ／（ｒ−１））を満たす値をセットし、
第２のステップにおいて、
上記桁選択回路により、平方根の逆数の桁ｑj+1をｒＷ[j]とＸとＰ[j]の見積り値に応じて桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択し、
上記変換器を用いて、上記中間結果Ｓ[j]に関する漸化式、Ｓ[j+1]:=Ｓ[j]＋ｑj+1ｒ-j-1を求めるとともに、
上記一桁乗算器と上記加算器とを用いて、それぞれ、
残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=ｒＷ[j]−（２Ｐ[j]＋Ｘｑj+1ｒ-j-1）
ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1ｒ-j-1と
について演算を行ない、
上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なうことを特徴とする平方根の逆数計算方法。
【請求項２】
コンピュータシステムにおける、桁選択回路と変換器と一桁乗算器と加算器とを用いて基数が２のときの平方根の逆数を計算する方法であって、
ｊ回の繰り返し計算後の中間結果をＳ[j]、残余をＷ[j]、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積をＰ[j]としたときに、
第１のステップにおいて、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、
第２のステップにおいて、
上記桁選択回路により、平方根の逆数の桁ｑj+1を２Ｗ[j]の見積り値に応じて桁集合｛−１，０，１｝から選択し、
上記変換器を用いて、中間結果Ｓ[j]からＳ[j+1]を求めるとともに、
上記一桁乗算器と上記加算器とを用いて、それぞれ、
残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=２Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1２-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1２-j-1とについて演算を行ない、
上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なうことを特徴とする平方根の逆数計算方法。
【請求項３】
コンピュータシステムにおける、桁選択回路と変換器と一桁乗算器と加算器とを用いて基数が４のときの平方根の逆数を計算する方法であって、
ｊ回の繰り返し計算後の中間結果をＳ[j]、残余をＷ[j]、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積をＰ[j]としたときに、
第１のステップにおいて、演算数Ｘが３／８より小さい場合には、初期値Ｓ[0]として２、Ｗ[0]として１−４Ｘ、Ｐ[0]として２Ｘをセットし、演算数Ｘが３／８以上３／４未満の場合には、初期値Ｓ[0]として３／２、Ｗ[0]として１−９Ｘ／４、Ｐ[0]として３Ｘ／２をセットし、演算数Ｘが３／４以上の場合には、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、
第２のステップにおいて、
上記桁選択回路により、平方根の逆数の桁ｑj+1を４Ｗ[j]の見積り値とＰ[j]の見積り値に応じて桁集合｛−２，−１，０，１，２｝から選択し、
上記変換器を用いて、中間結果Ｓ[j]からＳ[j+1]を求めるとともに、
上記一桁乗算器と上記加算器とを用いて、それぞれ、
残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=４Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1４-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1４-j-1とについて演算を行ない、
上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なうことを特徴とする平方根の逆数計算方法。
【請求項４】
ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘと中間結果Ｓ[j]との積Ｐ[j]とを用いて基数がｒのときの平方根の逆数を計算する回路であって、
所定の漸化式を用いてｊ＝０からｎ−１までのｎ回の繰り返し演算における、繰り返しの１回分を計算するための回路構成として、
平方根の逆数の桁ｑj+1をｒＷ[j]とＸとＰ[j]の見積り値に応じて桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択する桁選択回路と、
演算数Ｘをｊ＋１桁シフトしたＸｒ-j-1に、前記桁選択回路の出力を乗じ、Ｘｑj+1ｒ-j-1を生成する第１の一桁乗算器と、
２Ｐ[j]と前記第１の一桁乗算器の出力とを加え合わせる第１の加算器と、
前記第１の加算器の出力に前記桁選択回路の出力を乗ずる第２の一桁乗算器と、
ｒＷ[j]と前記第２の一桁乗算器の出力を加え合わせてＷ[j+1]を計算する第２の加算器と、
Ｐ[j]と前記第１の一桁乗算器の出力を加え合わせてＰ[j+1]を計算する第３の加算器と、
Ｓ[j]を前記桁選択回路の出力に応じてＳ[j+1]に変換する変換器と、
を備えていることを特徴とする平方根の逆数計算回路。
【請求項５】
Ｓ[j]の値を記憶するためのレジスタと、Ｗ[j]の値を記憶するためのレジスタと、Ｐ[j]の値を記憶するためのレジスタと、Ｘを記憶するためのレジスタとをさらに有することを特徴とする請求項４記載の平方根の逆数計算回路。
【請求項６】
ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘと中間結果Ｓ[j]との積Ｐ[j]とを用いて基数がｒのときの平方根の逆数を計算する機能をコンピュータに実現させるためのプログラムであって、上記機能は、
第１のステップにおいて、初期値Ｓ[0]、Ｗ[0]、Ｐ[0]＝Ｘ・Ｓ[0]に、−２Ｘ・Ｓ[0]ρ＋Ｘρ2＜Ｗ[0]＝１−Ｘ・Ｓ[0]2＜２Ｘ・Ｓ[0]ρ＋Ｘρ2（ρ＝ａ／（ｒ−１））を満たす値をセットし、
第２のステップにおいて、
平方根の逆数の桁ｑj+1をｒＷ[j]とＸとＰ[j]の見積り値に応じて桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択し、
中間結果Ｓ[j]に関する漸化式、Ｓ[j+1]:=Ｓ[j]＋ｑj+1ｒ-j-1と、
残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=ｒＷ[j]−（２Ｐ[j]＋Ｘｑj+1ｒ-j-1）ｑj+1と、
積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1ｒ-j-1とについて演算を行ない、
上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なうことを特徴とするプログラム。
【請求項７】
ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積Ｐ[j]を用いて基数が２のときの平方根の逆数を計算する機能をコンピュータに実現させるためのプログラムであって、上記機能は、
第１のステップにおいて、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、
第２のステップにおいて、
平方根の逆数の桁ｑj+1を２Ｗ[j]の見積り値に応じて桁集合｛−１，０，１｝から選択し、
中間結果Ｓ[j]からＳ[j+1]を求めるとともに、
残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=２Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1２-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1２-j-1とを用いて加算を行ない、
上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なうことを特徴とするプログラム。
【請求項８】
ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積Ｐ[j]を用いて基数が４のときの平方根の逆数を計算する機能をコンピュータに実現させるためのプログラムであって、上記機能は、
第１のステップにおいて、演算数Ｘが３／８より小さい場合には、初期値Ｓ[0]として２、Ｗ[0]として１−４Ｘ、Ｐ[0]として２Ｘをセットし、演算数Ｘが３／８以上３／４未満の場合には、初期値Ｓ[0]として３／２、Ｗ[0]として１−９Ｘ／４、Ｐ[0]として３Ｘ／２をセットし、演算数Ｘが３／４以上の場合には、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、
第２のステップにおいて、
平方根の逆数の桁ｑj+1を４Ｗ[j]の見積り値とＰ[j]の見積り値に応じて桁集合｛−２，−１，０，１，２｝から選択し、
中間結果Ｓ[j]からＳ[j+1]を求めるとともに、
残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=４Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1４-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1４-j-1とを用いて加算を行ない、
上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なうことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、平方根の逆数計算方法、平方根の逆数計算回路、及び平方根の逆数計算をコンピュータに行なわせるためのプログラムに関する。
【０００２】
【従来の技術】
平方根逆数演算回路の例として、特開平０３−１３８７２５号公報や特開平０９−３１９５６１号公報がある。特開平０３−１３８７２５号公報には、ニュートン法を用いた乗算型の平方根逆数演算回路の例が示されている。また、特開平０９−３１９５６１号公報には減算シフト型の除算器と開平器を直列に接続し、商全体が求まるのを待たずに、パイプライン的に、開平の計算も進めるタイプの平方根逆数演算回路の例が示されている。
【０００３】
【発明が解決しようとする課題】
上記した特開平０３−１３８７２５号公報に記載の回路では、乗算器及び初期値メモリを用いるために回路規模が大きくなるという問題がある。
【０００４】
また、特開平０９−３１９５６１号公報では、除算を行なっている間は２サイクルに１ステップの割合で開平計算を進め、除算終了後は各サイクルに１ステップの割合で開平計算を行うため、レイテンシが大きくなってしまうという問題があった。
【０００５】
本発明はこのような課題に着目してなされたものであり、その目的とするところは、従来の乗算型平方根逆数演算回路よりも省ハードウェアであり、かつ従来の除算器及び開平器を用いた平方根逆数演算回路よりも高速である平方根の逆数計算方法、計算回路、及びプログラムを提供することにある。
【０００６】
【課題を解決するための手段】
上記の目的を達成するために、第１の発明は、コンピュータシステムにおける、桁選択回路と変換器と一桁乗算器と加算器とを用いて基数がｒのときの平方根の逆数を計算する方法であって、ｊ回の繰り返し計算後の中間結果をＳ[j]、残余をＷ[j]、演算数Ｘと中間結果Ｓ[j]との積をＰ[j]としたときに、第１のステップにおいて、初期値Ｓ[0]、Ｗ[0]、Ｐ[0]＝Ｘ・Ｓ[0]に、−２Ｘ・Ｓ[0]ρ＋Ｘρ2＜Ｗ[0]＝１−Ｘ・Ｓ[0]2＜２Ｘ・Ｓ[0]ρ＋Ｘρ2（ρ＝ａ／（ｒ−１））を満たす値をセットし、第２のステップにおいて、上記桁選択回路により、平方根の逆数の桁ｑj+1をｒＷ[j]とＸとＰ[j]の見積り値に応じて桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択し、上記変換器を用いて、上記中間結果Ｓ[j]に関する漸化式、Ｓ[j+1]:=Ｓ[j]＋ｑj+1ｒ-j-1を求めるとともに、上記一桁乗算器と上記加算器とを用いて、それぞれ、残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=ｒＷ[j]−（２Ｐ[j]＋Ｘｑj+1ｒ-j-1）
ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1ｒ-j-1とについて演算を行ない、上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なう。
【０００７】
また、第２の発明は、コンピュータシステムにおける、桁選択回路と変換器と一桁乗算器と加算器とを用いて基数が２のときの平方根の逆数を計算する方法であって、ｊ回の繰り返し計算後の中間結果をＳ[j]、残余をＷ[j]、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積をＰ[j]としたときに、第１のステップにおいて、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、第２のステップにおいて、上記桁選択回路により、平方根の逆数の桁ｑj+1を２Ｗ[j]の見積り値に応じて桁集合｛−１，０，１｝から選択し、上記変換器を用いて、中間結果Ｓ[j]からＳ[j+1]を求めるとともに、上記一桁乗算器と上記加算器とを用いて、それぞれ、残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=２Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1２-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1２-j-1とについて演算を行ない、上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なう。
【０００８】
また、第３の発明は、コンピュータシステムにおける、桁選択回路と変換器と一桁乗算器と加算器とを用いて基数が４のときの平方根の逆数を計算する方法であって、ｊ回の繰り返し計算後の中間結果をＳ[j]、残余をＷ[j]、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積をＰ[j]としたときに、第１のステップにおいて、演算数Ｘが３／８より小さい場合には、初期値Ｓ[0]として２、Ｗ[0]として１−４Ｘ、Ｐ[0]として２Ｘをセットし、演算数Ｘが３／８以上３／４未満の場合には、初期値Ｓ[0]として３／２、Ｗ[0]として１−９Ｘ／４、Ｐ[0]として３Ｘ／２をセットし、演算数Ｘが３／４以上の場合には、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、第２のステップにおいて、
上記桁選択回路により、平方根の逆数の桁ｑj+1を４Ｗ[j]の見積り値とＰ[j]の見積り値に応じて桁集合｛−２，−１，０，１，２｝から選択し、上記変換器を用いて、中間結果Ｓ[j]からＳ[j+1]を求めるとともに、上記一桁乗算器と上記加算器とを用いて、それぞれ、残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=４Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1４-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1４-j-1とについて演算を行ない、上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なう。
【０００９】
また、第４の発明は、ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘと中間結果Ｓ[j]との積Ｐ[j]とを用いて基数がｒのときの平方根の逆数を計算する回路であって、所定の漸化式を用いてｊ＝０からｎ−１までのｎ回の繰り返し演算における、繰り返しの１回分を計算するための回路構成として、平方根の逆数の桁ｑj+1をｒＷ[j]とＸとＰ[j]の見積り値に応じて桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択する桁選択回路と、演算数Ｘをｊ＋１桁シフトしたＸｒ-j-1に、前記桁選択回路の出力を乗じ、Ｘｑj+1ｒ-j-1を生成する第１の一桁乗算器と、２Ｐ[j]と前記第１の一桁乗算器の出力とを加え合わせる第１の加算器と、前記第１の加算器の出力に前記桁選択回路の出力を乗ずる第２の一桁乗算器と、ｒＷ[j]と前記第２の一桁乗算器の出力を加え合わせてＷ[j+1]を計算する第２の加算器と、Ｐ[j]と前記第１の一桁乗算器の出力を加え合わせてＰ[j+1]を計算する第３の加算器と、Ｓ[j]を前記桁選択回路の出力に応じてＳ[j+1]に変換する変換器と、を備えている。
【００１０】
また、第５の発明は、第４の発明に係る平方根の逆数計算回路において、Ｓ［ｊ］の値を記憶するためのレジスタと、Ｗ［ｊ］の値を記憶するためのレジスタと、Ｐ［ｊ］の値を記憶するためのレジスタと、Ｘを記憶するためのレジスタとをさらに有する。
【００１１】
また、第６の発明は、ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘと中間結果Ｓ[j]との積Ｐ[j]とを用いて基数がｒのときの平方根の逆数を計算する機能をコンピュータに実現させるためのプログラムであって、上記機能は、第１のステップにおいて、初期値Ｓ[0]、Ｗ[0]、Ｐ[0]＝Ｘ・Ｓ[0]に、−２Ｘ・Ｓ[0]ρ＋Ｘρ2＜Ｗ[0]＝１−Ｘ・Ｓ[0]2＜２Ｘ・Ｓ[0]ρ＋Ｘρ2（ρ＝ａ／（ｒ−１））を満たす値をセットし、第２のステップにおいて、
平方根の逆数の桁ｑj+1をｒＷ[j]とＸとＰ[j]の見積り値に応じて桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択し、中間結果Ｓ[j]に関する漸化式、Ｓ[j+1]:=Ｓ[j]＋ｑj+1ｒ-j-1と、残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=ｒＷ[j]−（２Ｐ[j]＋Ｘｑj+1ｒ-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1ｒ-j-1とについて演算を行ない、上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なう。
【００１２】
また、第７の発明は、ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積Ｐ[j]を用いて基数が２のときの平方根の逆数を計算する機能をコンピュータに実現させるためのプログラムであって、上記機能は、
第１のステップにおいて、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、第２のステップにおいて、平方根の逆数の桁ｑj+1を２Ｗ[j]の見積り値に応じて桁集合｛−１，０，１｝から選択し、中間結果Ｓ[j]からＳ[j+1]を求めるとともに、残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=２Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1２-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1２-j-1とを用いて加算を行ない、上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なう。
【００１３】
また、第８の発明は、ｊ回の繰り返し計算後の中間結果Ｓ[j]と、残余Ｗ[j]と、演算数Ｘ（１／４＜Ｘ＜１）と中間結果Ｓ[j]との積Ｐ[j]を用いて基数が４のときの平方根の逆数を計算する機能をコンピュータに実現させるためのプログラムであって、上記機能は、
第１のステップにおいて、演算数Ｘが３／８より小さい場合には、初期値Ｓ[0]として２、Ｗ[0]として１−４Ｘ、Ｐ[0]として２Ｘをセットし、演算数Ｘが３／８以上３／４未満の場合には、初期値Ｓ[0]として３／２、Ｗ[0]として１−９Ｘ／４、Ｐ[0]として３Ｘ／２をセットし、演算数Ｘが３／４以上の場合には、初期値Ｓ[0]として１、Ｗ[0]として１−Ｘ、Ｐ[0]としてＸをセットし、第２のステップにおいて、平方根の逆数の桁ｑj+1を４Ｗ[j]の見積り値とＰ[j]の見積り値に応じて桁集合｛−２，−１，０，１，２｝から選択し、
中間結果Ｓ[j]からＳ[j+1]を求めるとともに、残余Ｗ[j]に関する漸化式、Ｗ[j+1]:=４Ｗ[j]−（２Ｐ[j]＋Ｘｑj+1４-j-1）ｑj+1と、積Ｐ[j]に関する漸化式Ｐ[j+1]:=Ｐ[j]＋Ｘｑj+1４-j-1とを用いて加算を行ない、上記第２のステップにおける各処理を、ｊ＝０からｎ−１までｎ回繰り返して行なう。
【００１４】
【発明の実施の形態】
１．まず、基数がｒの場合における、平方根の逆数計算のハードウェアアルゴリズムについて説明する。浮動小数点数の平方根の逆数計算の仮数部の計算について考える。１／４＜Ｘ＜１なる演算数Ｘに対し、その平方根の逆数としてＳ＝Ｘ−１／２を求める。ここで１＜Ｘ−１／２＜２である。Ｘはｎ桁のｒ進小数とする。基数ｒは２の冪、すなわちｒ＝２ｂであるとする。
【００１５】
−ｒ−ｎ＜Ｘ−１／２−Ｓ＜ｒ−ｎ                            （１）
を満たすＳをｒ進で小数点以下ｎ桁目まで求める。
【００１６】
ここでは平方根等の計算と同様、平方根の逆数の桁ｑｊを上位から一桁ずつ求める。Ｓ［ｊ］をｊ回の繰り返し計算後の中間結果とすると、
【数１】
0003563043.tif 000002
である。ここにＳ［０］は結果の初期値である。中間結果に関する漸化式は、
Ｓ［ｊ＋１］：＝Ｓ［ｊ］＋ｑｊ＋１ｒ−ｊ−１                          （２）
となる。平方根の逆数の桁ｑｊ＋１を冗長な桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択する。ここに、ｒ／２＜ａ＜ｒである。最終結果は
【数２】
0003563043.tif 000003
となる。結果をｎ桁の精度で求める。すなわち、（１）を満たすＳを求める。
【００１７】
残余（スケーリングした剰余）Ｗ［ｊ］を
Ｗ［ｊ］＝ｒｊ（１−Ｘ・Ｓ［ｊ］２）                        （３）
と定義する。（３）のｊにｊ＋１を代入すると、Ｗ［ｊ＋１］＝ｒｊ＋１（１−Ｘ・Ｓ［ｊ＋１］２）となり、これと（２）および（３）より、残余に関する漸化式
Ｗ［ｊ＋１］：＝ｒＷ［ｊ］−２Ｘ・Ｓ［ｊ］ｑｊ＋１−Ｘｑｊ＋１２ｒ−ｊ−１      （４）
を得る。この漸化式は−２Ｘ・Ｓ［ｊ］ｑｊ＋１という項を含むので、そのまま計算すると、ｎ桁の数Ｘとｊ桁の数Ｓ［ｊ］の乗算が必要になる。この乗算を避けるため、Ｘ・Ｓ［ｊ］を記憶し、これをシフトと加減算と一桁の乗算で更新して行く。
【００１８】
Ｘ・Ｓ［ｊ］をＰ［ｊ］とおく。Ｗ［ｊ］に関する漸化式は、
Ｗ［ｊ＋１］：＝ｒＷ［ｊ］−ｑｊ＋１（２Ｐ［ｊ］＋Ｘｑｊ＋１ｒ−ｊ−１）      （５）
と書き直される。また、積Ｐ［ｊ］に関する漸化式は、
Ｐ［ｊ＋１］：＝Ｐ［ｊ］＋Ｘｑｊ＋１ｒ−ｊ−１                      （６）
となる。ｑｊ＋１の選択法については、後で述べる。
【００１９】
（１）より、（Ｓ−ｒ−ｎ）２＜Ｘ−１＜（Ｓ＋ｒ−ｎ）２が成り立たなければならない。
【００２０】
【数３】
0003563043.tif 000004
であり、平方根の逆数の桁の最小値と最大値は−ａとａであるから、上式は、（Ｓ［ｊ］−ｒ−ｊρ）２＜Ｘ−１＜（Ｓ［ｊ］＋ｒ−ｊρ）２と書き直される。ここに、ρ＝ａ／（ｒ−１）は平方根の逆数の桁集合の冗長度である。よって、（３）より、Ｗ［ｊ］の満たすべき条件として、
−２Ｘ・Ｓ［ｊ］ρ＋Ｘρ２ｒ−ｊ＜Ｗ［ｊ］＜２Ｘ・Ｓ［ｊ］ρ＋Ｘρ２ｒ−ｊ    （７）
を得る。
【００２１】
最初、ｊ＝０において、
0003563043.tif 000005
が成り立たなければならない。２−２＜Ｘ＜１であるから、例えば、Ｓ［０］＝３／２、Ｗ［０］＝１−９Ｘ／４とすることで、（８）を満たすことができる。このときＰ［０］＝３Ｘ／２となる。ρ＝１の場合は、Ｓ［０］＝１、Ｗ［０］＝１−Ｘとすることもできる。
【００２２】
基数がｒの場合の平方根の逆数計算のアルゴリズムは、漸化式、（２）と（５）と（６）のｎ回の繰り返しからなる。アルゴリズムをまとめると以下のようになる。
【００２３】
0003563043.tif 000006
図１は上記した平方根の逆数計算のアルゴリズムをフローチャートで示した図である。まず、初期値Ｓ［０］、Ｗ［０］、Ｐ［０］に適切な値をセットする（ステップＳ１）。次に、平方根の逆数の桁ｑｊ＋１を冗長な桁集合｛−ａ，…，−１，０，１，…，ａ｝から選択し、中間結果Ｓ［ｊ］に関する漸化式、Ｓ［ｊ＋１］：＝Ｓ［ｊ］＋ｑｊ＋１ｒ−ｊ−１と、残余Ｗ［ｊ］に関する漸化式、Ｗ［ｊ＋１］：＝ｒＷ［ｊ］−（２Ｐ［ｊ］＋Ｘｑｊ＋１ｒ−ｊ−１）ｑｊ＋１と、積Ｐ［ｊ］に関する漸化式Ｐ［ｊ＋１］：＝Ｐ［ｊ］＋Ｘｑｊ＋１ｒ−ｊ−１とについての演算をｊ＝０からｎ−１までｎ回繰り返して行なう（ステップＳ２〜Ｓ５）。次に求めたＳ［ｎ］を演算数Ｘの平方根の逆数として出力する（ステップＳ６）。
【００２４】
Ｓ［ｎ］が求めるＸ−１／２であるが、ｒ進符号付きディジット表現（ｒ進ＳＤ表現）になっているので、通常の２進表現に変換する必要がある。この変換は、計算の最後に行ってもよいし、既存の除算器等で用いられているＯｎ−ｔｈｅ−ｆｌｙ変換により、計算と並行して行ってもよい。Ｐ［ｎ］として、Ｘ１／２も求まる。
【００２５】
冗長表現を用いて漸化式の計算に現れる加減算を桁上げの伝搬なしに行うことにより、若干のハードウェアの増加で、計算を大幅に高速化できる。そこで、ここでは、冗長表現を用いた実現を考える。すなわち、残余Ｗ［ｊ］および中間結果Ｓ［ｊ］と演算数Ｘの積Ｐ［ｊ］を桁上げ保存形あるいは２進ＳＤ表現で表し、これらの漸化式の計算に現れる加減算を桁上げの伝搬なしに行う。
【００２６】
以下に、平方根の逆数の桁の選択について説明する。
【００２７】
平方根の逆数の桁ｑｊ＋１はＷ［ｊ＋１］が
0003563043.tif 000007
を満たすように、冗長な桁集合｛−ａ，…，−１，０，１，…，ａ｝の中から選ぶ。ｑｊ＋１はｒＷ［ｊ］、Ｘ、Ｓ［ｊ］に依存する。
【００２８】
ｑｊ＋１としてｋ（＝−ａ，−ａ＋１，…，ａ）を選んでもよいｒＷ［ｊ］の範囲を（Ｌｋ［ｊ］，Ｕｋ［ｊ］）とすると、
Ｌｋ［ｊ］＝２Ｘ・Ｓ［ｊ］（ｋ−ρ）＋Ｘ（ｋ−ρ）２ｒ−ｊ−１      （１０）
Ｕｋ［ｊ］＝２Ｘ・Ｓ［ｊ］（ｋ＋ρ）＋Ｘ（ｋ＋ρ）２ｒ−ｊ−１      （１１）
となる。ｋ＝−ａに対する下限およびｋ＝ａに対する上限は、それぞれ、ｒＷ［ｊ］の下限と上限に一致する。
【００２９】
ｑｊ＋１としてｋ−１が選ばれるｒＷ［ｊ］の範囲と、ｋが選ばれる範囲は連続していなければならないので、Ｕｋ−１［ｊ］＞Ｌｋ［ｊ］が成り立たなければならない。すなわち、
（２ρ−１）（２Ｘ・Ｓ［ｊ］＋Ｘ（２ｋ−１）ｒ−ｊ−１）＞０      （１２）
が成り立たなければならない。これは、常に成り立っている。（１２）の左辺は、隣り合う選択領域の重なりを表している。この重なりを用いて、桁選択関数を簡単化できる。すなわち、ｑｊ＋１はｒＷ［ｊ］とＸとＳ［ｊ］に依存するが、この重なりを利用して、ｑｊ＋１をこれらの値の見積り値（上位数ビット）から定めることができる。
【００３０】
Ｐ［ｊ］＝Ｘ・Ｓ［ｊ］であるから、（１０）と（１１）は、
Ｌｋ［ｊ］＝２Ｐ［ｊ］（ｋ−ρ）＋Ｘ（ｋ−ρ）２ｒ−ｊ−１          （１３）
Ｕｋ［ｊ］＝２Ｐ［ｊ］（ｋ＋ρ）＋Ｘ（ｋ＋ρ）２ｒ−ｊ−１       （１４）
と書き直すことができる。したがって、ｑｊ＋１は、ｒＷ［ｊ］とＸとＰ［ｊ］の見積り値から定めることができる。（１３）および（１４）の右辺の第２項は、ｊが増えると急速に小さくなるので、桁選択関数を、あるとしてもごく少数の小さなｊについてを除き、Ｘに依存しないようにすることができる。
【００３１】
ｒＷ［ｊ］およびＰ［ｊ］の見積り値をｒＷ［ｊ］ｅおよびＰ［ｊ］ｅとする。ｒＷ［ｊ］ｅおよびＰ［ｊ］ｅは、冗長表現で表されたｒＷ［ｊ］およびＰ［ｊ］を、それぞれ、小数点以下ｔビットおよびｄビットで打ち切って求めるものとする。（ｒ進の桁でなく、２進のビットであることに注意。）桁選択関数は、選択の境界となる値の集合
【数４】
0003563043.tif 000008
で表される。ここに、ｍｋ（Ｐ［ｊ］ｅ）＜ｒＷ［ｊ］ｅ＜ｍｋ＋１（Ｐ［ｊ］ｅ）ならば、ｑｊ＋１としてｋが選択される。
【００３２】
Ｗ［ｊ］が桁上げ保存形で表されており、ｒＷ［ｊ］ｅとしてｒＷ［ｊ］を小数点以下ｔビットで打ち切った値をそのまま用いる場合は、ｒＷ［ｊ］ｅ＜ｒＷ［ｊ］＜ｒＷ［ｊ］ｅ＋２−ｔ＋１である。したがって、ｍｋ（Ｐ［ｊ］ｅ）＞ｍａｘ  Ｐ［ｊ］ｅ（Ｌｋ［ｊ］）かつｍｋ（Ｐ［ｊ］ｅ）−２−ｔ＋２−ｔ＋１＜ｍｉｎ  Ｐ［ｊ］ｅ（Ｕｋ−１［ｊ］）が成り立たなければならない。すなわち、
0003563043.tif 000009
が満たされなければならない。ここに、ｍａｘ  Ｐ［ｊ］ｅ（Ｌｋ［ｊ］）は、Ｐ［ｊ］の見積り値がＰ［ｊ］ｅであるとき、ｑｊ＋１としてｋを選んでもよいｒＷ［ｊ］の下限の最大値を表し、ｍｉｎ  Ｐ［ｊ］ｅ（Ｕｋ−１［ｊ］）はｑｊ＋１としてｋ−１を選んでもよいｒＷ［ｊ］の上限の最小値を表す。Ｐ［ｊ］ｅは（１５）を満たす２−ｔの倍数でなければならない。なお、ｑｊ＋１としてｋ−１を選んでもよいｒＷ［ｊ］ｅの最大値は、ｍｋ（Ｐ［ｊ］ｅ）−２−ｔである。桁選択が可能なための最小限の領域の重なりの必要条件は、
ｍｉｎ  Ｐ［ｊ］ｅ（Ｕｋ−１［ｊ］）−ｍａｘ  Ｐ［ｊ］ｅ（Ｌｋ［ｊ］）＞２−ｔ          （１６）
である。
【００３３】
Ｐ［ｊ］が桁上げ保存形で表されており、Ｐ［ｊ］ｅとしてＰ［ｊ］を小数点以下ｄビットで打ち切った値を用いる場合、Ｐ［ｊ］ｅ＜Ｐ［ｊ］＜Ｐ［ｊ］ｅ＋２−ｄ＋１である。したがって、（１３）および（１４）より、ｋ＞０のとき、
0003563043.tif 000010
ｋ＜０のとき、
0003563043.tif 000011
が成り立たなければならない。
【００３４】
これらの値から桁選択関数を定めればよい。これらの値はｊに依存するので、ｊによって桁選択関数が異なることもある。実際には、あるとしてもごく少数の小さなｊについてを除き、共通の桁選択関数を得ることができる。
【００３５】
このアルゴリズムに基づき、基数ｒや平方根の逆数の桁集合の冗長度ρ、残余Ｗ［ｊ］および演算数Ｘと中間結果Ｓ［ｊ］の積Ｐ［ｊ］の表現に用いる数表現（桁上げ保存形か２進ＳＤ表現か）、桁選択関数等を定めることにより、種々の具体的なアルゴリズムを設計することができる。
【００３６】
以下に、回路実現に関する一般的考察を行なう。上記したアルゴリズムに基づく平方根の逆数計算回路は、組合せ回路としても順序回路としても実現できる。パイプライン化も可能である。
【００３７】
まず、アルゴリズムのＳｔｅｐ２の繰り返しの１回分の計算を行う回路について考える。図２のブロック図はこのときの回路構成を示している。ここでは、Ｗ［ｊ］およびＰ［ｊ］は桁上げ保存形で表されるものとする。また、Ｏｎ−ｔｈｅ−ｆｌｙ変換を用いるものとし、Ｓ［ｊ］の２進表現Ｓ［ｊ］＝とＳ［ｊ］−２−ｊの２進表現Ｓ［ｊ］−を保持するものとする。
【００３８】
図２において、桁選択回路１１は、ｒＷ[j]およびＰ[j]の上位数ビットの値からｑj+1を決定する桁選択回路である。一桁乗算器１（１３）は、演算数Ｘをｊ＋１桁シフトしたＸｒ-j-1に、桁選択回路１１の出力ｑj+1を乗じ、Ｘｑj+1ｒ-j-1を生成する乗数が１桁の乗算器である。桁上げ保存加算器Ｗ１（１４）は、２Ｐ[j]と一桁乗算器１（１３）の出力とを加え合わせる、いくつかの桁上げ保存加算器である。
【００３９】
一桁乗算器２（１５）は、桁上げ保存加算器Ｗ１（１４）の出力に桁選択回路１１の出力ｑｊ＋１を乗ずる、乗数が１桁の乗算器である。桁上げ保存加算器Ｗ２（１２）は、ｒＷ［ｊ］と一桁乗算器２（１５）の出力を加え合わせてＷ［ｊ＋１］を計算する、いくつかの桁上げ保存加算器である。桁上げ保存加算器Ｐ（１６）は、Ｐ［ｊ］と一桁乗算器１（１３）の出力を加え合わせてＰ［ｊ＋１］を計算する、いくつかの桁上げ保存加算器である。
【００４０】
Ｏｎ−ｔｈｅ−ｆｌｙ変換器（１０）は、Ｓ［ｊ］＝とＳ［ｊ］−  とからＳ［ｊ＋１］＝とＳ［ｊ＋１］−を計算する、主にセレクタからなる変換器である。
【００４１】
上記一桁乗算器１（１３）と、桁上げ保存加算器Ｗ１（１４）と、一桁乗算器２（１５）と、桁上げ保存加算器Ｗ２（１２）とはＷ更新回路２１を構成する。上記一桁乗算器１（１３）と、桁上げ保存加算器Ｐ（１６）とはＰ更新回路２２を構成する。Ｏｎ−ｔｈｅ−ｆｌｙ変換器（１０）は、Ｓ更新回路２０を構成する。
【００４２】
平方根の逆数計算回路をＳｔｅｐ２の１回分の計算を１クロックで行う順序回路として実現する場合、回路は組合せ回路部とレジスタ群からなる。組合せ回路部は図２に示した回路に、レジスタに初期値を設定するための簡単な回路を付加したものである。レジスタとしては、Ｓ［ｊ］＝とＳ［ｊ］−を記憶するためのＲＥＧ−ＳＥとＲＥＧ−ＳＭ、Ｗ［ｊ］を記憶するためのＲＥＧ−ＷＣとＲＥＧ−ＷＳ、Ｐ［ｊ］を記憶するためのＲＥＧ−ＰＣとＲＥＧ−ＰＳ、Ｘを記憶するためのＲＥＧ−Ｘが必要である。
【００４３】
Ｗ［ｊ］とＰ［ｊ］は桁上げ保存形であるから、それぞれにレジスタが二つ必要である。Ｓｔｅｐ２の繰り返しの各回で、Ｘの可変（ｊ＋１桁）のシフトを避けるため、ＲＥＧ−ＸにはＸｒ−ｊを記憶し、各クロックで１桁右シフトする。この順序回路は、ｎ＋１クロックでｎ桁の平方根の逆数計算を行う。クロックのサイクル時間はｎに無関係な定数である。ハードウェア量はｎに比例する。桁スライス構造の規則正しい回路構造で、ＶＬＳＩ実現に適している。
【００４４】
もちろん、１クロックにＳｔｅｐ２の２回分以上の計算を行う順序回路としても実現することができる。
【００４５】
平方根の逆数計算回路を組合せ回路として実現する場合、回路はＳｔｅｐ１を計算するための簡単な回路と、上述したＳｔｅｐ２の１回分の計算を行う回路ｎ個を、直列に接続することにより構成できる。シフトは配線によって実現できる。回路の遅延（論理ゲートの段数）はｎに比例する。ハードウェア量はｎ２  に比例する。規則正しい２次元セル配列構造になり、ＶＬＳＩ実現に適している。
【００４６】
２．次に、基数が２の場合における、平方根の逆数計算のハードウェアアルゴリズムについて説明する。
【００４７】
１．で説明したアルゴリズムの具体的な例として、基数ｒが２で、平方根の逆数の桁集合が｛−１，０，１｝、すなわち冗長度ρが１で、残余Ｗ［ｊ］および積Ｐ［ｊ］を桁上げ保存形で表す場合について考える。
【００４８】
基数が２の場合の漸化式は、
Ｓ［ｊ＋１］：＝Ｓ［ｊ］＋ｑｊ＋１２−ｊ−１，
Ｗ［ｊ＋１］：＝２Ｗ［ｊ］−（２Ｐ［ｊ］＋Ｘｑｊ＋１２−ｊ−１）ｑｊ＋１，
Ｐ［ｊ＋１］：＝Ｐ［ｊ］＋Ｘｑｊ＋１２−ｊ−１
となる。ρ＝１であるから、ｊ＝０における初期値を、すべてのＸについて、Ｓ［０］＝１、Ｗ［０］＝１−Ｘ、Ｐ［０］＝Ｘ、とすることができる。このとき、０＜Ｗ［０］＜３／４となる。
【００４９】
桁選択関数を定めるために、まず、式（１３）と（１４）から、ＬｋとＵｋを求める。
【００５０】
Ｕ−１［ｊ］＝０
Ｌ０［ｊ］＝−２Ｐ［ｊ］＋２−ｊ−１Ｘ
Ｕ０［ｊ］＝２Ｐ［ｊ］＋２−ｊ−１Ｘ
Ｌ１［ｊ］＝０
Ｘ＞１／４、Ｐ［ｊ］＞１／４、ｊ＞０であるから、
ｍａｘ  （Ｌ０［ｊ］）＜−３／８
ｍｉｎ  （Ｕ０［ｊ］）＞１／２
である。これらの値は、Ｐ［ｊ］やＸ、ｊの値によらない。したがって、（１５）より、−３／８＜ｍ０＜−２−ｔおよび０＜ｍ１＜１／２−２−ｔが満たされなければならない。よって、ｔ＝２とすることにより、ｍ０＝−１／４、ｍ１＝１／４とすることができる。これは、ｊに依存しない。
【００５１】
基数２のアルゴリズムは以下のようになる。−２＜Ｗ［ｊ］＜３であるから、Ｗ［ｊ］は整数部３ビット（符号ビットを含む）の負数２の補数表示の桁上げ保存形で表すことができる。したがって、ｑｊ＋１は２Ｗ［ｊ］の上位６ビット（桁上げ保存形の６桁）から決定できる。
【００５２】
0003563043.tif 000012
【数５】
0003563043.tif 000013
0003563043.tif 000014
得られたＳ［ｎ］＝が求めるＳである。
【００５３】
図３は上記した平方根の逆数計算のアルゴリズムをフローチャートで示した図である。まず、初期値Ｓ［０］、Ｗ［０］、Ｐ［０］に適切な値をセットする（ステップＳ１０）。次に、平方根の逆数の桁ｑｊ＋１を２Ｗ［ｊ］の見積り値に応じて桁集合｛−１，０，１｝から選択する。同時に、Ｏｎ−ｔｈｅ−ｆｌｙ変換によりＳ［ｊ＋１］＝とＳ［ｊ＋１］−を求めるとともに、残余Ｗ［ｊ］に関する漸化式、Ｗ［ｊ＋１］：＝２Ｗ［ｊ］−（２Ｐ［ｊ］＋Ｘｑｊ＋１２−ｊ−１）ｑｊ＋１と、積Ｐ［ｊ］に関する漸化式Ｐ［ｊ＋１］：＝Ｐ［ｊ］＋Ｘｑｊ＋１２−ｊ−１とについての桁上げ保存加算をｊ＝０からｎ−１までのｎ回繰り返して行なう（ステップＳ１１〜Ｓ１４）。次に得られたＳ［ｎ］＝を求めるＳとして出力する（ステップＳ１５）。
【００５４】
次に、上記した基数２のアルゴリズムの順序回路実現について考える。回路は、１クロックでアルゴリズムのＳｔｅｐ２の繰り返しの１回分の計算を行うものとする。図４のブロック図はこのときの回路構成を示しており、いくつかの組合せ回路モジュールとレジスタ群からなる。
【００５５】
図４の構成は、図２の構成と同様に、桁選択回路３６に加えて、Ｗ更新回路４２として、一桁乗算器１（３８）と、桁上げ保存加算器Ｗ１（３９）と、一桁乗算器２（４０）と、桁上げ保存加算器Ｗ２（４１）とを有している。また、Ｐ更新回路４６として、一桁乗算器１（３８）と、桁上げ保存加算器Ｐ（４５）とを有している。また、Ｓ更新回路３３としてＯｎ−ｔｈｅ−ｆｌｙ変換器３２を有している。
【００５６】
さらに図２の構成に加えて、Ｓ［ｊ］の値を記憶するためのレジスタＳＥ（３０），ＳＭ（３１）と、Ｗ［ｊ］の値を記憶するためのレジスタＷＳ（３４），ＷＣ（３５）と、Ｐ［ｊ］の値を記憶するためのレジスタＰＳ（４３），ＰＣ（４４）と、Ｘを記憶するためのシフトレジスタＸ（３７）とを有する。
【００５７】
桁選択回路３６は、６ビットの桁上げ伝搬加算器と簡単な定数比較器からなる。ｑｊ＋１をドライブするバッファも必要となる。Ｏｎ−ｔｈｅ−ｆｌｙ変換器３２は、主に二つの２−１セレクタからなる。一桁乗算器１（３８）、２（４０）は、桁選択回路３６の出力ｑｊ＋１の値により、０か、データ入力そのものか、データ入力のビット反転を出力するマルチプレクサである。
【００５８】
桁上げ保存加算器Ｗ１（３９）、Ｐ（４５）はそれぞれ、桁上げ保存加算器であり、桁上げ保存加算器Ｗ２（４１）は４−２加算器である。打ち切り誤差を考慮すると、Ｗ［ｊ］とＰ［ｊ］は２−ｎ−ｃの精度で計算すべきである。ただし、
【数６】
0003563043.tif 000015
である。
【００５９】
３．次に、基数が４の場合における、平方根の逆数計算のハードウェアアルゴリズムについて説明する。
【００６０】
ここでは、基数ｒが４で、平方根の逆数の桁集合が｛−２，−１，０，１，２｝、すなわち冗長度ρが２／３で、残余Ｗ［ｊ］および積Ｐ［ｊ］を桁上げ保存形で表す場合について考える。
【００６１】
基数が４の場合の漸化式は、
Ｓ［ｊ＋１］：＝Ｓ［ｊ］＋ｑｊ＋１４−ｊ−１，
Ｗ［ｊ＋１］：＝４Ｗ［ｊ］−（２Ｐ［ｊ］＋Ｘｑｊ＋１４−ｊ−１）ｑｊ＋１，
Ｐ［ｊ＋１］：＝Ｐ［ｊ］＋Ｘｑｊ＋１４−ｊ−１
となる。
【００６２】
ｊ＝０における初期値は、Ｘ＜３／８のとき、Ｓ［０］＝２、Ｗ［０］＝１−４Ｘ、Ｐ［０］＝２Ｘ、３／８＜Ｘ＜３／４のとき、Ｓ［０］＝３／２、Ｗ［０］＝１−９Ｘ／４、Ｐ［０］＝３Ｘ／２、Ｘ＞３／４のとき、Ｓ［０］＝１、Ｗ［０］＝１−Ｘ、Ｐ［０］＝Ｘとする。すべてのＸについて、Ｓ［０］＝３／２、Ｗ［０］＝１−９Ｘ／４、Ｐ［０］＝３Ｘ／２とすることも可能であるが、ｊ＝０においてもｊ＞１の場合と同じ桁選択関数を用いることができるようにするために、これらの初期値を用いる。
【００６３】
桁選択関数を定めるために、まず、式（１７）と（１８）からｍａｘ  Ｐ［ｊ］ｅ（Ｌｋ［ｊ］）とｍｉｎ  Ｐ［ｊ］ｅ（Ｕｋ［ｊ］）を求める。
【００６４】
【数７】
0003563043.tif 000016
【００６５】
ｊ＞１の場合、（１５）より、以下が満たされなければならない。
【００６６】
【数８】
0003563043.tif 000017
【００６７】
ｊ＞１の場合、Ｐ［ｊ］ｅ＞Ｘ（Ｘ−１／２−（２／３）・４−ｊ）−２−ｄ＋１であるから、ｄ＝６、ｔ＝４とすることにより、
ｍ−１（Ｐ［ｊ］ｅ）＝−ｔｒｕｎｃ４（３（Ｐ［ｊ］ｅ＋２−ｄ））
ｍ０（Ｐ［ｊ］ｅ）＝−ｔｒｕｎｃ４（Ｐ［ｊ］ｅ＋２−ｄ）
ｍ１（Ｐ［ｊ］ｅ）＝ｔｒｕｎｃ４（Ｐ［ｊ］ｅ＋２−ｄ）
ｍ２（Ｐ［ｊ］ｅ）＝ｔｒｕｎｃ４（３（Ｐ［ｊ］ｅ＋２−ｄ））
とすることができる。ｔｒｕｎｃ４（  ）は小数点以下４ビット目までの打ち切りを示す。
【００６８】
ｊ＝０の場合について考える。Ｘ＜３／８のとき、Ｓ［０］＝２、Ｗ［０］＝１−４Ｘであるから、上記のｍｋ（Ｐ［ｊ］ｅ）について、４Ｗ［０］＝４−１６Ｘ＞Ｌ−１［０］かつ４Ｗ［０］ｅ＞ｍ−１（Ｐ［０］ｅ）、ｍａｘ  Ｐ［０］ｅ（Ｌ０［０］）＜ｍ０（Ｐ［０］ｅ）＜ｍｉｎ  Ｐ［０］ｅ（Ｕ−１［０］）、ｍａｘ  Ｐ［０］ｅ（Ｌ１［０］）＜ｍ１（Ｐ［０］ｅ）＜ｍｉｎ  Ｐ［０］ｅ（Ｕ０［０］）、４Ｗ［０］＜Ｕ１［０］かつ４Ｗ［０］ｅ＜ｍ２（Ｐ［０］ｅ）−２−４である。
【００６９】
３／８＜Ｘ＜３／４のとき、Ｓ［０］＝３／２、Ｗ［０］＝１−９Ｘ／４であるから、４Ｗ［０］＝４−９Ｘ＞Ｌ−１［０］かつ４Ｗ［０］ｅ＞ｍ−１（Ｐ［０］ｅ）、ｍａｘ  Ｐ［０］ｅ（Ｌ０［０］）＜ｍ０（Ｐ［０］ｅ）＜ｍｉｎ  Ｐ［０］ｅ（Ｕ−１［０］）、ｍａｘ  Ｐ［０］ｅ（Ｌ１［０］）＜ｍ１（Ｐ［０］ｅ）＜ｍｉｎ  Ｐ［０］ｅ（Ｕ０［０］）、４Ｗ［０］＜Ｕ１［０］かつ４Ｗ［０］ｅ＜ｍ２（Ｐ［０］ｅ）−２−４である。
【００７０】
Ｘ＞３／４のとき、Ｓ［０］＝１、Ｗ［０］＝１−Ｘであるから、４Ｗ［０］＝４−４Ｘ＞Ｌ−１［０］かつ４Ｗ［０］ｅ＞ｍ−１（Ｐ［０］ｅ）、ｍａｘ  Ｐ［０］ｅ（Ｌ０［０］）＜ｍ０（Ｐ［０］ｅ）＜ｍｉｎ  Ｐ［０］ｅ（Ｕ−１［０］）、ｍａｘ  Ｐ［０］ｅ（Ｌ１［０］）＜ｍ１（Ｐ［０］ｅ）＜ｍｉｎ  Ｐ［０］ｅ（Ｕ０［０］）、４Ｗ［０］＜Ｕ１［０］かつ４Ｗ［０］ｅ＜ｍ２（Ｐ［０］ｅ）−２−４である。
【００７１】
したがって、いずれの場合も、ｊ＞１の場合と同じ桁選択関数を用いることができ、ｑ１は｛−１，０，１｝から選ばれる。
【００７２】
基数４のアルゴリズムは以下のようになる。−２＜Ｗ［ｊ］＜２であるから、Ｗ［ｊ］は整数部３ビット（符号ビットを含む）の負数２の補数表示の桁上げ保存形で表すことができる。また、０＜Ｐ［ｊ］＜２であるから、Ｐ［ｊ］は整数部１ビットの符号なしの桁上げ保存形で表すことができる。したがって、ｑｊ＋１は４Ｗ［ｊ］の上位８ビットとＰ［ｊ］の上位７ビット（いずれも桁上げ保存形の桁）から決定できる。
【００７３】
0003563043.tif 000018
｛
【数９】
0003563043.tif 000019
0003563043.tif 000020
図５は上記した平方根の逆数計算のアルゴリズムをフローチャートで示した図である。まず、演算数Ｘが３／８より小さいかどうかを判断し（ステップＳ２０）、小さい場合には、初期値Ｓ［０］として２、Ｗ［０］として１−４Ｘ、Ｐ［０］として２Ｘをセットする（ステップＳ２２）。また、Ｘが３／８以上の場合にはステップＳ２１においてＸが３／８以上３／４未満かどうかを判断する。ここでＹＥＳの場合には、初期値Ｓ［０］として３／２、Ｗ［０］として１−９Ｘ／４、Ｐ［０］として３Ｘ／２をセットする（ステップＳ２３）。また、ステップＳ２１の判断がＮＯの場合にはステップＳ２４において、初期値Ｓ［０］として１、Ｗ［０］として１−Ｘ、Ｐ［０］としてＸをセットする。
【００７４】
このように基数が４の場合には、Ｘの値に応じて３つのケースに場合分けして各ケースごとに適切な初期値をセットすることにより、ｊ＝０の場合にもｊ＞１の場合と同じ桁選択関数を用いることができるようにしている。
【００７５】
次に平方根の逆数の桁ｑｊ＋１を４Ｗ［ｊ］の見積り値とＰ［ｊ］の見積り値に応じて桁集合｛−２，−１，０，１，２｝から選択する。同時に、Ｏｎ−ｔｈｅ−ｆｌｙ変換によりＳ［ｊ＋１］＝とＳ［ｊ＋１］−を求めるとともに、残余Ｗ［ｊ］に関する漸化式、Ｗ［ｊ＋１］：＝４Ｗ［ｊ］−（２Ｐ［ｊ］＋Ｘｑｊ＋１４−ｊ−１）ｑｊ＋１と、積Ｐ［ｊ］に関する漸化式Ｐ［ｊ＋１］：＝Ｐ［ｊ］＋Ｘｑｊ＋１４−ｊ−１とについての桁上げ保存加算をｊ＝０からｎ−１までのｎ回繰り返して行なう（ステップＳ２５〜Ｓ２８）。次に得られたＳ［ｎ］＝を求めるＳとして出力する（ステップＳ２９）。
【００７６】
次に、上記した基数４のアルゴリズムの順序回路実現について考える。回路は、１クロックで、アルゴリズムのＳｔｅｐ２の繰り返しの１回分の計算を行うものとする。基数４の場合の回路構成は、図４に示した基数２の回路構成とほぼ同じになる。唯一の違いは、桁選択回路にＰ［ｊ］の上位数桁も入力されることである。
【００７７】
桁選択回路は、８ビット桁上げ伝搬加算器と、７ビット桁上げ伝搬加算器と１５ビット入力の組合せ回路からなる。ｑｊ＋１をドライブするバッファも必要である。Ｏｎ−ｔｈｅ−ｆｌｙ変換器（３２）は、主に二つの２−１セレクタからなる。一桁乗算器１（３８）と一桁乗算器２（４０）は、ｑｊ＋１の値により、０か、データ入力そのものか、データ入力のビット反転か、データ入力の２倍か、データ入力の２倍のビット反転を出力するマルチプレクサである。桁上げ保存加算器Ｐ（４５）と、桁上げ保存加算器Ｗ１（３９）はそれぞれ、桁上げ保存加算器であり、桁上げ保存加算器Ｗ２（４１）は４−２加算器である。
【００７８】
以上、上記した実施形態によれば、従来のニュートン法等の乗算型の平方根逆数演算回路と異なり、シフトと加減算と一桁の乗算という簡単な計算の繰り返しにより、途中で演算数の逆数や平方根を求めることなく、直接、平方根の逆数を計算するようにしたので、乗算型のものに比べて回路が小さく、また、除算器と開平器を単純に組み合わせたものに比べて高速になる。
【００７９】
また、除算器と開平器とを組み合わせて除算と開平とを重畳させる方法では、除算、開平よりもレイテンシが大きくなってしまうが、本発明では，レイテンシを除算、開平と同じにすることができる。
【００８０】
【発明の効果】
本発明によれば、従来の乗算型平方根逆数演算回路よりも省ハードウェアであり、かつ従来の除算器及び開平器を用いた平方根逆数演算回路よりも高速である平方根の逆数計算方法、計算回路、及びプログラムを提供することができる。
【図面の簡単な説明】
【図１】基数がｒの場合における平方根の逆数計算のアルゴリズムをフローチャートで示した図である。
【図２】Ｓｔｅｐ２の繰り返しの１回分を計算する回路のブロック図である。
【図３】基数が２の場合における平方根の逆数計算のアルゴリズムをフローチャートで示した図である。
【図４】基数２の平方根の逆数計算回路のブロック図である。
【図５】基数が４の場合における平方根の逆数計算のアルゴリズムをフローチャートで示した図である。
【符号の説明】
１０  Ｏｎ−ｔｈｅ−ｆｌｙ変換器
１１  桁選択回路
１２  桁上げ保存加算器Ｗ２
１３  一桁乗算器１
１４  桁上げ保存加算器Ｗ１
１５  一桁乗算器２
１６  桁上げ保存加算器Ｐ
２０  Ｓ更新回路
２１  Ｗ更新回路
２２  Ｐ更新回路
３０  レジスタＳＥ
３１  レジスタＳＭ
３２  Ｏｎ−ｔｈｅ−ｆｌｙ変換器
３３  Ｓ更新回路
３４  レジスタＷＳ
３５  レジスタＷＣ
３６  桁選択回路
３７  シフトレジスタＸ
３８  一桁乗算器１
３９  桁上げ保存加算器Ｗ１
４０  一桁乗算器２
４１  桁上げ保存加算器Ｗ２
４２  Ｗ更新回路
４３  レジスタＰＳ
４４  レジスタＰＣ
４５  桁上げ保存加算器Ｐ
４６  Ｐ更新回路
【図１】
0003563043.tif 000021
【図２】
0003563043.tif 000022
【図３】
0003563043.tif 000023
【図４】
0003563043.tif 000024
【図５】
0003563043.tif 000025