Re: [multiprecision] Proposal for enhancing cpp_int multiplication

From: kotika98 (kotika98_at_[hidden])
Date: 2019-08-19 12:29:07

-------- Original message --------From: Ankur Dua via Boost <boost_at_[hidden]> Date: 17/08/2019  18:17  (GMT+08:00) To: boost_at_[hidden] Cc: Ankur Dua <ankurdua15_at_[hidden]> 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__________________________________________________________________________________%c2%a0Nice 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