The double-dabble bin-bcd conversion algorithm

I have just written the following small paper, which I expect to
eventually mount on my page together with C code to implement it. 
The point is that this is well suited for both conversion on a
system with no multiply or divide instructions, or on systems
which need to deal with very long binary numbers.  I have not
dealt with reversing the process, which can easily be done to
implement bcd-binary conversions.

Meanwhile I would like to hear criticisms as to clarity and
general readability, and other things I have not thought of.  I
expect to edit it accordingly.


________________________________________________________________
An Explanation of the Double-Dabble Bin-BCD conversion Algorithm
                      by C.B. Falconer.
================================================================                      

The algorithm starts from this description, shifting left, and
converting an 8 bit value to BCD.  If a prospective BCD digit is
five or larger, add three before shifting left.

  HUNDREDS     TENS      UNITS        BINARY
    0000       0000       0000       11111111   Start
    0000       0000       0001       11111110   Shift 1
    0000       0000       0011       11111100   Shift 2
    0000       0000       0111       11111000   Shift 3
    0000       0000       1010       11110000   ADD-3 to UNITS
    0000       0001       0101       11110000   Shift 4
    0000       0001       1000       11110000   ADD-3 to UNITS
    0000       0011       0001       11100000   Shift 5
    0000       0110       0011       11000000   Shift 6
    0000       1001       0011       11000000   ADD-3 to TENS
    0001       0010       0111       10000000   Shift 7
    0001       0010       1010       10000000   ADD-3 to UNITS
    0010       0101       0101       00000000   Shift 8
    
The rationale for the ADD-3 rule is that whenever the shifted
value is 10 or more the weight of that shifted out bit has been
reduced to 10 from 16.  To compensate, we add 1/2 that 6, or 3, 
before shifting.  We detect the 10 value after shifting by the
fact that the value before shifting is 5 or greater.  Notice 
that the rule ensures that the various digits cannot hold non-
BCD values.

The shifting is the double part of the algorithm.  The ADD-3 is
the dabble part.  It might be better named dabble-double.  Alas,
history has decreed otherwise.

Next, we modify to extract the lsd (least sig. digit) and divide
by 10, by adding a shift connection from the units high order 
bit to the binary low order bit.  We also mark the highest order
converted bit by x (for 0) and by X (for 1).

  HUNDREDS     TENS      UNITS        BINARY
    0000       0000       x000       11111111   Start
    0000       000x       0001       1111111x   Shift 1
    0000       00x0       0011       111111x0   Shift 2
    0000       0x00       0111       11111x00   Shift 3
    0000       0x00       1010       11111x00   ADD-3 to UNITS
    0000       x001       0101       1111x001   Shift 4
    0000       x001       1000       1111x001   ADD-3 to UNITS
    000x       0011       0001       111x0011   Shift 5
    00x0       0110       0011       11x00110   Shift 6
    00x0       1001       0011       11x00110   ADD-3 to TENS
    0x01       0010       0111       1x001100   Shift 7
    0x01       0010       1010       1x001100   ADD-3 to UNITS
    x010       0101      -0101       x0011001   Shift 8
                         |      <--         ^
                         v__________________|

Now, try it with a 10 bit number, and move the UNITS register
to the right of the BINARY register.  Since we no longer have a
TENS register we can't to the ADD-3 to it, but we leave it in
the annotations for future use.

      BINARY      UNITS  
     1111111111   x000   Start
     111111111x   0001   Shift 1
     11111111x0   0011   Shift 2
     1111111x00   0111   Shift 3
     1111111x00   1010   ADD-3 to UNITS
     111111x001   0101   Shift 4
     111111x001   1000   ADD-3 to UNITS
     11111x0011   0001   Shift 5
     1111x00110   0011   Shift 6
     1111x00110   0011   ADD-3 to TENS (dummy)
     111x001100   0111   Shift 7
     111x001100   1010   ADD-3 to UNITS
     11x0011001   0101   Shift 8
     11x0011001   1000   ADD-3 to UNITS
     1x00110011   0001   Shift 9
     x001100110   0011   Shift 10
     |         <--   ^
     v_______________|
     
