|
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?
[Prev in Thread] | Current Thread | [Next in Thread] |