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
Valued Contributor
Posts: 507
Joined: Wed May 31, 2017 11:57 am
Has thanked: 52 times
Been thanked: 279 times
Contact:

DoubleDabble Algorithm

Postby mnf » Sun Sep 23, 2018 7:38 pm

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
(23.23 KiB) Downloaded 52 times

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
gotch.png (10.15 KiB) Viewed 1307 times


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
These users thanked the author mnf for the post (total 3):
Steve (Mon Sep 24, 2018 3:46 pm) • Benj (Tue Sep 25, 2018 12:48 pm) • jgu1 (Sat Sep 29, 2018 4:14 pm)
Rating: 15.79%
 

User avatar
Benj
Matrix Staff
Posts: 14223
Joined: Mon Oct 16, 2006 10:48 am
Location: Matrix TS Ltd
Has thanked: 4363 times
Been thanked: 4096 times
Contact:

Re: DoubleDabble Algorithm

Postby Benj » Tue Sep 25, 2018 12:54 pm

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)..
These users thanked the author Benj for the post (total 2):
mnf (Tue Sep 25, 2018 10:09 pm) • jgu1 (Sat Sep 29, 2018 4:14 pm)
Rating: 10.53%
 

mnf
Valued Contributor
Valued Contributor
Posts: 507
Joined: Wed May 31, 2017 11:57 am
Has thanked: 52 times
Been thanked: 279 times
Contact:

Re: DoubleDabble Algorithm

Postby mnf » Tue Sep 25, 2018 10:09 pm

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
Valued Contributor
Posts: 507
Joined: Wed May 31, 2017 11:57 am
Has thanked: 52 times
Been thanked: 279 times
Contact:

Re: DoubleDabble Algorithm

Postby mnf » Fri Sep 28, 2018 9:50 pm

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
(28.9 KiB) Downloaded 52 times


Note that StringToBin destroys the input string.. If you'd rather it didn't then edit the macro details and check 'Make a local copy' for the string. This does what it says - but note that you need to also alter the string definition to be as large as you'll need (s[80] in the example here). I left it unticked to 1) save memory 2) for a little extra speed. Thinking about this - DoubleDabble also clears the input binary number - but because I pass it as an array of bytes there is no option to make a local copy (and this might be ok - obviously you'll only convert to a string when the math is done :? ). One fix might be just to pass it in as a string (which is just an array of bytes) - another would be to make a local copy using a 'buffer' variable in the macro - although this would need to be large enough to handle any eventuality (and given the complete lack of bounds checking in my code this might be a suitable approach). Another might be to have a play with malloc / free in a C block (which I'd kinda been looking for an excuse to try)

Just got an 'increment' function to work - will post when 'decrement' works as well.

Martin
These users thanked the author mnf for the post (total 2):
jgu1 (Sat Sep 29, 2018 4:14 pm) • Benj (Mon Oct 01, 2018 10:18 am)
Rating: 10.53%