JP2575984B2 - べき乗計算器及び乗算器 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は数ｘと数ｎとのべき乗
ｘⁿ を、ｎを２べき乗に分解することにより少ない演算
回数で計算するべき乗計算器、および加算と減算とによ
り乗算ｎ・ｘを計算する乗算器に関する。

【０００２】

【従来の技術】べき乗計算を少ない演算回数で（高速
に) 行なう方法としてバイナリ法（Ｂｉｎａｒｙ ｍｅ
ｔｈｏｄ）が知られている。（Ｄ．Ｅ．Ｋｎｕｔｈ：
“Ｓｅｍｉｎｕｍｅｒｉｃａｌ ａｌｇｏｒｉｔｈｍ
（ａｒｉｔｈｍｅｔｉｃ）”ＴｈｅＡｒｔ ｏｆ Ｃｏ
ｍｐｕｔｅｒ Ｐｒｏｇｒａｍｍｉｎｇ Ｖｏｌ．２，
Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ（１９６９）バイナリ法
はｎを２のべき乗の和ｎ＝２ ^k1＋２^k2＋…＋２^kmに分解
し、（ｘ² ) ^k1×（ｘ² ) ^k2×…×（ｘ² ) ^kmを計算し
てｘⁿ を得るものである。たとえば、Ｘ⁴⁷（ｎ＝４７)
の演算回路は以下のようになる。まず、ｘ³²は以下のよ
うに５回の乗算で計算できる。

【０００３】ｘ→ｘ² →ｘ⁴ →ｘ⁸ →ｘ¹⁶→ｘ³²（（ｘ
² ) ^k は２乗をｋ回繰り返すことで計算できる)また、
４７＝３２＋８＋４＋２＋１より、さらに４回の乗算で
ｘ³²×ｘ⁸ ×ｘ ⁴ ×ｘ² ×ｘ＝ｘ^32+8+4+2+1＝ｘ⁴⁷とな
る。よってＸ⁴⁷は９回の乗算で計算できる。

【０００４】バイナリ法の演算回数をｒ_B は指数ｎに対
して式（１) のとおりである。 ｒ_B （ｎ) ＝ａ（ｎ）＋Σ_i=0 ^a(n)-1Ｂ_i （１） ただしａ（ｎ）＝〔ｌｏｇ₂ ｎ〕， Ｂ_i ∈｛０，
１｝， ｎ＝２^a(n)＋Σ_i=0 ^a(n)-1Ｂ_i ・２ⁱ （２） ただし、〔Ｄ〕はＤの小数点以下を切捨た整数、Ｂ_i の
組Ｂ＝〔Ｂ_a(n)-1, Ｂ _a(n)-2, …，Ｂ₁ ，Ｂ₀ 〕はｎ−
２^a(n)の二進表現である。

【０００５】バイナリ法の特徴として、指数ｎを二進表
現したとき“１”の桁数が少ない場合には少ない乗算回
数でべき乗が求まるが、“１”の桁数が多い場合には乗
算回数が多くなることが問題であった。そのようなｎに
対しては、乗算に加え除算を用いることで演算回数（乗
算回数と除算回数の和) を減らせることが知られてい
る。Ｍｏｒａｉｎ−Ｏｌｉｖｏｓ法は、加算と減算を用
いてｎｘを計算する方式であり、その加算と減算をそれ
ぞれ乗算と除算に置き換えることによりべき乗計算に適
用できる。この方法では、加算と減算の組合せを求める
手順においてｎの上位桁に対する場合分けが不十分であ
り、減算を用いるよう拡張したバイナリ法の枠組のなか
で演算回数を最小化する手順になっていない。

【０００６】この発明は、べき乗計算や乗算において、
それぞれ従来より少ない演算回数で計算することができ
るべき乗計算器及び乗算器を提供することを目的とす
る。

【０００７】

