Crates.io | fastdivide |
lib.rs | fastdivide |
version | 0.4.1 |
source | src |
created_at | 2017-06-13 13:14:52.329928 |
updated_at | 2024-04-01 06:41:16.264222 |
description | Fastdivide is a partial port of libdivide. It makes it possible to reduce the cost of divisions. |
homepage | |
repository | https://github.com/fulmicoton/fastdivide |
max_upload_size | |
id | 18838 |
size | 15,370 |
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 u64
integers.
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 fastdivide
is to apply the same trick by letting you precompute a DivideU64
object.
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.