🚀 go-pugleaf

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