【課題を解決するための手段】この発明のべき乗計算器
によれば、三値化変換回路と三値化二進計算回路とより
なり、三値化変換回路ではｎの二進表現の各ビットが順
次得られ、そのビットの“０”と“１”の出現回数の差
が順次計数され、この差の値により反転状態と非反転状
態との間で遷移され、その状態と“０”及び“１”の出
現回数の差とにより１，０，−１の列である三値化二進
数Ｔが出力され、ｎ＝２^a(n)＋Σ_i=0 ^a(n)Ｔ_i Ｚⁱ 、
（Ｔ_i ∈｛−１，０，１｝，ａ（ｎ）＝〔ｌｏｇ₂
ｎ〕）となるＴ_i の組Ｔ＝〔Ｔ_a(n)，…，Ｔ₁ ，Ｔ₀ 〕
のうち、Σ_i=0 ^a(n)｜Ｔ_i ｜が最小なる組合せが求めら
れる。三値化二進計算回路はＸレジスタにｘが初期値と
して格納され、そのＸレジスタの値が各ｉ回目ごとに２
乗手段で２乗されてＸレジスタに格納され、Ｙレジスタ
及びＺレジスタにそれぞれ初期値として１が格納され、
乗算手段により、ｉ回目の繰り返しで得られたＸレジス
タの値（Ｘ² ) ⁱ と、Ｔ_iに応じてＹレジスタ（Ｔ_i ＝
１のとき) の値とが乗算されてＹレジスタに格納され、
またはＺレジスタ（Ｔ_i ＝−１のとき) の値とが乗算さ
れてＺレジスタに格納され、繰り返しの終了後にＸレジ
スタの値とＹレジスタの値とが乗じられて、その乗算結
果がＺレジスタの値で除算され、（ｘ² ) ^a(n)Π_i=0
^a(n)（ｘ² ）^Tiが演算されてｘⁿ が得られる。

【０００８】この発明の乗算器によれば、三値化変換回
路と、三値化二進計算回路とよりなり、三値化変換回路
は前記べき乗計算器のそれと同一であり、三値化二進計
算回路はＸレジスタにｘが初期値として格納され、その
Ｘレジスタの値が２倍手段により各ｉ回目ごとに２倍し
てＸレジスタに格納され、ＹレジスタおよびＺレジスタ
にそれぞれ初期値として１が格納され、加算手段によ
り、ｉ回目の繰り返しで得られるＸレジスタの値２ⁱ ・
ｘと、Ｔ_i に応じてＹレジスタ（Ｔ_i ＝１のとき) の値
とが加算されてＹレジスタに格納され、またはＺレジス
タ（Ｔ_i ＝−１のとき) の値とが加算されてＺレジスタ
に格納され、繰り返しの終了後にＸレジスタの値とＹレ
ジスタの値とが加算され、その加算結果からＺレジスタ
の値が減算され、２^a(n)・ｘ＋Σ_i=0 ^a(n)Ｔ_i ・２ⁱ ・
ｘが演算されてｎｘが得られる。

【０００９】べき乗計算においてこの発明により乗算と
除算を用いることで従来のバイナリ法にくらべて演算回
数が削減できる例としてｘ⁴⁷を考える（上記と同じ例で
あり、バイナリ法では９回の乗算が必要となる) 。ま
ず、ｘ³²は以下のように５回の乗算で計算できる。 ｘ→ｘ² →ｘ⁴ →ｘ⁸ →ｘ¹⁶→ｘ³² また、４７＝３２＋１６−１であるから、さらに２回の
乗除算でｘ³²×ｘ¹⁶／ｘ＝ｘ^32+16-1 ＝ｘ⁴⁷となる。よ
ってｘ⁴⁷は７回の乗除算で計算できる。

【００１０】演算回数は以下の式で与えられる。 ｒ₀ （ｎ）＝ａ（ｎ）＋Σ_i=0 ^a(n)｜Ｔ_i ｜ （３） ただし Ｔ_i ＝｛１，０，−１｝，ｎ＝２^a(n)＋Σ_i=0 ^a(n)Ｔ_i ・２ⁱ （４） 式（４) を満たすＴ_i の組をＴ＝〔Ｔ_a(n)，Ｔ_a(n)-1，
…，Ｔ₁ ，Ｔ₀ 〕と表す。Ｔは一意でなく、式（３) を
最小にする組合せが存在する。

【００１１】

【実施例】この発明のべき乗計算は図１に示すように （ｉ) 三値化変換回路１１により、ｎを入力し、式
（１) を最小にする三値化二進表現Ｔを出力する。 （ii) 三値化二進計算回路１２により，Ｔ，ｘを入力し
ｘⁿ を出力する。

