4 ms·
#1 got me and I had a good laugh. I wonder if there's a faster method for #2 using AVX and bit tiddling, or if the optimizer is smart enough to find the most ef
by vortico 7y ago
#1 got me and I had a good laugh. I wonder if there's a faster method for #2 using AVX and bit tiddling, or if the optimizer is smart enough to find the most efficient code for a particular architecture.
- leni536 7y agoThese are the five numbers in binary, to give some inspiration for a bit twiddling algorithm: 110 11100 111110000 1111111000000 1111111111111000000000000
- leni536 7y agoOne 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.
- zzo38computer 7y agoIt might matter then what cases you need to optimize for, which statistics are most important, and what instruction set you are using.
- leni536 7y agoSure, 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.
- amptorn 7y agoThe 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.)
- pmiller2 7y agoYou should also note that there are no known odd perfect numbers, period. Any that do exist must exceed 10^1500.
- vortico 7y agoHmm, 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 https://godbolt.org/z/6W8rZy
- saagarjha 7y agoI’d benchmark that before being sure.
- vortico 7y agoIt might not be faster, but unfortunately the computer I'm typing this on doesn't support AVX2. :(
- deleted 7y ago[deleted]
- x0 7y agoSeems 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
- OskarS 7y agoI 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.
- abnry 7y agoGot me to laugh too! I thought I was clever with my O(n) solution. Let A be the original array and let B be the sorted array. Just loop through A and assign B[A[i]] = A[i]. But this is still dumb! lol.
- BubRoss 7y agoIt says from 1 to N inclusive, so each offset would need to have 1 subtracted from it. (Yes I realize it would just be an iota function in c++)
- Someone 7y agoAssuming arguments will be uniformly picked an extra check would speed things up on many architectures: return (x & 0xFE0000001 == 0) && (x == 6 || x == 28 || x == 496 || x == 8128 || x == 33550336): The original code does about 5 comparisons in each call. The improvement always does a binary ‘and’ and 1 comparison, and only does the original 5 in 1/256 of the calls.
- contravariant 7y agoAlthough unlike the original code it will be trickier to refactor for >5000 bit architectures once we encounter an odd perfect number.
- hairtuq 7y agoHere's a version that at least for 64 bit might be faster: bool isPerfect(uint64_t x) { int ctz = __builtin_ctzll(x); return ((0x40051056 >> ctz) & 1) && ((x >> ctz) + 1) == (uint64_t(1) << (ctz + 1)); }