The binary value has become 0x066 or 102 decimal.  The units 
digit is now 3, so the system has divided by 10 and extracted
the remainder.  The count of shifts is dictated by the length
of the binary register, or by when the 'x' marker reaches the
left hand bit of the binary register.  This is the point at
which all the original binary bits have been 'used'.

This is sufficient to do BCD conversions, extracting the least
significant digit in N operations from an N-bit binary.  By
repeating it for each digit we end up with roughly N/4 * N
operations for the complete conversion, or O(N*N).

The next version is identical, but we have broken the binary
register up into 4 bit groups.

   ----BINARY----
   THOU HUND TENS   UNITS  
     11 1111 1111   x000   Start
     11 1111 111x   0001   Shift 1
     11 1111 11x0   0011   Shift 2
     11 1111 1x00   0111   Shift 3
     11 1111 1x00   1010   ADD-3 to UNITS
     11 1111 x001   0101   Shift 4
     11 1111 x001   1000   ADD-3 to UNITS
     11 111x 0011   0001   Shift 5
     11 11x0 0110   0011   Shift 6
     11 11x0 0110   0011   ADD-3 to TENS (dummy)
     11 1x00 1100   0111   Shift 7
     11 1x00 1100   1010   ADD-3 to UNITS
     11 x001 1001   0101   Shift 8
     11 x001 1001   1000   ADD-3 to UNITS
     1x 0011 0011   0001   Shift 9
     x0 0110 0110   0011   Shift 10
     |           <--   ^
     v_________________|

Now alter the ADD-3 rule to say - Add 3 whenever the digit value
is 5 or more, AND the digit is entirely to the right of the x 
marker, inclusive.  Notice that the ADD-3 to TENS suddenly is
back in effect.  So are two new dabbles, marked by <-- below.

      ----BINARY----
INDEX THOU HUND TENS   UNITS  
  0     11 1111 1111   x000   Start
  1     11 1111 111x   0001   Shift 1
  2     11 1111 11x0   0011   Shift 2
  3     11 1111 1x00   0111   Shift 3
  4     11 1111 1x00   1010   ADD-3 to UNITS
  4     11 1111 x001   0101   Shift 4
  5     11 1111 x001   1000   ADD-3 to UNITS
  5     11 111x 0011   0001   Shift 5
  6     11 11x0 0110   0011   Shift 6
  7     11 11x0 1001   0011   ADD-3 to TENS (live)
  7     11 1x01 0010   0111   Shift 7
  8     11 1x01 0010   1010   ADD-3 to UNITS
  8     11 x010 0101   0101   Shift 8
  9     11 x010 0101   1000   ADD-3 to UNITS
  9     11 x010 1000   1000   ADD-3 to TENS  <--
  9     1x 0101 0001   0001   Shift 9
 10     1x 1000 0001   0001   ADD-3 to HUND  <--
 10     x1 0000 0010   0011   Shift 10
        |           <--   ^
        v_________________|

and we come out with the BCD conversion to 1023.  Notice that
all the "ADD-3"s are associated with the following shift.  The 
above has an INDEX column added to correspond.  Now we can see
when to energize the ADD-3s for each BCD column, in terms of 
the index value.  Units are available immediately, TENS after
4 or more, HUND after 8 or more, and we never can dabble the 
THOU column.  Looks like the rule there should be 12 or more.  
This bears a startling resemblance to (index DIV 4) indicating
a BCD digit.

Notice that the conversion has been done in place, with only 
one 4 bit BCD digit of auxiliary storage.  At some size of the
binary this will not be enough, but the solution is more zero
bits on the left of the binary value.  This increases the max
index value on conversion.

