divmod10() : a fast replacement for /10 and %10 (unsigned)

Yes that's OK. Consider what I wrote to be in the public domain so anyone can use it under any license. Just put something like "this section of code based on public domain code by Stimmer, see post at forum.arduino.cc/whatever-the-url-is ".

agree these should be standard libs of the core,
but the arduino team wont,

I'm definitely not sure of the latter.
The code is not core lib ready yet. For Arduino-team the portability of core libs is a very important issue. The divmod10() function should be decorated with #ifdefs to select the C (portable to DUE?) or the assembly (328 only?) implementation .

So the fun part is over, now the real work starts :wink:

So the fun part is over, now the real work starts

It ought to be pretty simple to surround this code with #ifdef AVR, or perhaps a check for the AVR architecture with multiply? In fact, the Print.cpp I posted has #ifdef checks to use either the original C code, Stimmer's optimization, or your version of the Hackers Delight algorithm. Yes, it requires some careful attention, but this part really isn't very difficult.

Whether the Arduino Team will accept this for the Print.cpp that ships for all Arduino boards is a good question. Historically, they've been pretty uninterested in speed optimizations.

I definitely do plan to publish this in the next version of Teensyduino, likely within the next 6 weeks. Of course, if Coding Badly is satisfied with the licensing? ... Thanks Stimmer! :smiley: You definitely did the heavy lifting with an amazing optimization!

Good enough for me.

