Fastest way to get integer mod 10 and integer divide 10?

Assuming unsigned integers, division and multiplication can be formed from bit shifts. And from (integer) division and multiplication, modulo can be derived.

To multiply by 10:

y = (x << 3) + (x << 1); 

To divide by 10 is more difficult. I know of several division algorithms. If I recall correctly, there is a way to divide by 10 quickly using bit shifts and subtraction, but I can't remember the exact method. If that's not true, then this is a divide algorithm which manages <130 cycles. I'm not sure what micro you're using, but you can use that in some way, even if you have to port it.

EDIT: Somebody says over at Stack Overflow, if you can tolerate a bit of error and have a large temporary register, this will work:

temp = (ms * 205) >> 11; // 205/2048 is nearly the same as /10 

Assuming you have division and multiplication, modulo is simple:

mod = x - ((x / z) * z) 

You can convert from binary to packed BCD without any division using double dabble algorithm. It uses only shift and add 3.

For example convert 243₁₀ = 11110011₂ to binary

0000 0000 0000 11110011 Initialization 0000 0000 0001 11100110 Shift 0000 0000 0011 11001100 Shift 0000 0000 0111 10011000 Shift 0000 0000 1010 10011000 Add 3 to ONES, since it was 7 0000 0001 0101 00110000 Shift 0000 0001 1000 00110000 Add 3 to ONES, since it was 5 0000 0011 0000 01100000 Shift 0000 0110 0000 11000000 Shift 0000 1001 0000 11000000 Add 3 to TENS, since it was 6 0001 0010 0001 10000000 Shift 0010 0100 0011 00000000 Shift 2 4 3 BCD 

This algorithm is very efficient when there's no hardware divisor available. More over only left shift by 1 is used, so it's fast even when a barrel shifter is not available

Depending on the amount of digits you need you may be able to use the brute force method (d - input number, t - output ASCII string):

t--; if (d >= 1000) t++; *t = '0'; while (d >= 1000) { d -= 1000; *t += 1; } if (d >= 100) t++; *t = '0'; while (d >= 100) { d -= 100; *t += 1;} if (d >= 10) t++; *t = '0'; while (d >= 10) { d -= 10; *t += 1;} t++; *t = '0' + d; 

You can also change the multiple ifs into a loop, with powers of ten obtained by multiplication or a lookup table.

Application note AVR204 describes algorithms for BCD arithmetic, including conversion from binary to BCD and vice versa. The appnote is by Atmel, which is AVR, but the described algorithms are processor-independent.

I don't have a good answer, but there's a great discussion on our sister site Stack Overflow on the exact same subject of division and modulo optimization.

Do you have enough memory to implement a lookup table?

Hackers Delight has a paper on optimal division algorithms.

Have you considered holding that value as BCD all the time (using simple special "BCD increment" and "BCD add" subroutines), rather than holding that value in binary form and converting to BCD as needed (using a more difficult to understand "convert from binary to BCD" subroutine)?

At one time, all computers stored all data as decimal digits (ten-position gears, two-out-of-five code vacuum tubes, BCD, etc.), and that legacy still lingers on today. (see Why do real-time clock chips use BCD ).

The PICList is an amazing resource for people programming PIC processors.

BCD conversion

Have you considered using an off-the-shelf tried-and-tested binary-to-BCD subroutine specifically optimized for the PIC16F?

In particular, people on the PICList have spent a lot of time optimizing binary-to-BCD conversions on a PIC16F. Those routines (each one hand-optimized for a specific size) are summarized at "PIC Microcontoller Radix Conversion Math Methods" http://www.piclist.com/techref/microchip/math/radix/index.htm

integer division and mod

On a CPU like the PIC16F, a subroutine specialized to divide by a constant is often much faster than a general-purpose "divide variable A by variable B" routine. You may want to put your constant (in this case, "0.1") in the "Code Generation for Constant Multiplication/Division" http://www.piclist.com/techref/piclist/codegen/constdivmul.htm or check out the canned routines near http://www.piclist.com/techref/microchip/math/basic.htm .

Given an 8x8 hardware multiply, one can compute a divmod-10 of an arbitrary-size number by using a routine which computes it for 12-bit number in the range 0-2559 via the procedure:

1. Assume original number in OrigH:OrigL
2. Divide the original number by two and store that in TempH:TempL
3. Add the MSB of TempL*51 to the LSB of TempH*51. That is the approximate quotient
4. Multiply the approximate quotient by 10, discarding the MSB of the value.
5. Subtract the LSB of that result from the LSB of the original number.
6. If that value is 10 or greater (max will be 19), subtract 10 and add 1 to the approximate quotient

I would suggest writing a divmod routine which the MSB of the number will be in W, and the LSB pointed to by FSR; the routine should store the quotient in FSR with post-decrement and leave the remainder in W. To divide a 32-bit long by 10, one would then use something like:

 movlw 0 lfsr 0,_number + 3 ; Point to MSB call _divmod10_step call _divmod10_step call _divmod10_step call _divmod10_step 

A divmod-6 step would be very similar, except using constants of 85 and 6 rather than 51 and 10. In either case, I would expect the divmod10_step would be 20 cycles (plus four for the call/return) so a short divmod10 would be about 50 cycles and a long divmod10 would be about 100 (if one special-cases the first step, one could save a few cycles).

this may not be the fastest but is a simple way.

 a = 65535; l = 0; m = 0; n = 0; o = 0; p = 0; while (a >= 10000) { a -= 10000; l += 1; } while (a >= 1000) { a -= 1000; m += 1; } while (a >= 100) { a -= 100; n += 1; } while (a >= 10) { a -= 10; o += 1; } while (a > 0) { a -= 1; p += 1; }