Since the various ADD-3s are limited to a single BCD digit, and 
they do not interact, they can all be done in parallel, and in
fact in parallel with the following shift operation.  This means
that converting an N bit value to BCD requires no more than N
operations, provided that N bit value has sufficient leading 
zero bits.  This is now O(N), which is a large improvement for
large binary numbers.

A purely software attack will probably not be able to do all the
ADD-3s in parallel, but in hardware this is simply a set of
gates in the shift path.

We can also, if convenient, think of the added units digit as 
being supplied by an initial 4 bit left rotary shift of the
binary register.

Problems with software implementation
=====================================

We can normally implement left shifts fairly easily in software,
with some complications to implement carrying bits across word
or octet boundaries.  This is probably simplified as much as
possible in C by using unsigned chars, and limiting their range
to 0..255.  Combined with a carry in and a carry out variable,
unlimited sized binary shifts can be handled.

A practical problem arises with the dabble portion.  We could
mask off each four bit section of an octet, compare the value to
5, and modify accordingly.  This is fairly computationally 
intensive.

Another possibility is to treat the octet as a whole, and pre-
prepare a translation table with 256 entries.  This should be
able to handle the whole octet in one operation.  However two
table will be needed, depending on whether or not the left
hand portion of the octet (see the x bit above) is to be
modified.

The byte sex of the binary values has to be settled, and it will
normally control the order of the BCD values that result.  It 
will usually be convenient for the most significant BCD digit to
appear in the lowest address, which in turn implies that the
most significant binary bit appears in the lowest address.  The
reverse is, of course, perfectly feasible.

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

CBFalconer wrote:

> I have just written the following small paper, which I expect to
> eventually mount on my page together with C code to implement it.
> The point is that this is well suited for both conversion on a
> system with no multiply or divide instructions, or on systems
> which need to deal with very long binary numbers.  I have not
> dealt with reversing the process, which can easily be done to
> implement bcd-binary conversions.
> 
> Meanwhile I would like to hear criticisms as to clarity and
> general readability, and other things I have not thought of.  I
> expect to edit it accordingly.

There you are ;-)
 
> The algorithm starts from this description, shifting left, and
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
???
I really don't know what you want to say here. I think my problem is
that I don't know what "*The* algorithm" and "*this* description"
means.

> converting an 8 bit value to BCD.  If a prospective BCD digit is
> five or larger, add three before shifting left.

[...]

> The rationale for the ADD-3 rule is that whenever the shifted
> value is 10 or more the weight of that shifted out bit has been
> reduced to 10 from 16.  To compensate, we add 1/2 that 6, or 3,
> before shifting.  We detect the 10 value after shifting by the
> fact that the value before shifting is 5 or greater.  Notice
> that the rule ensures that the various digits cannot hold non-
> BCD values.

I know the algorithm and understand why I works. However, I don't
think that it is trivial to everyone. Perhaps you should note that
the BCD number is doubled by the dabble-bouble.

You also should consider proving that the algorithm works by giving a
loop-invariant like:

BCD-number*256+BINARY = Initial-Binary*2^i (where i is a loop counter)
 
> The shifting is the double part of the algorithm.  The ADD-3 is
> the dabble part.  It might be better named dabble-double.  Alas,
> history has decreed otherwise.

I like this note about the name ;-)

> Next, we modify to extract the lsd (least sig. digit) and divide
> by 10, by adding a shift connection from the units high order
> bit to the binary low order bit.  We also mark the highest order
> converted bit by x (for 0) and by X (for 1).

[...}

If one has really unterstood the first variant this should be okay.

> Now, try it with a 10 bit number, and move the UNITS register
> to the right of the BINARY register.  Since we no longer have a
> TENS register we can't to the ADD-3 to it, but we leave it in
                         ^^ do?

