Text preview for : TIE6309-0164_1401binTblSrch.pdf part of IBM TIE6309-0164 1401binTblSrch IBM 140x TIE6309-0164_1401binTblSrch.pdf
Back to : TIE6309-0164_1401binTblSr | Home
ITEM NUMBER 6309-0164 (T. 1.1:.)
24 pages
DATE July 29, 1963
AUTHOR Edward C. Knapp, Jr.
TITLE TRUE BINARY TABLE SEARCH FOR THE IBM 1400 SERIES
SOURC]!: IBM CORPORATION
205 Whitney Avenue
New Haven, Connecticut
Thts paper Is In the author's original form.
The objectlve In provlding this copy h. to
keep you Informed In YOUl" field of Interest.
Please do not distribute this paper to persons
outside the IBM Company.
---_..------ ......... -- --------....--...--
IBM CONFIDENTIAL .....
DISTRIBUTED BY
6309 0164
'THE PROGRAM INFORMA TION DEPAR TMENT (TIE)
:lBM CORP.
11 Z EAST POST ROAD
'WlnTE PLAINS. NY
Table of Contents
Wny the True Binary Search is Needed 1
Theory of Binary Search 2
Binary Theory Applied to All Tables 6
Programming Example of Equal Search 8
Logic Diagram 9
Autocoder Program Segment 10
Bi.nary Search for Equal-High 11
Binary Search for Equal-Low 13
Tables in Descending Sequence 15
How to Construct the Subsidiary Tables 16
Conclusion 20
TITLE: True Binary Table Search
AUTHOR: Edward C. Knapp
DATE: July 24, 1963
DIRECT INQUIRIES TO: Edward C. Knapp
IBM Corporation
205 Whitney Avenue
New Haven 10, Connecticut
ABSTRACT: This paper describes a new
theory of a true binary table
search that may be used on any
size sequential table. Originally
developed for the IBM 1410, it is
most attractive on 1400 series and
other computers not equipped with
the table look-up feature. This
technique proves to be superior
in both speed and memory require-
ments to previously used programmed
table look -up routines.
[)f3- if
ytby the True Binary Search is Needed
It is a rare computer program which does not at some point search
through an ordered table or group of records to find a number or
name that matches some input. We are confronted with very
similar problems in looking up an electricity rate, sorting tape
records internally, converting codes, finding a disk record within
a blocked track, distributing charges to general ledger accounts,
or searching a symbol table.
Table look-up instructions with which some computers are equipped
generally provide a simple and efficient method of accomplishing
such searches. However, they require that certain rules be
observed, such a s the placement of word mark s, which may not
be desirable in all cases. Then too, the straight table look-up
becomes very time-consuming when directed at large tables or
when long functions must be interspersed between the table
arguments.
Computers such as the IBM 1401, 1440, 1460, and 1620 do not
po ssess any table look -up commands I but are frequently called
upon to perform these functions with whatever instructions are
available. Programmers usually take the most straight-forward
approach and search a table item by item by means of indexing or
address modification. This can be costly on large volume jobs
where the operation must be done repeatedly. Alternative methods,
used where timing is the main consideration, usually prove to be
rather complicated and tend to use a large amount of memory for
instructions.
The true binary search described in thi s paper was developed by
the author for use on the IBM 1410 in a situation where it was
impossible to include the word marks needed by the table look-up
instruction. However, its greatest application should prove to be
for the computers mentioned above which do not have table look-up
abi.lity. It will completely search any size sequential table or
group of records in a minimum number of comparisons, but does not
require a great deal of storage for the program itself. Once
understood, it is found to be quite straight-forward and easily
adapted to many table search operations.
-/-
Theory of Binary Search
Using a table that is either in ascending or descending sequence,
it is possible to compare a search argument against the center
table argument. If they are equal, the search is already finished.
Otherwise the result of the comparison tells in which half of the
table the desired argument may be found. A second comparison
at the center of one of the halves can further tell which quarter
of the original table might contain it. This procedure can be
repeated as long as it is possible to subdivide whatever portion
of the table remains.
Obviously a table that can be repeatedly divided in half until
only one logical entry is left must in itself be related to some
power of 2. It must in fact contain a total of entries equal to one
less than some power of 2 in order to simulate a "look-up equall1
operation and exactly some power of 2 far "look-up equal-high"
or "look-up equal-low." This distinction will be explained later
in this paper. For the moment we shall concentrate on the search
for equal only so that this topic may be followed through to
conclusion.
To illustrate the application of a binary table, let us refer to the
following sample table:
Position in
Table Argument Function
1 015 9463001
2 027 1004076
3 066 3472300
4 094 6875679
5 123 4221842
6 148 3884468
7 159 5123779
8 li77 6897212
9 200 2011897
10 251 3675774
11 283 2001480
12 694 7581531
13 733 0175000
14 746 6361792
15 999 *******
- 2 -
~/3~~
The table consists of 15 entries in ascending sequence. Each
entry contains ten digits three for the argument which is the
I
field against which we must make our comparisons and seven
for the function. The other element of our problem is the searc.h
argument which must match exactly with one of the table arguments.
The obj eet of the search is I of course I to extract the function from
the table which lies to the right of the matching table argument.
To search this table by the binary method the program must
I
compare the search argument against the table argument of the
eighth entry. If an equal condition results the desired item
I
has been found and the search terminates. H-owever, if the search
argument is low, the item must be among entries 1 - 7 of the
table, and if high, it has to be in the upper seven entrie s (9 - 15).
The next comparison is made on the item which is the next lower
power of two entries away from the previously compared item.
Thus I we must look at entry 4 (low) or entry 12 (high). Succes sive
comparisons are then made which always reduce the number of
pas sibilitie s by half until only one entry remains. If that entry
is not equal to the search argument, it means that the argument is
not in the table.
The course taken by the search is best demonstrated by using
an actual input argument such as 123. This is initially compared
against item #8 (177) and found to be low. The next comparison
against the center item of the lower half of the table item #4
I
(094) results in a high condition caus:Lng the search to move
I
upward to item #6 (148). The low indication at this point means
that only one pos sibility remains item #5 (123) which in this
I I
ca se satisfies the equal condition desired.
Had the input search argument been a number like 105 which doe s
not exist in the table the program would have followed the same
I
course, but would have given a low result on the final comparison.
Since it had previously been found to be higher than item #4, this
low result means that the search argument falls somewhere
between items #4 and #5.
- 3 -
To completely search a 15 item table such as the one on the
previous page requires a maximum of only four comparisons. Note
that the average number of comparisons is somewhat below this
because if an equal condition results at some earlier point I no
further comparisons are necessary.
It is easy to see that as a binary table increases in size to one
item less than higher powers of 2 I the number of comparisons
needed for a complete search beComes lower in relation to the
size of the table. Thus the following numbers of iterations are
all that are needed for various larger tables:
No. of Items Maximum No. of
In Table Comparisons
31 5
63 6
127 7
255 8
511 9
1023 10
The essential value of the binary table lies in the fact that it is
perfectly symmetrical. Each successive comparison must move
to a point higher or lower on the table which is exactly half the
distance travelled by the previous comparison. When this
di stance ha s been reduced to the length of one item I the search
is completed.
This type of table organization lends itself to computer programming
in that a simple loop containing just one compare instruction,
one of whose addresses is continually modified by the lengths
noted above, can perform the whole search. The key to this
loop is a small subsidiary table of values containing an entry
for each iteration needed equal to the amount the table address
to be compared against mu st be incremented or decremented at
that point of the search. It must terminate with some indicator
which tells the program that the last iteration ha s been completed.
For the IS-item table described above the subsidiary table would
look like this:
- 4 -
4XL 40
2XL = 20
lXL = 10
End = **
L equals the length of the table argument plus the function which
total 10 digits in the example. After the initial comparison has
been made at the table's center / the value 40 is added to the
compare address if the result were high and subtracted if low.
In this manner the programmed loop can accomplish the search
described previously. The program is actually controlled by the
subsidiary table which means that m rely by changing its values
the same program can operate on tables with different sized
entries or, by adding more values at the beginning (80/160, etc.),
upon larger binary table s.
;-...7~- /L.t v I / 2.. S~ b s. ,j l <:YJ t!;"Jks <';r-~ "'- 4-
VoI.,I" t~ /tl( (!"' ..... l"k ... .,,1:. (.-'1 1<) q V., ~~."4",7f- s"" J. &,~t- .e. . .
- 5 -
Binary Theory.Applied to All Tables
At this point the reader may be wondering what practical applica-
tion the binary search can have I since it appears to require tables
of only certain sizes which of course are not often found in
actual practice. The salient fact here is that any sequential table
of any size can be thought of as beinq made up