Search |
 |
|
 |
| Author |
Message |
|
|
 Posted: Jun 14, 2007 - 06:17 PM |
|
Joined: Apr 16, 2001
Posts: 3522
Location: Phoenix, Arizona
|
|
Nothing like a nice jolt when I saw who the OP was!  Then I realized it's an old thread.  |
|
|
| |
|
|
|
|
|
|
Posted: Dec 19, 2007 - 05:27 AM |
|
Joined: Jun 25, 2007
Posts: 7
|
|
Wouldn't it be nice to not deal with the rounding error? If we were to add a compensation amount before multiplying by 26, we then have no error:
Code:
.def temp1 = r16
.def temp2 = r17
.def A = r18
// Input: A
// Output: r1
DivBy10:
// calculate the amount needed to add to A to compensate for the rounding error to come
// compensation = (A + 3) / 64
mov temp2, A
ldi temp1, 3
add temp2,temp1
// "divide by 64" shortcut
swap temp2
andi temp2, 15
lsr temp2
lsr temp2
// now use 'A - compensation'
mov temp1, A
sub temp1, temp2
// Multiply by magic number
ldi temp2, 26
mul temp1, temp2
ret
I've checked it out on my computer and seems like this works good, and doesn't eat many more cycles than the original. |
|
|
| |
|
|
|
|
|
|
Posted: Feb 24, 2009 - 08:47 PM |
|
Joined: Dec 07, 2008
Posts: 347
Location: germany
|
|
|
Quote:
Code:
; the input number must be in register "input"
; value/10 is in register "result"
; register temp1 and R1:R0 are clobbered
div10:
ldi temp1, 205
mul temp1, input
lsr R1
lsr R1
lsr R1
mov result, R1
ret
This one rocks! Saved my day, today  |
_________________
Jan Kießling
74HC Overview
Flowchart CAD
schematic CAD
|
| |
|
|
|
|
|
|
Posted: Mar 06, 2009 - 03:54 AM |
|
Joined: Jan 18, 2005
Posts: 38
|
|
| i suppose one could allocate a huge look up table ln FLASH on the larger AVR range ... practically instant result which i have done many many years ago... (code lost to time) |
|
|
| |
|
|
|
|
|
|
Posted: Dec 21, 2009 - 08:04 PM |
|
Joined: Sep 29, 2001
Posts: 53
Location: Superior, Colorado USA
|
|
Thanks to all for alively discussion. I need help on a 16 bit divide:
I have been using the DIV16u straight from apnote 1011 (AVR200) since 1998, and found a possible error.
When you have $7080 (28,800) divided by $3841 (14,401), the correct answer is: $0001 and remainder $FFF6 (1.99986).
However, the Atmel DIV16u returns $0001 remainder $383F, quite an error.
When you have $7080 (28,800) divided by $3840 (14,400), the correct answer is: $0002 and remainder $0000 (2.00000), and the Atmel code returns the correct same answer.
Please help, I need a fix fast, or am I wrong?
Vern Bunch, AVR consultant and AVR designer |
|
|
| |
|
|
|
|
|
|
Posted: Jan 05, 2010 - 06:41 PM |
|
Joined: May 26, 2004
Posts: 2538
Location: Las Vegas, Nevada
|
|
|
vbunch wrote:
When you have $7080 (28,800) divided by $3841 (14,401), the correct answer is: $0001 and remainder $FFF6 (1.99986).
However, the Atmel DIV16u returns $0001 remainder $383F, quite an error.
Dude, WTF?
Let's do this manually, by long division.
$3841 goes into $7080 once.
Code:
(hex assumed)
____1___
3841 ) 7080
3841 -
----
383F
$3841 won't go into $383F, so the quotient is 1 and the remainder is $383F. The Atmel routine returns the correct answer.
The number $FFF6 might possibly occur in some floating point representation, but can never happen in unsigned integer math, since it is larger than the dividend. |
|
|
| |
|
|
|
|
|
|
Posted: Jan 05, 2010 - 07:02 PM |
|
Joined: May 26, 2004
Posts: 2538
Location: Las Vegas, Nevada
|
|
Oh, I see where you got it from.
If you want to generate the fractional bits, take the remainder, multiply by 16 (shift left 4) and divide this by the divisor. Repeat until you have enough "(hexa)decimal" places.
Code:
____1FF...
3841 ) 7080
3841 -
----
383F <<4
3841 * F -
----
3821 <<4
3841 * F -
----
3641
... etc
Again, this is just confirming that the original division routine got it right. You didn't carry out enough steps to format the answer the way you expected.
Note that since the first remainder is guaranteed to be less than the divisor, each successive step is guaranteed to produce a quotient less than 16, ie a single hex digit. You have to manually concatenate these single digits to the number of places you want. |
|
|
| |
|
|
|
|
|
|
Posted: Jan 08, 2010 - 05:53 PM |
|
Joined: Sep 29, 2001
Posts: 53
Location: Superior, Colorado USA
|
|
Thank you my friends for your correct responses. It is my fault that I mentioned "remainder" when I expected a fully usable result, without having to divide again, and one that had 16 bit accuracy. So the Atmel division routine is "correct" but unusable without more computation. Since there was no mention that the result is unusable without further division, I niavely skipped the true math definition of "remainder" and went right to "answer", I should not have done that.
I have since written an assembly language routine that gives me a correct (and directly usable) 16 bit division in one run, and it is less time (156 cycles) then the published 16 bit divide routine. It took 3 weeks at 104 hours a week, and I'm way beyond tired.  |
|
|
| |
|
|
|
|
|
|
Posted: Jan 08, 2010 - 06:01 PM |
|
Joined: Jul 18, 2005
Posts: 62371
Location: (using avr-gcc in) Finchingfield, Essex, England
|
|
|
Quote:
I have since written an assembly language routine that gives me a correct (and directly usable) 16 bit division in one run, and it is less time (156 cycles) then the published 16 bit divide routine. It took 3 weeks at 104 hours a week, and I'm way beyond tired
I guess it's too late to say that you could have "borrowed" the source for a / routine from an open source C compiler? |
_________________
|
| |
|
|
|
|
|
|
Posted: Jan 08, 2010 - 06:09 PM |
|
Joined: May 26, 2004
Posts: 2538
Location: Las Vegas, Nevada
|
|
|
Quote:
I guess it's too late to say that you could have "borrowed" the source for a / routine from an open source C compiler?
Actually I suspect in this case he could not, because the answer he wanted was in a fixed point format. He got simple integer division from the appnote. The compiler would have given him full float, which would challenge me to adapt to a fixed format in assembler (and I consider myself rather good at it).
As a matter of interest, if we did look at the source for a / routine in an open source C compiler - let's say, and why not, the GCC compiler - would we be looking at assembler, or C? |
|
|
| |
|
|
|
|
|
|
Posted: Jan 08, 2010 - 06:16 PM |
|
Joined: Jul 18, 2005
Posts: 62371
Location: (using avr-gcc in) Finchingfield, Essex, England
|
|
|
Quote:
would we be looking at assembler, or C?
Assembler. Here's a snippet from gcc/config/avr/libgcc.s:
Code:
/*******************************************************
Division 16 / 16 => (result + remainder)
*******************************************************/
#define r_remL r26 /* remainder Low */
#define r_remH r27 /* remainder High */
/* return: remainder */
#define r_arg1L r24 /* dividend Low */
#define r_arg1H r25 /* dividend High */
/* return: quotient */
#define r_arg2L r22 /* divisor Low */
#define r_arg2H r23 /* divisor High */
#define r_cnt r21 /* loop count */
#if defined (L_udivmodhi4)
.global __udivmodhi4
.func __udivmodhi4
__udivmodhi4:
sub r_remL,r_remL
sub r_remH,r_remH ; clear remainder and carry
ldi r_cnt,17 ; init loop counter
rjmp __udivmodhi4_ep ; jump to entry point
__udivmodhi4_loop:
rol r_remL ; shift dividend into remainder
rol r_remH
cp r_remL,r_arg2L ; compare remainder & divisor
cpc r_remH,r_arg2H
brcs __udivmodhi4_ep ; remainder < divisor
sub r_remL,r_arg2L ; restore remainder
sbc r_remH,r_arg2H
__udivmodhi4_ep:
rol r_arg1L ; shift dividend (with CARRY)
rol r_arg1H
dec r_cnt ; decrement loop counter
brne __udivmodhi4_loop
com r_arg1L
com r_arg1H
; div/mod results to return registers, as for the div() function
mov_l r_arg2L, r_arg1L ; quotient
mov_h r_arg2H, r_arg1H
mov_l r_arg1L, r_remL ; remainder
mov_h r_arg1H, r_remH
ret
.endfunc
#endif /* defined (L_udivmodhi4) */
#if defined (L_divmodhi4)
.global __divmodhi4
.func __divmodhi4
__divmodhi4:
.global _div
_div:
bst r_arg1H,7 ; store sign of dividend
mov __tmp_reg__,r_arg1H
eor __tmp_reg__,r_arg2H ; r0.7 is sign of result
rcall __divmodhi4_neg1 ; dividend negative : negate
sbrc r_arg2H,7
rcall __divmodhi4_neg2 ; divisor negative : negate
rcall __udivmodhi4 ; do the unsigned div/mod
rcall __divmodhi4_neg1 ; correct remainder sign
tst __tmp_reg__
brpl __divmodhi4_exit
__divmodhi4_neg2:
com r_arg2H
neg r_arg2L ; correct divisor/result sign
sbci r_arg2H,0xff
__divmodhi4_exit:
ret
__divmodhi4_neg1:
brtc __divmodhi4_exit
com r_arg1H
neg r_arg1L ; correct dividend/remainder sign
sbci r_arg1H,0xff
ret
.endfunc
#endif /* defined (L_divmodhi4) */
|
_________________
|
| |
|
|
|
|
|
|
Posted: Jan 15, 2010 - 03:50 PM |
|
Joined: Nov 02, 2009
Posts: 3239
Location: Zelenograd, Russia
|
|
Just for fun, I have castrated the OP's div_10 code even further:
Code:
;----------------------------------------
; 8-bit division by 10 routine.
;
; Input: R0 = dividend.
; Output: R1 = result = dividend/10.
;
; Registers R0 and R16 are clobbered.
; 5 words/10 clocks including RET.
;
div10:
ldi r16,205
mul r0,r16
ldi r16,32
mul r1,r16
ret
;----------------------------------------
|
|
|
| |
|
|
|
|
|
|
Posted: Apr 30, 2010 - 11:37 AM |
|
Joined: Jul 18, 2007
Posts: 154
Location: Germany
|
|
The OP's div_10 code was buggy at values like 19, 29, 39, ... or at 21, 31, 41, ... depending on whether the correction (INC) was done or not. Here's a fixed version, with remainder calculation (remainder lines marked, strip them if not needed, saves 5 cycles):
Code:
// input: A, output/value: R1, output/remainder: A
// total cycles: 13
PUSH A //2 Me (for remainder)
INC A //1 Me
CPI A, 0 //1 Me
BRNE x //1,2 Me
DEC A //1 Me
x: //0 Me
LDI B, 51 //1 RetroDan
MUL A, B //2 RetroDan
LSR R1 //1 RetroDan
POP A //2 Me (for remainder)
SUB A, R1 //1 Me (for remainder)
Hope this is useful for someone out there.
My approach:
I made a list with values, RetroDan and RetroDan with INC. It looked somehow like this:
8 - 0 0
9 - 0 1
10 - 0 1
11 - 1 1
So one was too low, the other too high around exact matches (i.e. dividable by 10 with no remainder). So I took the one without INC (saves one cycle), INCreased the value before giving it to the RetroDan stuff, so all results were accurate - but "255" which becomes 0.
A quick check for the overflow after increasing (i.e. value=0), decrease it again (make it 255 again, which gives the correct result) and done.
P.S: I know it's an old thread, but I think it's an important one that's read by a lot of people for finding a good divide-by-10 routine. |
_________________
Markus
|
| |
|
|
|
|
|
|
Posted: May 03, 2010 - 10:49 AM |
|
Joined: Sep 05, 2001
Posts: 2499
|
|
But I would ask at first, whats the purpose to do a division by 10?
Mostly it was the decimal output conversion.
The fastest way to do so, was the subtraction method, since no divison nor multiplication was needed.
A small example for 16 bit ASCII output can be seen on:
http://www.avrfreaks.net/index.php?name ... 721#453721
Peter |
|
|
| |
|
|
|
|
|
|
Posted: May 03, 2010 - 08:20 PM |
|
Joined: Nov 17, 2004
Posts: 13852
Location: Vancouver, BC
|
|
|
Quote:
The fastest way to do so, was the subtraction method, since no divison nor multiplication was needed.
But repeated subtraction that that routine uses is division. And the multiplies when done with the hardware multiply are very fast. |
_________________
Regards,
Steve A.
The Board helps those that help themselves.
|
| |
|
|
|
|
|
|
|
|
FAQ
Search
Register
Log in to check your private messages
Log in
Maximize
RSS
