AVR Freaks

Given a half-decent FPGA, it could process every bit in parallel, thus one cycle (with some daisy-chained LUTs, but still - a fistful of nanoseconds).  The output's only 20 bits.  At this point the speed limit is "How fast can you get the input data out of the AVR".  S.

Ok FPGA's are getting bigger  but I don't think you can get one that can hold everything in 1 clk.

but 3 clk is possible.

if the speed is 1GHz that would be about 300MHz output speed.

But 50-100MHz output speed would be realistic to make. 

I was thinking the way OP splved it

Then we need to define a gate, (normally 2 input NAND), and for speed one level deep, (or one LUT deep), but with 16 inputs it's a bigger than gate.

But if it's just one big LUT then it would be better with ROM(FLASH) 16 bit addr. and 20 bit out. or 192k flash so even a big AVR could solve that. So that would be about 2MHz output, (useless unless data in and/or out are moved via DMA).

One of my more fundamental assumptions here is that there is absolutely no reason to convert to BCD except for display, so there never is any reason to read the output of the LUT back into the AVR, and the resulting BCD must be sent out.  That given:

Writing out two bytes hex is by definition faster than writing out three bytes packed BCD (not even considering the AVR's internal gymnastics for pointing to and fetching from the LUT.  Three LPMs to get the result out of your flash lookup are nine cycles just by themselves).  Another advantage to external ROM is the outputs automatically show up parallel - 20 bits on 20 pins (24, actually, since nobody makes 20-bit output parallel EEPROMs).  You might want yet another 'latch' signal indicating that the AVR is done outputting bytes, but with a synchronized clock that could be overlooked.  That's three cycles, including 'latch'. 
 

A different problem is that those big parallel EEPROM chips are slooo...  70ns or worse.  If you want faster, get parallel SRAM and load them up with the LUT from an equally large serial EE every time you power-up.  FPGAs (at least Xilinx's ones) do that anyhow.  S.

For example, if the least significant bit of the input hex is set, then the number is odd, and therefore the least significant bit of the packed BCD is therefore set - because it's also an odd number.  Numbers larger than that do require some gating.

eta: And the hex input numbers 0x0000 through 0x0009 are bit-equal to the packed BCD output of 00000 through 00009.  Does that help any?

  S.

One of my more fundamental assumptions here is that there is absolutely no reason to convert to BCD except for display

who do you expect to read the display at that speed?

From what I understood, the algo from the other thread was actually a fast division by 1000. It's use for BCD conversion was just an "excuse" to present the division method.

The algorithm from this thread is based on "there is some magic number we can add to an hex number to convert it to it's BCD representation. Here is a formula to calculate such number."

So they are not even that related... this one only has one instance of division by 1000, and replacing that division by the fast algo wouldn't make a big difference.

I discovered that the OP's formula can be written in a different way. I would explain how to derive it, but unfortunately I was writing that when I lost the whole post 

Meanwhile, I leave this demo https://godbolt.org/z/cTWva9

The drop in replacement for the OP's function is:

// magic numbers
// tens: 6
// hundreds: 6*10 + 6*16 = 156
// thousands: 6*10*10 + 6*10*16 + 6*16*16 = 3096
// 10000s: 6*10*10*10 + 6*10*10*16 + 6*10*16*16 + 6*16*16*16 = 55536

#define M10 6
#define M100 156
#define M1000 3096
#define M10000 55536

unsigned long bin2bcd (uint32_t n)     // convert 16 bit binary n to 5 digit BCD (packed)
{
    unsigned long result = n;
    while (n >= 10000) {
        n -= 10000;
        result += M10000;
    }
    while (n >= 1000) {
        n -= 1000;
        result += M1000;
    }
    while (n >= 100) {
        n -= 100;
        result += M100;
    }
    while (n >= 10) {
        n -= 10;
        result += M10;
    }
    return result;
}

I didn't do any effort to optimize it, but I believe it should be somewhat faster, since there are no divisions, I used successive subtractions instead (I know, not the fastest method either).