> the annotations for future use.
> 
>       BINARY      UNITS
>      1111111111   x000   Start
>      111111111x   0001   Shift 1
>      11111111x0   0011   Shift 2
>      1111111x00   0111   Shift 3
>      1111111x00   1010   ADD-3 to UNITS
>      111111x001   0101   Shift 4
>      111111x001   1000   ADD-3 to UNITS
>      11111x0011   0001   Shift 5
>      1111x00110   0011   Shift 6
>      1111x00110   0011   ADD-3 to TENS (dummy)
What's that "dummy"-thing?
>      111x001100   0111   Shift 7
>      111x001100   1010   ADD-3 to UNITS
>      11x0011001   0101   Shift 8
>      11x0011001   1000   ADD-3 to UNITS
>      1x00110011   0001   Shift 9
>      x001100110   0011   Shift 10
>      |         <--   ^
>      v_______________|

[...]
>      11 11x0 0110   0011   ADD-3 to TENS (dummy)
see above.
[...]

> Notice that the conversion has been done in place, with only
> one 4 bit BCD digit of auxiliary storage.  At some size of the
> binary this will not be enough, but the solution is more zero
> bits on the left of the binary value.  This increases the max
> index value on conversion.
> 
> Since the various ADD-3s are limited to a single BCD digit, and
> they do not interact, they can all be done in parallel, and in
> fact in parallel with the following shift operation.  This means
> that converting an N bit value to BCD requires no more than N
> operations, provided that N bit value has sufficient leading
> zero bits.  This is now O(N), which is a large improvement for
> large binary numbers.

Actually, the number of bits needed to store the BCD-representation of
a N-bit binary number is O(N).
 
> A purely software attack will probably not be able to do all the
> ADD-3s in parallel, but in hardware this is simply a set of
> gates in the shift path.

I think you should mention the software vs. hardware thing earlier.
The (initial) simple double-dabble can already be implemented in O(N)
in hardware. The only improvement of the new algorithm is the
reduction of necessary registers by a constant factor.

Altogether, you seem a bit undetermined:
- What is your intended audience?
- Do you want to explain *how* the algorithms are implemented or *why*
they work?

/Jan-Hinnerk

PS: Despite all criticism, I was able to learn a few new things from
your paper ;-)

Jan-Hinnerk Reichert wrote:
> 
... various pertinant criticisms ...
> 
> Altogether, you seem a bit undetermined:
> - What is your intended audience?
> - Do you want to explain *how* the algorithms are implemented or
>   *why* they work?
> 
> /Jan-Hinnerk
> 
> PS: Despite all criticism, I was able to learn a few new things
> from your paper ;-)

Thank-you.  Your comments have been saved for a future revision.

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

Jan-Hinnerk Reichert schrieb:
> CBFalconer wrote:
> > Now, try it with a 10 bit number, and move the UNITS register
> > to the right of the BINARY register.  Since we no longer have a
> > TENS register we can't to the ADD-3 to it, but we leave it in
>                          ^^ do?
> 
> > the annotations for future use.

> >      1111x00110   0011   ADD-3 to TENS (dummy)
> What's that "dummy"-thing?

You even annotated the sentence where CBF wrote he'd leave it in; maybe
that spelling check blinded you to what the sentence said, because I
found that quite clear.

I sent my feedback to CBF by email.
Michael
-- 
Feel the stare of my burning hamster and stop smoking!

A quibble

The add three algorithm is just a way of doing BCD math on a binary
processor.
It's not an inherent part of double-dabble and If you've got a processor
that does BCD math you don't need it.
I learned double-dabble as a way of doing conversions on paper and
there's no reason you can't use double-dabble to convert binary to bases
other than ten 

CBFalconer <cbfalconer@yahoo.com> wrote in message news:<4054AA62.79308D46@yahoo.com>...
> I have just written the following small paper, which I expect to
> eventually mount on my page together with C code to implement it. 
> The point is that this is well suited for both conversion on a
> system with no multiply or divide instructions, or on systems
> which need to deal with very long binary numbers.  I have not
> dealt with reversing the process, which can easily be done to
> implement bcd-binary conversions.
> 
> Meanwhile I would like to hear criticisms as to clarity and
> general readability, and other things I have not thought of.  I
> expect to edit it accordingly.
> 
> 
> ________________________________________________________________
> An Explanation of the Double-Dabble Bin-BCD conversion Algorithm
>                       by C.B. Falconer.
> ================================================================                      
> 
> The algorithm starts from this description, shifting left, and
> converting an 8 bit value to BCD.  If a prospective BCD digit is
> five or larger, add three before shifting left.
> 
>   HUNDREDS     TENS      UNITS        BINARY
>     0000       0000       0000       11111111   Start
>     0000       0000       0001       11111110   Shift 1
>     0000       0000       0011       11111100   Shift 2
>     0000       0000       0111       11111000   Shift 3
>     0000       0000       1010       11110000   ADD-3 to UNITS
>     0000       0001       0101       11110000   Shift 4
>     0000       0001       1000       11110000   ADD-3 to UNITS
>     0000       0011       0001       11100000   Shift 5
>     0000       0110       0011       11000000   Shift 6
>     0000       1001       0011       11000000   ADD-3 to TENS
>     0001       0010       0111       10000000   Shift 7
>     0001       0010       1010       10000000   ADD-3 to UNITS
>     0010       0101       0101       00000000   Shift 8
>     
> The rationale for the ADD-3 rule is that whenever the shifted
> value is 10 or more the weight of that shifted out bit has been
> reduced to 10 from 16.  To compensate, we add 1/2 that 6, or 3, 
> before shifting.  We detect the 10 value after shifting by the
> fact that the value before shifting is 5 or greater.  Notice 
> that the rule ensures that the various digits cannot hold non-
> BCD values.
> 
> The shifting is the double part of the algorithm.  The ADD-3 is
> the dabble part.  It might be better named dabble-double.  Alas,
> history has decreed otherwise.
> 
> Next, we modify to extract the lsd (least sig. digit) and divide
> by 10, by adding a shift connection from the units high order 
> bit to the binary low order bit.  We also mark the highest order
> converted bit by x (for 0) and by X (for 1).
> 
>   HUNDREDS     TENS      UNITS        BINARY
>     0000       0000       x000       11111111   Start
>     0000       000x       0001       1111111x   Shift 1
>     0000       00x0       0011       111111x0   Shift 2
>     0000       0x00       0111       11111x00   Shift 3
>     0000       0x00       1010       11111x00   ADD-3 to UNITS
>     0000       x001       0101       1111x001   Shift 4
>     0000       x001       1000       1111x001   ADD-3 to UNITS
>     000x       0011       0001       111x0011   Shift 5
>     00x0       0110       0011       11x00110   Shift 6
>     00x0       1001       0011       11x00110   ADD-3 to TENS
>     0x01       0010       0111       1x001100   Shift 7
>     0x01       0010       1010       1x001100   ADD-3 to UNITS
>     x010       0101      -0101       x0011001   Shift 8
>                          |      <--         ^
>                          v__________________|
> 
> Now, try it with a 10 bit number, and move the UNITS register
> to the right of the BINARY register.  Since we no longer have a
> TENS register we can't to the ADD-3 to it, but we leave it in
> the annotations for future use.
> 
>       BINARY      UNITS  
>      1111111111   x000   Start
>      111111111x   0001   Shift 1
>      11111111x0   0011   Shift 2
>      1111111x00   0111   Shift 3
>      1111111x00   1010   ADD-3 to UNITS
>      111111x001   0101   Shift 4
>      111111x001   1000   ADD-3 to UNITS
>      11111x0011   0001   Shift 5
>      1111x00110   0011   Shift 6
>      1111x00110   0011   ADD-3 to TENS (dummy)
>      111x001100   0111   Shift 7
>      111x001100   1010   ADD-3 to UNITS
>      11x0011001   0101   Shift 8
>      11x0011001   1000   ADD-3 to UNITS
>      1x00110011   0001   Shift 9
>      x001100110   0011   Shift 10
>      |         <--   ^
>      v_______________|
>      
> The binary value has become 0x066 or 102 decimal.  The units 
> digit is now 3, so the system has divided by 10 and extracted
> the remainder.  The count of shifts is dictated by the length
> of the binary register, or by when the 'x' marker reaches the
> left hand bit of the binary register.  This is the point at
> which all the original binary bits have been 'used'.
> 
> This is sufficient to do BCD conversions, extracting the least
> significant digit in N operations from an N-bit binary.  By
> repeating it for each digit we end up with roughly N/4 * N
> operations for the complete conversion, or O(N*N).
> 
> The next version is identical, but we have broken the binary
> register up into 4 bit groups.
> 
>    ----BINARY----
>    THOU HUND TENS   UNITS  
>      11 1111 1111   x000   Start
>      11 1111 111x   0001   Shift 1
>      11 1111 11x0   0011   Shift 2
>      11 1111 1x00   0111   Shift 3
>      11 1111 1x00   1010   ADD-3 to UNITS
>      11 1111 x001   0101   Shift 4
>      11 1111 x001   1000   ADD-3 to UNITS
>      11 111x 0011   0001   Shift 5
>      11 11x0 0110   0011   Shift 6
>      11 11x0 0110   0011   ADD-3 to TENS (dummy)
>      11 1x00 1100   0111   Shift 7
>      11 1x00 1100   1010   ADD-3 to UNITS
>      11 x001 1001   0101   Shift 8
>      11 x001 1001   1000   ADD-3 to UNITS
>      1x 0011 0011   0001   Shift 9
>      x0 0110 0110   0011   Shift 10
>      |           <--   ^
>      v_________________|
> 
> Now alter the ADD-3 rule to say - Add 3 whenever the digit value
> is 5 or more, AND the digit is entirely to the right of the x 
> marker, inclusive.  Notice that the ADD-3 to TENS suddenly is
> back in effect.  So are two new dabbles, marked by <-- below.
> 
>       ----BINARY----
> INDEX THOU HUND TENS   UNITS  
>   0     11 1111 1111   x000   Start
>   1     11 1111 111x   0001   Shift 1
>   2     11 1111 11x0   0011   Shift 2
>   3     11 1111 1x00   0111   Shift 3
>   4     11 1111 1x00   1010   ADD-3 to UNITS
>   4     11 1111 x001   0101   Shift 4
>   5     11 1111 x001   1000   ADD-3 to UNITS
>   5     11 111x 0011   0001   Shift 5
>   6     11 11x0 0110   0011   Shift 6
>   7     11 11x0 1001   0011   ADD-3 to TENS (live)
>   7     11 1x01 0010   0111   Shift 7
>   8     11 1x01 0010   1010   ADD-3 to UNITS
>   8     11 x010 0101   0101   Shift 8
>   9     11 x010 0101   1000   ADD-3 to UNITS
>   9     11 x010 1000   1000   ADD-3 to TENS  <--
>   9     1x 0101 0001   0001   Shift 9
>  10     1x 1000 0001   0001   ADD-3 to HUND  <--
>  10     x1 0000 0010   0011   Shift 10
>         |           <--   ^
>         v_________________|
> 
> and we come out with the BCD conversion to 1023.  Notice that
> all the "ADD-3"s are associated with the following shift.  The 
> above has an INDEX column added to correspond.  Now we can see
> when to energize the ADD-3s for each BCD column, in terms of 
> the index value.  Units are available immediately, TENS after
> 4 or more, HUND after 8 or more, and we never can dabble the 
> THOU column.  Looks like the rule there should be 12 or more.  
> This bears a startling resemblance to (index DIV 4) indicating
> a BCD digit.
> 
> Notice that the conversion has been done in place, with only 
> one 4 bit BCD digit of auxiliary storage.  At some size of the
> binary this will not be enough, but the solution is more zero
> bits on the left of the binary value.  This increases the max
> index value on conversion.
> 
> Since the various ADD-3s are limited to a single BCD digit, and 
> they do not interact, they can all be done in parallel, and in
> fact in parallel with the following shift operation.  This means
> that converting an N bit value to BCD requires no more than N
> operations, provided that N bit value has sufficient leading 
> zero bits.  This is now O(N), which is a large improvement for
> large binary numbers.
> 
> A purely software attack will probably not be able to do all the
> ADD-3s in parallel, but in hardware this is simply a set of
> gates in the shift path.
> 
> We can also, if convenient, think of the added units digit as 
> being supplied by an initial 4 bit left rotary shift of the
> binary register.
> 
> Problems with software implementation
> =====================================
> 
> We can normally implement left shifts fairly easily in software,
> with some complications to implement carrying bits across word
> or octet boundaries.  This is probably simplified as much as
> possible in C by using unsigned chars, and limiting their range
> to 0..255.  Combined with a carry in and a carry out variable,
> unlimited sized binary shifts can be handled.
> 
> A practical problem arises with the dabble portion.  We could
> mask off each four bit section of an octet, compare the value to
> 5, and modify accordingly.  This is fairly computationally 
> intensive.
> 
> Another possibility is to treat the octet as a whole, and pre-
> prepare a translation table with 256 entries.  This should be
> able to handle the whole octet in one operation.  However two
> table will be needed, depending on whether or not the left
> hand portion of the octet (see the x bit above) is to be
> modified.
> 
> The byte sex of the binary values has to be settled, and it will
> normally control the order of the BCD values that result.  It 
> will usually be convenient for the most significant BCD digit to
> appear in the lowest address, which in turn implies that the
> most significant binary bit appears in the lowest address.  The
> reverse is, of course, perfectly feasible.

