🚀 go-pugleaf

こんにちは、パズル[バイナリ・サーチの高速化]の問題
を投稿した榛葉です。(^^)/    

ここから先の文は、正解とそれに関連するものですので、
解答を自分で考えたい人は、ここから先を読まないで下さい。
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
「匿名希望のＹ氏」から、メールにて即日正解答を頂きました。
どうも有り難うございます。

解答例は、「Ｙ氏」のものが分かりやすいので、引用いたします。

ここから------------------------------------------------------------
＜解答＞

>    a = (a / b) * b;
>    printf("a:%d, b:%d\n", a, b);

まずここで a を b の倍数に丸め、aの値として表示に使用しているため、
"aがbの倍数"の場合のみ考えればよい。また、bが0の場合は除外される。

sub()関数の内容
>    return (a & b & -b);
を  (a & (b & -b )) として考える。

まず、( b & -b ) であるが、 bのbitのうち'1'になっているbitの最下位の
ものに着目する。また、2の補数として"bit反転後1を加える"という操作を
考える。

1) これより下位のbitは b において'0'のため、'&' 時には全て'0'になる

bit反転時にこのbitは'0'になり、下位はすべて'1'になる。1を足した場合
繰り上がりはこのbitに及ぶが上位桁には達しない。したがって、

2) 2の補数を取った場合、このbitは常に'1'になる
3) これより上位のbitは'&'操作で相殺され、すべて'0'になる

すなわち、( b & -b )は、「b の中で'1'になっているbitのうち最下位のも
のだけが残る」操作である。

次に、(a & b & -b)では上記位置のbitしか残らないので、aのこの位置のbit
を中心にして考える。

1) a が b の 2倍の場合、このbitおよび下位のbitはすべて'0'である
2) a が b の偶数倍の場合、"bの2倍の和"であり、このbit以下はすべて
  '0'である
3) a が bの奇数倍の場合、2n + 1個の b の和と考えられ、従ってこの位置
  のbitは常に'1'である

したがって、sub()の戻り値は、「aがbの偶数倍のときは0、奇数倍のときは
bの'1'になっているbitのうち最下位のものだけが残る」数値である。

>    if (sub(a, b))
sub()の戻り値が0かそうでないかのみ判定しているため、
a が b の「奇数倍」か否かを判定している事になる。

答: 奇数倍
===========
-------------------------------------------------------------ここまで

パズル〔バイナリ・サーチの高速化〕は以下の特許が基になっています。

ここから------------------------------------------------------------
【発明の名称】  電子計算機における商の奇偶判定方法

【要約】
  【目的】  配列の中間要素の位置を高速に求める。
  【構成】  固定長２進整数の除算において、被除数と除数
と除数の２の補数の論理積を求め、それが０であれば除算の
商は偶数、０でなければ除算の商は奇数と判断する。
-------------------------------------------------------------ここまで

特許そのものは、パズルで示した範囲だけなのですが、特許内容に
使用例として以下のような、バイナリ・サーチのフロー・チャート
が載っていました。ただし、分かりやすくするために最適化はせず、
標準的な一例としたようです。

ここから------------------------------------------------------------
           +--------------------------------------------+                
           | レジスタ１←先頭要素の位置                 |～Ｓ１１        
           +--------------------------------------------+                
           | レジスタ２←末尾要素の位置                 |～Ｓ１２        
           +-----------------+--------------------------+                
     +--------------------→ |                    ～Ｓ１３               
     |     ------------------+----------------------   Yes             
     |  ＜   レジスタ１＝レジスタ２                  ＞------------------+  
     |     ------------------+----------------------                     | 
 +-→|                       | No                                        | 
 |   |     +-----------------+--------------------------+                |
 |   |     | レジスタ３←レジスタ２－レジスタ１         |～Ｓ１４        | 
 |   |     +--------------------------------------------+                |
 |   |     | レジスタ４←要素の長さの２の補数           |～Ｓ１５        |
 |   |     +--------------------------------------------+                |
 |   |     | レジスタ４←レジスタ４と要素の長さの論理積 |～Ｓ１６        |
 |   |     +--------------------------------------------+                |
 |   |     | レジスタ４←レジスタ４とレジスタ３の論理積 |～Ｓ１７        |
 |   |     +-----------------+--------------------------+                |
 |   |                       |                   ～Ｓ１８                | 
 |   |     ------------------+---------------------     Yes(偶数)        | 
 |   |  ＜            レジスタ４＝０                ＞---------------+   |
 |   |     ------------------+---------------------                  |   |
 |   |                       | No(奇数)                              |   |
 |   |     +-----------------+--------------------------+            |   |
 |   |     | レジスタ３←レジスタ３＋要素の長さ         |～Ｓ１９    |   |
 |   |     +-----------------+--------------------------+            |   |
 |   |                       |←-------------------------------------+   |
 |   |     +-----------------+---------------------------+               |
 |   |     | レジスタ３を１ビット右シフト                |～Ｓ２０       |
 |   |     +---------------------------------------------+               |
 |   |     | レジスタ３←レジスタ３＋レジスタ１          |～Ｓ２１       |
 |   |     +-----------------+---------------------------+               |
 |   |                       |                   ～Ｓ２２                |   
 |   |     ------------------+---------------------     Yes              |   
 |   |  ＜   レジスタ３の指す要素＞検査値           ＞----------------+  |   
 |   |     ------------------+---------------------                   |  |   
 |   |                       | No                                     |  |   
 |   |     +-----------------+---------------------------+            |  |   
 |   |     | レジスタ１←レジスタ３                      |～Ｓ２３    |  |   
 |   |     +-----------------+---------------------------+            |  |   
 |   |                       |                                        |  |   
 |   +-----------------------+                                        |  |   
 |                                                                    |  |   
 |                           ＋---------------------------------------+  |   
 |                           ↓                                          |   
 |         +-----------------＋--------------------------+               |   
 |         | レジスタ２←レジスタ３－要素の長さ          |～Ｓ２４       |   
 |         +-----------------＋--------------------------+               |   
 |                           ｜                                          |   
 +---------------------------＋                                          |   
                                                                         |   
                             ＋------------------------------------------+  
                             ↓                   ～Ｓ２５               
           ------------------＋---------------------     Yes         
        ＜   レジスタ１の指す要素＝検査値            ＞-------＋
           ------------------＋---------------------          ｜     
                             ↓ No                            ↓    
                       +-----＋-----+                     +---＋---+      
                       | アンマッチ |                     | マッチ |     
                       +------------+                     +--------+     
