[multiprecision] Proposal for enhancing cpp_int multiplication

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[multiprecision] Proposal for enhancing cpp_int multiplication

Boost - Dev mailing list
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.

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
[hidden email]
[hidden email]

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
Reply | Threaded
Open this post in threaded view
|

Re: [multiprecision] Proposal for enhancing cpp_int multiplication

Boost - Dev mailing list

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
> [hidden email]
> [hidden email]
>
> 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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [multiprecision] Proposal for enhancing cpp_int multiplication

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list

-------- Original message --------From: Ankur Dua via Boost <[hidden email]> Date: 17/08/2019  18:17  (GMT+08:00) To: [hidden email] Cc: Ankur Dua <[hidden email]> Subject: [boost] [multiprecision] Proposal for enhancing cpp_int
  multiplication We have benchmarked cpp_int vs mpz_int (GNU GMP backend) and we found thataround 10^6 bits, cpp_int is tremendously slow (almost 1200x times). Wehave also prepared a document containing the benchmarks [1] alongwith thedetails about the idea and the project.References,[1] Introductory document -https://docs.google.com/document/d/1cclKlbBWDVmY9zKSdn0ga2yTcCkyD9ZiUUdCZZkVyaI/edit?usp=sharing__________________________________________________________________________________ Nice idea for a project!  In GMP, things are organized around thresholds for switching to the next algorithm. It is impossible to predict theoretically what that threshold will be or how it will evolve in the future with changes to computer architecture.1. However, for very large input, FFT dominates over Karatsuba and Toom. The threshold is around 4000 limbs which is roughly 250,000 bits. BTW, it is below your test limits.2. For most sizes in between 0 and 4000 limbs, Toom-8 dominates, not Karatsuba.3. Karatsuba and Toom are anyway both special cases of FFT.https://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithmshttps://gmplib.org/devel/thres/Cheers,Kostas

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost