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?
_______________________________________________
AVR-GCC-list mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list
