Multi-digit multiplication time up to 300 million digits in python

We compared multi-digit multiplication between python and C (gnu gmp). The calculation time on a personal computer (4Ghz) is shown below (unit: seconds). Decimal 300 million digits (result) Calculated in order from 1 time to half the number of digits and multiple times. The value at the right end of both is the time calculated 128 times in decimal 2.36 million digits. python  : 1627, 1084, 723, 482, 322, 215, 143, 96 (s) gnu(gmp)  : 4.5, 3.9, 3.7, 3,4, 3.2, 2.8, 2.6, 2.2 (s) You can see that python uses the Karatsuba algorithm and gmp uses FMT (integer FFT) with more than 1000 digits. Python has twice the number of digits and requires three times as much time (1.5 times in reverse order in the example). Since gmp is an FMT calculation, the log (number of digits) ratio is calculated by multiplying the number of digits by the number of times. See the multi-digit multiplication of the python program at https://ecc-256.com for the python source and detailed results for both. Interestingly, python is only about twice as slow in decimal 20 to 200 digits (both are huge). This is probably because it takes a lot of time to secure a place to store the results and the pointer. Python is slow to convert a to decimal with d10 = format (a). The conversion takes four times as long as the multiplication takes twice as many digits and three times as long. The multiplication and conversion times of 1.18 million digits, 2.36 million digits, and 4.72 million digits are shown in order. Multiplication: 0.24, 0.72, 2,19 (s), Conversion: 19, 77, 308 (s)

Recommended Posts

Multi-digit multiplication time up to 300 million digits in python
How to display multiplication table in python
3 ways to parse time strings in python [Note]
A clever way to time processing in Python
To represent date, time, time, and seconds in Python
Convert timezoned date and time to Unixtime in Python2.7
How to get the number of digits in Python
How to measure processing time in Python or Java
Solve multiplication (equivalent to paiza rank D) in Python
To flush stdout in Python
Login to website in Python
Matrix multiplication in python numpy
Speech to speech in python [text to speech]
How to develop in Python
Post to Slack in Python
Script to count and stop up to 5 seconds in Python in Blender
How to import Python library set up in EFS to Lambda
How to generate exponential pulse time series data in python
Determine the date and time format in Python and convert to Unixtime
[Python] How to do PCA in Python
Convert markdown to PDF in Python
How to collect images in Python
How to use SQLite in Python
Measure function execution time in Python
Try to calculate Trace in Python
How to write offline real time Solve E04 problems in Python
Python (from first time to execution)
How to use Mysql in python
How to wrap C in Python
How to use ChemSpider in Python
6 ways to string objects in Python
How to use PubChem in Python
How to speed up Python calculations
Code tests around time in Python
How to handle Japanese in Python
An alternative to `pause` in Python
How to calculate "xx time" in one shot with Python timedelta
Challenge Fizz Buzz! Problems with Python in 5 patterns (only now up to 398)
How to get the date and time difference in seconds with python
A note I looked up to make a command line tool in Python
How to stop a program in python until a specific date and time
[Introduction to Python] How to use class in Python?
Install Pyaudio to play wave in python
How to access environment variables in Python
I tried to implement permutation in Python
Method to build Python environment in Xcode 6
[Python] Matrix multiplication processing time using NumPy
How to dynamically define variables in Python
How to do R chartr () in Python
Pin current directory to script directory in Python
[Itertools.permutations] How to put permutations in Python
PUT gzip directly to S3 in Python
Just print Python elapsed time in seconds
Send email to multiple recipients in Python (Python 3)
Convert psd file to png in Python
Sample script to trap signals in Python
I tried to implement PLSA in Python 2
Private Python handbook (updated from time to time)
To set default encoding to utf-8 in python
How to work with BigQuery in Python
Log in to Slack using requests in Python