Fastest Leap method

I found this on how to do Leap very fast when I was working on my MIPS version. I thought others might be interested. Note I have updated my C and other versions of Leap to use this method it is pretty cool. I also made a version of it with Nasm for that track.

4 Likes

@krperry Would you be interested in writing this up in a blog post that we then publish on the website?

I could do that this weekend. I got a tasking from PNC yesterday and need to finish it up. If someone gets to it first I will not be offended. I really like this method it is a brilliant use of factoring and bit twiddling.

If I write this do you want the code for Nasm and for Mips? Should I show it in C or anything else like Javascript? It seems to work for most of the C like languages. Or should this just be a Blog about the Algorithm.

I think showing a few languages would be nice (JS, C, MIPS?), but I think the key thing is the algorithm/performance itself and discussing that. So maybe starting off with one language (I’d suggest JS as it’ll get the most virility as a result) and then maybe at the bottom show in a couple of other languages.

Can do. Who should I send it to for review and how. ?

1 Like

A PR to the blog repo please. See this as a recent example: Add hello world article by iHiD · Pull Request #191 · exercism/blog · GitHub

You only need to do the markdown file. We’ll add config.

Also, tell me if you’ve got a photo of yourself you’d like me to include in the thumbnail.

Thanks! :slight_smile:

I posted a blog on the posts and then left a new topic as the pull request requested. I am not sure I did everything right so let me know.

1 Like

I added the picture to the pull request.

For anybody else looking for it, here’s a link to the pull request:

1 Like

@krperry Thanks! We’ll take a look next week :slight_smile:

Looking at the SO post, I was wondering whether that is actually the best you can do, because it still involves branches. With operations this cheap, at least on modern x86 CPUs, a branch prediction miss can be very costly and outweigh the benefit of being able to early return (because the operations we save by early returning are actually cheaper than having to flush the pipeline). Somebody added this argument along with benchmark results here: How to find leap year programmatically in C - Stack Overflow

Before finding the other answer to the SO question I actually put together a trivial branchless version on QuickBench by simply replacing logical with bitwise operations. I now also added the version from the post with most votes: Quick C++ Benchmarks
Turns out that with GCC, this is actually slower than the straightforward implementation. With Clang it’s on par, but not faster.

Bottom line, always run your own benchmarks on the target system.

Well in truth I was using this with Mips and X86 and had no logical just the three terms in a step by step method which is as good I think as it gets. I didn’t think of switching to bitwise in c and the other languages but I can see how that would help the compilers know what to compile down to. Everyone feel free to regect this whole post. I probably just jumped the gun with the title. I probably just should have called it a Reduced method of doing it. Then everyone would not have their pants in a knot. Enjoy the post. Dump the post. Shrug.

Maybe ERic and jeromy can just do a video and talk about this all.

I didn’t mean to say the post should be dumped or anything! I think it’s very valuable to be aware of those things. How much a difference branching makes I only learned a couple of months ago myself. What I wanted to point out was that the reformulation from the top-voted SO post is just one way of optimizing this and that it can happen that there’s no benefit at all, in which case I would prefer the more readable solution.