-------------------------------------------------------------ここまで

この一例が、バイナリ・サーチの高速化になっている理由ですが、

（１）論理演算の処理時間≦加算・減算の処理時間≦乗算・除算の処理時間。
（特にＲＩＳＣでは≦は＜）

（２）この一例のバイナリ・サーチでは、乗算・除算を使っていない。

（３）これまでのバイナリ・サーチでは、インデックスから配列の値を
求めるので、要素サイズが２のベキ乗で無い時に、アドレス計算時に、
乗算が使われる。

（４）パズルも特許も要素サイズになる被除数は２のベキ乗に限定されていない。

被除数が何でも良いのが特許提案者の自慢のようです。
何に応用するつもりかは不明です。

ついでに、性能の効果を示すプログラムの見本です。

ここから------------------------------------------------------------
#include <stdio.h>
#include <time.h>
long sub1(long a, long b){return ((a / b) & 1);}
long sub2(long a, long b){return (a & b & -b);}
void main() {long i;
    printf("time:%d\n", time(0));
    for (i = 0; i < 20000000; i++) sub1(300, 5);
    printf("time:%d\n", time(0));
    for (i = 0; i < 20000000; i++) sub2(300, 5);
    printf("time:%d\n", time(0));
}
-------------------------------------------------------------ここまで

それから、特許明細に関して「特許提案者」に、問い合わせて
見たのですが、以下の解答を頂く事が出来ました。

ここから------------------------------------------------------------
榛葉様、特許提案者の塚本です。  お問い合わせを戴き恐縮です。

  私の特許公報に基づいたパズルをニュースにアップしたとのことですが、
レスを戴いたというのは幸いなことです。

  私は、一応プロなので、この種のニュースは遠慮しています。けれども、
この特許案は公開済みなので、コメントして差し支えないと思います。

  「商の奇遇の判定」は近頃のＲＩＳＣ向けの処理方式として面白いと思い、
特許提案したものです。「バイナリ・サーチの高速化」は、効果より分かり
やすさを意図した実施例に過ぎません。但しＣ言語で配列を宣言して添字を
使う場合でもコンパイラはどこかでアドレスを計算することになります。
インデクス・レジスタを使える場合でも乗算が発生するとＲＩＳＣでは遅く
なる訳です。バイナリ・サーチの対象は要素数が多いのですから、キー長を
２のベキ乗にするようなメモリーの無駄使いは不味いのです。

  配列の中ほどを求めるものなら、ＱＵＩＣＫソートもありますね。

  良い応用例があったら教えて戴きたいと思います。

  昔は、このような方式は数学の公式の類とみなされ、特許を認められない
時代がありました。（年がバレそう。）  最近は電脳の特性を活かしたもの
なら良いという状況です。これが特許と認められるかはともかく、真面目な
電脳プログラムは全て特許の対象になり得ると考えています。

                                     塚本(CZR20071@niftyserve.or.jp)
------------------------------------------------------------ここまで

最後に、「Ｙ」さん、解答を頂きまして、大変感謝しております。
パズル作成者としては、解答を頂けました事を、大変光栄に思って
思っております。本当に有り難うございました。

                                                     1998-02-15(Sun)
--
****************************************************************  
早稲田大学 理工学研究科 物理学及応用物理学専攻 大谷研究室      
榛葉  理誠   SHINBA Masanobu  しんば まさのぶ                  
E-mail: simba@otani.phys.waseda.ac.jp, KFQ02005@niftyserve.or.jp 
URL: http://www.phys.waseda.ac.jp/otani/~simba/                
****************************************************************