[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [avr-gcc-list] udivmodqi optimization

From: Paulo Marques
Subject: Re: [avr-gcc-list] udivmodqi optimization
Date: Mon, 19 Dec 2005 12:05:27 +0000
User-agent: Mozilla Thunderbird 1.0.6 (X11/20050716)

Dmitry K. wrote:
On Saturday 10 December 2005 01:32, Paulo Marques wrote:

Hi, all

A while ago I noticed gcc for i386 sometimes optimized a division with a
constant value by doing a multiply with the inverse in fixed point.

It goes something like:

a / b <=> (a * (0x10000 / b)) / 0x10000  (*)

Due to the fact that this actual truncates the result (instead of
rounding), the factor should be ((0x10000 / b) + 1), instead.

I did a small program to test this out on a PC and it turns out that it
works just fine.

It is very interesting idea.
Is it really possible to use this method for 'b' which is not
a power of 2 ?  (Case of 'b is power of 2' is not interesting:
Gcc optimizes such division).

Yes, I know :)

Just run the code attached on the first email on a PC. It shows that with a 16 bit multiplier you can do *any* 8 / 8 bit division.

It probably can also be done with a 32 bit multiplier to do 16/16 bit divisions.

The great limitation is that the divider must be a constant known at compile time. But IMHO many divisions we do on regular code fall under this category.

Note that this is just worth it on a enhanced AVR that has MUL instructions. If you have to do the multiply yourself, you migth as well do the division instead...

Paulo Marques
Software Development Department - Grupo PIE, S.A.
Phone: +351 252 290600, Fax: +351 252 290601
Web: www.grupopie.com

Pointy-Haired Boss: I don't see anything that could stand in our way.
           Dilbert: Sanity? Reality? The laws of physics?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]