[cfe-dev] Loop optimised into div (?)

[Joerg Sonnenberger via cfe-dev]

On Mon, Oct 28, 2019 at 02:17:50PM -0700, Bruce Hoult via cfe-dev wrote:
> > I found this when compiling a function that will convert a binary number to a sequence of decimal digits expressed in ascii. Every digit is determined by counting the number of subtractions required for power-or-ten factors . For that algorithm, only up to 9 subtractions are required at every step (or factor). Replacing that by divisions is a lot more expensive for the affected targets.
> 
> Aha. I see, yes.
> 
> I think the divisions are not as expensive as you might be assuming.
> The key is to do the same as for the subtact version and divide by
> 10000, then when the remainder is less than 10000 divide by 1000, and
> so on. Don't repeatedly divide by 10 as in the recursive algorithm --
> that *will* be slow.

It is also important to note that on any somewhat sane architecture, no
division will actually be created here. Now if your architecture has
neither a division nor a multiplication in hardware... Even then,
division by 10 needs ~10 adds and shift in total.

Joerg