How to speed up the division?

[Nikitos]

Hello again. I started to work with 4 bytes variable. I need to divide variable by 300 and 3000. By my tests I need more than 70 us to divide variable. If to compare with multiplication = less 10 us. So by this way I have a question. Is it possible somehow to reduce the time of the division operation? I can not change 300 and 3000 to numbers of bits shifting. In internet I found next list how to make division faster

Code: Select all

Divide by 3: (((uint32_t)A * (uint32_t)0xAAAB) >> 16) >> 1
Divide by 5: (((uint32_t)A * (uint32_t)0xCCCD) >> 16) >> 2
Divide by 6: (((uint32_t)A * (uint32_t)0xAAAB) >> 16) >> 2
Divide by 7: ((((uint32_t)A * (uint32_t)0x2493) >> 16) + A) >> 1) >> 2
Divide by 9: (((uint32_t)A * (uint32_t)0xE38F) >> 16) >> 3
Divide by 10: (((uint32_t)A * (uint32_t)0xCCCD) >> 16) >> 3
Divide by 11: (((uint32_t)A * (uint32_t)0xBA2F) >> 16) >> 3
Divide by 12: (((uint32_t)A * (uint32_t)0xAAAB) >> 16) >> 3
Divide by 13: (((uint32_t)A * (uint32_t)0x9D8A) >> 16) >> 3
Divide by 14: ((((uint32_t)A * (uint32_t)0x2493) >> 16) + A) >> 1) >> 3
Divide by 15: (((uint32_t)A * (uint32_t)0x8889) >> 16) >> 3
Divide by 30: (((uint32_t)A * (uint32_t)0x8889) >> 16) >> 4
Divide by 60: (((uint32_t)A * (uint32_t)0x8889) >> 16) >> 5
Divide by 100: (((((uint32_t)A * (uint32_t)0x47AF) >> 16U) + A) >> 1) >> 6
Divide by PI: ((((uint32_t)A * (uint32_t)0x45F3) >> 16) + A) >> 1) >> 1
Divide by √2: (((uint32_t)A * (uint32_t)0xB505) >> 16) >> 0

Somebody tried this?

[darko.minic]

Hi,

Dividing is more complex operation for MCU than multiplication, therefore it takes more time for dividing.
For fast divide it is best to use MCUs with hardware dividers.
However there is some trick which can be found on internet.

I tried to divide by 300 using your list (first with 3 and then with 100), it takes 24.25us for complete division by 300.

Regards,
Darko

[aCkO]

I tried to divide by 300 using your list (first with 3 and then with 100)

This won't work for integer division.

@Nikitos
This method is called reciprocal multiplication and has been around for a long time. However it is used mainly for dividing 16-bit integer by a constant. If you want to use it for long integers you have to be careful that the first product doesn't overflow, but then it's use becomes limited.

Check these links:
http://homepage.cs.uiowa.edu/~jones/bcd/divide.html
http://www.hackersdelight.org/divcMore.pdf

Regards

[Nikitos]

Thanks.