- The number to be divided is multiplied by 256 or 65,536 and stored in the upper one or two bytes of the result. The additionally needed lower 8 or 16 bits are cleared.
- These two (8-bit numbers) or four (16-bit numbers) bytes are copied to additional two or four bytes.
- Now the copy of the number is repeatedly divided by two, until nothing is left over. Following each division by 2 the divided number is either subtracted from the result or not. Depending from the subtraction pattern applied, the divisor value is selected. As an example: one with subtraction and one without subtraction divides by three.
- If the copied and divided number is empty, the result is in the two or four registers: if an 8-bit number was divided, the MSB of the result is the division result, if 16-bit were treated, the upper two of the four-byte result are the division result.
- If the next lower byte is larger or equal 0x80, the result has to be rounded up by adding one.

The number, here 255, is divided by the divisor, which yields the target value.

Now the number we started with is divided by two, four, eight and sixteen, etc. in the first and second row. The third row determines if the divided number has to be subtracted: if the subtracted value is smaller than the target value, then this is not subtracted (0). If the subtracted value is larger or equal the target value, then subtraction has to be done. The fourth column holds the result. With each further subtraction the result value comes nearer to the target value (column delta).

If the lower byte of the result is equal or larger than 0.5, the result is to be rounded up.

The row of ones and zeros in the column 4 is always the same, no matter with which number we started with. It is a specific pattern for this divider. The start number must not be too small, otherwise you loose some lower bits at the end. 128 is in any case sufficient. As can be seen, the bit pattern for three is simply 10 and repeats over and over. It's period length is two. Not all bit pattern have such simple periods, as we will see later on.

The bit pattern can simply be applied in a very simple assembler source code. Only the two- or four-byte bit pattern is needed, together with two or four additional register bytes. The source code demonstrating this is here. Just add the bit pattern on top of the code, and it divides by another divider. Just copy the hex text from the LibreOffice sheet and run the program in a simulator, such as avr_sim.

After lots of steps, shifting and subtracting, the result is in rRH (R17). It should be correct. The time needed for that, 165 clock cycles, shows that the division is not very fast. But we'll see later on how we can accelerate that.

This here shows selected rows for dividing 8-bit numbers. Given are

- the divider,
- the bit pattern in binary and hexadecimal format,
- the number of clock cycles when dividing 255, plus
- the number of clock cycles that simple repeated subtraction of the divisor from the number would need.

As additional example the source code for dividing by 1.1 is given here. The program assembles to 20 words flash code and needs 96 clock cycles for dividing 255 by 1.1.

Compared to the method with repetitive subtraction of the divider my method is faster for all dividers equal or below six. Only if accelerated by first dividing by a larger divider and then shifting the result right (/2, /4, /8, /16) plus rounding the repetitive subtraction method is faster.

The Schmidt-method is only attractive for cases where non-integer dividers have to be used or when no acceleration is possible for the repetitive subtraction method.

Or: if we accelerate the Schmidt-method.

If the number to be divided is small, its division by two reaches zero after a few cycles. If the divided number is zero, we can end earlier and do not have to divide 16 times and subtract the zeros from the result. And further: if the upper byte is already zero and the lower byte of the subtractor is smaller than the lower byte of the result, any further subtraction cannot alter the MSB any more. This saves you a lot of dividing and subtracting without any effect on the result.

But this has the disadvantage that rounding the result is not possible at the early end, because the accelerated break leaves results with a too high LSB. So, rounding is not done at the end but from the early beginning on: we add little more than half the divisor to the number. That leaves an irrelevant LSB at the end, but a correct up-rounded MSB.

That adding the round-up from the beginning has the disadvantage that not the whole 8- or 16-bit range can be used. Depending from the divider, the upper part of the range gets unusable. I gues you can live with that in practice.

The optimized dividing can be tested in the spreadsheet here, in the sheet "8bit-optimized". Dividing by 3 means adding roughly 1.5 to the number, so the range of possible numbers does not include 255. So we start with 254. The exact adder can be copied from the spreadsheet directly into the source code file.

Now it can be seen in the first column that the two criteria for the break already stops the execution after 10 cycles, we don't have to do all 16 (even though we are starting with a high number). If the number is smaller, then the break appears even earlier.

As already mentioned above, the bit pattern of a three, as divider, repeats already after two divisions. Therefore we really do not need the whole pattern: 14 out of 16 bits are useless information. So we can skip the two registers for the bit pattern and the LSR/ROR instructions, too.

This is the algorithm that the source code div3_8.asm here demonstrates. With 19 instruction words and in ultrafast 56 clock cycles the whole procedure is done. And: with 254 as divident.

