32-bit square root in Assembler?
2006-08-14 by Mark Jordan
I'm looking for a 32-bit Square-Root Assembler routine for the ATMEGA162 processor. Have adapted a 16-bit routine I found on the net, but is is very slow. Any ideas? Thanks, Mark Jordan
Thread
32-bit square root in Assembler?
Re: [AVR-Chat] 32-bit square root in Assembler?
2006-08-14 by Peter Harrison
Mark Jordan wrote: > I'm looking for a 32-bit Square-Root Assembler routine > for the ATMEGA162 processor. > > Have adapted a 16-bit routine I found on the net, but > is is very slow. > > Any ideas? > > Thanks, > Mark Jordan > How slow? Can you give a figure for an example calculation at a quoted clock speed? This is just so that I (we) know whether it can be beaten. After all, it may seem slow to you but actually just be how life is for everyone. Peter Harrison
Re: [AVR-Chat] 32-bit square root in Assembler?
2006-08-14 by Mark Jordan
On 14 Aug 2006 at 16:51, Peter Harrison wrote: > Mark Jordan wrote: > > I'm looking for a 32-bit Square-Root Assembler routine > > for the ATMEGA162 processor. > > > > Have adapted a 16-bit routine I found on the net, but > > is is very slow. > > > > Any ideas? > > > > Thanks, > > Mark Jordan > > > > How slow? Can you give a figure for an example calculation at a quoted > clock speed? > > This is just so that I (we) know whether it can be beaten. After all, it > may seem slow to you but actually just be how life is for everyone. > > Peter Harrison > It takes some 20mS @ 11MHz to do the square root of $0F000000. Here is the routine: ----------- Sqrt_32bit: ldi two, $02 ldi one, $01 ldi zero, $00 ldi val1, $01 ; Odd subtraction value clr val2 clr val3 clr val4 clr res1 ; Root in res2:res1 clr res2 loop: sub root1, val1 sbc root2, val2 sbc root3, val3 sbc root4, val4 brlo done add res1, one adc res2, zero add val1, two adc val2, zero adc val3, zero adc val4, zero rjmp loop done: etc...
Re: [AVR-Chat] 32-bit square root in Assembler?
2006-08-14 by Zack Widup
You wouldn't have something for arctangent, would you? I've been kicking around the Pade approximation in my spare time but it's a lot of work. Accuracy to a degree is probably sufficient for my usage. Zack
Show quoted textHide quoted text
On Mon, 14 Aug 2006, Mark Jordan wrote: > On 14 Aug 2006 at 16:51, Peter Harrison wrote: > > > Mark Jordan wrote: > > > I'm looking for a 32-bit Square-Root Assembler routine > > > for the ATMEGA162 processor. > > > > > > Have adapted a 16-bit routine I found on the net, but > > > is is very slow. > > > > > > Any ideas? > > > > > > Thanks, > > > Mark Jordan > > > > > > > How slow? Can you give a figure for an example calculation at a quoted > > clock speed? > > > > This is just so that I (we) know whether it can be beaten. After all, it > > may seem slow to you but actually just be how life is for everyone. > > > > Peter Harrison > > > > It takes some 20mS @ 11MHz to do the square root of $0F000000. > Here is the routine: > > ----------- > Sqrt_32bit: > ldi two, $02 > ldi one, $01 > ldi zero, $00 > > ldi val1, $01 ; Odd subtraction value > clr val2 > clr val3 > clr val4 > > clr res1 ; Root in res2:res1 > clr res2 > > loop: > sub root1, val1 > sbc root2, val2 > sbc root3, val3 > sbc root4, val4 > brlo done > > add res1, one > adc res2, zero > > add val1, two > adc val2, zero > adc val3, zero > adc val4, zero > rjmp loop > > done: > etc... > > >
Re: [AVR-Chat] 32-bit square root in Assembler?
2006-08-14 by Peter Harrison
Mark Jordan wrote:
> On 14 Aug 2006 at 16:51, Peter Harrison wrote:
>
>> Mark Jordan wrote:
>>> I'm looking for a 32-bit Square-Root Assembler routine
>>> for the ATMEGA162 processor.
>>>
>>> Have adapted a 16-bit routine I found on the net, but
>>> is is very slow.
>>>
>>> Any ideas?
>>>
>>> Thanks,
>>> Mark Jordan
>>>
>> How slow? Can you give a figure for an example calculation at a quoted
>> clock speed?
>>
>> This is just so that I (we) know whether it can be beaten. After all, it
>> may seem slow to you but actually just be how life is for everyone.
>>
>> Peter Harrison
>>
>
> It takes some 20mS @ 11MHz to do the square root of $0F000000.
Well, I don't have a sqrt() function in assembler but I do have the GCC
compiler (V 3.4.6) and some sqrt() code I found at
http://local.wasp.uwa.edu.au/~pbourke/other/sqrt/
Here is the code:
unsigned long sqrt(unsigned long r)
{
unsigned long t,b,c=0;
for (b=0x10000000;b!=0;b>>=2) {
t = c + b;
c >>= 1;
if (t <= r) {
r -= t;
c += b;
}
}
return(c);
}
It gives the answer 15863 (which may or may not be close enough) in
about 62us simulated for a MEGA163 at 11MHz using AVR studio. The
compiler was set to optimize for size. Changing the optimisation to O=2
gets an execution time of 54us.
I have not looked at what is going on here - your posting just caught my
eye when I was looking at square roots for something.
When compiled with optimize for speed (O=2) set in GCC, the generated
code is:
unsigned long sqrt(unsigned long r)
{
df4: ef 92 push r14
df6: ff 92 push r15
df8: 0f 93 push r16
dfa: 1f 93 push r17
dfc: cf 93 push r28
dfe: df 93 push r29
e00: fc 01 movw r30, r24
e02: eb 01 movw r28, r22
unsigned long t,b,c=0;
e04: ee 24 eor r14, r14
e06: ff 24 eor r15, r15
e08: 87 01 movw r16, r14
for (b=0x10000000;b!=0;b>>=2) {
e0a: 80 e0 ldi r24, 0x00 ; 0
e0c: 90 e0 ldi r25, 0x00 ; 0
e0e: a0 e0 ldi r26, 0x00 ; 0
e10: b0 e1 ldi r27, 0x10 ; 16
t = c + b;
e12: a8 01 movw r20, r16
e14: 97 01 movw r18, r14
e16: 28 0f add r18, r24
e18: 39 1f adc r19, r25
e1a: 4a 1f adc r20, r26
e1c: 5b 1f adc r21, r27
c >>= 1;
e1e: 16 95 lsr r17
e20: 07 95 ror r16
e22: f7 94 ror r15
e24: e7 94 ror r14
if (t <= r) {
e26: c2 17 cp r28, r18
e28: d3 07 cpc r29, r19
e2a: e4 07 cpc r30, r20
e2c: f5 07 cpc r31, r21
e2e: 40 f0 brcs .+16 ; 0xe40 <sqrt+0x4c>
r -= t;
e30: c2 1b sub r28, r18
e32: d3 0b sbc r29, r19
e34: e4 0b sbc r30, r20
e36: f5 0b sbc r31, r21
c += b;
e38: e8 0e add r14, r24
e3a: f9 1e adc r15, r25
e3c: 0a 1f adc r16, r26
e3e: 1b 1f adc r17, r27
e40: b6 95 lsr r27
e42: a7 95 ror r26
e44: 97 95 ror r25
e46: 87 95 ror r24
e48: b6 95 lsr r27
e4a: a7 95 ror r26
e4c: 97 95 ror r25
e4e: 87 95 ror r24
e50: 00 97 sbiw r24, 0x00 ; 0
e52: a1 05 cpc r26, r1
e54: b1 05 cpc r27, r1
e56: e9 f6 brne .-70 ; 0xe12 <sqrt+0x1e>
}
}
return(c);
}
e58: c8 01 movw r24, r16
e5a: b7 01 movw r22, r14
e5c: df 91 pop r29
e5e: cf 91 pop r28
e60: 1f 91 pop r17
e62: 0f 91 pop r16
e64: ff 90 pop r15
e66: ef 90 pop r14
e68: 08 95 ret
Pete Harrison
http://micromouse.cannock.ac.uk/