AVR-Chat

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/