目錄

Python 數學運算性能測試

封面圖片由 Google Gemini 生成。

在先前修習研究所課程「模擬方法」時,老師曾提到,現今電腦與程式運算所使用的隨機數,其實大多並非真正意義上的隨機,而是所謂的偽隨機數(Pseudo-random Number)。偽隨機數是透過數學演算法,根據前一個狀態推算出下一個數值,因此只要知道演算法、初始值(Seed)以及目前的狀態,理論上便能重現整串隨機數序列。那麼,既然每一個偽隨機數都可以由前一個數值計算而來,那麼第一個數究竟是從何而來的呢?

真偽隨機數

要回答這個問題,首先需要了解隨機數大致可分為兩種類型:真隨機數(True Random Number)與偽隨機數(Pseudo-random Number)。

真隨機數是由真實世界中不可預測的物理現象所產生,例如硬體電路產生的熱雜訊、振盪器的時脈抖動(Clock Jitter)、滑鼠移動軌跡、鍵盤輸入時間間隔,以及磁碟 I/O、網路封包等系統事件。現代作業系統會持續收集這些資訊,建立所謂的熵池(Entropy Pool),並將其作為安全亂數產生器的初始來源。由於這些資訊難以預測,因此真隨機數具有較高的安全性,廣泛應用於密碼學、金鑰交換、 HTTPS 、 SSH 、數位簽章等安全相關領域。然而,收集熵來源與進行安全處理需要額外成本,因此真隨機數的產生速度通常較慢。

相較之下,偽隨機數則完全建立在數學運算之上。它並不是直接來自自然界,而是利用固定的數學公式,不斷根據前一個狀態推算出下一個數值,因此本質上是一條具有良好統計性質的數列。雖然只要知道初始值與演算法,就能完整重現整串數列,因此在安全性方面不如真隨機數,但其最大的優勢在於計算速度快、可重現性高,且只需極少的記憶體即可產生極長的隨機數序列。因此,在蒙地卡羅模擬(Monte Carlo Simulation)、數值分析、統計模擬、電腦遊戲以及一般科學計算等領域,幾乎都是使用偽隨機數。

偽隨機數的演算法

回到最初的問題,既然偽隨機數需要依賴前一個狀態,那麼第一個數又是從哪裡來的?答案便是初始值(Seed)。如果使用者自行指定 Seed,例如 Python 中的 random.seed(42),則每次執行程式都會得到完全相同的隨機數序列,方便除錯與重現實驗結果;若未指定 Seed,Python 則會向作業系統取得一組具有足夠熵值的初始狀態,通常來自作業系統所維護的熵池,再以此作為偽隨機數產生器的起點。換句話說,現代電腦的隨機數產生方式並非完全依賴真隨機數,而是利用少量的真隨機資訊作為初始值,再透過高速的數學演算法快速產生大量的偽隨機數。

目前最常見的偽隨機數產生器之一為線性同餘產生器(Linear Congruential Generator, LCG),其利用一次乘法、一次加法及一次取模運算即可產生下一個數值,其數學表示式為

$$ X_{n+1} = (a X_n + c) \bmod (m), $$

其中 $X_n$ 代表目前的狀態, $X_{n + 1}$ 代表下一步狀態。由於演算法結構簡單,因此 LCG 的運算速度非常快,但若參數選擇不佳,容易產生週期較短或統計性質不佳的問題,因此後續又衍生出許多改良版本。

其中一種重要的變形為Lehmer Generator。其只保留 LCG 中的乘法與 mod 運算,如下所示:

$$ X_{n+1} = a X_n \bmod (m). $$

1973 年, P. A. W. Lewis 與 G. P. Learmonth 對 Lehmer Generator 進行研究,提出了一組具有良好統計特性的參數,因此部分文獻將採用此類參數的實作稱為 Lewis–Learmonth Generator 。其後,Park 與 Miller 於 1988 年發表著名論文 Random Number Generators: Good Ones Are Hard to Find ,推薦使用 $a = 16807$ 與 $m = 2^{31} − 1 = 2147483647$ 作為 Lehmer Generator 的參數,並將其稱為 Minimal Standard Generator 。由於其具有良好的統計性質、實作簡單且運算效率高,因此成為目前最廣為人知的 Lehmer Generator 實作之一,也被許多程式語言、數值計算函式庫及教科書作為經典範例。

另一方面,Python 標準函式庫中的 random 模組則預設採用 Mersenne Twister(MT19937) 演算法。相較於傳統 LCG , Mersenne Twister 擁有長達 $2^{19937}-1$ 的週期以及更優異的統計特性,因此能提供品質更好的偽隨機數,同時仍具有相當高的運算效率,也因此成為目前最常見的通用偽隨機數產生器之一。

由上述介紹可以發現,偽隨機數的產生本身就是一連串數學運算的結果,而不同演算法所使用的運算方式,也會直接影響其執行效率。事實上,不僅是亂數產生器,Python 中各種常見的數學函式,例如加、減、乘、除、指數、對數、三角函數以及各類機率分布,其底層都需要經過不同程度的數學計算。因此,不同運算之間究竟存在多大的效能差異,便成為一個值得探討的問題。接下來,本文將利用 Python 的 timeit 模組,針對各種常見數學運算與隨機數產生方式進行效能測試,並比較它們在實際執行時所需花費的時間。

Python 數學性能測試

為了盡可能公平地比較各種運算的執行效率,本次測試使用 Python 標準函式庫中的 timeit 模組進行計時。相較於直接使用 time.time()time.perf_counter() 記錄單次執行時間, timeit 會將指定函式重複執行大量次數,並盡可能降低背景程序、系統排程以及計時誤差所造成的影響,因此也是 Python 官方建議用於微基準測試(Microbenchmark)的方法。

本次測試將每一種運算包裝成獨立函式,並利用 timeit.timeit() 重複執行一億次($10^8$ 次),記錄完成所有運算所需的總時間。測試項目除了最基本的加、減、乘、除與取餘數外,也包含次方、對數、平方根、三角函數、反三角函數、雙曲函數等常見數學函式。此外,為了比較不同偽隨機數產生方式的效率,也將 Python random 模組中的 Uniform 、 Normal 、 Gamma 、 Beta 、 Triangular 等常見機率分布納入測試,並實作 LCG 與 Lewis–Learmonth Generator ,最後再與 Python 內建採用 Mersenne Twister 的 random.random() 進行比較。

提示
本文比較的是Python 程式實際執行時的整體效能,而非各演算法的理論時間複雜度。由於 Python 每次函式呼叫、物件存取以及模組函式的封裝都會產生額外的執行成本,因此最終測得的時間除了反映演算法本身的運算量外,也包含 Python 執行環境所帶來的額外負擔,運算結果也會因電腦硬體環境而異。

以下為本次測試所使用的 Python 程式碼。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# version 1131002
import timeit
import math
import random
import pandas as pd

# calculate U(0, 1) pseudo-random number by Linear Congruential Generator (LCG)
class LCG:
    def __init__(self, seed):
        if not isinstance(seed, (int, float)):
            raise TypeError('seed must be a number (int or float).')
        self.state = seed

    def random(self):
        self.state = (1103515245 * self.state + 12345) % 2147483648
        return self.state / 2147483648
    
    def randint(self, low, high):
        return low + int(self.random() * (high - low))


# calculate U(0, 1) pseudo-random number by Learmonth-Lewis Generator (LLG)
class LLG:
    def __init__(self, seed):
        if not isinstance(seed, (int, float)):
            raise TypeError('seed must be a number (int or float).')
        self.state = seed
        
    def random(self):
        self.state = (16807 * self.state) % 2147483647
        return self.state / 2147483647
    
    def randint(self, low, high):
        return low + int(self.random() * (high - low + 1))

# function
def test_add(): return a + b
def test_sub(): return a - b
def test_mul(): return a * b
def test_div(): return a / b
def test_mod(): return a % b
def test_pow(): return math.pow(a, b)
def test_abs(): return abs(a)
def test_log(): return math.log(a)
def test_log10(): return math.log10(a)
def test_exp(): return math.exp(a)
def test_sqrt(): return math.sqrt(a)
def test_square(): return a ** 2
def test_sin(): return math.sin(a)
def test_cos(): return math.cos(a)
def test_tan(): return math.tan(a)
def test_asin(): return math.asin(a / b)
def test_acos(): return math.acos(a / b)
def test_atan(): return math.atan(a)
def test_sinh(): return math.sinh(a)
def test_cosh(): return math.cosh(a)
def test_tanh(): return math.tanh(a)
def test_asinh(): return math.asinh(a)
def test_acosh(): return math.acosh(b)
def test_atanh(): return math.atanh(a / b)
def test_uniform(): return random.uniform(0, 1)
def test_normal(): return random.gauss(0, 1)
def test_randint(): return random.randint(0, 100)
def test_exponential(): return random.expovariate(1)
def test_gamma(): return random.gammavariate(2, 2)
def test_beta(): return random.betavariate(2, 5)
def test_triangular(): return random.triangular(0, 10, 5)
def test_mt(): return random.random()
def test_lcg(): return lcg.random()
def test_llg(): return llg.random()

a = 1.234
b = 5.678
lcg = LCG(seed = 42)
llg = LLG(seed = 42)
times = 100000000

operations = [
    ("Addition (+)", test_add),
    ("Subtraction (-)", test_sub),
    ("Multiplication (*)", test_mul),
    ("Division (/)", test_div),
    ("Modulus (%)", test_mod),
    ("Power (pow)", test_pow),
    ("Absolute (abs)", test_abs),
    ("Logarithm (log)", test_log),
    ("Logarithm Base 10 (log10)", test_log10),
    ("Exponential (exp)", test_exp),
    ("Square Root (sqrt)", test_sqrt),
    ("Square (**)", test_square),
    ("Sine (sin)", test_sin),
    ("Cosine (cos)", test_cos),
    ("Tangent (tan)", test_tan),
    ("Arcsine (asin)", test_asin),
    ("Arccosine (acos)", test_acos),
    ("Arctangent (atan)", test_atan),
    ("Hyperbolic Sine (sinh)", test_sinh),
    ("Hyperbolic Cosine (cosh)", test_cosh),
    ("Hyperbolic Tangent (tanh)", test_tanh),
    ("Inverse Hyperbolic Sine (asinh)", test_asinh),
    ("Inverse Hyperbolic Cosine (acosh)", test_acosh),
    ("Inverse Hyperbolic Tangent (atanh)", test_atanh),
    ("Random Uniform", test_uniform),
    ("Random Normal", test_normal),
    ("Random Integer", test_randint),
    ("Exponential Distribution", test_exponential),
    ("Gamma Distribution", test_gamma),
    ("Beta Distribution", test_beta),
    ("Triangular Distribution", test_triangular),
    ("Mersenne Twister (MT)", test_mt),
    ("Linear Congruential Generator (LCG)", test_lcg),
    ("Linear Lagged Generator (LLG)", test_llg),
]

# output
results = []
for name, func in operations:
    time = timeit.timeit(func, number = times)
    results.append((name, time))
    print(f"{name}: {time:.6f} seconds")

min_time = min([time for name, time in results])
output_data = [(name, time, time / min_time) for name, time in results]
df = pd.DataFrame(output_data, columns = ["Operation", "Time (seconds)", "Relative Time (min = 1)"])
df.to_csv("operation_timing_results.csv", index = False)

print("result:\n", df)

經由上述程式進行測試後,可以得到各種數學運算與偽隨機數產生方式的執行時間。由於每項測試皆重複執行 $10^8$ 次,因此表中的時間代表該運算大量執行時所累積的總耗時,而非單次運算所需時間。為了方便比較不同運算之間的效能差異,本文同時列出「相對耗時」(Relative Time),並以執行時間最低的乘法運算(Multiplication, *)作為基準值 1。測試結果如下表所示:

運算項目執行時間 (seconds)相對耗時
Multiplication (*)7.8796761.000
Subtraction (-)7.9226461.005
Addition (+)8.0031401.016
Division (/)8.0130741.017
Modulus (%)8.8231061.120
Absolute (abs)8.6883031.103
Mersenne Twister (MT)10.5629461.341
Square Root (sqrt)12.4810481.584
Exponential (exp)13.0038021.650
Sine (sin)13.1963231.675
Cosine (cos)13.3902401.699
Logarithm Base 10 (log10)13.6604721.734
Arctangent (atan)13.7103291.740
Hyperbolic Sine (sinh)14.4261541.831
Hyperbolic Cosine (cosh)14.4323881.832
Square (**)14.7487661.872
Arccosine (acos)15.0954591.916
Hyperbolic Tangent (tanh)15.1956171.928
Inverse Hyperbolic Cosine (acosh)14.8847971.889
Inverse Hyperbolic Sine (asinh)15.5598971.975
Tangent (tan)15.9032632.018
Power (pow)16.3763592.078
Inverse Hyperbolic Tangent (atanh)16.7084712.120
Logarithm (log)17.3605672.203
Random Uniform28.0619363.561
Exponential Distribution37.6720434.781
Linear Lagged Generator (LLG)36.6612244.653
Linear Congruential Generator (LCG)40.5223695.143
Triangular Distribution54.2954626.891
Random Normal62.2041527.894
Random Integer72.2156409.165
Gamma Distribution141.51939617.960
Beta Distribution281.85035135.769

由測試結果可以觀察到,最基本的四則運算所需時間相當接近,其中乘法運算速度最快,約花費 7.88 秒完成一億次計算;減法、加法與除法也皆落在約 8 秒左右,彼此差異非常小。這表示在現代 CPU 架構下,基本算術運算通常能透過硬體直接完成,因此其執行成本相當低。

在較複雜的數學函式方面,可以發現平方根、指數、對數以及三角函數的執行時間明顯高於基本四則運算。其中自然對數(log)約為乘法運算的 2.20 倍,而次方函式(pow)約為 2.08 倍。三角函數方面, sin()cos() 的執行時間約為 13 秒,而 tan() 則需要約 15.9 秒。

除了基本數學函式外,本次測試也比較了不同隨機數產生方式的效能。結果顯示,Python 內建的 Mersenne Twister(MT)僅需約 10.56 秒,明顯快於自行以 Python 實作的 LCG 與 LLG。雖然從演算法角度來看,LCG 與 Lehmer Generator 的計算流程非常簡單,但 Python 類別方法呼叫、物件狀態更新以及模運算等額外成本,使得實際執行速度低於經過高度最佳化的內建 random 模組。

在機率分布函式方面,可以觀察到其耗時普遍高於單純產生均勻分布亂數。例如 random.uniform() 約需 28 秒,而常態分布(Normal Distribution)則需要約 62 秒。這是因為許多機率分布並不是直接產生一個亂數,而是需要先取得基礎均勻分布亂數,再透過額外數學轉換得到目標分布,因此執行時間大幅增加。其中 Beta Distribution 的執行時間最高,約為 281.85 秒,是基本乘法運算的 35.77 倍。這顯示不同數學函式之間的計算成本差異非常明顯,即使它們最後都只回傳一個數值,其背後所使用的演算法複雜度可能存在巨大差異。

運行環境

  • 作業系統:Windows 11 25H2
  • 處理器:13th Gen Intel(R) Core(TM) i7-13700 (2.10 GHz)
  • 記憶體:32.0 GB
  • 程式語言:Python 3.10.11

參考資料