4 ms·
Division is slow. I recently needed to send 16 bit integers over a UART and came up with something like this: uint16_t n,d; // 10K digit d = ((uint32_t)n
by phkahler 9y ago
Division is slow. I recently needed to send 16 bit integers over a UART and came up with something like this:
uint16_t n,d;
// 10K digit
d = ((uint32_t)n * 53687 + 8208) >> 29;
n -= d*10000;
// output d+’0’
// 1K digit
d = ((uint32_t)n * 2097 + 1368) >> 21;
n -= d*1000;
// output d+’0’
// 100s digit
d = (n * 41) >> 12;
n -= d*100;
// output d+’0’
// 10s digit
d = (n * 51 + 40) >> 9;
n -= d*10;
// output d+’0’
// output n+’0’
It does scale to 32 bits but will require 64bit intermediates.
- Const-me 9y agoYou’re probably using some exotic compiler. Most C compilers already do something very similar, check this out: https://godbolt.org/g/weicFj https://godbolt.org/g/weicFj Obviously, "x / 10" is much easier to read and support, compared to these manual optimizations.
- phkahler 9y agoI'm not doing mod 10 operations, I'm printing left to right. I also put each digit in a case: and the digit printing is part of a larger state machine transmitting various things. No characters are stored, one of these blocks was run whenever the UART was ready to receive a new character. I didn't want to do the entire conversion to string all at once and this is a very fast way to extract digits in order.
- Const-me 9y agoYour “d = ((uint32_t)n * 53687 + 8208) >> 29;” is no faster than “d = n / 10000;” Modern compilers already apply these multiply-shift tricks when dividing by a constant.
- phkahler 9y agoI was writing for an ARM based micro controller. The compiler may well have been GCC. I should have timed it vs the obvious use of division. I was not aware that they would do such things for division by arbitrary large numbers. If that's all so, then why is TFA worried about the speed of itoa?
- Const-me 9y ago> I was not aware that they would do such things for division by arbitrary large numbers. They don’t, just 10000 is not large enough :-) But yeah, apparently 32-bit 10k division works on GCC ARM as well: https://godbolt.org/g/ebJqrw https://godbolt.org/g/ebJqrw > why is TFA worried about the speed of itoa? Because itoa is slow. I once needed to read / write large (100MB+) G-code files. Profiler showed me it spent majority of time in standard library routines like itoa / atof / etc. Replacing itoa with http://fmtlib.net http://fmtlib.net lead to much faster code.