AVR Freaks

Or shift right three times (/8) subtract the result twice more (/10) and multiply by ten again.  S.

PS - No, that won't work in BCD.  Do all the math in hex and only convert for display.  S.

if it's 16 bit unsigned int to 16 bit unsigned int you want, I would find the way El targas do it (I can't find it) it's 16 unsigned int to bcd in less than 50 clk, an my guess is if it's only the reminder you need it then can be done in about 40 clk, the corection will then be sub the reminder (and add 10 if reminder >=5, , best to adjust the value of reminder).

so all in all about 50 clk

What's wrong with the suggestion in #53?

(first add 5 to round to nearest)

then, as suggested in #53, Div by 10, truncate to integer, mul by 10.

edit: here is an implementation, in C, for the 8 bit case (note, not really 8 bit, max input is 250). The algorithm may not be immediately obvious, but it's the one stated above.

#include <stdio.h>
#include <stdint.h>

uint8_t round10 (uint8_t);

int main()
{
	for (uint8_t i = 0; i <= 250; i++) {
		printf("%d %d \n", i, round10(i + 5));
	}
}

#define MAGIC 205							/* 205 = 256/10*8 */
uint8_t round10 (uint8_t bin) {
	bin = (MAGIC * bin) >> 8;
	bin &= 0xF8;
	bin += bin >> 2;
	return bin;
}

Conversion to AVR asm is straightforward, left as an exercise to the interested reader

No, because when 5 is added (because of the rounding), it will overflow, 254+5=259. But here is a corrected version, that actually works to 254:

#include <stdio.h>
#include <stdint.h>

uint8_t round10 (uint8_t);

int main()
{
	for (uint8_t i = 0; i <= 254; i++) {
		printf("%d %d \n", i, round10(i));
	}
}

#define MAGIC 205							/* 205 = 256/10*8 */
uint8_t round10 (uint8_t bin) {
	bin = (MAGIC * bin + MAGIC * 5) >> 8;
	bin &= 0xF8;
	bin += bin >> 2;
	return bin;
}

In this case I add 5 at a different stage of the calculation, where overflow will not happen. A nice piece of code, if I do say so myself.

Avrcandies wants a 16 bit algo, but said 8 bits would suffice as proof of concept.

However, I have a feeling there must be a better algorithm, some pattern present in the multiples of 10 in binary, that is repeated and can be used for the rounding.

edit: I think I can prove that if you have a 16 bit number HL (H - high byte, L - low byte), and H is even, then, in decimal, H+L has the same units digit as HL, that is, (H+L)%10 = HL%10. An interesting result, I believe.

The fundamental problem that needs to be solved is:

n += 5;
n -= n%10;

So playing with modular arithmetic will eventually yield a good method, I think.

So, my plan was to reduce the 16 bit number into something that fits in 8 bits with the same decimal units digit. Then get this digit and subtract to the original number.

I used the method of adding 5 when H is odd.

This is what I have:

#include <stdio.h>
#include <stdint.h>

uint8_t reduce (uint16_t);

int main()
{
	for (uint16_t i = 10000; i <= 12000; i++) {
		printf("%d %d \n", i, reduce(i));
	}
}

uint8_t reduce (uint16_t bin) {
	uint8_t h_sign = (bin >> 8) & 0x01;		/* save sign of high bit for later */
	bin = (bin >> 8) + (bin & 0xFF);		/* reduction round 1 */
	bin = (bin & 0x1F) + ((bin >> 4) & 0x1E);	/* reduction round 2 */
	bin += h_sign ? 5 : 0;				/* if h was odd, add 5 to correct */
	return bin;
}

Round 1 reduces 16 bit to 9 bit.

Round 2 reduces 9 bit to roughly a 5 bit number.

"reduction round 2" will need quite a few assembly instructions to implement, this will never be as pretty as the 8 bit version

Sure. The "magic numbers" are just representations of the 1/10 fraction in binary, that is: 0.00011001100 (1100)

For 8 bits, you grab the portion marked, the largest that can fit in 8 bits, and round up: 11001101, which is 205. When you multiply by this number, you are in a way dividing by 10.

So, for 16 bits, you would use 1100110011001101 which is 52429.

The problem is you would need to do a 16x16 multiply, and that is quite a few AVR instructions. This is why I'm trying to find a different algo for larger numbers.

Meanwhile, I translated the "reduction" routine in #67 to assembly:

start:
    ;input in r24:r25
    bst		r25,0
    add		r25, r24
    sbc		r24, r24
    andi	r24, 0x10
    ldi		r18, 0x1F
    and		r18, r25
    swap	r25
    andi	r25, 0x0E
    add		r24, r25    ;or r24, r25 will also do, maybe it's clearer
    add		r24, r18
    brtc	end
    subi	r24, -5
end:                      ;output in r24

forever:
    rjmp	forever

Lol, I wish. True, I always had some affinity for discrete math, but these are little more than parlour tricks compared to some number theory and crypto stuff...

And thanks for the challenge, it really gave me food for thought.

Typically I use the default one.  Of course, this is from Studio 4 running on Win2k, but I recall it incessantly complaining about 'duplicate labels'.  I didn't think it would treat a number label in any exceptional manner, and again - what does that do to the label list?  Granted I've not tried this - Perhaps I should. 

S.

PS - Given functions with a dozen branches or more, I think the '++' format would start to come unhinged at about '+++++++++' and '+++++++++++++'.  ;-)  S.

really many "local" labels like those in this routine just clutter up a reference list

what I would like is just to type + I just don't want to type long labels like the routine name and then a number, but that would be ok if that's then end product.

like it would be nice to have a function where the values of the flags was showed (known and unknown(to see the life time)).  

If you look at the tail end of my code in #49 that convert the last two digit (and use 26 as magic number) I make an adjustment if the number is bigger than 64 (because 26 is to big!)

In my old code I used to use 51 that is way better but then there is a shift involved :( 
and because it's smaller than the correct value an offset is needed (510<512 where 260>256). 

but it bugs me a bit that the code don't always take the same time ;)

This function just gets the units digit. To solve the rounding problem, it needs a few tweaks.

Change line 3 to:

			SUBI ZH, 105 ; no carry

Lets call r the result of the modified function. Now, add (5-r) to the original number (edit: or subtract r-5), and it should give the result you need.

edit: wait, this line is not always executed. You need to add 5 somewhere in the function before the multiplies.