[GSoC 2019] cpp_int Improvement
Hi, Integers with the capability to store large numbers has always been a requirement in C++ which has successfully been implemented by boost/multiprecision/cpp_int. Other languages such as Python and Java also supports such integer datatypes. I performed a speed test for C++ and python integers. While comparing speed of cpp_int and python int, I noticed that even though C++ source program was compiled with -O2 and -O3 flags, cpp_int was slow as compared for python int for multiplication and left-shift operations. The time taken for multiplication was: 1) cpp_int = 17.06 seconds 2) python int = 8.39 seconds I used the attached files to perform the testing on Linux. The execution time was measured using the time command. I would like to optimize this library. Being a GSoC aspirant, I was looking to pair up with a potential mentor in this domain who could guide me. Any feedback would be appreciated. Regards, Fenil Mehta
On 19/02/2019 18:32, Fenil Mehta via Boost wrote:
Hi,
Integers with the capability to store large numbers has always been a requirement in C++ which has successfully been implemented by boost/multiprecision/cpp_int. Other languages such as Python and Java also supports such integer datatypes.
I performed a speed test for C++ and python integers. While comparing speed of cpp_int and python int, I noticed that even though C++ source program was compiled with -O2 and -O3 flags, cpp_int was slow as compared for python int for multiplication and left-shift operations. The time taken for multiplication was: 1) cpp_int = 17.06 seconds 2) python int = 8.39 seconds
I used the attached files to perform the testing on Linux. The execution time was measured using the time command.
I would like to optimize this library. Being a GSoC aspirant, I was looking to pair up with a potential mentor in this domain who could guide me. Any feedback would be appreciated.
Hi Fenil, First off good on you for finding a potential project on your own - that's a good start in my book! I looked into the speed difference, and it's all down to base-10 string formatting which it turns out is about 90% of the runtime of the Boost code (I assume it's a large part of the python code too, just not quite as bad). There's a couple of obvious changes which may help in this case (but may make things worse in others!) that I'll look at later. But yes, that not withstanding there are certainly improvements that could be made to the Boost code, most notably it could usefully make use of the Karatsuba multiplication algorithm for medium sized integers. Unfortunately, I don't think I have the time to be a mentor this year, I would try to advise as best I can if someone else would like to take on that role though. Regards, John Maddock.
Regards, Fenil Mehta
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
participants (2)
-
Fenil Mehta -
John Maddock