On 11/07/2019 18:04, Neill Clift via Boost-users wrote:
Hi,
I develop a program for generating optimal addition chains. I normally use 64 bit integers but in order to attack some conjectures I compile up my program with boost using uint128_t.
In order to get some functionality I need I used the backend access to limbs. For example I need population count/hamming weight/binary digit count. I did this like this:
static
LPTYPER
bits(NTYPE n)
/*++
Calculates the number of 1 bits in a number.
--*/
{
LPTYPER b = 0;
std::size_t size = n.backend().size();
boost::multiprecision::limb_type* p = n.backend().limbs();
for (std::size_t i = 0; i < size; i++) {
b += (LPTYPER)__popcnt64(p[i]);
}
return b;
}
If you're writing platform/compiler specific code anyway, you could rely on the fact that uint128_t will have an even number of limbs, and reinterpret_cast the limb pointer to a pointer to uint64_t's and have things still work - for performance reasons multiprecision does this internally when initializing from a type twice the width of a limb. There are also typedefs: boost::multiprecision::detail::limb_type, and boost::multiprecision::detail::double_limb_type. Which could help here. Aside: adding a native population count function might well be a useful addition to the library...
I use the same sort of logic to calculate Floor(Log2(n)) (number of largest bit set), to clear the bottom say b bits of an integer.
Is this a reasonable (though probably not idea) way to go?
I noted that the limbs are 32 bits on Windows and this leads me to my second question. How can I get the internals of boost using bigger chunks like 64 bit?
The limb size is always half the width of the largest compiler supported integer type - this is a necessary condition to implement arithmetic entirely within the language. So on GCC we have __int128 and so the limb size is 64-bits, but on msvc there's nothing wider than a 64 bit integer type, so the limbs are 32 bits. If clang-win can have __int128 support enabled, then defining BOOST_HAS_INT128 will activate it's use and you'll get 64-bit limbs in general, though in this specific case boost::uint128_t will become a thin wrapper around unsigned __int128 (ie will have only one limb). Of course in this specific case, if you have unsigned __int128 then you don't really need Boost.Multiprecision unless it's to ensure portability of the program to platforms without that type.
It seems I need a compiler supporting __int64. I have access to the intel compiler (19) and MSVC but neither seem to change this. I tried LLVM but that seemed quite slow. I may not have put enough effort into investigating LLVM up to this point.
Various bit operations seem overly slow in boost. For example I use sequences like this:
Control &= Control + 1;
Mask = ((Control - 1) ^ Control) >> 1;
Control |= Mask;
These seem to be bottlenecks under boost. That sequence above is meant to generate masks that straddle the first run of zero bits in control so 1010100000111111_2 produces a mask of 11111111111_2.
Well I'm always open to suggestions for performance improvements, but there's not much low hanging fruit in the bitwise operations which are pretty simple on the whole. BTW I'm not sure they help here, but there are a few operations like lsb/msb which use compiler intrinsics on msvc should they help. HTH, John.
Thanks.
Neill.
Sent from Mail https://go.microsoft.com/fwlink/?LinkId=550986 for Windows 10
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
--- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus