91 posts / 0 new

## Pages

first which format is the output you want? (bin or BCD)

but I guess just take El Tangas's solution that is somewhere here that make 16 bit to BCD in 45-48 (I can't remember) and use the formula, and then make the adjustment.

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.

BCD rounding is too easy (check LSD for >=5)...wonder if it can be done in binary efficiently (maybe not)...useful for further math operations on the binary value (such as set motor RPM to nearest 10 rpm).

Previously I convert to BCD, round the digits & cvt back to binary...wonder if here is a more direct way.

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Last Edited: Sat. Apr 28, 2018 - 07:37 AM

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

I think you mean this thread: https://www.avrfreaks.net/commen...

No I don't want BCD result at all.

Given an unsigned 16 bit binary unsigned integer, can it be converted (using some rather fancy tricks, without using BCD)  into a rounded-to-tens binary number?    You give it 12345 it returns 12350, you give it 223 it returns 220.  Would even settle for 8 bit solution for starters. It is a rather difficult challenge.   Was looking for something slick, like swap bits 3 &4, add to original, number shift right, swap bits 1&2, add to previous result, shift right...gives answer.

For an example of an unrelated slick method, here's a binary-friendly example to find the greatest common divisor of two numbers.   https://en.wikipedia.org/wiki/Binary_GCD_algorithm#Efficiency   I've used this a few times.

```unsigned int gcd(unsigned int u, unsigned int v)
{
// simple cases (termination)
if (u == v)
return u;

if (u == 0)
return v;

if (v == 0)
return u;

// look for factors of 2
if (~u & 1) // u is even
{
if (v & 1) // v is odd
return gcd(u >> 1, v);
else // both u and v are even
return gcd(u >> 1, v >> 1) << 1;
}

if (~v & 1) // u is odd, v is even
return gcd(u, v >> 1);

// reduce larger argument
if (u > v)
return gcd((u - v) >> 1, v);

return gcd((v - u) >> 1, u);
}```

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Last Edited: Sat. Apr 28, 2018 - 03:52 PM

If you happen to have \$F0 lying around in a register, 'and' and 'swap' is faster than four right-shifts.  S.

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

Last Edited: Sat. Apr 28, 2018 - 08:00 PM

That is most excellent...nice magic!!!   The shift by 8 is nice, since you can just grab the high byte.

note, not really 8 bit, max input is 250

well, actually 254...it works!

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

avrcandies wrote:
well, actually 254...it works!

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.

No, because when 5 is added

NO it does work as was given...all the way up to 254 (changed for loop from 250 to 254):

255 rounds up to 260...so 254 is the limit (give it 8 bits, get 8 bit answer)

here is some output from your  #59 posting...I suppose what do you mean by overflow? 16bits?   Pelles on PC, was happy (though I made everything int).

......

....

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Last Edited: Sun. Apr 29, 2018 - 02:17 AM

I see what you mean ...in 8 bits you get the over flwo , but on the PC kit is happy.

I made a version with your update...works good from 0 to 254...THIS is quick & slick!

```ldi ZL, 205		 ;magic constant
mul ZL, mynumber  ;number to convert
movw ZH:ZL, r1:r0
subi ZL, low(-1025)   ;5*205
sbci ZH, high(-1025)
andi ZH, 0xF8
mov ZL, ZH
lsr ZH
lsr ZH

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Last Edited: Sun. Apr 29, 2018 - 03:12 AM

but you asked for 16 bit ?!

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.

Last Edited: Sun. Apr 29, 2018 - 01:16 PM

an 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.

As a constrained subset let L=0 , then we are saying 256*H has the same last digit as H, when H is even.  If that is true, then adding L, from 0 to 9, would keep it true.

Also if N is odd, the 256*N ends in either N+5 or N-5  (or perhaps there is a more cohesive way of stating this).

 256*N N ends in last digit 0 0 match 2 2 match 4 4 match 6 6 match 8 8 match 1 6 adds 5 3 8 adds 5 5 0 subtract 5 7 2 subtract 5 9 4 subtract 5 got N ends last digit in either 0 0,5 2 2,7 4 4,9 6 1,6 8 3,8

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Last Edited: Mon. Apr 30, 2018 - 12:53 AM

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

this will never be as pretty as the 8 bit version

Thanks for the try!  Wouldn't there be a magic number that would work for 16bits, just as in the 8 bit method?

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

avrcandies wrote:
Wouldn't there be a magic number that would work for 16bits, just as in the 8 bit method?

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
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
brtc	end
subi	r24, -5
end:                      ;output in r24

forever:
rjmp	forever```

Last Edited: Mon. Apr 30, 2018 - 06:18 PM

you would need to do a 16x16 multiply, and that is quite a few AVR instructions

I wonder, since part of the result will be shifted into oblivion, if perhaps the full 16x16 result might not need calculated (or more likely, saved), especially if the +5 is kept in the original argument.

You are a master of the numerical domain!!

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

avrcandies wrote:

You are a master of the numerical domain!!

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.

Last Edited: Mon. Apr 30, 2018 - 07:53 PM

first the 16x16 you only "save" the high byte because 54429 is 8 times bigger than wanted so the reminder is placed in 3 bytes.(but you save)

But if you MUL the 3 bytes with 20 (not 10) the result will have a shift of 4th bit and then the reminder should be placed correct (perhaps some of the top bits needs to be and'ed off).

And perhaps the value at the lowest byte is so small that it isn't needed.

but there is an other "real" problem what about 65535! a correct rounding will give 0 it 16bit !!!

And it could be faster with a more sloppy value of 1/10  (perhaps the reminder have to be found as x-(1/10x*10) )

17 cycles will do for 16-bit mod 10:

```  ; select SH:SL to be a pair of upper registers (LDI range)
: EDIT sou:rce is the pair of input registers
​  MOVW SH:SL, sou:rce
SBRC SH, 7
SUBI SH, 100 ; no carry
SBRC SH, 0
ADDI SH, 5 ; no carry
BRCC 1f
ADDI SL, 6  ; no carry
1:
LDI SH, 26
MUL SL, SH
LDI SH, 10
MUL R1, SH
SUB SL, R0
BRCC 1f
1: ; SL=sou:rce % 10  R1=0```

Moderation in all things. -- ancient proverb

Last Edited: Tue. May 1, 2018 - 03:27 PM

17 cycles will do for 16-bit mod 10:

That's amazing--haven't tried it yet, but will.

Wondering why not use ZH:ZL, ZH, XL, etc   SH, SL sound mysterious like they are needed for something else.

can you repost ...what is 1: ???  should be lf:??  also, 1: is in two places

but there is an other "real" problem what about 65535! a correct rounding will give 0 it 16bit !!!

We have to live with it... just like 255 rounds up to 260, which doesn't fit well into a byte...you could do some tricks:

a) If 260, return with the overflow set, otherwise return with the overflow cleared (to alert the caller).

b) If 260, return with the value 251, which could be trapped out by the caller....but likely to be forgotten about & cause "strange" issues to surface later!

c) Simply don't try rounding anything above 254 (or 65534)

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

Last Edited: Tue. May 1, 2018 - 03:19 AM

what is 1: ???  should be lf:??  also, 1: is in two places

https://stackoverflow.com/questions/27353096/1b-and-1f-in-gnu-assembly

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

I don't think AVR Studio will let you do that.  Even if it did, it would do horrible things to the label listing(s).  Yeah, the alternative isn't much fun either, labels with suffixes of 'aaa' and 'bbb' get to be par for the course, but at least they're unique.  S.

Scroungre wrote:
I don't think AVR Studio will let you do that.
That depends which of the assemblers you use. As long as you are using one of the GNU ones then Nf or Nb are standard practice and always have been.

User manual: https://sourceware.org/binutils/...

Example from that:

Here is an example:

```1:        branch 1f
2:        branch 1b
1:        branch 2f
2:        branch 1b
```

Which is the equivalent of:

```label_1:  branch label_3
label_2:  branch label_1
label_3:  branch label_4
label_4:  branch label_3
```

Last Edited: Tue. May 1, 2018 - 08:48 AM

nice work a thing to remember

I checked it with this code: (for all combinations )

```	MOVW  r24, r16
SBRC  r25, 7
SUBI  r25, 100 ; no carry
SBRC  r25, 0
SUBI  r25, -5 ; no carry
BRCC  L0
SUBI  r24, -6  ; no carry
L0:
LDI   r25, 26
MUL   r24, r25
LDI   r25, 10
MUL   R1, r25
SUB   r24, R0
BRCC  L1
SUBI  r24, -10
L1: ; SL=sou:rce % 10  R1=0
```

Do you have an assembler that "eat" 1f ?

I always wanted to make one where + was 1f and ++ 2f etc.

UPS I see I'm late with this

And perhaps this is one for the compiler it make a mul with 0xCCCD from a lib and then some shifts.(a lot of shifts because it also solve the /)

Last Edited: Tue. May 1, 2018 - 09:31 AM

clawson wrote:

Scroungre wrote:
I don't think AVR Studio will let you do that.
That depends which of the assemblers you use. As long as you are using one of the GNU ones then Nf or Nb are standard practice and always have been.

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.

AS4 only really gave access to the Atmel Assembler (though it's true avr-as was there too if you added WinAVR) but in AS7 it comes as standard with the Atmel Assembler and three different GCC assemblers (avr-as, avr32-as and arm-as) so you start with a wider choice. For AV8 the "plain" assembler is probably still the best choice for stand alone Asm projects as there's so much prior knowledge about its use. But for anything that involves inter-working between C/C++ and Asm then the GNU as assembler is the more obvious choice.

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)).

That's very clever code. I had already tried to use 26 as "magic number", since it aligns the result to 8 bits (shift not needed). But some numbers were generating rounding errors:

```uint8_t reduce (uint16_t);
uint8_t units (uint8_t);

int main()
{
for (uint16_t i = 0; i < 65535; i++) {
if ((i%10) != units(reduce(i))){
printf("%d %d \n", i, units(reduce(i)));
}
}
}

uint8_t units (uint8_t reduced){
reduced = (reduced * 26) & 0xFF;
reduced = (reduced * 10) >> 8;
return reduced;
}

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;
}```

Output of errors is:

```57854 5
58364 5
58874 5
59384 5
59894 5
60404 5
60914 5
61424 5
61934 5
62444 5
62954 5
63464 5
63974 5
64484 5
64994 5
65504 5
65534 5```

These are all large numbers. So by subtracting 100 to numbers with the high bit set, this problem is solved (I would probably subtract 120, which is the largest multiple of 10 smaller than 128).

Very nice code indeed.

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!)

Ah, I see it, in this part:

```	sbrs	        r24,6
rjmp	        L0
subi            r20,20
sbci	        r21,0```

Yeah, it's the same thing

I also used the "adjustment technique" many years ago for a x86 algo: https://board.flatassembler.net/...

It allowed me to save one "mul" compared to the base code. But mul is usually more expensive in x86 CPUs than in AVR (naturally, since it's 32/64 bit), sot it is usually worthwhile to get rid of them, in AVR not so much.

Last Edited: Tue. May 1, 2018 - 12:06 PM

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 ;)

avrcandies wrote:
Wondering why not use ZH:ZL, ZH, XL, etc SH, SL sound mysterious like they are needed for something else.
Not mysterious, generic:

```#define SH ...
#define SL ...
#define sou ...
#define rce ...
#include "mod1016.S"```

Moderation in all things. -- ancient proverb

This doesn't seem to be working.  if I give 2345, I get 2565 (should get 2350)...if I give 5678, I get  2568 (should get 5680)

did I mess something up?

```			MOVW ZH:ZL, myval_hi:myval_low
SBRC ZH, 7
SUBI ZH, 100 ; no carry
SBRC ZH, 0
SUBI ZH, -5 ; no carry
BRCC abc

SUBI ZL, -6  ; no carry

abc:		LDI ZH, 26
MUL ZL, ZH
LDI ZH, 10
MUL R1, ZH
SUB ZL, R0
BRCC bbb

SUBI ZL, -10
bbb:		rcall bin2ascii  ;report ZH:ZL as ascii number
ret```

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

what does the code state !

17 cycles will do for 16-bit mod 10:

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.

Last Edited: Tue. May 1, 2018 - 05:42 PM

17 cycles will do for 16-bit mod 10:

Oh I see, I thought this was just a self-note.  I didn't realize this was for something else (though very related) & was more concerned about some other factors I asked about.

This solution, is also quite marvelous!

Another way to get rounding is to use this to get the last digit , always subtract this from the original number (always giving last digit of 0).  If last digit was >4, add 10 to this

That might not be the shortest path, but usable.

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

One point that nobody touched yet... does it REALLY needs to have three digits for temperature?

I would use only two, "42" means 420 degrees, and that is it.

Much easier to convert to decimal, he could even use a simple 99 bytes table in flash with the conversion already done, a simple LPM and badabim, packed bcd done.

The OP can even use three displays and even shows the zero on the third one to show "420"...

On soldering iron, the temperature changes in a way that those 10°C resolution will not interfere so much.

Also, the OP is fantastically worried about clock cycles, when the uC will be more than 95% of the time in idle.

I understand the OP is missing a lot of knowledge about everything, maybe he is young or new in the area, he will learn in time.

We need to support all new, young and novice people, one day we will die anyway and they will inherit the planet.

Well, yeah, for sure that will happens.  For our luck, we will not be here to see the consequences.

Wagner Lipnharski
Orlando Florida USA