### 6 releases (3 breaking)

new 0.4.2 | Nov 1, 2024 |
---|---|

0.4.1 | Apr 1, 2024 |

0.4.0 | Jan 27, 2022 |

0.3.0 | Feb 22, 2021 |

0.1.0 | Jun 13, 2017 |

#**105** in Data structures

**295,665** downloads per month

Used in **131** crates
(13 directly)

**zlib-acknowledgement OR MIT**

13KB

211 lines

# FastDivide...

FastDivide is a simple/partial RUST port of libdivide by ridiculous_fish Libdivide is distributed under the zlib license, so does fast divide.

This port is only partial :
It only include one implementation of division for

integers.`u64`

# Yes, but what is it really ?

Division is a very costly operation for your CPU. You may have noticed that when the divisor is known at compile time, your compiler transforms the operations into a cryptic combination of a multiplication and bitshift.

The key idea is that, rather than computing

`N ``/` D

It is faster to compute (with k sufficiently large)

`N ``*` `(` `2``^`k `/` D `)` `/` `(``2``^`k`)`

If D is known in advance, (2^k / D) can be precomputed by the compiler.

Unfortunately if the divisor is unknown at compile time, the compiler cannot use this trick.

The point of

is to apply the same trick by letting you precompute a `fastdivide`

object.`DivideU64`

# When is it useful ?

If you do a lot (> 10) of division with the same divisor ; and this division is a bottleneck in your program.

This is for instance useful to compute histograms.