## DoubleDabble Algorithm

Tips, Tricks and methods for programming, learn ways of making your programming life easier, and share your knowledge with others.

Moderators: Benj, Mods

mnf
Valued Contributor
Posts: 853
Joined: Wed May 31, 2017 11:57 am
Contact:

### DoubleDabble Algorithm

What a quiet day on the forums - I like to imagine everyone else is at a party.

I came across this algorithm by chance - it allows arbitrary bit length integers to be converted to a string (or BCD - binary coded decimal) - and as I had an hour to while away.

So Some Fun for Fans of Flowcode. Lovers of alliteration will have to look elsewhere.
double.fcfx
You can find details of the algorithm at https://en.wikipedia.org/wiki/Double_dabble - I've implemented it twice here - once that takes an array of bytes as a (possibly very) large integer (if you're working with public keys?) - and once where it takes a long (32bit) unsigned integer.

I was impressed that it converts an binary value to a decimal string without a single division (except one - that calculates an approximate number of characters in the resultant string) 'Main' here just runs lots of conversions for timing. ToString\$ is quicker for small integers but slower as the numbers get bigger (on AVR at least) - but if you want to work with larger integers (and who doesn't?) - then this would be good. Other MCUs mileage may vary depending on the efficiency of the divide instruction.

So - first a challenge - anyone like to create a string to binary conversion (that works for any length string?)
I've also left leading zeroes on the resultant string - an easy fix?

Second a gotcha (at least with the AVR compiler)
gotch.png
Here the first icon works - as expected but the second (which was the first I tried) doesn't

Code: Select all

``1 << (31 - .j)``
Only shifts a byte value left - not a 32 bit value (as I expected). I worked around it by tweaking the size of .j (which was unnecessary) and then by using a mask variable (32 bit - as in first icon). This doesn't seem to affect most C compilers - maybe someone could test with some different toolchains? A possible work around would be to allow '1L' or '1ul' which in C would define a long or unsigned long integer constant (but this doesn't currently work in FC)..

Enjoy!

Martin

Benj
Matrix Staff
Posts: 14929
Joined: Mon Oct 16, 2006 10:48 am
Location: Matrix TS Ltd
Contact:

### Re: DoubleDabble Algorithm

Thanks Martin,

Great post.
Here the first icon works - as expected but the second (which was the first I tried) doesn't
In C a shift of up to 16-bits is defined, over 16-bits it's up to the compiler creator on how this is implemented. Some compilers may be fine where as other simply won't work.

So if you just do this.

1 << (31 - .j)

Then the 1 will be cast as a 16-bit value. After 15 shifts the set bit will simply be lost.

To force the compilers hand you either have to cast the calculation to be 32-bit using C or you can use a temporary 32-bit variable to force the compilers hand.

Seems you are aware of the C casts, and you're right there currently isn't a nice clean way to do this.
A possible work around would be to allow '1L' or '1ul' which in C would define a long or unsigned long integer constant (but this doesn't currently work in FC)..

mnf
Valued Contributor
Posts: 853
Joined: Wed May 31, 2017 11:57 am
Contact:

### Re: DoubleDabble Algorithm

Thanks Ben,

I've seen that the algorithm reverses without problem so the string to binary is fairly straightforward too..

Martin

Oops - yes I meant WORD rather than BYTE...

mnf
Valued Contributor
Posts: 853
Joined: Wed May 31, 2017 11:57 am
Contact:

### Re: DoubleDabble Algorithm

So I did the reverse algorithm..

I tweaked my original to allow even bigger numbers (cos if big is good then bigger must be better).

Here it converts a 78 digit number (Fermat's 8th) into a 512 bit binary number and back to a string....

Now we just need some math functions (+,-,* and if you're feeling brave / and % ) I'll volunteer a x2 and /2 function (left and right shift by 1 bit)....
double.fcfx