bogax wrote:
> 
> A quibble
> 
> The add three algorithm is just a way of doing BCD math on a
> binary processor.  It's not an inherent part of double-dabble
> and If you've got a processor that does BCD math you don't need
> it. I learned double-dabble as a way of doing conversions on
> paper and there's no reason you can't use double-dabble to
> convert binary to bases other than ten

Such things as the x86 DAA instruction are highly useful as
implementation tools, but they are not universally available.  BCD
math is generally not in favor for various reasons, including
memory usage, negation, incompatibility with C standards, etc.

Of course it can be used to convert to other bases.  In part, that
is why I pointed out the division by 10 functional byproduct. 
Even bases are much more convenient in general.

The system is most useful where multiplication and division are
not available primitives.

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

CBFalconer <cbfalconer@yahoo.com> writes:
> bogax wrote:
> > 
> > A quibble
> > 
> > The add three algorithm is just a way of doing BCD math on a
> > binary processor.  It's not an inherent part of double-dabble
> > and If you've got a processor that does BCD math you don't need
> > it. I learned double-dabble as a way of doing conversions on
> > paper and there's no reason you can't use double-dabble to
> > convert binary to bases other than ten
> 
> Such things as the x86 DAA instruction are highly useful as
> implementation tools, but they are not universally available.  BCD
> math is generally not in favor for various reasons, including
> memory usage, negation, incompatibility with C standards, etc.
> 
> Of course it can be used to convert to other bases.  In part, that
> is why I pointed out the division by 10 functional byproduct. 
> Even bases are much more convenient in general.
> 
> The system is most useful where multiplication and division are
> not available primitives.

Do you mean binary mul/div?

Does anyone have the answer to my question as to how BCD
mul/div are implemented on machines with a native BCD math
capability?