[integer][math]Heads up on revised gcd/lcm code
First some history.... Some time ago, the old gcd/lcm code was moved from Boost.Math to Boost.Integer as a means of reducing inter-library dependencies. Unfortunately a number of tasks were never completed: the docs weren't added to Boost.Integer, and the Boost.Math code never got updated to redirect to the moved headers. Fast forward a couple of years and when Jeremy Murphy contributed a new version of the gcd/lcm code as part of supporting polynomial gcd, and since I'd completely forgotten about the move, this got integrated into Boost.Math leaving us with two divergent versions. As part of sorting this mess out, I've now pushed to Boost.Integer a "best of both" version of this code, so far as I can tell, all dependent libraries are unaffected by the change, though I do need to do some more work on supporting obsolete compilers I no longer have access to. The main enhancements are: * New mixed binary/Euclid algorithm added, this seems to be the best performing algorithm in most cases, and is now the default for most integer types (performance is deeply dependent on the input though, so your mileage may vary). * In addition to integer and rational support, polynomial gcd is now supported via boost::math::polynomial. * There are new range based gcd-lcm algorithms for calculating the gcd/lcm of all the values in an iterator range, this is primarily for polynomial gcd support. * There are new variadic overloads of gcd/lcm for calculating gcd/lcm over more than 2 values. * The gcd/lcm functions are now constexpr in C++14 land, this means that the old compile time calculation traits classes are rendered obsolete for current compilers. * The gcd/lcm functions are now noexcept where appropriate. * Compiler intrinsics are now used speed up binary-gcd steps where possible, sadly this is incompatible with constexpr support since the intrinsics aren't yet constexpr :( Please do let me know if you find any snags, best, John. --- This email has been checked for viruses by AVG. http://www.avg.com
On 4/24/2017 1:37 PM, John Maddock via Boost wrote:
First some history....
Some time ago, the old gcd/lcm code was moved from Boost.Math to Boost.Integer as a means of reducing inter-library dependencies. Unfortunately a number of tasks were never completed: the docs weren't added to Boost.Integer, and the Boost.Math code never got updated to redirect to the moved headers. Fast forward a couple of years and when Jeremy Murphy contributed a new version of the gcd/lcm code as part of supporting polynomial gcd, and since I'd completely forgotten about the move, this got integrated into Boost.Math leaving us with two divergent versions.
As part of sorting this mess out, I've now pushed to Boost.Integer a "best of both" version of this code, so far as I can tell, all dependent libraries are unaffected by the change, though I do need to do some more work on supporting obsolete compilers I no longer have access to.
To which obsolete compilers are you referring ?
The main enhancements are:
* New mixed binary/Euclid algorithm added, this seems to be the best performing algorithm in most cases, and is now the default for most integer types (performance is deeply dependent on the input though, so your mileage may vary).
* In addition to integer and rational support, polynomial gcd is now supported via boost::math::polynomial.
* There are new range based gcd-lcm algorithms for calculating the gcd/lcm of all the values in an iterator range, this is primarily for polynomial gcd support.
* There are new variadic overloads of gcd/lcm for calculating gcd/lcm over more than 2 values.
* The gcd/lcm functions are now constexpr in C++14 land, this means that the old compile time calculation traits classes are rendered obsolete for current compilers.
* The gcd/lcm functions are now noexcept where appropriate.
* Compiler intrinsics are now used speed up binary-gcd steps where possible, sadly this is incompatible with constexpr support since the intrinsics aren't yet constexpr :(
Please do let me know if you find any snags, best, John.
I will test rational, which is part of CMT, and uses Integer's gcd/lcm implementation.
On 24/04/2017 20:03, Edward Diener via Boost wrote:
On 4/24/2017 1:37 PM, John Maddock via Boost wrote:
First some history....
Some time ago, the old gcd/lcm code was moved from Boost.Math to Boost.Integer as a means of reducing inter-library dependencies. Unfortunately a number of tasks were never completed: the docs weren't added to Boost.Integer, and the Boost.Math code never got updated to redirect to the moved headers. Fast forward a couple of years and when Jeremy Murphy contributed a new version of the gcd/lcm code as part of supporting polynomial gcd, and since I'd completely forgotten about the move, this got integrated into Boost.Math leaving us with two divergent versions.
As part of sorting this mess out, I've now pushed to Boost.Integer a "best of both" version of this code, so far as I can tell, all dependent libraries are unaffected by the change, though I do need to do some more work on supporting obsolete compilers I no longer have access to.
To which obsolete compilers are you referring ?
Primarily VC7.1, 8, 9. Also Sun+STLPort (which I do have access to, but I haven't fired up that virtual machine yet). All have tentative fixes in place which I think will fix things, but I'm waiting on the tests to cycle. John. --- This email has been checked for viruses by AVG. http://www.avg.com
On 4/25/2017 3:22 AM, John Maddock via Boost wrote:
On 24/04/2017 20:03, Edward Diener via Boost wrote:
On 4/24/2017 1:37 PM, John Maddock via Boost wrote:
First some history....
Some time ago, the old gcd/lcm code was moved from Boost.Math to Boost.Integer as a means of reducing inter-library dependencies. Unfortunately a number of tasks were never completed: the docs weren't added to Boost.Integer, and the Boost.Math code never got updated to redirect to the moved headers. Fast forward a couple of years and when Jeremy Murphy contributed a new version of the gcd/lcm code as part of supporting polynomial gcd, and since I'd completely forgotten about the move, this got integrated into Boost.Math leaving us with two divergent versions.
As part of sorting this mess out, I've now pushed to Boost.Integer a "best of both" version of this code, so far as I can tell, all dependent libraries are unaffected by the change, though I do need to do some more work on supporting obsolete compilers I no longer have access to.
To which obsolete compilers are you referring ?
Primarily VC7.1, 8, 9. Also Sun+STLPort (which I do have access to, but I haven't fired up that virtual machine yet).
VC 8,9 all pass both integer and rational which uses integer for gcd/lcm. Sun+STLPort can still be any Sun/Oracle release I believe, but I will test against 12.2 through 12.5 and let you know if I see any failures.
All have tentative fixes in place which I think will fix things, but I'm waiting on the tests to cycle.
John
On 04/25/2017 03:22 AM, John Maddock via Boost wrote:
On 24/04/2017 20:03, Edward Diener via Boost wrote:
On 4/24/2017 1:37 PM, John Maddock via Boost wrote:
First some history....
Some time ago, the old gcd/lcm code was moved from Boost.Math to Boost.Integer as a means of reducing inter-library dependencies. Unfortunately a number of tasks were never completed: the docs weren't added to Boost.Integer, and the Boost.Math code never got updated to redirect to the moved headers. Fast forward a couple of years and when Jeremy Murphy contributed a new version of the gcd/lcm code as part of supporting polynomial gcd, and since I'd completely forgotten about the move, this got integrated into Boost.Math leaving us with two divergent versions.
As part of sorting this mess out, I've now pushed to Boost.Integer a "best of both" version of this code, so far as I can tell, all dependent libraries are unaffected by the change, though I do need to do some more work on supporting obsolete compilers I no longer have access to.
To which obsolete compilers are you referring ?
Primarily VC7.1, 8, 9. Also Sun+STLPort (which I do have access to, but I haven't fired up that virtual machine yet).
I have tested sun 12.2 through 12.5 with stlport and running the integer
lasts from the latest 'develop'. My user-config.jam entry for each
version has:
<cxxflags>-std=sun03
<cxxflags>-library=stlport4
<linkflags>-std=sun03
<linkflags>-library=stlport4
<cxxflags>-features=tmplife
<cxxflags>-features=tmplrefstatic ;
I get, starting from the latest:
12.5
sun.compile.c++
/home/fceldiener/build/boost/bin.v2/libs/integer/test/common_factor_test.test/sun-12.5stlport/debug/address-model-32/common_factor_test.o
"../../../boost/rational.hpp", line 141: Error: The type
"boost::STATIC_ASSERTION_FAILURE<0>" is incomplete.
"common_factor_test.cpp", line 327: Where: While specializing
"boost::rational
All have tentative fixes in place which I think will fix things, but I'm waiting on the tests to cycle.
John.
I have tested sun 12.2 through 12.5 with stlport and running the integer lasts from the latest 'develop'.
Thanks for this!
My user-config.jam entry for each version has:
<cxxflags>-std=sun03 <cxxflags>-library=stlport4 <linkflags>-std=sun03 <linkflags>-library=stlport4 <cxxflags>-features=tmplife <cxxflags>-features=tmplrefstatic ;
I get, starting from the latest:
12.5
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/common_factor_test.test/sun-12.5stlport/debug/address-model-32/common_factor_test.o
"../../../boost/rational.hpp", line 141: Error: The type "boost::STATIC_ASSERTION_FAILURE<0>" is incomplete.
"common_factor_test.cpp", line 327: Where: While specializing "boost::rational
>". "common_factor_test.cpp", line 327: Where: Specialized in non-template code.
1 Error(s) detected.
This is now fixed in develop by altering the tests
This issue is caused (and would have been equally caused before) by
simply including
12.4
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/common_factor_test.test/sun-12.4stlport/debug/address-model-32/common_factor_test.o
"../../../boost/integer/common_factor_rt.hpp", line 110: Warning: Identifier expected instead of "}".
That's a bug in the header for C++98 compilers (extraneous , in enum declaration), fixed in develop. I'm hoping the rest of the errors are cascading off this.
12.2
../../../boost/cstdint.hpp", line 381: Error: uintptr_t is not defined.
appears for each test.
I've pushed a tentative fix to Boost.Config, but it's likely that this has never worked before either!
I did not try 64-bit tests. Should I try with a higher -std=c++11 level with stlport ? I have separate jam entries which test each version without the stlport library but with c++03 or c++11 as the standard.
I don't believe it's possible to compile with both STLPort and C++11 or later as these use a different ABI. There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later. Many thanks for those tests! John. --- This email has been checked for viruses by AVG. http://www.avg.com
There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later.
Also now fixed. John. --- This email has been checked for viruses by AVG. http://www.avg.com
On 04/26/2017 02:54 PM, John Maddock via Boost wrote:
There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later.
Also now fixed.
12.5 is fixed but 12.4, 12.3, and 12.2 have the same errors.
John.
--- This email has been checked for viruses by AVG. http://www.avg.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 27/04/2017 04:55, Edward Diener via Boost wrote:
On 04/26/2017 02:54 PM, John Maddock via Boost wrote:
There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later.
Also now fixed.
12.5 is fixed but 12.4, 12.3, and 12.2 have the same errors.
OK, I finally got those compilers installed, and after a couple of minor fixes to Config and Integer, these all pass for me now. Thanks, John. --- This email has been checked for viruses by AVG. http://www.avg.com
On 04/27/2017 01:27 PM, John Maddock via Boost wrote:
On 27/04/2017 04:55, Edward Diener via Boost wrote:
On 04/26/2017 02:54 PM, John Maddock via Boost wrote:
There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later.
Also now fixed.
12.5 is fixed but 12.4, 12.3, and 12.2 have the same errors.
OK, I finally got those compilers installed, and after a couple of minor fixes to Config and Integer, these all pass for me now.
I see 12.4 and 12.5 passing. With 12.3 I see: sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o "/opt/oracle/solarisstudio12.3/bin/CC" +d -library=stlport4 -features=tmplife -features=tmplrefstatic -g -erroff=%none -m32 -KPIC -DBOOST_ALL_NO_LIB=1 -I"../../.." -c -o "/home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o" "fail_uint_65.cpp" ...failed sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o... with a jam entry of: using sun : 12.3stlport : /opt/oracle/solarisstudio12.3/bin/CC : <cxxflags>-library=stlport4 <linkflags>-library=stlport4 <cxxflags>-features=tmplife <cxxflags>-features=tmplrefstatic ; I can not see why it fails to compile and no reason seems to be given. With 12.2 I still see: sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o "../../../boost/cstdint.hpp", line 381: Error: uintptr_t is not defined. 1 Error(s) detected. "/opt/oracle/solstudio12.2/bin/CC" +d -library=stlport4 -features=tmplife -features=tmplrefstatic -g -erroff=%none -m32 -KPIC -DBOOST_ALL_NO_LIB=1 -I"../../.." -c -o "/home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o" "integer_traits_test.cpp" ...failed sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o... etc. with a jam entry of: using sun : 12.2stlport : /opt/oracle/solstudio12.2/bin/CC : <cxxflags>-library=stlport4 <linkflags>-library=stlport4 <cxxflags>-features=tmplife <cxxflags>-features=tmplrefstatic ; I picked up the latest changes from config and integer.
Thanks, John.
On 4/27/2017 1:27 PM, John Maddock via Boost wrote:
On 27/04/2017 04:55, Edward Diener via Boost wrote:
On 04/26/2017 02:54 PM, John Maddock via Boost wrote:
There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later.
Also now fixed.
12.5 is fixed but 12.4, 12.3, and 12.2 have the same errors.
OK, I finally got those compilers installed, and after a couple of minor fixes to Config and Integer, these all pass for me now.
I see 12.4 and 12.5 passing. With 12.3 I see: sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o "/opt/oracle/solarisstudio12.3/bin/CC" +d -library=stlport4 -features=tmplife -features=tmplrefstatic -g -erroff=%none -m32 -KPIC -DBOOST_ALL_NO_LIB=1 -I"../../.." -c -o "/home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o" "fail_uint_65.cpp" ...failed sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o... with a jam entry of: using sun : 12.3stlport : /opt/oracle/solarisstudio12.3/bin/CC : <cxxflags>-library=stlport4 <linkflags>-library=stlport4 <cxxflags>-features=tmplife <cxxflags>-features=tmplrefstatic ; I can not see why it fails to compile and no reason seems to be given. With 12.2 I still see: sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o "../../../boost/cstdint.hpp", line 381: Error: uintptr_t is not defined. 1 Error(s) detected. "/opt/oracle/solstudio12.2/bin/CC" +d -library=stlport4 -features=tmplife -features=tmplrefstatic -g -erroff=%none -m32 -KPIC -DBOOST_ALL_NO_LIB=1 -I"../../.." -c -o "/home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o" "integer_traits_test.cpp" ...failed sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o... etc. with a jam entry of: using sun : 12.2stlport : /opt/oracle/solstudio12.2/bin/CC : <cxxflags>-library=stlport4 <linkflags>-library=stlport4 <cxxflags>-features=tmplife <cxxflags>-features=tmplrefstatic ; I picked up the latest changes from config and integer.
Thanks, John.
On 04/26/2017 02:54 PM, John Maddock via Boost wrote:
There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later.
Also now fixed.
12.5 with stlport now works but 12.2, 12.3, and 12.4 still have the same problems.
John.
--- This email has been checked for viruses by AVG. http://www.avg.com
On 4/27/2017 12:48 AM, Edward Diener via Boost wrote:
On 04/26/2017 02:54 PM, John Maddock via Boost wrote:
There is one remaining failure with Oracle 12.5 in C++11 mode relating to how it handles variadic templates, I'll try to find a workaround for that later.
Also now fixed.
12.5 with stlport now works but 12.2, 12.3, and 12.4 still have the same problems.
Sorry about the multiple posts. I have been having some trouble with Thunderbird. I think it is fixed now.
John.
Sorry about the multiple posts. I have been having some trouble with Thunderbird. I think it is fixed now.
No problem, for some reason I lost all boost messages for a couple of days.... but I see from the archives you replied as below:
With 12.3 I see:
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o
I can not see why it fails to compile and no reason seems to be given.
It's a compile-fail test, which compiles when it should not - as I understand it, it tries to create a 65-bit integer which should of course fail. I assume it's a compiler bug, but either way, nothing has changed in that code for years.
With 12.2 I still see:
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o "../../../boost/cstdint.hpp", line 381: Error: uintptr_t is not defined. 1 Error(s) detected.
That's weird, it should have been fixed in https://github.com/boostorg/config/commit/19766b0a0e3d8c92e4c0d058cc47190ce7... - solaris.hpp unconditionally defines BOOST_HAS_STDINT_H so that pp-branch should only be taken when INTPTR_MAX is defined and ::intptr actually exists. Or are you on red-hat? In which case are you able to figure out why that pp-branch is taken? Thanks! John. --- This email has been checked for viruses by AVG. http://www.avg.com
On 4/29/2017 1:49 PM, John Maddock via Boost wrote:
Sorry about the multiple posts. I have been having some trouble with Thunderbird. I think it is fixed now.
No problem, for some reason I lost all boost messages for a couple of days....
Something apparently happened to everybody, where the mailing lists stopped working along with the GMane reflection. Everything seems to be back now.
but I see from the archives you replied as below:
With 12.3 I see:
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o
I can not see why it fails to compile and no reason seems to be given.
It's a compile-fail test, which compiles when it should not - as I understand it, it tries to create a 65-bit integer which should of course fail. I assume it's a compiler bug, but either way, nothing has changed in that code for years.
With 12.2 I still see:
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o "../../../boost/cstdint.hpp", line 381: Error: uintptr_t is not defined. 1 Error(s) detected.
That's weird, it should have been fixed in https://github.com/boostorg/config/commit/19766b0a0e3d8c92e4c0d058cc47190ce7... - solaris.hpp unconditionally defines BOOST_HAS_STDINT_H so that pp-branch should only be taken when INTPTR_MAX is defined and ::intptr actually exists. Or are you on red-hat?
I am on Linux ( Fedora 25 ), not Solaris. I will look at it and see what I can figure out.
In which case are you able to figure out why that pp-branch is taken?
Thanks!
John.
On 04/29/2017 01:49 PM, John Maddock via Boost wrote:
Sorry about the multiple posts. I have been having some trouble with Thunderbird. I think it is fixed now.
No problem, for some reason I lost all boost messages for a couple of days.... but I see from the archives you replied as below:
With 12.3 I see:
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/fail_uint_65.test/sun-12.3stlport/debug/address-model-32/fail_uint_65.o
I can not see why it fails to compile and no reason seems to be given.
It's a compile-fail test, which compiles when it should not - as I understand it, it tries to create a 65-bit integer which should of course fail. I assume it's a compiler bug, but either way, nothing has changed in that code for years.
With 12.2 I still see:
sun.compile.c++ /home/fceldiener/build/boost/bin.v2/libs/integer/test/integer_traits_test.test/sun-12.2stlport/debug/address-model-32/integer_traits_test.o "../../../boost/cstdint.hpp", line 381: Error: uintptr_t is not defined. 1 Error(s) detected.
That's weird, it should have been fixed in https://github.com/boostorg/config/commit/19766b0a0e3d8c92e4c0d058cc47190ce7... - solaris.hpp unconditionally defines BOOST_HAS_STDINT_H so that pp-branch should only be taken when INTPTR_MAX is defined and ::intptr actually exists. Or are you on red-hat? In which case are you able to figure out why that pp-branch is taken?
For sun-12.2 stlport because: (defined(_XOPEN_UNIX) && (_XOPEN_UNIX+0 > 0) && !defined(__UCLIBC__)) is true while BOOST_HAS_STDINT_H is not defined.
Thanks!
John.
On 24 April 2017 at 18:37, John Maddock via Boost
* Compiler intrinsics are now used speed up binary-gcd steps where possible, sadly this is incompatible with constexpr support since the intrinsics aren't yet constexpr :(
Which intrinsics are those? GCC built-ins are typically constexpr, while the MSVC ones are not.
* Compiler intrinsics are now used speed up binary-gcd steps where possible, sadly this is incompatible with constexpr support since the intrinsics aren't yet constexpr :(
Which intrinsics are those? GCC built-ins are typically constexpr, while the MSVC ones are not.
In that case I'll investigate some more, it's the bitscan forward/backward that I need for this. Thanks, John. --- This email has been checked for viruses by AVG. http://www.avg.com
participants (3)
-
Edward Diener
-
John Maddock
-
Mathias Gaunard