Re: [multiprecision] Proposal for enhancing cpp_int multiplication

From: John Maddock (jz.maddock_at_[hidden])
Date: 2019-08-18 08:04:38

On 17/08/2019 11:17, Ankur Dua via Boost wrote:
> Hi Boost community,
>
> We are team of two students (Senior Undergraduate) from IIT(ISM) Dhanbad —
> Madhur Chauhan & Ankur Dua.
>
> We want to bring your attention towards the the potential project that we
> wish to complete — Enhancing multplication of cpp_int by using Karatsuba as
> the multiplication algorithm.
>
> We have benchmarked cpp_int vs mpz_int (GNU GMP backend) and we found that
> around 10^6 bits, cpp_int is tremendously slow (almost 1200x times). We
> have also prepared a document containing the benchmarks [1] alongwith the
> details about the idea and the project.

I'm not surprised - cpp_int is only really optimised for small bit counts.

Adding Karatsuba has always been on the TODO list, but just hasn't 
materialized yet.  If you have code then I'd certainly welcome a PR that 
adds the algorithm - it's not actually an especially complex algorithm 
to implement - most of the work is likely to be in identifying the 
crossover position where it become faster than "schoolbook" multiplication.

Best, John.

>
> We are awaiting response from the community after which we will prepare a
> formal proposal containing the details of approach and possible
> implementations with documentation and test code changes.
>
> Thanks & Regards
> Madhur Chauhan & Ankur Dua
> madhur4127_at_[hidden]
> ankurdua15_at_[hidden]
>
> References,
> [1] Introductory document -
> https://docs.google.com/document/d/1cclKlbBWDVmY9zKSdn0ga2yTcCkyD9ZiUUdCZZkVyaI/edit?usp=sharing
>
> _______________________________________________
> 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