- Boost-users - lists.preview.boost.org

Comment on divide_unsigned_helper
by Neill Clift 03 Sep '21

03 Sep '21

Hi, I was trying to understand the algorithm inside the main divide routine. I struggled with this bit of code: if ((prem[r_order] <= py[y_order]) && (r_order > 0)) { double_limb_type a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1]; double_limb_type b = py[y_order]; double_limb_type v = a / b; if (v <= CppInt1::max_limb_value) { guess = static_cast<limb_type>(v); --r_order; } } I was trying to understand why we essential set guess to 1 in the case that the division is too big. I finally realized that the only way we can have v > CppInt1::max_limb_value is if we have prem[r_order] == py[y_order]. Some simple inequalities with floor can convince you of this. So in the case of equality we do an expensive divide and test when we could move the test outside like this: limb_type guess = 1; if (r_order == 0) { <-------- do this first to simplify guess = prem[0] / py[y_order]; } else if (prem[r_order] == py[y_order]) { <----------- handle it here to avoid the divide guess = 1; ... This leads to another question. Why is this line: guess = prem[0] / py[y_order]; not this line: guess = prem[0] / py[0]; Logically for division it must be the second line. In fact this loop has the invariant that r_order >= y_order. That makes sense for division. So the divisor must be py[0]. That suggests a divisor with one element and we handle that case via a special divide. So that code is not needed I believe. We end up with this: BOOST_ASSERT(r_order >= y_order && y_order >= 1); if (prem[r_order] == py[y_order]) { guess = 1; } else if (prem[r_order] < py[y_order]) { double_limb_type a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1]; double_limb_type b = py[y_order]; double_limb_type v = a / b; BOOST_ASSERT(v <= CppInt1::max_limb_value); guess = static_cast<limb_type>(v); --r_order; } else { double_limb_type a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1]; double_limb_type b = (y_order > 0) ? (static_cast<double_limb_type>(py[y_order]) << CppInt1::limb_bits) | py[y_order - 1] : (static_cast<double_limb_type>(py[y_order]) << CppInt1::limb_bits); BOOST_ASSERT(b); double_limb_type v = a / b; guess = static_cast<limb_type>(v); } BOOST_ASSERT(guess); // If the guess ever gets to zero we go on forever.... Some simple random divide tests seem to show a little over 2% improvement from doing this. Of course this could just be code layout changes. Just thinking that the 64 bit values are random would make me think this case is rare but I guess we subtract out multiples of the divisor and cause this to happen more for reasons that are hard to understand (for me anyway). I see the path hit a lot. Neill.

1 0

Jamshell query
by Mohammed Zahid 03 Sep '21

03 Sep '21

Hi, I am trying to run boost build in distributed environment by setting JAMSHELL I tried setting as environment variable and passing as command line variable -sJAMSHELL= Both didn't work https://github.com/bfgroup/b2/discussions/78 Need you guidence on how to do it. Thanks, Mohammed zahid

1 0

3D Tree Queries
by Glenn, Rachel M 02 Sep '21

02 Sep '21

I have a question about 3D RTree spatial queries, like a cube, sphere, or something. Are there any examples of how that can be done? I know how to do it for 2D RTree. Do you recommend the regular RTREE or a is there another one to use, like an rstar, that would be better? Thanks, Rachel

3 2

[Compute] automatically determine work group size
by Stephan Menzel 30 Aug '21

30 Aug '21

Hello everyone, I have recently made the switched an existing OpenCL application to boost compute. For reasons mostly. Now the transition went well for the most part but I struggle with one feature that appears to be missing. The determination of the local work group size. Originally the code was using clEnqueueNDRangeKernel() which has an option for the local work group size called local_work_size. When left empty, the system will determine that value itself at a small cost. Boost compute doesn't seem to have that. When I process an image for example: command_queue.enqueue_nd_range_kernel(kernel, bc::extents<2>{ 0, current_line }, bc::extents<2>{ width, height }, bc::extents<2>{ 128, 1 }); The last parameter is very hard for me to understand. I know roughly what it is and I understand it has to be dividable by 64, the total size (width * height) however has to be a multiple of it too, so there's a bunch of rules that apply and I would much rather leave that auto-determined as it was before. Leaving it bc::extents<2>{ 0, 0 } throws an assertion. So, essentially: Is there a way to leave it empty to be auto-defined? Cheers, Stephan

1 0

boost/rational.hpp and VS2019
by John Emmas 24 Aug '21

24 Aug '21

I'm guessing this might be solvable by updating to a newer version of boost (currently I'm running ver 1.71.0) but before updating, I wondered if there might be something obvious that 'm missing.... I'm building with Visual Studio 2019 and I get a whole bunch of errors simply by adding this line to an empty source file:- #include "boost/rational.hpp" It seems to be the same 6 errors but at various different lines - i.e. these errors, over & over again:- Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\ammintrin.h(146,19): error C4430: missing type specifier - int assumed. Note: C++ does not support default-int Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\ammintrin.h(146,8): error C2146: syntax error: missing ';' before identifier '_mm_macc_ps' Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\ammintrin.h(147,20): error C4430: missing type specifier - int assumed. Note: C++ does not support default-int Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\ammintrin.h(147,9): error C2146: syntax error: missing ';' before identifier '_mm_macc_pd' Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\ammintrin.h(148,19): error C4430: missing type specifier - int assumed. Note: C++ does not support default-int Visual Studio\2019\Community\VC\Tools\MSVC\14.29.30133\include\ammintrin.h(148,1): error C2086: 'int __m128': redefinition I just wondered if this might ring a bell with someone? e.g. might there be some preprocesser #define that I should've defined? (or a #define that I shouldn't be defining...) Thanks for any suggestions, John

3 18

Boost's Stage\Lib *.a Files
by Alexander Tanseco 23 Aug '21

23 Aug '21

I am running a tutorial program and I found out that in the program's build options under Linker settings/Link Libraries I can put both or either of the ff and the program compiles & runs without errors. What is the difference between the two? libboost_filesystem-mgw8-mt-d-x64-1_77.dll.a OR libboost_filesystem-mgw8-mt-x64-1_77.dll.a

2 1

[multiprecission] Large divides layered on 128 bit divides
by Neill Clift 21 Aug '21

21 Aug '21

Hi, The architecture of cpp_int being build on 64 bit arithmetic using 128 bit double_limb_type is interesting. I have a question on the large divide (divide_unsigned_helper). It uses the upper portions of the large integers to get an estimation of the quotient. Subtracts out a multiple of that quotient and repeats. It does this in 128 bit values if available from the compiler: double_limb_type a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1]; double_limb_type b = py[y_order]; double_limb_type v = a / b; The compiler emulates this operation in the routine __udivmodti4 which itself uses an iterative approach. It seems to use a pretty basic shift and subtract algorithm mind you. As a general rule for multiprecision is it OK to layer the Knuth like algorithm D on top of each other this way. I have no idea myself but wonder if this is a known issue. I would have guessed that it made sense to do a 64 by 64 bit divide to guess the quotient and repeat. Thoughts? Thanks. Neill.

2 2

[multiprecission] some thoughts on add_unsigned.hpp
by Neill Clift 19 Aug '21

19 Aug '21

Hi, In my program I see a lot of time taken up by add/subtract_unsigned. I have a couple of thoughts on the code: Carry propagation outside the range of the smallest number can be improved: for (; i < x && carry; ++i) carry = ::boost::multiprecision::detail::addcarry_limb(carry, pa[i], 0, pr + i); Maybe this: for (; i < x && carry; ++i) carry = ::boost::multiprecision::detail::addcarry_limb(0, pa[i], 1, pr + i); This generates just an inc on my machine but unfortunately it doesn't eliminate the loads and stores. I think on average the carry chain must be small though. You have the same situation on subtract. add_unsigned and subtract_unsigned are inconsistent at the tail end after carry propagation: add_unsigned: if (i == x && carry) { // We overflowed, need to add one more limb: result.resize(x + 1, x + 1); if (result.size() > x) result.limbs()[x] = static_cast<limb_type>(1u); } else std::copy(pa + i, pa + x, pr + i); <--- if I == x we do the copy. We also do the copy even if the output and input overlap subtract_unsigned: // Any remaining digits are the same as those in pa: if ((x != i) && (pa != pr)) <-------- we do these checks here and avoid the copy std_constexpr::copy(pa + i, pa + x, pr + i); I am seeing a lot of time being used by that general copy above in add_unsigned when it can be avoided. This stuff is totally awesome and works well in my program. So thanks for working on this stuff. Neill.

2 1

Boost Installation in Codeblocks
by Alexander Tanseco 18 Aug '21

18 Aug '21

To Gavin Lambert, many thanks for your help. I finally got my program running without errors with the ff settings: Global variable Lib: c:\boost_1_77_0\stage\lib Program's build options: Linker settings/Link libraries: blank Search Directories/Compiler: $(#boost) Search Directories/Linker: $(#boost.lib).

1 0

Boost uses unoptimized subtraction because of typo in intel_intrinsics.hpp
by Neill Clift 18 Aug '21

18 Aug '21

Hi, In my program I am seeing my code use the slower (I assume) subtract_unsigned_constexpr rather than subtract_unsigned with he borrow chain handled intrinsics. This seems to be happening because of these lines in intel_intrinsics.hpp: #if defined(__clang__) && (__clang__ < 9) // We appear to crash the compiler if we try to use these intrinsics? #undef BOOST_MP_HAS_IMMINTRIN_H #endif __clang__ is not the version but just the value 1. I expect this should be the major version instead: #define __clang__ 1 #define __clang_major__ 12 #define __clang_minor__ 0 As an aside 128bit support does work in windows with clang. I have to force it on like this: #define __STRICT_ANSI__ #define BOOST_HAS_INT128 #define BOOST_MP_HAS_IMMINTRIN_H #include <boost/multiprecision/cpp_int.hpp> Thanks. Neill.

2 1