Click here to Skip to main content
12,402,666 members (75,440 online)
Click here to Skip to main content
Add your own
alternative version

Stats

11.2K views
6 bookmarked
Posted

Bracketing Binary Chop in COBOL

, 18 Jun 2010 CC (ASA 2.5)
Rate this:
Please Sign up or sign in to vote.
COBOL already has SEARCH ALL, but what if you want to find table values which bracket a searched value - here is the solution.

Introduction

Binary Chop (binary search) is a really fast way of searching a sorted table. Here is a simple example of how to do it with Visual COBOL.

How many steps does it take to find where a number fits in an ordered series of one hundred million numbers? The answer is around 26!

This illustrates how picking the correct algorithm for a problem makes all the difference. The problem I want to illustrate here is finding which two numbers in a table 'bracket' a third number. Consider that I have a table with the numbers 0 10 20 30 in it, then 15 is bracketed by 10 and 20.

Because I am not actually looking for a number in the table itself, I cannot use an index. Just searching from one end of the table to the other could be very expensive. In the example of a 100 000 000 element table - it could take more then one hundred million steps.

However, if my tabled is sorted (see Declarative Sorting in COBOL), I can use the binary chop search algorithm. So here it is in COBOL:

identification division.
program-id. BinaryChop.

environment division.
configuration section.

data division.
working-storage section.
01 to-find    binary-long occurs 100000000.
01 bl-1       binary-long.
01 bl-2       binary-long.
01 ln         binary-long.
01 look-4     binary-long.
01 found-prev binary-long.
01 found-next binary-long.
01 chop-pt    binary-long.
01 chop-ln    binary-long.
01 chop-ofst  binary-long.

procedure division.

   move 100000000 to ln
   perform varying bl-1 from 1 by 1 until bl-1 > ln
       compute bl-2 = bl-1 * 3
       move bl-2 to to-find(bl-1)
   end-perform
   
   move 428201 to look-4
   perform binary-chop
   
   display "Prev=" to-find(found-prev) " "
           "Next=" to-find(found-next)
   goback.
   
   binary-chop section.
   compute chop-ln = ln / 2
   compute chop-pt = chop-ln
   display "Start point: " chop-pt
   move -1 to found-prev found-next 
   perform until found-prev not = -1
           
       compute chop-ofst = chop-pt - 1
       *> Off the start
       if chop-ofst = 0
           move 0  to found-prev
           move 1  to found-next
           exit perform
       end-if
       *> found to left
       if  to-find(chop-ofst) <= look-4 
       and to-find(chop-pt)   >= look-4
           move chop-pt   to found-next
           move chop-ofst to found-prev
           exit perform
       end-if
       
       compute chop-ofst = chop-pt + 1
       *> Off the end
       if chop-ofst > ln
           move 0           to found-next
           move to-find(ln) to found-prev
           exit perform
       end-if
       *> found to right
       if  to-find(chop-ofst) >= look-4 
       and to-find(chop-pt)   <= look-4
           move chop-pt   to found-prev
           move chop-ofst to found-next
           exit perform
       end-if

       *> not found - go again
       compute chop-ln = chop-ln / 2
       if chop-ln = 0
           move 1 to chop-ln
       end-if
       display "New chop-ln: " chop-ln
       if to-find(chop-pt) < look-4
           add chop-ln      to chop-pt
       else
           subtract chop-ln from chop-pt
       end-if
       display "New chop-pt: " chop-pt
   end-perform
   .
   
end program BinaryChop.

Running the above program in Visual COBOL (COBOL for Visual Studio - see here) produces the following output:

Start point: +0050000000
New chop-ln: +0025000000
New chop-pt: +0025000000
New chop-ln: +0012500000
New chop-pt: +0012500000
New chop-ln: +0006250000
New chop-pt: +0006250000
New chop-ln: +0003125000
New chop-pt: +0003125000
New chop-ln: +0001562500
New chop-pt: +0001562500
New chop-ln: +0000781250
New chop-pt: +0000781250
New chop-ln: +0000390625
New chop-pt: +0000390625
New chop-ln: +0000195312
New chop-pt: +0000195313
New chop-ln: +0000097656
New chop-pt: +0000097657
New chop-ln: +0000048828
New chop-pt: +0000146485
New chop-ln: +0000024414
New chop-pt: +0000122071
New chop-ln: +0000012207
New chop-pt: +0000134278
New chop-ln: +0000006103
New chop-pt: +0000140381
New chop-ln: +0000003051
New chop-pt: +0000143432
New chop-ln: +0000001525
New chop-pt: +0000141907
New chop-ln: +0000000762
New chop-pt: +0000142669
New chop-ln: +0000000381
New chop-pt: +0000143050
New chop-ln: +0000000190
New chop-pt: +0000142860
New chop-ln: +0000000095
New chop-pt: +0000142765
New chop-ln: +0000000047
New chop-pt: +0000142718
New chop-ln: +0000000023
New chop-pt: +0000142741
New chop-ln: +0000000011
New chop-pt: +0000142730
New chop-ln: +0000000005
New chop-pt: +0000142735
New chop-ln: +0000000002
New chop-pt: +0000142733
Prev=+0000428199 Next=+0000428202

Which is to say that it has found the bracketing elements out of a table with more elements than there are humans in Britain, is quite impressive! The algorithm functions by splitting the table in half and asking the question - is my number in the bottom (left) half or the top (right) half. It then picks the appropriate sub-table and repeats the process. By so doing, it repeatedly divides the problem size by 2 until the solution is found. Because we are working with integers, there needs to be a trap to avoid the table size going to zero:

compute chop-ln = chop-ln / 2
if chop-ln = 0
   move 1 to chop-ln
end-if

Along with this, there are two traps to detect if the number looked for is above or below the range of the table:

*> Off the start
if chop-ofst = 0
   move 0  to found-prev
   move 1  to found-next
   exit perform
end-if
*> Off the end
if chop-ofst > ln
   move 0           to found-next
   move to-find(ln) to found-prev
   exit perform
end-if

All the other algorithm exit conditions are where the bracketing numbers are found:

*> found to left
if  to-find(chop-ofst) <= look-4 
and to-find(chop-pt)   >= look-4
   move chop-pt   to found-next
   move chop-ofst to found-prev
   exit perform
end-if
*> found to right
if  to-find(chop-ofst) >= look-4 
and to-find(chop-pt)   <= look-4
   move chop-pt   to found-prev
   move chop-ofst to found-next
   exit perform
end-if

Finally, we just need the code to work out which sub-table (left or right) to look in next:

if to-find(chop-pt) < look-4
   add chop-ln      to chop-pt
else
   subtract chop-ln from chop-pt
end-if

License

This article, along with any associated source code and files, is licensed under The Creative Commons Attribution-ShareAlike 2.5 License

Share

About the Author

alex turner
Web Developer
United Kingdom United Kingdom
I am now a Software Systems Developer - Senior Principal at Micro Focus Plc. I am honoured to work in a team developing new compiler and runtime technology for Micro Focus.

My past includes a Ph.D. in computational quantum mechanics, software consultancy and several/various software development and architecture positions.

For more - see

blog: http://nerds-central.blogspot.com

twitter: http://twitter.com/alexturner

You may also be interested in...

Comments and Discussions

 
GeneralCOBOL - How Quaint ! Pin
Dave Cross18-Jun-10 1:22
memberDave Cross18-Jun-10 1:22 
GeneralVisual COBOL Pin
alex turner18-Jun-10 0:40
memberalex turner18-Jun-10 0:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160721.1 | Last Updated 18 Jun 2010
Article Copyright 2010 by alex turner
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid