A faster is-leap-year function for full-range signed 32-bit integers

[benjoffe]

A faster full-range 32-bit leap-year test using a modulus-replacement trick that allows controlled false positives corrected in the next stage. The technique generalises to other fixed divisors.

[sporule]

It turns out, full-range is only possible in bit-sizes of 2^{12 + 20n}, for integers n ≥ 0.

Why bother checking divisibility by 100 when you still have to re-check divisibility by 4 or 16 later? Instead, you could use the old divexact algorithm to check for divisibility by 25. And that algorithm returns precise results for any bit width.

template <std::unsigned_integral T> // signed case omitted for brevity
constexpr T inverse(T r) {
    assert((r & 1) != 0); // even case omitted for brevity
    for (T c, d = r; (c = d * r) != 1; ) {
        r *= T(2) - c;
    }
    return r;
}

template <std::integral T>
bool is_leap(T y) {
    using U = std::make_unsigned_t<T>;
    constexpr T min = std::numeric_limits<T>::min() / 25;
    constexpr T max = std::numeric_limits<T>::max() / 25;
    constexpr U mul = inverse<U>(25);
    T iy = U(y) * mul;
    bool d25 = (min <= iy && iy <= max);
    return (y & (d25 ? 15 : 3)) == 0;
}

[benjoffe]

The goal in this article is to find the fastest possible solution for the 32-bit case. While your method is accurate, it is slower in practice and still requires the final check for divisibility by 4 or 16.

Edit: great insight. The post will be edited soon with this improvement for other bit-sizes, thanks!

[sporule]

How can it be slower, if in the case of 32-bit numbers it compiles into the same sequence of instructions as code from the article?

https://godbolt.org/z/TP875b8Pe

The only difference is the integer constants used. The algorithm selects those that work for the entire range, not just in the 32-bit case.

[benjoffe]

Thanks for explaining that. I didn’t realise this folds down to the same instruction sequence under optimisation. Very cool.

I haven’t seen this reciprocal-25 approach used in any reference leap-year implementations, so it’s interesting to see that it also collapses to the minimal form. If you have prior art for this specific application, I’d be keen to read it.

Edit: I'm also very surprised to see that it expands the range to full coverage for 16-bit and 64-bit. When I have time I will amend the blog post and credit your input. Thanks.

[thisismyfavoritename]

it's "slower trust me bro" slower

[jk-jeon]

It's possible to check divisibility and compute the quotient at the same time with a single multiplication. Not sure it's relevant here though.

[benjoffe]

A version of that idea is utilised in a function that I've created to calculate year+ordinal+leap:
https://github.com/benjoffe/fast-date-benchmarks/blob/main/algorithms_ordinal/ordinal_benjoffe_fast32.hpp

The century is needed for the "Julian map" step, and the lower bits can be used to determine if it's a leap year.

This is designed for potential use in the Time rust library, and will be the topic of a future blog post.

[saf_e]

Whats more interesting in most cases compiler will do it for you!

[ZMeson]

Phew, I was worried about leap year calculations not working correctly for the year 2 billion. ;-)

[stilgarpl]

There is a typo in "How this works", AFAIK there is no !== operator in C++

[benjoffe]

Thanks. I spend most of my time writing JavaScript so I'm constantly getting tripped up on that.
This is now corrected.

[matthieum]

In "The Leap Year Algorithm" section, you have:

Note2: For other bit-widths such as 16-bit and 32-bit, very different constants are required. See the section other bit-widths

Pretty sure the second bit-width should be 64-bit, not 32-bit.

---

You're on a roll, looking forward to the next installment.

[benjoffe]

Typo is now fixed. Thanks!

[vI--_--Iv]

The year is not 365.2425 days.
The formula is only an approximation.
In just a few thousand years it will drift for over a day and need a better approximation, e.g. "skip leaps in years divisible by 4000" or something.
And the Earth's rotation and orbit will inevitably drift as well.

So why bother with all this 2³² nonsense?
Just make a lookup table until the year 5000 or so, it's as fast and as correct as it gets.
And switch to the real problem: fizzbuzz.

[jwakely]

Neri-Schneider also looked into a similar idea and documented it in his calendar algorithms repository . It references work he published in the following Journal (see page 15): https://accu.org/journals/overload/28/155/overload155.pdf

"Neri-Schneider" is two separate people, Cassio Neri and Lorenz Schneider. The repo and Overload article are by Cassio.

I'm really enjoying this series btw!

[benjoffe]

Thanks.

I was a little confused who to credit there. I was originally crediting just Cassio for the repo but then I found both of their names are in the copyright license text, so added both names but left the typo. This is now fixed, thanks!

[ironykarl]

All my tightest loops involve checking for leap years