update on printfloat version using divmod10() (follows - divmod10() : a fast replacement for /10 and %10 (unsigned) - #77 by robtillaart - Libraries - Arduino Forum - )

a new version to print the remainder (limited to 10 decimals) of a float

  • timing is slightly shorter
  • code is more straightforward than the previous one

insert in Print.cpp ==> size_t Print::printFloat()

  // Print the decimal point, but only if there are digits beyond
  if (digits > 0)
  {
    n += print("."); 

    uint32_t t = 1;
    for (uint8_t i=0; i<digits; i++) t = ((t<<2) + t)<<1;  // t *= 10
    uint32_t rem = remainder * t;
    char z[11]="0000000000";  // max 10 decimals
    z[digits]='\0';
  
    uint32_t d = 0;
    uint8_t m = 0;
    while (rem > 10)
    {
      divmod10(rem, d, m);
      z[--digits] = m + '0';
      rem = d;
    }
    z[--digits] = rem + '0';  // last digit
    n += print(z);
  }

testing
10737.4179
1.0182
107.37
Time=1104 << original Print.cpp 2144; almost 50% off (for this particular test)
done

testsketch

unsigned long start = 0;
unsigned long stop = 0;
volatile unsigned long q;

void setup()
{

  Serial.begin(115200);
  Serial.println("testing");
  
  byte backup = TIMSK0;
  
  TCCR1A = 0;
  TCCR1B = 4; 
  TIMSK1 |= _BV(TOIE1);
  
  Serial.flush(); //wait for serial buffer to clear
  TIMSK0 = 0; //disable millis;
  TCNT1 = 0;
  
  Serial.println(10737.41824, 4);
  Serial.println(1.01819584, 4);
  Serial.println(107.37, 2);
  
  stop = TCNT1; //how many clock cycles.
  TIMSK0 = backup; //renable millis;
  stop*=16;//There are 16us per clock cycle with a 1:256 prescaler.
  Serial.print("Time=");
  Serial.println(stop);
  Serial.println("done");
  TIMSK1 &= ~_BV(TOIE1);
}

void loop()
{
}

ISR(TIMER1_OVF_vect) {
  Serial.println("I Overflowed!"); //just to make sure we can tell if this happens.
}

update
replace n += print("."); with n += print('.');

Time=1072 << original 2144 is 50% off

Does this make any difference...

n += write('.');

not measurable with the test script, but removing some "stacked calls" and use write() where possible may add up.

update on printfloat version using divmod10() . Code see- divmod10() : a fast replacement for /10 and %10 (unsigned) - #100 by robtillaart - Libraries - Arduino Forum -

Incorporated the Stimmer ASM divmod10_asm into the floating point test. - divmod10() : a fast replacement for /10 and %10 (unsigned) - #72 by stimmer - Libraries - Arduino Forum -
It strips of another 3% for printing floats

output:
testing
10737.4179
1.0182
107.37
Time=1008 << original 2144 is 53% off
done

1 millisecond for 19 digits is about 50+ uSec per digit (iso 100)

update: printFloat continues in its own thread here - faster printing of floats by divmod10() and others - Libraries - Arduino Forum -

I published a Teensyduino release candidate today, which includes Stimmer's optimization.

Thanks to everyone who worked and contributed to this awesome speedup. Soon it'll be in widespread use on Teensy 2.0 and Teensy++ 2.0 boards. :slight_smile:

Thanks Paul,

We can propose on the developers list that the divmod10 code (including #ifdef to select asm or C version) becomes a separate .h file within the core. I've seen " x/10 x%10" code constructs in several libs
(recently - TM1638 display library - Libraries - Arduino Forum - )

what do you think?

update: the divmod.h (?) could include work discussed here - divu5() and divu3(). Fast replacements for unsigned division by 3, 5, 6, 10, 15 - Libraries - Arduino Forum -

I think it's a good idea.

But I also find proposing stuff on the developer mail list to be exhausting. I'm not personally planning to propose it and respond to the many "bike shedding" replies that are likely to result.

If you propose it, I'll chime in with a "+1". When/if Arduino publishes it, I'll adopt whatever naming and header file convention they use.

1 Like

If you do write up a good proposal on the developer mail list and Cristian replies favorably (really, anything other than saying no or probably not), perhaps I'll adopt it for Teensyduino 1.17 or 1.18? I just posted the first release candidate today. I don't have a deadline for 1.17, but unless there's any problems or other urgent stuff to add, I'll probably release sometime next week.

I can't see the harm in placing this into a header where it can be used by libraries. There just needs to be some consensus from Arduino (where really, Cristian's voice is the only one that matters) so I don't end up publishing this in a way that will later break when/if they do it.

Personally, I would love to see it wrapped in a function which, for purposes of this post, I shall call digit().

Example use of digit():
long n = 4216738;
byte ones = digit(n, 0);  // now, ones == 8
byte tens = digit(n, 1);  // now, tens == 3
byte hund = digit(n, 2);  // now, hund == 7
byte thou = digit(n, 3);  // now, thou == 6
byte myri = digit(n, 4);  // now, myri == 1
byte lakh = digit(n, 5);  // now, lakh == 2
byte mill = digit(n, 6);  // now, mill == 4
byte cror = digit(n, 7);  // now, cror == 0

This would be extremely useful for displays.

I'm not sure how it should behave for negative numbers, though.

for negatives you would have to first negate to make them positive, then use divmod10 then negate the resulting division value (the mod value I believe would stay positive). If you are doing it multiple times in a row then you would leave the results all positive and then at the very end negate the remaining division part.

odometer:
Personally, I would love to see it wrapped in a function which, for purposes of this post, I shall call digit().

Example use of digit():

long n = 4216738;
byte ones = digit(n, 0);  // now, ones == 8
byte tens = digit(n, 1);  // now, tens == 3
byte hund = digit(n, 2);  // now, hund == 7
byte thou = digit(n, 3);  // now, thou == 6
byte myri = digit(n, 4);  // now, myri == 1
byte lakh = digit(n, 5);  // now, lakh == 2
byte mill = digit(n, 6);  // now, mill == 4
byte cror = digit(n, 7);  // now, cror == 0



This would be **extremely** useful for displays. 

I'm not sure how it should behave for negative numbers, though.

@odometer
Have you seen this thread, - http://forum.arduino.cc/index.php?topic=179111.0 -
it uses divmod10 to increase the speed of the print class from which display classes are derived. But also the Serial class is derived from Print.

1 Like

hi Rob

I know that Arduino code mainly uses LGPL license, but since this topic is not source code it can have less restrictive licensing.
Unfortunately for my project (not related to Arduino) I cannot use any license requiring exposure of proprietary sources.
Could you please license your algorithm on same terms as the Hacker Delight's book?

Thanks in advance

samepaul:
Could you please license your algorithm on same terms as the Hacker Delight's book?

What a strange world we live in, in which dividing two numbers requires a license!

1 Like

Copying someone’s code requires a license, regardless of what it does.