0
Answered

Conversion from string to mp is 4 times as slow than vpa.

Jacob 3 years ago updated by Pavel Holoborodko 3 years ago 6

I am trying to speed up a program I wrote using MATLAB's built in VPA function. I am working with integers on the order of 5 to 6 million digits. The bottleneck in my code was converting a string to VPA where the conversion would take around 2.5 seconds. In order to solve this I thought I would use the Multiprecision Computing Toolbox. I downloaded the free trial and only made 2 alterations to my code. I set the mp.Digits value to 10 million (the same as the vpa digits value) and I replaced my vpa() function with mp(). After running the code multiple times I found that the mp version was significantly slower. As you can see in the picture below conversion to mp took 10 seconds while conversion to vpa took 2.5 seconds. Since I am new to the Multiprecision Computing Toolbox I very well could misunderstand how it is supposed to work. If anyone could tell me either a better way to solve my speed issue, and/or why mp is slower then please let me know.

Image 41

Answer

Answer
Answered

Ok, great, please keep us updated on your experience with toolbox.

Under review

Thank you for your question.


Frankly, we didn't expect that conversion to string would be an important part of numerical computations (e.g. running in O(n^2) loop or similar). That is why we didn't optimize it to the maximum extent. I guess your case is very special in this regard.

What do you with the number after conversion (e.g. numeric computations)? I am pretty sure computations will be way more faster compared to vpa.


After converting the string I check for primality. For VPA I first take the square root and run a while loop to check each odd modulus up to the square root (this is significantly faster that the isprime function). The total time for this is 8.3 seconds (2.4 seconds to convert, 4.8 for sqrt, and 1.1 for modulus loop). When I use Multiprecision I can skip the square root and use the isprime function which results in a time of 10.6 seconds, 9.9 seconds of which is conversion. The numerical calculations with mp are significantly faster that vpa, but the overall time is still longer due to the conversion.

Thank you for the details. We are looking into the conversion code to make it faster. Will update you shortly..

+1

We have just released new version (Windows) with speed-optimized conversion for your case. In our tests speed-up is ~20 times.

Please download and try new trial from our website (our just use this link: https://bit.ly/3mvxXqg ).

Let me know what kind of speed improvement you see in your tests.

The newest version of mp appears to be ~25 times faster than the old version of mp and ~7 times faster than vpa. Thank you for such a quick fix.

Answer
Answered

Ok, great, please keep us updated on your experience with toolbox.