Xref: utzoo comp.lang.misc:6729 comp.sys.ibm.pc.misc:7013 comp.sources.wanted:15531
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uunet!mcsun!cernvax!chx400!chx400!bernina!neptune!inf.ethz.ch!brandis
From: brandis@inf.ethz.ch (Marc Brandis)
Newsgroups: comp.lang.misc,comp.sys.ibm.pc.misc,comp.sources.wanted
Subject: Re: Multiple-Precision Binary to ASCII Decimal Machine Languae Routine
Message-ID: <25716@neptune.inf.ethz.ch>
Date: 20 Feb 91 18:39:56 GMT
References: <1991Feb18.155207.24378@ux1.cso.uiuc.edu> <7565@uklirb.informatik.uni-kl.de>
Sender: news@neptune.inf.ethz.ch
Reply-To: brandis@inf.ethz.ch (Marc Brandis)
Organization: Departement Informatik, ETH, Zurich
Lines: 65

In article <7565@uklirb.informatik.uni-kl.de> kirchner@informatik.uni-kl.de (Reinhard Kirchner) writes:
>
>There is a very simple algorithm to convert binaries of arbitrary length
>to decimal WITHOUT division. I post it here since it may be of general
>interest.
>
>You need to arrays in storage, one for the decimal ( bcd ) number and one
>for the binary.
>
>    |---------------------------|-------------|
>          bcd                       binary
>
>Then you simply shift this whole thing to the left bitwise. So the bits
>from the binary cross the border to the bcd-part. And now the conversion-trick:
>
>if the rightmost digit in the bcd-part, the one where the binary bits go in,
>is >= 5, then add 3 to this digit. On the next shift this will result in a
>higher next digit.
>
>So you shift and perhaps add 64 times in the above case.
>

This would be a really great algorithm, but I do not see how it should work.
In fact, the first example I thought about did not work, so I present it here
as a counterexample.

Let us assume we just want to convert a 16-bit value N to its BCD 
representation. I choose N = 1280.

The binary representation of this is

	0000 0101 0000 0000	(spaces for readability)

and the BCD representation is

	0001 0010 1000 0000 .

After eight steps in the algorithm, we get the following picture.

	BCD part	  	      binary part
	0000 0000 0000 0101 | 0000 0000 0000 0000

Note that up to now, the case where 3 had to be added has never occured. Now,
the rightmost digit of the BCD part is 5, so we add 3 yielding:

        BCD part                      binary part
        0000 0000 0000 1000 | 0000 0000 0000 0000

Now, we continue shifting. Note that the case where the rightmost digit of
the BCD part is >= 5 will not occur any more, the digit is always zero. After
eight steps, the algorithm stops with

        BCD part                      binary part
        0000 1000 0000 0000 | 0000 0000 0000 0000

which is the BCD number 800.

I do not see how this algorithm can be made work, and I really doubt that it
can be done without a division at all. Does anybody know for sure?


Marc-Michael Brandis
Computer Systems Laboratory, ETH-Zentrum (Swiss Federal Institute of Technology)
CH-8092 Zurich, Switzerland
email: brandis@inf.ethz.ch