【００１２】三値化変換回路１１は、ｎの二進表現Ｂ′
から三値化二進表現Ｔを求めるものである。二進表現
Ｂ′は、式（２) から｛Ｂ_a(n)，Ｂ_a(n)-1, Ｂ_a(n)-2，
…，Ｂ ₁ ，Ｂ₀ ｝であり、また、三値化二進表現Ｔは式
（４) で与えられる〔Ｔ_a(n)，Ｔ_a(n)-1，…，Ｔ₁ ，Ｔ
₀ 〕である。ところで、ｊ≦ｋのときΣ_i=j ^k ２ⁱ ＝２
^k+1 −２^j より、 ２^k+1 −２^j −Σ_i=j ^k ２ⁱ ＝０（ｊ≦ｋ) （５） また、Ｂ_j ＝１，〜Ｂ_k ＝１，Ｂ_k+1 ＝０のとき（５) より、 Σ_i=j ^k Ｂ_i ・２ⁱ ＝Σ_i=j ^k Ｂ_i ・２ⁱ ＋（２^k+1 −２^j −Σ_i=j ^k ２ⁱ ) ＝Σ_i=j ^k （Ｂ_i −１）・２ⁱ ＋２^k+1 −２^j ＝Σ_i=j+1 ^k （Ｂ_i −１) ・２ⁱ ＋２^k+1 −２^j （Ｂ_j ＝１より) よって、 Σ_i=j ^k Ｂ_i ・２ⁱ ＝２^k+1 ＋Σ_i=j+1 ^k （Ｂ_i −１）・２ⁱ −２^j （Ｂ_j ＝ １，Ｂ_k+1 ＝０，ｊ≦ｋ) （６) が導かれる。

【００１３】また、式（６) の右辺＝Σ_i=j ^k+1 Ｔ_i ・
２ⁱ とおいて２ⁱ の係数を比較することにより、右辺第
１項はＢ_k ＝１，第３項はＢ_j ＝−１であるから、以下
のように二進表現から三値化二進表現への変換が得られ
る。 Ｂ_j ＝１，Ｂ_k+1 ＝０のときＴ_j ＝−１，Ｔ_k+1 ＝１，Ｔ_i ＝Ｂ_i −１ （ｊ＜ｉ≦ｋ) （７） なお演算回数は式（１) 、（３) より０でない桁の数に
よって決まることがわかる。したがって式（６) の両辺
の０でない桁の数に着目すると、左辺はΣ_i=j ^k Ｂ_i 、
右辺は２＋Σ_i=j ^k （１−Ｂ_i ) となる。Ｂ_j ＝１であ
るから（ｉ−Ｂ _j ) ＝０となり、Σ_i=j+1 ^k(1-Bi) ＝Σ
_i=j ^k(1-Bi) これより、二進表現（左辺) にくらべて三
値化二進表現（右辺) の項の数が等しいかまたは少なく
なるのは以下の場合である。

【００１４】 Σ_i=j ^k Ｂ_i −Σ_i=j ^k （１−Ｂ_i ) ≧２ （８） すなわちＢ_j からＢ_k までにおいて“１”の桁の数と
“０”の桁の数の差が３以上の場合には、右辺の三値化
二進数で計算する方が少ない演算回数となる。ただしｋ
＝ａ（ｎ）−１の場合には、Ｔ_a(n)＝１となり三値化二
進表現Ｔの桁数がＢの桁数より多くなるため追加の乗算
が必要となるため、（８) の条件にさらに場合分けが必
要である。（７) を適用して三値化二進表現に変換した
区間（ｊビット目からｋビット目) を反転区間と呼び、
それ以外を非反転区間と呼ぶ。

【００１５】三値化変換回路１１では、ｎの二進表現を
最下位ビットから順次読みだし、“１”の桁が現れた回
数から“０”の桁が現れた回数を引いた値（回数差) を
順次カウントする。以下の条件を満たし、かつカウント
の差が最大となるｊ，ｋで反転／非反転区間の切替を行
なっている。 （ｉ) カウントの差（“１”の回数から“０”の回数を
引いた値) が３以上のとき非反転から反転に切替える。 （ii) ｋ≠ａ（ｎ）−１かつカウントの差が−２以下の
とき反転から非反転に切替える。 （iii)ｋ＝ａ（ｎ）−１かつカウントの差が０以下のと
き反転から非反転に切替える。

【００１６】この手順の詳細を図２、３に示す。以下、
図２，３を参照して、三値化変換回路１１の処理手順を
示す。ｎを入力し値をＮに代入し、Ｍ，Ｊ，Ｙ，Ｘ，
Ｕ，Ｖ，Ｗ，Ｚの値を０に初期化する（Ｓ ₁ ，Ｓ₂ ）。
Ｎの値が１になるまで、以下の処理を繰り返す
（Ｓ₃ ）。Ｙは、Ｎの最下位ビットが１のとき１加算さ
れ、０のとき１減算される（Ｓ₄ ）。Ｎは繰り返し処理
中で一回左シフト（Ｎ＝Ｎ／２）されるため、Ｎの最下
位ビットは繰り返し処理の先頭で順次Ｂ₀ ，Ｂ₁ ，
Ｂ₂ ，…となる。Ｘは繰り返しごとに１加算され、Ｎを
１ビットづつ読みとる際のビット位置を表す（Ｓ₅ ）。
Ｍは非反転（Ｍ＝０）または、反転（Ｍ＝１）を表し、
Ｍの値により処理がわかれる（Ｓ₆）。

【００１７】非反転中（Ｍ＝０）のときはルーチンＲ₁
が実行される。すなわち、Ｙの最小値をＺに保存し、Ｙ
が最小となるときのビット位置Ｘの値をＷに保存する
（Ｓ₈，Ｓ₉ ）。このＷは、非反転区間から反転区間へ
切り替わるビット位置の候補となる。またＹ−Ｚ≧３の
場合、すなわちＹが最小値Ｚとなったビット位置Ｗから
現在のビット位置Ｘまでにおいて二進表現での１の桁の
数が０の桁の数より３以上多くなるとき（Ｓ₇ ）、ビッ
ト位置Ｗにおいて反転区間に切替え（Ｍ＝１）、現在の
Ｙを反転区間の最大値としてＶに保存し、このときのＸ
をＵに保存する。同時にビット位置ＪからＷ−１までを
非反転で計算するようＪをインクリメントしながら繰り
返しＴ_J を１にセットする（Ｔ_J ＝Ｂ_J ）（Ｓ₁₀，
Ｓ₁₁，Ｓ₁₂）。三値化二進数Ｔは下位ビットから順次決
定していくが、このインデックスがＪである。つまり反
転区間とする必要がある所を探し、その前のビット位置
までを非反転区間とする。

【００１８】同様に、反転中（Ｍ＝１）のときはルーチ
ンＲ₂ が実行される。すなわちＹの最大値をＶに保存
し、Ｙが最大となるときのビット位置Ｘの値をＵに保存
する（Ｓ₁₄，Ｓ₁₅）。このＵは、反転区間から非反転区
間へ切り替わるビット位置の候補となる。またＶ−Ｙ≧
２の場合、すなわちＹが最大値Ｖとなったビット位置Ｕ
から現在のビット位置Ｘまでにおいて二進表現での１の
桁の数が０の桁の数より２以上少なくなるとき、ビット
位置Ｕにおいて非反転区間に切替え（Ｍ＝０）、現在の
Ｙを非反転区間の最小値としてＺに保存し、このときの
ＸをＷに保存する。同時にビット位置ＪからＵ−１まで
を非反転で計算するようＪをインクリメントしながら繰
り返しＴ_J を−１にセットする（Ｔ_J ＝Ｂ_J −１）。以
上をＮが１となるまで繰り返す（Ｓ₁₃，Ｓ₁₆，Ｓ₁₇，Ｓ
₁₈）。

