Talk:Double dabble

Isn't n + 4n / 3 just 7n/3.. Is it -n or n...the dash before the formula is confusing.

Verilog Code Error?

Is it just me or is there an error in the Verilog code? The output port should be

output reg [W+(W-4)/3:0] bcd

should it not? As it is right now, the code wouldn't compile. Chessplayer dude (talk) 05:25, 1 June 2022 (UTC)

I confirmed with simulation that there is an error in the Verilog code. The code you showed is correct, and it is the same as the code in the github source. I made the change to the code. Toollica (talk) 20:47, 8 October 2022 (UTC)

double dabble after a binary point

I just found out how to use double dabble after a binary point: You simply invert the algorithm. Start with the rightmost (least significant) bit, and proceed to the left, towards the binary point. If, in the current final digit, bit 0 is set, the bit will get shifted out in the current iteration, so create a new 0 digit to the right as the new final digit. Then proceed over all digits (from right to left), shifting bits to the right, propagating borrows: If bit 0 is set in the previous digit, OR 8 into the current digit, then shift the previous digit 1 bit to the right, and so on. In the first digit, set bit 3 (=8) as the input bit. Then proceed over all digits and SUBTRACT 3 where a digit is greater than 4. That's all!! Brought to you as a thank you to the author of this article who helped me solve a problem I had for a long time! 79.227.181.141 (talk) 06:18, 11 March 2012 (UTC)

Optimizations

While coding Double Dabble I noticed some optimizations. I don't know if this is "new research" or in the references, so didn't include it in the main article. First, the most significant BCD digit need not ever be tested for "if > 4 add 3". It will never be > 4 before the last shift. It can't lead to a carry into a more significant BCD digit. Second, the first 3 shifts won't ever have an "add 3" step before them since it takes at least 3 shifts to get a value > 4 into the least significant BCD digit. This means the BCD 1s digit can actually be considered as 3 more significant input binary value bits before the algorithm ever begins. For example the 8-bit binary input, 3 BCD digit, 8 shifts algorithm will actually convert up to 999 (hex 3E7), not just 255 (hex FF), being limited only by the 3 BCD digits. To convert 999, start with the BCD 1s digit set to 3 (the MS byte of input value hex 3E7) and the input byte set to E7. Now do 8 iterations of "if any BCD digit is > 4 add 3, then shift". To extend even further, if space for another BCD digit is added (4 BCD digits plus an 8-bit LS-input byte), the input range is extended to hex 7FF (decimal 2047). (Rick314 (talk) 23:26, 10 January 2015 (UTC))

Relationship to 6502 patent?

I was looking for a "See also" link for the algorithm used by the 6502. The patent documents (US3991307) are probably a lot easier than looking at Visual6502!  ;)

If no one adds this content to the 6502 document and links to it here, I'll probably do it later. 192.153.23.101 (talk) 00:15, 11 March 2018 (UTC)

A simple C implemenation for up to 8 decimal digits.

Uses parallel bit-twiddling to propagate the carries quickly

long bin2BCD(long bin) { // double dabble
  long bit = 0x4000000; // 8 decimal digits 99999999 MSB
  long bcd = 0;
  long carry = 0;

  if (!bin) 
    return 0;
  while (!(bin & bit)) bit >>= 1; // quickly skip to MSB

  while (1) {
    bcd <<= 1;
    bcd += carry; // carry to next BCD digit ( 10 + 6 = 16 = LSB of next BCD digit)
    if (bit & bin) bcd |= 1;
    if (!(bit >>= 1)) 
      return bcd;
    carry = ((bcd + 0x33333333) & 0x88888888) >> 1; // carries: 8s -> 4s
    carry += carry >> 1; // carries -> 6s
  }
}

References