Divide function in AVR 8 bit

Go To Last Post
22 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Please Help in this regard;

ATMEGA168V

I want to divide some unsigned value with 60

but can not find divide instruction in AVR instruction set.
how it can be do.

AVR Studio in assembly mode not in c.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The AVR has no divide instruction so you must do the division in a software routine. The AVR appnote AVR200 gives examples of such routines tailored for either speed or small size. Go on to atmel.com and download both the appnote and the software file, since the actual code is not in the appnote but only in the file.

Mike

Last Edited: Sun. Dec 6, 2009 - 04:27 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Or multiply by 1/60, which is .0166. I notice that .0166 times 65536 is about 1088, and just remember the decimal point is 16 bits from the right.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Think a division as multiple subtracts and a register increases by one when a subtraction is done.
ldi r16,250
clr r17
div:
subi r16,60
inc r17
cpi r16,60
brsh div

In the final of this routine r16 contains the remainder.Think a multiply a multiple add.Add this value to itself and increase a register until reaches 10,is the same like multiply it by ten.Then execute again the above routine to get a floating result.
Here is the complete routine:
example 59/60=0.983333

.include "2313def.inc"

main:
ldi r16,ramend
out spl,r16
ldi r30,0x80
do:
ldi r16,low(59)
ldi r20,high(59)
ldi r21,low(60)
ldi r22,high(60)
clr r17
div:
cp r16,r21
cpc r20,r22
brlo store
sub r16,r21
sbc r20,r22
inc r17
cp r16,r21
cpc r20,r22
brsh div
store:
mov r0,r17
clr r17
st z+,r0
cpi r30,0x8a
breq end
clr r18
mov r4,r16
mov r5,r20
clr r19
tst r16
breq end
clr r19
ad:
add r16,r4
adc r20,r5
inc r19
cpi r19,9
brne ad
rjmp div
end:
rjmp end

Last Edited: Sun. Dec 6, 2009 - 11:56 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

if a slightly less than 0.1% error is tolerable, just multiply the number with 1092 and after that, divide the result with 65536 by shifting it right 16 times.
For better precision, just operate with other numbers. Hope you got the idea.

Dor

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

masoodlodhran wrote:

I want to divide some unsigned value with 60

What is the range of "some value" or result? 8-bit? 16-bit? 32-bit?

And even better questions: what are you calculating, why do you need to divide, and is there no other way to calculate what you are doing than dividing?

If not, there are neat tricks you can utilize to have a fixed divide by 60, as the AVR200 routines have divide any by any.

Just for the record, if you are dividing 8-bit value by 60, then most efficient may be to subtract 60 in a loop (max 4 loops) or just compare if the source is greater than 1x60,2x60,3x60 or 4x60. If dividing 16-bit value, you really don't want to do that, rather you want to work with bits, as then you need to only see 10 loops if the value is greater than 1024x60, if it is then subtract it from the value, add 1024 to result, loop over to see if value is greater than 512x60, then 256x60, etc, until you hit 1x60. It may be best to be a loop, since you most likely don't want to copypaste the same thing for 10 times for every bit. Expand that to 32-bit values if you like.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I actually ran into a very similar situation about a year and a half ago--I was wanting to divide by 30. A bit of thinking got me a solution. You can simplify the problem by thinking of a divide-by-60 as a divide-by-15 followed by a divide-by-4.

So, I thought to myself, a divide-by-15 is pretty close to a divide-by-16. If we do a bit of fudging, we can get pretty darn close to the right answer. Note that I've only tried this on 8-bit numbers, so higher-precision numbers will require a more work.

My solution was this:

; multiply by 17/16, and add a fudge factor of 1
; this equates to x+x/16+1
; catch the overflow early--as it turns out, almost all overflow cases mean that x/15 = 16
; then, divide by 16, so the final equation is:
;     answer = (x+x/16+1)/16
   mov r17, r16
   swap r17
   cbr r17, 0xf0
   addi r17, 1    ;this is the fudge factor
   add r16, r17
   brcs ANSWER_IS_16 ; catch the overflow case
; now, divide by 16:
   swap r16
   cbr r16, 0xf0
   rjmp DONE
ANSWER_IS_16:
   ldi r16, 16
DONE:

(I'm doing all this code from memory, so it might not be right, or even syntactically correct...)

If you're doing just a divide-by-15 (in which case you'd remove the LSR at the end of my code), there's a single case where it doesn't work--when x=255. If you're doing a divide-by-30, however, the error disappears, and if you add another LSR in order to get a divide-by-60, it similarly has no errors.