【００１９】このように逆のぼってＴ_J を決めているた
め、Ｎ＝１となって繰り返しを終了したあとは図３に示
すようにして残りの部分のＴ_J を決定する。すなわち、
非反転中（Ｍ＝０）のとき、ＪからＸ−１までを非反転
で計算するようＪをインクリメントしながらＴ_J をセッ
トする（Ｔ_J ＝Ｂ_J −Ｍ＝Ｂ_J ）（Ｓ₂₀，Ｓ₂₁，
Ｓ₂₂）。反転中（Ｍ＝１）かつＶ≦Ｙのとき、ＪからＸ
−１までを反転で計算するようＪをインクリメントしな
がらＴ_J をセットする（Ｔ_J ＝Ｂ_J −Ｍ＝Ｂ_J −１）。
また、反転中（Ｍ＋１）かつＶ＞Ｙのとき、ＪからＵ−
１までを反転で計算するよう、Ｊをインクリメントしな
がらＴ_J をセットし（Ｔ_J ＝Ｂ_J −１）、さらにＵから
Ｘ−１までを非反転で計算するよう、Ｊをインクリメン
トしながらＴ_Jをセットする（Ｔ_J ＝Ｂ_J ）（Ｓ₁₉，Ｓ
₂₃〜Ｓ₂₉）。そして最後にＴを出力する（Ｓ₃₀）。

【００２０】三値化二進計算回路１２におけるべき乗計
算の処理の流れを図４に示す。Ｔとｘとを入力し
（Ｓ₃₁）、Ｘをｘとし、Ｉを０とし、Ｙ及びＺをそれぞ
れ１とする（Ｓ₃₂）。Ｔ〔Ｉ〕が＋１の場合はＹ×Ｘを
Ｙとし（Ｓ₃₃，Ｓ₃₄）、Ｔ〔Ｉ〕が−１の場合はｚ×Ｘ
をＺとし（Ｓ₃₃，Ｓ₃₅，Ｓ₃₆）、Ｉがａ（ｎ）以下の間
はＴ〔Ｉ〕の値に無関係にＸ×ＸをＸとすると共にＩ＋
１をＩとしてステップＳ₃₃に戻る（Ｓ₃₇，Ｓ₃₈）。Ｉ＜
ａ（ｎ）でなくなると、Ｘ×Ｙ／Ｚを演算して計算結果
とする（Ｓ₃₉）。

【００２１】この処理を実行する三値化二進計算回路１
２の具体例を図５に示すように三値化二進数Ｔを入力
し、Ｔレジスタ１３に値を格納する。またｘを入力しＸ
レジスタ１４に格納する。以下、Ｔレジスタ１３を１桁
ずつ左シフトしながら処理を繰り返す。Ｔレジスタ１３
の最下位桁の内容によりスイッチ１５，１６が切替え制
御され、Ｔ₀ ＝−１で乗算器１７にＺレジスタ１８が接
続され、Ｔ₀ ＝１で乗算器１７にＹレジスタ１９が接続
される。乗算器２１は、Ｔレジスタ１３をシフトするご
とに、Ｘレジスタ１４の値を２乗してＸレジスタ１４に
格納する。乗算器１７は、Ｔ₀ ＝１の場合、Ｙレジスタ
１９の値にＸレジスタ１４の値を掛け込みその結果をＹ
レジスタ１９に格納し、また、Ｔ₀ ＝−１の場合にはＺ
レジスタ１８の値にＸレジスタ１４の値を掛け込み、そ
の結果をＺレジスタ１８に格納する。乗算器２２は、上
記の繰り返し処理の終了後Ｘレジスタ１４の内容とＹレ
ジスタ１９の内容とを乗ずる。乗算器２３は、乗算器２
２の結果をＺレジスタ１８の内容で割算する。

【００２２】ｘⁿ のべき乗計算における乗算と除算と
を、それぞれ加算と減算とに置き換えることによりｎｘ
の乗算を行うことができることが知られている。従って
図２、図３に示した三値化二進計算により、ｎの三値化
二進表現Ｔを求め、これを三値化二進計算によりｎｘを
計算するには、図６に示すようにすればよい。つまり図
４に示したべき乗計算の処理において、ステップＳ₃₂で
Ｙ＝０、Ｚ＝０とし、ステップＳ₃₄でＹ＋Ｘ＝Ｙとし、
ステップＳ₃₆でＺ＋Ｘ＝Ｚとし、ステップＳ₃₇でＸ＋Ｘ
＝Ｘとし、ステップＳ₃₈でＸ＋Ｙ−Ｚとすればよく、そ
の他は同一である。

【００２３】従ってこの処理を実行する三値化二進計算
回路の構成例は図７に示すようになる。つまり図５に示
したべき乗計算回路において、乗算器１７，２１，２２
の代りにそれぞれ加算器２４，２５，２６が用いられ、
除算器２３の代りに減算器２７が用いられる。Ｚレジス
タ１８及びＹレジスタ１９にはそれぞれ初期値として０
がセットされる。加算器２４はＴ₀ ＝−１でＸレジスタ
１４の値とＺレジスタ１８の値とを加算してその結果を
Ｚレジスタ１８に格納し、Ｔ＝１でＸレジスタ１４の値
とＹレジスタ１９の値とを加算し、その結果をＹレジス
タ１９に格納する。加算器２５はＸレジスタ１４の値を
２倍にしてその結果をＸレジスタ１４に格納する。加算
器２６はＸレジスタ１４の値とＹレジスタ１９の値とを
加算し、減算器２７は加算器２６の加算結果からＺレジ
スタ１８の値を減算し、その結果をｎｘとして出力す
る。

【００２４】

【発明の効果】この発明の装置は以下の場合に特に有効
である。 （１）三値化変換のコストに較べて、乗除算（または加
減算）のコストが大きい場合 （２）指数ｎが大きい数の場合 （３）指数ｎが定数であり、予め三値化変換のみを行な
うことができる場合 適応型バイナリ法、Ｍｏｒａｉｎ−Ｏｌｉｖｏｓ法、バ
イナリ法の演算回数をそれぞれｒ_O,ｒ_M,ｒ_B とするとａ
（ｎ）≦ｒ_O （ｎ）≦ｒ_M （ｎ）≦ｒ_B （ｎ）が成り立
つ。

【００２５】例として、ｎ＝４７（１０１１１１）₂ で
は、ｒ_O （４７）＝７，ｒ_M （４７）＝８，ｒ_B （４
７）＝９である。このとき適応型バイナリ法ではＴ＝
〔０，１，０，０，０，−１〕であり、Ｍｏｒａｉｎ−
Ｏｌｉｖｏｓ法の演算回数は適応型バイナリ法において
Ｔ＝〔１，−１，０，０，０，−１〕とした場合と等価
である。

【００２６】また、Ｍｏｒａｉｎ−Ｏｌｉｖｏｓの文献
にある例ｎ＝６７７５＝（１１０１００１１１０１１
１）₂ では、ｒ_O （６７７５）＝１７，ｒ_M （６７７
５）＝１８，ｒ_B （６７７５）＝２０である。適応型バ
イナリ法において、式（６）の適用は一区間のみでｊ＝
０，ｋ＝６となっている。よってＴ＝〔１，０，１，
０，１，０，０，０，−１，０，０，−１〕である。

【００２７】二進ｋ＋１桁のすべてのｎ（２^k ≦ｎ＜２
^k+1 ）のうち演算回数が最も少なくなるのはｎ＝２^k の
場合であり、ｋ＝ａ（ｎ）＝ｒ_O （ｎ）＝ｒ_M （ｎ）＝
ｒ_B（ｎ）である。またｒ_B は二項分布となる。ｋ＝１
６の場合の演算回数は、バイナリ法では最小１６，最大
３２，平均２４であり、適応型バイナリ法では最小１
６，最大２５，平均で約２１．７７となる。適応型バイ
ナリ法ではバイナリ法に比べ最大４４％（ｎ＝２¹⁶−１
のとき）、平均で約９．３％の速度向上ができる。

【図面の簡単な説明】

【図１】この発明の基本構成を示すブロック図。

【図２】三値化変換回路１１の処理の一例の前半を示す
流れ図。

【図３】図２の続きを示す流れ図。

【図４】この発明によるべき乗計算器における三値化二
進計算回路１２の処理の一例を示す流れ図。

【図５】図４に示した処理を実現するハードウェア構成
の例を示すブロック図。

【図６】この発明による乗算器における三値化二進計算
回路１２の処理の一例を示す流れ図。

【図７】図６に示した処理を実現するハードウェア構成
の例を示すブロック図。

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】 正の整数ｎおよびｘからｘⁿ を計算する
   べき乗計算器において、 ｎを入力してｎの二進表現の各ビットを順次得る手段
   と、そのビットの“０”と“１”の出現回数の差を順次
   計数する手段と、この差の値により反転状態と非反転状
   態との間の遷移を行なう手段と、その状態および“０”
   と“１”の出現回数の差により１，０，−１の列である
   三値化二進数Ｔを出力する手段とにより、ｎ＝２^a(n)＋
   Σ_i=0 ^a(n)Ｔ_i ・２ⁱ 、（Ｔ_i ∈｛−１，０，１｝，ａ
   （ｎ）＝〔ｌｏｇ₂ ｎ〕，ここで〔Ｂ〕はＢの小数点以
   下を切捨た整数を意味する）、となるＴ_i の組Ｔ＝〔Ｔ
   _a(n)，…，Ｔ_1,Ｔ₀ 〕のうち、Σ_i=0 ^a(n)｜Ｔ_i ｜が最
   小となる組合せを求める三値化変換回路と、 初期値としてｘが格納されるＸレジスタと、Ｘレジスタ
   の値を各ｉ回目ごとに２乗してＸレジスタに格納する２
   乗手段と、ともに初期値が１であるＹレジスタ及びＺレ
   ジスタと、ｉ回目の繰り返しで得られる上記Ｘレジスタ
   の値（ｘ² ) ⁱと、Ｔ_i に応じてＹレジスタ（Ｔ_i ＝１
   のとき) の値とを乗じてＹレジスタに格納し、またはＺ
   レジスタ（Ｔ_i ＝−１のとき) の値と乗じてＺレジスタ
   に格納する乗算手段と、繰り返しの終了後にＸレジスタ
   の値とＹレジスタの値とを乗じる手段と、その乗算結果
   をＺレジスタの値で除する手段とにより、ｘⁿ ＝（ｘ
   ² )^a(n)・Π_i=0 ^a(n)（（ｘ² ）ⁱ ）^Tiとなるｘⁿ を計
   算する三値化二進計算回路とを具備するべき乗計算器。
2. 【請求項２】 正の整数ｎおよびｘからｎ・ｘを計算す
   る乗算器において、ｎを入力してｎの二進表現の各ビッ
   トを順次得る手段と、そのビットの“０”と“１”の出
   現回数の差を順次計数する手段と、この差の値により反
   転状態と非反転状態との間の遷移を行う手段と、その状
   態および“０”と“１”の出現回数の差により１，０，
   −１の列である三値化二進数Ｔを出力する手段とによ
   り、ｎ＝２^a(n)＋Σ_i=0 ^a(n)Ｔ_i ・２ⁱ 、（Ｔ_i ∈｛−
   １，０，１｝，ａ（ｎ）＝〔ｌｏｇ₂ ｎ〕) 、となるＴ
   _i の組Ｔ＝〔Ｔ_a(n)，…，Ｔ₁ ，Ｔ₀ 〕のうち、Σ_i=0
   ^a(n)｜Ｔ_i ｜が最小となる組合せを求める三値化変換回
   路と、 初期値としてｘが格納されるＸレジスタと、そのＸレジ
   スタの値を各ｉ回目ごとに２倍してＸレジスタに格納す
   る２倍手段と、ともに初期値が０であるＹレジスタ及び
   Ｚレジスタと、ｉ回目の繰り返しで得られる上記Ｘレジ
   スタの値２ⁱ 、ｘと、Ｔ_i に応じてＹレジスタ（Ｔ_i ＝
   １のとき) の値とを加算してＹレジスタに格納し、また
   はＺレジスタ（Ｔ_i ＝−１のとき) の値とを加算してＺ
   レジスタに格納する加算手段と、繰り返しの終了後にＸ
   レジスタの値とＹレジスタの値とを加算する手段と、そ
   の加算結果からＺレジスタの値を減ずる手段とにより、
   ｎ・ｘ＝２^a(n)・ｘ＋Σ_i=0 ^a(n)Ｔ_i ・２ⁱ ・ｘとなる
   ｎ・ｘを計算する三値化二進計算回路とを具備する乗算
   器。