How the doubledabble algorithm works

[newomaster]

Okay, so a few people have asked me to make an explanation video on my youtube for this, so I did. I thought I would also post it here for the community as well.
My Video: https://www.youtube.com/watch?v=x8oPR61sdg0

The doubledabble algrorithm basically states: shift n times (n being bits in the binary starting number) if the total in any of the BCD digits is over 4, then add 3 before shifting again.

BCD number binary starting number
0000 0000 11111 starting number (31 in binary)
0000 0001 11110 First shift
0000 0011 11100 Second shift
0000 0111 11000 Third shift
0000 1010 11000 Ones digit was over 4, add 3 before shifting again.
0001 0101 10000 Fourth shift
0001 1000 10000 Ones digit was over 4, add 3 before shifting again.
0011 0001 00000 Fifth shift
answer: 0011 0001 or 31 (yay it worked)

[redstonewarrior]

Now, why it works :3 (W/O Video)
I think the easiest explanation is this:
Each shift operation does BCD multiplication by two. So for each digit, multiply it by two (shift), and if the result is over ten then carry. So you have a series of multiplications by two (in BCD format) and additions of one. By placing the increments properly (BCD adding one, a simple operation), you can end up with this where V is the final value and Ia is the ath element.)
V = I[/size]0 + 2* (I[/size]1 + 2 * ( I[/size]2 + 2* (...)))
And you end up with
V = I7 * 2^7 + I6 * 2^6 + I5 * 2^5 + I4 * 2^4 + I3 * 2^3 +I2 * 2^2 +I1 * 2^1 + I0 * 2^0, or the exact same value, but in BCD.
I hope that helps. :3

[fibonatic]

I was messing around with this, but I tried to generalize this method so it could be applied to any numeral system. So from binary to binary coded <numeral system>. However so far I have only been able to get it working for all the numeral systems with even base numbers:

The amount of bits to represent each digit equals: ceil(log2(base))
Edge from which you have to add a certain number to the value before shifting equals: base / 2
This is also way it only works for even base numbers.
The certain number which has to be conditionally added to the value equals: 2^(amount of bits - 1) - egde
So in terms of the base value: 2^(floor(log2(base))) - base / 2

For example base-12:
amount of bits per digit = ceil(log2(12)) = 4 (same amount as BCD)
Edge = 12 / 2 = 6
Add = 2^(floor(log2(12)) - 12 / 2 = 2

Lets start with the binary value 10100111001 (which equals 1337 in decimal)
0000 0000 0000 10100111001 start
0000 0000 0001 01001110010 First shift
0000 0000 0010 10011100100 Second shift
0000 0000 0101 00111001000 Third shift
0000 0000 1010 01110010000 Fourth shift
0000 0000 1100 01110010000 First digit is 6 or higher, add 2 before shifting.
0000 0001 1000 11100100000 Fifth shift
0000 0001 1010 11100100000 First digit is 6 or higher, add 2 before shifting.
0000 0011 0101 11001000000 Sixth shift
0000 0110 1011 10010000000 Seventh shift
0000 1000 1101 10010000000 First and second digit are 6 or higher, add 2 before shifting.
0001 0001 1011 00100000000 Eighth shift
0001 0001 1101 00100000000 First digit is 6 or higher, add 2 before shifting.
0010 0011 1010 01000000000 Ninth shift
0010 0011 1100 01000000000 First digit is 6 or higher, add 2 before shifting.
0100 0111 1000 10000000000 Tenth shift
0100 1001 1010 10000000000 First and second digit are 6 or higher, add 2 before shifting.
1001 0011 0101 00000000000 Eleventh shift
So 935 in base-12 should equal 1337 base-10 (or 10100111001 base-2)
Lets test this: 935 base-12 = 9 * 12^2 + 3 * 12^1 + 5 * 12^0 = 9 * 144 + 3 * 12 + 5 = 1337

By the way I was thinking about writing about this method on the ORE wiki, however all the current info is posted into one long page. Maybe we should restructurize this and divide into more manageable pages?

[redstonewarrior]

Been there, done that. A way of thinking about the even-base rule is that every shift, you will always end up with a zero in the lowest bit in a "cell." If you have an odd base, this is not necessarily true, and thus carries can propagate farther. For instance, in base five, 3 * 2 = 11. Definitely neat stuff to play with.

[Nickster258]

This is helpful, even to a person like me who already knows it. I learned it through a much harder to understand diagram, other than being that simple :3