Re: [boost] [GSoC 2019] cpp_int Improvement

Subject: Re: [boost] [GSoC 2019] cpp_int Improvement
From: John Maddock (jz.maddock_at_[hidden])
Date: 2019-02-20 19:08:35

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