为何Python中两个n位整数相乘的耗时仅在n为10的倍数时上升？

Great question! Let's break down what's happening here, from how Python stores big integers to why your test shows that step-like increase in time.

First, let's clarify your test setup #

Your code uses 10**i to generate numbers, but note that 10**i creates a number with i+1 decimal digits (e.g., 10**1 = 10 is 2 digits). If your X-axis is n (the number of digits), you might want to adjust to 10**(n-1) to get an n-digit number—but that's a minor detail compared to the core issue.

The root cause: How CPython stores big integers #

Under the hood, CPython represents integers larger than the small integer cache (-5 to 256) using an array of "digits", where each digit is a fixed-size chunk of binary data (30 bits on 64-bit systems, to be precise).

• A single 30-bit digit can hold numbers up to ~1.07e9 (since 2^30 = 1073741824).
• Two digits can hold up to ~1.15e18 (2^60), three digits up to ~1.23e27 (2^90), and so on.

When you multiply two integers, the time taken depends on how many digits each number has:

• Multiplying two 1-digit integers takes O(1*1) operations.
• Multiplying two 2-digit integers takes O(2*2) operations (or better with optimized algorithms like Karatsuba for very large numbers).

Why the jump at multiples of 10? #

Let's map your 10**i numbers to their digit counts:

• For i=9 (10-digit number: 1000000000), it fits in 1 digit (since 1e9 < 2^30).
• For i=10 (11-digit number: 10000000000), it needs 2 digits (1e10 > 2^30).
• For i=19 (20-digit number: 10000000000000000000), it needs 3 digits (1e19 > 2^60).
• For i=29 (30-digit number: 10^29), it needs 4 digits (1e29 > 2^90).

When i hits a multiple of 10 (10, 20, 30...), your 10**i number crosses a digit boundary—suddenly requiring one more chunk of binary storage. This means the multiplication goes from a smaller number of digit-digit operations to a larger set, causing that noticeable jump in time.

Between those multiples (e.g., i=10 to i=19), all your numbers fit in 2 digits, so the multiplication complexity stays roughly the same—hence the flat line in your graph.

Bonus: Optimize your test for better results #

If you want a more accurate picture of n-digit integer multiplication time, consider:

• Testing random n-digit integers instead of 10**i—since 10**i has a lot of trailing zeros, its multiplication is faster than a typical n-digit number.
• Using f-strings for your setup to avoid string concatenation: setup=f"a=10**{i};b=10**{i}"
• Adjusting the number parameter in timeit for larger i values (e.g., use fewer iterations when i is big to avoid long test times).

内容的提问来源于stack exchange，提问作者Aphrodite