Hacker News Reader

Comment by leni536 | Hacker News Reader

These are the five numbers in binary, to give some inspiration for a bit twiddling algorithm:

                          110
                        11100
                    111110000
                1111111000000
    1111111111111000000000000

View on HN

Hmm, I can't think of a way to use the mathematical structure of those numbers to speed up checking.

However, the reason I said AVX is because it can be used for checking equality of 5 (well, 8) numbers simultaneously. This solution requires AVX2 and is probably faster than the optimized reference code.

    // Copy x to all 8 elements.
    __m256i a = _mm256_set1_epi32(x);
    // Duplicate 6 because we need to fill all 8 elements.
    __m256i b = _mm256_set_epi32(6, 28, 496, 8128, 33550336, 6, 6, 6);
    // Check for element-wise equality.
    __m256i c = _mm256_cmpeq_epi32(a, b);
    // Check if any bytes are nonzero.
    return _mm256_movemask_epi8(c) != 0;

https://godbolt.org/z/6W8rZy

I have a hunch that the actually fastest version is to change all those "||" to "|" in the original version. Short-circuiting and adding branches probably just slows the whole thing down compared to just running the comparisons, which will probably pipeline really well.

Interestingly the compiler doesn't do this optimization, even though it could. So maybe I'm wrong. No real way to know without benchmarking, though.

Good idea. This does change the optimized assembly, but it doesn't seem to make a measureable difference in performance on my machine.

I’d benchmark that before being sure.

It might not be faster, but unfortunately the computer I'm typing this on doesn't support AVX2. :(

Seems to be faster, did a crappy shell benchmark. It takes 5.7 seconds to run that SIMD function INT_MAX times, compared to 6.6 seconds for the original. MacBook Air, late 2014, clang, -O3 -mavx2

The even perfect numbers all have the formula

    2^(p - 1)(2^p - 1)

for some prime `p`. In code that's

    ((1 << p) - 1) << (p - 1)

for `p` = 2, 3, 5, 7 and 13, which is why you're seeing that interesting pattern of bits.

(There are no odd perfect numbers in the range under consideration.)

You should also note that there are no known odd perfect numbers, period. Any that do exist must exceed 10^1500.

One things that comes to mind: popcnt(x^(x>>1))==2 for all 5 numbers. Maybe the checking function could start with that condition, then fall back to the slower one-by-one check when that evaluates to two. For most numbers the popcnt check would fail.

edit: Not to mention that all 5 numbers are even, so a parity check could also help for odd number inputs (but it makes it slower for even numbers). I do not think that AVX has anything to offer here though.

It might matter then what cases you need to optimize for, which statistics are most important, and what instruction set you are using.

Sure, my tricks are mostly aimed for improving the average performance for uniform inputs between 0 and 2^32-1.

Edit: And yeah, you need a fast popcnt here.

Reply on news.ycombinator.com