The picture to the right illustrates the steps that the software performs. When dividing 100, one further clock cycle is necessary. The

- loading of the number requires one cycle,
- adding 1.3988 (for rounding) needs 5 additional cycles,
- copying needs only two cycles,
- twi right rotations and subtraction needs two clock cycles each,
- a further right rotation without subtraction needs a little bit longer, because of the included checks if the MSB is empty and the LSB is smaller than the LSB of the result,
- further executions after these conditions are met can be skipped.

- three subtractions, and
- five divisions by 2, plus
- two further condition tests.

The drawing is available in the graphic file here in LibreOffice draw format.

Promised too much? Nope.

Here are some further source codes with fixed dividers for your own experiments.

Divide by | periods | Binary bit pattern | Source code | Cycles | Words |
---|---|---|---|---|---|

1.5 | 2 | 0b1010101010101010 | div1_5_8 | 52 | 15 |

2.5 | 4 | 0b1001100110011001 | div2_5_8 | 56 | 25 |

6 | 1+3 | 0b0100100100100101 | div6_8 | 49 | 23 |

7 | 3 | 0b1011011011011011 | div7_8 | 50 | 25 |

Much success with the new and ultrafast 8-bit division codes.

The bit pattern now has 32 bits. The start value for that determination is a large number, to avoid any rounding errors in the last bits. Following the last division by two, / 4.294.967.296, always zero results. Applying the same formula as in the cases above would lead to always one, the first binary digit of the bit pattern would be one. Because it doesn't matter if you subtract a zero from the result or not, this highest bit is insignificant. In later tables it is set to whatever value that fits best to the period length and pattern.

When dividing on the right side of the spreadsheet, the bit pattern on the left is applied. In a first step the rounding adder is determined. For numbers smaller than 10 this is the 0.51-fold of the divider, here that is 1.52999 or hexadecimal 0x000187AE. Just copy the hexadecimal formatted number to the source code's rounding adder

Those adders, and all result numbers, are down-rounded binaries, converted to decimals. When dividing by two and during subtraction no rounding up of the result is applied, to avoid these unnecessary rounding instructions. It works as it is, so rounding is unnecessary.

The following table lists the bit patterns and the rounding adders for the dividers 1.1, 1.5 and 2.5 plus those for 3 to 30 (except those for 4, 8 and 16). Those who need other dividers, such as 3.141592654, can use the spreadsheet here to determine the bit pattern and the rounding adder.

Divide by | Bit pattern: row of binary dividers to be subtracted 0=no subtraction, 1=subtract | Rounding | |||
---|---|---|---|---|---|

binary | hex | Period- length | decimal | hex | |

1.1 | 0b01001110100010111010001011101000 | 0x4E8BA2E8 | 10 | 0.561005 | 0x00008F9E |

1.5 | 0b10101010101010101010101010101010 | 0xAAAAAAAA | 2 | 0.764999 | 0x0000C3D7 |

2.5 | 0b10011001100110011001100110011001 | 0x99999999 | 4 | 1.274994 | 0x00014666 |

3 | 0b01010101010101010101010101010101 | 0x55555555 | 2 | 1.529999 | 0x000187AE |

5 | 0b00110011001100110011001100110011 | 0x33333333 | 4 | 2.550003 | 0x00028CCD |

7 | 0b11011011011011011011011011011011 | 0xDB6DB6DB | 3 | 3.570007 | 0x000391EC |

9 | 0b11000111000111000111000111000111 | 0xC71C71C7 | 6 | 4.589996 | 0x0004970A |

10 | 0b01100110011001100110011001100111 | 0x66666667 | 1 + 4 | 5.009995 | 0x0005028F |

11 | 0b01010001011101000101110100010111 | 0x51745D17 | 10 | 5.511002 | 0x000582D1 |

12 | 0b01010101010101010101010101010111 | 0x55555557 | 2+2 | 6.011993 | 0x00060312 |

13 | 0b00110111001000110111001000110111 | 0x37237237 | 12 | 6.513000 | 0x00068354 |

14 | 0b10110110110110110110110110110111 | 0xB6DB6DB7 | 1+3 | 7.014008 | 0x00070396 |

15 | 0b01110111011101110111011101110111 | 0x77777777 | 4 | 7.514999 | 0x000783D7 |

17 | 0b00001111000011110000111100001111 | 0x0F0F0F0F | 8 | 8.516998 | 0x0008845A |

18 | 0b01001110001110001110001110001111 | 0x4E38E38F | 1+6 | 9.018005 | 0x0009049C |

