Oppolzer - Informatik / Blog

Some hours after I posted this, I got the impressions that it might be better to
explain some of the hidden secrets that may be still in this code.

First, the key field is in the records of the table at offset 3, that is the
reason, why the compares with the search argument SUCHARG are done with 3(R7).
The length of the compare is derived from the definition of SUCHARG, and the
type of the compare is CLC or CP; the Structured Programming macro IF selects
the machine instruction depending on the definition of SUCHARG.

Then, as you can see, the IF has two conditions, separated by an asterisk; if
the first condition is true, then control goes to the first THEN, if the second
condition is true, then control goes to the second THEN, otherwise to the ELSE.
This is in fact not a simple IF statement - looks more like SELECT ... WHEN ...
OTHERWISE.

The SP macros are home grown ... originally bought from another company in the
early 70s, IIRC - long gone history. It's part of my job to keep them running;
I'm working as a free lancer for this company since 1988.

The rest should be self explaining ... I hope.

To generalize this example (for example, to put it into a macro), it is only
necessary to parameterize some pieces of the code, that is:

- the number of the elements on entry
- the size of one element which is multiplied to the index
- the position of the key field
- the length of the key field (which goes into the compare instruction)
- and maybe the type of the compare instruction

To further generalize it, the compare instruction should be a function call ...

Kind regards

Bernd



Am 26.10.2013 10:54, schrieb Bernd Oppolzer:
> This is not necessary, and the binary search code is not at all
> complicated.
>
> Look at this:
>
>          MVI   GEFUNDEN,C'0'
>          LH    R4,=H'1'
>          L     R5,EINGANZ
> *
>          XR    R9,R9 DURCHLAUFZAEHLER = 0
> *
>          LOOP WHILE,((R4),<=,(R5))
>          AHI   R9,1
> *                               MITTE DER RESTL. ELEMENTE ERMITTELN
>          LA    R6,0(R4,R5)                R5+R4->R6 (ANZ. ELEMENTE)
>          SRA   R6,1                       DURCH 2 DIVIDIEREN
>          LR    R7,R6
>          BCTR  R7,0
>          MH    R7,=Y(L'ESATZ)
>          AR    R7,R3                      TATSAECHL. ADR. MITTE
>          IF   (SUCHARG,<,3(R7)),*,(SUCHARG,>,3(R7))
> *
>          THEN
>          LR    R5,R6                      GROESSER, WEITERSUCHEN
>          BCTR  R5,0
> *
>          THEN
>          LA    R4,1(R6)                   KLEINER, WEITERSUCHEN
> *
>          ELSE
>          MVI   GEFUNDEN,C'1'
>          BREAK
> *
>          EIF
>          ELOOP
>
>
> R3 - points at the start of the sorted table at the beginning
> R4 - index, starting from 1, of the lower limit of the range to be
> examined
> R5 - upper limit, is initialized with EINGANZ at the beginning
> R6 - is used to compute the index "in the middle"
> R7 - is used to compute the address of the element "in the middle"
>
> then the element in the middle is compared against SUCHARG,
> depending on the result, R4 and R5 are adjusted, and the LOOP is
> executed again, if necessary.
>
> if not, you have a result (found or not).
>
> R9 is used to count the loop executions, which will be floor(log2(n)),
> where n is the number of elements in the vector (in the worst case).
>
> At our shop, we have a macro which does this. No need to code
> the binary search yourself every time you need it.
>
> Kind regards
>
> Bernd
>
>
>
> Am 21.10.2013 22:49, schrieb R.R.:
>> At 06:27 -0700 on 10/21/2013, R.M. wrote about Re:
>> Linear search vs binary:
>>
>>> If your search target is uniformly distributed against the key, then on
>>> average a linear search will require 1750 iterations of your compare
>>> loop.
>>> A binary search will require a constant 12 iterations regardless of
>>> distribution.
>>
>> One trick that would make the binary search code simpler is to make
>> the table 4096 entries long not 3500 long. Place 298 low value
>> entries, then the 3500 live entries, and then 298 high values. This
>> will cause some wasted compares when you hit the padding low/high
>> values but you do not need to worry about how to spit the table in
>> half for each round (the size is always the prior power of 2).
>>
>