Facebook
Google
GitHub
Linkedin
Binary to BCD
- Thread starter Ian0
- Start date
How many binary bits you need to convert, signed or unsigned?
Does the MCU have integer divide?
What MCU are you usiing?
32 bits, on a cortex M4
If you write it in C to be easy to understand, and general for most use cases, without fancy coding tricks, the compiler optimization will make it close to best. Best is not always Best.
No shortage of memory?
A look-up table.
But, there're LUTs and then there're LUTs.
The fastest would be a true brute-force LUT with the BCD values for every possible integer of interest. For 16-bit, that would be 64K entries (I'm assuming you are only working with unsigned integers) with each entry being five BCD values (so three bytes, if they are packed), which may or may not be feasible. For 32-bit integers, it's hard to imagine it being feasible.
But you could partition this pretty easily to get a tradeoff between computational effort and LUT size.
Also, avoid doing division, but depending on your compiler (if you are writing in a high-level language), it may do that for you by converting your division (or remainder) by a constant divisor into a multiplication by the reciprocal. If your compiler doesn't do that, you can do it yourself in your source code.
This is how we did logarithms for real-time data processing back in the 90s.
The ROM table consumed most of the I960's memory map, but it sure was fast!
There are several way to represent BCD, e.g. "packed" which one's on your mind?
Not familiar with that processor.
When you do a 32 bit integer multiply, does it result in a 64-bit result stored in two registers?
Yes, the UMULL or SMULL instruction does that, but when it does division, it doesn’t give you quotient and remainder, just quotient, and it takes a multiply and subtract to get the remainder
I'm curious what might motivate the use of BCD anyway, on an MCU I mean. IBM instruction sets supported (well, still do) BCD arithmetic, that was motivated by business and support for stuff like COBOL.
BCD arithmetic is not hard actually, I just learned that, in C it's pretty simple, we add two four bit values, if the result exceeds 0F, we just add 6 then split the byte (assuming were not using packed BCD).
Of course that's more work than jus adding two registers!
BCD arithmetic is not hard actually, I just learned that, in C it's pretty simple, we add two four bit values, if the result exceeds 0F, we just add 6 then split the byte (assuming were not using packed BCD).
Of course that's more work than jus adding two registers!
Last edited:
OK, so printf does that already, as does sprintf et al. - %d
Last edited:
Have you ever looked at how heavy the footprint of printf() is?
There's a reason why many embedded libraries don't include it.
Yes. That's what started this all off. The program "evolved" and ended up with four different functions to display numbers in decimal in four different formats, and I decided it needed "tidying".
I spent some time working out exactly how double dabble worked, and realised that a processor with a barrel shifter does a better job. Now I've just become intrigued as to what is the best way of doing it (with no particular idea what "best" means).
After some thought, I realised that converting the fractional part of a fixed point binary number is considerably easier than converting the integer part. It just needs a multiply from which the integer part is output and the fractional part goes on to the next stage, and UMULL will do that for you, outputting the top 32 bits in one register and the bottom 32 bits in another.
Applying that to a 32-bit integer doesn't work, because what you get is the number as a decimal fraction of 2^32.
However, multiplying the original number by 2^64/10^9 normalises it, and it gives the correct output, but I've not yet tested whether that number is big enough to avoid an error in the LSB for all numbers. In which case an extra shift would be required (but it would only be required ONCE for the whole conversion, not for every digit)
[EDIT] dividing by 10^9 by multiplying by 2^m/10^9 (where m=64) is a magic number division, and the theory says that m>(32+log2(n)).
Log2 of 10^9 is 29.9, so it suggests m=62 ought to be good enough.
Applying that to a 32-bit integer doesn't work, because what you get is the number as a decimal fraction of 2^32.
However, multiplying the original number by 2^64/10^9 normalises it, and it gives the correct output, but I've not yet tested whether that number is big enough to avoid an error in the LSB for all numbers. In which case an extra shift would be required (but it would only be required ONCE for the whole conversion, not for every digit)
[EDIT] dividing by 10^9 by multiplying by 2^m/10^9 (where m=64) is a magic number division, and the theory says that m>(32+log2(n)).
Log2 of 10^9 is 29.9, so it suggests m=62 ought to be good enough.
Last edited:
