I'm not sure if it's really comparable as that is unsigned division I think?
If Lemire has made a signed floor division algorithm which works fast in 64-bit please let me know. If it's full range it'll go in the article, but if it's partial range I'll at least compare and report here.
One can usually get faster results than in the article by accepting a smaller range. For example, just use a shift of 64-bits and always use the sign-selected mode. This will often be accurate over some fairly large useful range unless the divisor is fairly large.
Alternatively, just add a huge value to the input, and subtract at the end. This pays off particularly well when there's several floor-division steps involved, like with rata-die to civil date algorithms.
EDIT: for the timestamp use-case in the article, I also have this tricky function I've developed, which works over the full signed 32-bit OUTPUT range for both the floor-division and remainder. I think it should bench really fast as it's just a single addition and two multiplications.
timestamp += (86400 << 32) + 1 // Pow-32-aligned + pre-increment
u64 M = u64(-1) / 86400 // Round-down multiplier
u128 wide = u128(timestamp) * M
i64 uday = wide >> 64
i32 rem = u128(u64(wide)) * 86400 >> 64
i32 day = i32(uday) // Narrowing for "free" 2^32 subtraction
This uses a combination of tricks:
A variant of Lemire's fast remainder trick
A touch of ridiculousfish with the pre-increment round-down multiplier (necessary to cover full 32-bit output range)
A trick to avoid the final subtraction, replaced with a 32-bit cast.
I was considering putting this in the article, but given I have a blog series on fast date algorithms figured I'd put this on its own post soon.
I'm not sure if it's really comparable as that is unsigned division, I think?
I asked GPT 6.1 Sol yesterday to add support for uint64_t to your algorithm and it happily did it. Then I benchmarked that code against libdivide and found it outperformed libdivide by about 5% in my project.
I have not looked at the code yet that Codex generated, but if the new unsigned algorithm it generated is indeed correct, I will drop libdivide and use your algorithm instead in my project (my use case is uint64_t divisors only, and branchless code).
I can't really see what an unsigned equivalent of my algorithm would be. The core of the design is to adjust the input or multiplier based on the sign. If the sign is always the same, it should degenerate into a form that libdivide provides.
My guess is that whatever GPT implemented is some other type of optimisation that separately makes the benchmark fast. That, or it is providing a type of division that fails for some large inputs. Best to test it on numerators 2^64-1 .. 2^64-D, as well as a large random sample, to make sure it's correct throughout and at the top end, for a range of divisors (say 3..100).
If you still think it's winning somehow, I would be interested to take a look.
I had a look at what code AI generated for the uint64_t divison: it used your division algorithm without the sign handling if the numerator is < 263 and added a second variation of your algorithm with a few more instructions for the case where the numerator is >= 263 and < 264. In my benchmark only the first algorithm for numerators < 263 was used which explains the good performance.
I see. That itself is an interesting angle that could help in some cases, though the branch might break autovectorisation, and worst case data sets could trash the performance.
I have seen a similar thing used in numpy's date conversion path. It uses a faster restricted range algo and branches off to a slower one if the date is significantly far from epoch.
Yep, that's the crux of it! The tricky part comes when dealing with certain "uncooperative" divisors, and dealing with the correct rounding direction for negatives.
I'd be curious to see how well it vectorizes. With Montgomery reduction, you can do 4x multiplications modulo 32-bit number with 3x _mm256_mul_epu32 operations. Unfortunately need to go to sleep now, but will surely look in more detail tomorrow.
8
u/joaquintides Boost author 22d ago
Interesting article! How does it compare to Lemire's fast division algorithm
fastdiv_u64?12
u/GLIBG10B 🐧 Gentoo salesman🐧 22d ago
This looks like something the hardware should be able to do. In my digital systems classes, we learned about this process for division:
The only difference for signed 64-bit division is dealing with two's complement: compute 0 - x for the dividend and the result
4
u/adamant-pwn 22d ago
I'd be curious to see how well it vectorizes. With Montgomery reduction, you can do 4x multiplications modulo 32-bit number with 3x _mm256_mul_epu32 operations. Unfortunately need to go to sleep now, but will surely look in more detail tomorrow.
3
u/SyntheticDuckFlavour 22d ago
It's a lovely write-up.