19 | 0b00000101001111010110000101001111 | 0x053D614F | 18 | 9.518997 | 0x000984DD |

20 | 0b11001100110011001100110011001111 | 0xCCCCCCCF | 2+4 | 10.020004 | 0x000A051F |

21 | 0b11001111001111001111001111001111 | 0xCF3CF3CF | 12 | 10.520996 | 0x000A8560 |

22 | 0b01100010111010001011101000101111 | 0x62E8BA2F | 1+10 | 11.022003 | 0x000B05A2 |

23 | 0b11001011110110010111101100101111 | 0xCBD97B2F | 11 | 11.522995 | 0x000B85E3 |

24 | 0b10101010101010101010101010101111 | 0xAAAAAAAF | 3+2 | 12.024002 | 0x000C0625 |

25 | 0b00111010111100010100001110101111 | 0x3AF143AF | 20 | 12.524994 | 0x000C8666 |

26 | 0b00101110010001101110010001101111 | 0x2E46E46F | 1+12 | 13.026001 | 0x000D06A8 |

27 | 0b10000101101111010010000101101111 | 0x85BD216F | 18 | 13.526993 | 0x000D86E9 |

28 | 0b01101101101101101101101101101111 | 0x6DB6DB6F | 2+3 | 14.028000 | 0x000E072B |

29 | 0b11110010110001000011010011101111 | 0x72C434EF | 32 | 14.529007 | 0x000E876D |

30 | 0b11101110111011101110111011101111 | 0xEEEEEEEF | 1+4 | 15.029999 | 0x000F07AE |

As you can see from the table, only 29 does not have a periodic pattern. With all others the period length is shorter than 32. In some cases, one or two steps prior need to be considered to have a period, e.g. in the cases 12, 14, 18, 22, 24, 26 and 30. Those cases have a "1 +" etc.

Again, the rounding adder is 0.501 rather than 0.51 for dividers from 10 upward.

The following table links assembler source code files for selected dividers and bit patterns, so you can use them as starting point for your own. The necessary clock cycles for dividing zero (minimum) and the largest possible (maximum) number to be divided. Also given are the number of instruction words.

Divider | Periods | Source code | Clock cycles | Instruction words | |
---|---|---|---|---|---|

min. | max. | ||||

3 | 2 | div3_p2_16 | 95 | 200 | 36 |

7 | 3 | div7_p3_16 | 112 | 204 | 44 |

14 | 1+3 | div14_1p3_16 | 166 | 281 | 52 |

5 | 4 | div5_p4_16 | 101 | 182 | 48 |

div5_p4v_16 | 99 | 215 | 50 | ||

10 | 1+4 | div10_1p4_16 | 109 | 190 | 56 |

div10_1p4v_16 | 105 | 208 | 66 | ||

21 | 6 | div21_p6_16 | 108 | 196 | 65 |

11 | 10 | div11_p10_16 | 88 | 226 | 89 |

29 | 32 | div29_p32_16 | 447 | 43 | |

19 discrete | div29_14_16 | 110 | 111 | ||

Classical | divN_16_8 | 217 | 24 |

If two different source code files are given for the same divider, the second one has an extra break detection added in between, which causes extra clock cycles. As you see in the cases 5 and 10, such additional break detections make not much difference with small numbers, but add relevant execution time for larger numbers.

When dividing by 29, the first code linked packs the whole bit pattern 0x72C434EF into four registers and shifts those one position to the right, to determine whether to subract or not. If the lowest byte of those four registers is zero, the further execution is skipped. In that case all 32 divisions by two together with 17 subtractions are executed. Therefore this needs 447 clock cycles, the longest of all. But this is the one with the lowest number of instruction words of all Schmidt-divisions.

The second case for 29 demonstrates that there is lots of optimization potencial here. The 29 needs at maximum only 17 divisions by two, of which the last three do not need to subtract. So we are already done at 14 divisions by 2 and 10 subtractions. No need to check break conditions in between adds further execution speed. This yields the longest program with 111 instruction words, but it performs all this in very fast 110 clock cycles. And it needs these cycles independant of the number to be divided. One can see that there is much to win in the Schmidt-method with some intelligence.

- the classical method produces the shortest controller code (whoever needs to save flash uses this),
- the execution times of the Schmidt-method are mostly shorter than with the classical method, except for large numbers and dividers of 11 and 14 (execution time in the classical style is always the same),
- you can save lots of execution time if you fit the source code to exactly your own needs, as has been demonstrated with the division by 29.

To the page top

©2021 by http://www.avr-asm-tutorial.net