As a side note, this is a nice example of an accuracy-vs-speed tradeoff. If you're willing to be off-by-one in some edge cases, then (x+x/16)/16 might be accurate enough for you.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

To Mohonri:
Since there is no addi AVR instruction to add a constant to a register this can be done by subtracting a negative constant from a register.
Subi r16,-1 == r16 + 1

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I would do like Itdor and MUL with 1092.
With 1092 the result is correct or 1 to low.
So MUL the result with 60, if that is 60 or more from the org. value add one to the result.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But.. but.. Suggestions to multiply it by 1092, or some other multibyte number >255, make it more complicated than division! Everyone should know how to write a divide routine, anyway - it's a computing fundamental. What do they teach kids in school these days, mutter mutter, harrumph.

; 16/8 division, 16 bit result, 8 bit remainder
; divide r1:r0 by r24, quotient in r1:r0, remainder in r2
div168:
        clr     r2               ; clear remainder
        ldi     r25,0x10         ; 16 bits
_d161:  lsl     r0
        rol     r1
        rol     r2               ; next dividend bit to r2
        brcs    _d162            ; this should never, ever, happen
        cp      r2,r24           ; trial subtraction
        brcs    _d163            ; not big enough
_d162:  sub     r2,r24           ; ok, subtract it
        inc     r0               ; add this power of 2 to quotient
_d163:  dec     r25              ; count bit
        brne    _d161            ; do until done
        ret                      ; remainder in r2
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

As Mike pointed out above

Quote:
The AVR appnote AVR200 gives examples of such routines tailored for either speed or small size.
I don't see the big drama, just use the ready made Atmel routines.

John Samperi

Ampertronics Pty. Ltd.

https://www.ampertronics.com.au

* Electronic Design * Custom Products * Contract Assembly

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

peret wrote:
Everyone should know how to write a divide routine, anyway - it's a computing fundamental. What do they teach kids in school these days, mutter mutter, harrumph.

Funny, I also forgot previously to say that pen and paper don't have division operation either, but you can still use pen and paper to divide numbers. Now what is this thing called in English? Ah, long division?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

They teach .NET and C# bloatware.
harumpatoo

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Everyone should know how to write a divide routine, anyway - it's a computing fundamental. What do they teach kids in school these days, mutter mutter, harrumph.

A 16 bit looped div take about 200 clk.
A 16 bit mul take less than 20 clk

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
A 16 bit mul take less than 20 clk

Ok, so let me see your 20 cycle routine to divide by any arbitrary number I choose.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

No, that is a 20 cycle MUL. He said 200 cycles for divide.

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
No, that is a 20 cycle MUL. He said 200 cycles for divide.

Yes, but he's talking about doing a divide by multiplying with a fraction -
Quote:
I would do like Itdor and MUL with 1092.
With 1092 the result is correct or 1 to low.
So MUL the result with 60, if that is 60 or more from the org. value add one to the result.

You can't do that for an arbitrary value. He also omitted the cycles it takes to do a second multiplication by 60 and compare afterward for error correction.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes, but I read sparrow2's mul-in-20-clocks comment as a follow up on his earlier post on replacing a div with a mul.

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
You can't do that for an arbitrary value.

But 1092 is not an arbitrary value, it is a very specific value for a very specific situation.

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

/Peret out.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

geoelec wrote:
To Mohonri:
Since there is no addi AVR instruction to add a constant to a register this can be done by subtracting a negative constant from a register.
Subi r16,-1 == r16 + 1
Ah, thanks for pointing that out. That's what I get for trying to code off the top of my head. :oops: That should have been an inc rather than an addi. Also, instead of branching, just do a ROR and then three LSRs

Here's the cleaned-up code:

;again, assume that r16 holds the numerator
   mov r17, r16  ; multiply by 17/16
   swap r17
   cbr r17, 0xf0
   inc r17, 1    ; this is the fudge factor
   add r16, r17
   ror r16       ; divide by 16
   lsr r16
   lsr r16
   lsr r16
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Ok I'm back
yes it was a ref to 1092 because this is about div with 60 (div with 60 is the same as mul with 1/60).
1092/65536 = 1/60.1465

I made a extra check and if we use 1093 we will allways get correct value 1093/65536 = 1/59.9597
The max error is for 65535/60=1092(.25)
If we MUL with 1093/65536 we get 1092(.98) so if we just use the 16 high bits it will give the correct value in less than 20 clk

Jens