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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<meta name="author" content="韩暮秋">
<meta name="subtitle" content="暮秋小屋">
<meta name="description" content="这里是暮秋小屋，思念和灵感的寄存处">
<meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan">
<title>
OCaml Core.Int.pow 的实现 |
暮秋小屋
</title>
<link rel="icon" href="/favicon.ico">
<!-- stylesheets list from _config.yml -->
<link rel="stylesheet" href="/css/style.css">
<link rel="preload" href="/fonts/FZYouSongS-509R.woff2" as="font" type="font/woff2" crossorigin>
<!-- scripts list from _config.yml -->
<script
src="/js/menu.js"></script>
<script
src="https://polyfill.alicdn.com/polyfill.js?features=es6"></script>
<script
id="MathJax-script"
async
src="https://lf6-cdn-tos.bytecdntp.com/cdn/expire-1-M/mathjax/3.2.0/es5/tex-mml-chtml.js"></script>
<meta name="generator" content="Hexo 6.3.0"></head>
<body>
<div class="wrapper">
<div class="header">
<div class="flex-container">
<div class="header-inner">
<div class="site-brand-container">
<a href="/">
暮秋小屋
</a>
</div>
<div id="menu-btn" class="menu-btn" onclick="toggleMenu()">
菜单
</div>
<nav class="site-nav">
<ul class="menu-list">
<li class="menu-item">
<a href="/">
主页
</a>
</li>
<li class="menu-item">
<a href="/categories/gallery/">
日记本
</a>
</li>
<li class="menu-item">
<a href="/tags/Medicine/">
泛医学
</a>
</li>
<li class="menu-item">
<a href="/tags/Technique/">
计算机
</a>
</li>
<li class="menu-item">
<a href="/tags/Life/">
生活
</a>
</li>
<li class="menu-item">
<a href="/archives">
全部
</a>
</li>
<li class="menu-item">
<a href="/about">
关于
</a>
</li>
<li class="menu-item">
<a href="/search">搜索</a>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="main">
<div class="flex-container">
<article id="post">
<div class="post-head">
<div class="post-info">
<div class="tag-list">
<span class="post-tag">
<a href="/tags/Technique/">
Technique
</a>
</span>
</div>
<div class="post-title">
OCaml Core.Int.pow 的实现
</div>
<span class="post-date">
Oct 21, 2023
</span>
</div>
<div class="post-img">
<div class="h-line-primary"></div>
</div>
</div>
<div class="post-content">
<p>Core内部直接引用的Base的实现， Base的实现在 <a target="_blank" rel="noopener" href="https://github.com/janestreet/base/blob/494a0876168d24cda695cbb9a3d86ad8d1eb97d8/src/int_math.ml#L11-L18">src/int_math.ml</a> 中：</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> int_pow base exponent =</span><br><span class="line"> <span class="keyword">if</span> exponent < <span class="number">0</span> <span class="keyword">then</span> negative_exponent <span class="literal">()</span>;</span><br><span class="line"> <span class="keyword">if</span> abs base > <span class="number">1</span></span><br><span class="line"> && (exponent > <span class="number">63</span></span><br><span class="line"> || abs base > <span class="type">Pow_overflow_bounds</span>.int_positive_overflow_bounds.(exponent))</span><br><span class="line"> <span class="keyword">then</span> overflow <span class="literal">()</span>;</span><br><span class="line"> int_math_int_pow base exponent</span><br><span class="line">;;</span><br></pre></td></tr></table></figure>
<p>其中 <code>int_math_int_pow()</code> 由 C 实现:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">external</span> int_math_int_pow : <span class="built_in">int</span> -> <span class="built_in">int</span> -> <span class="built_in">int</span> = <span class="string">"Base_int_math_int_pow_stub"</span> [@@noalloc]</span><br></pre></td></tr></table></figure>
<p>其实现在 <a target="_blank" rel="noopener" href="https://github.com/janestreet/base/blob/494a0876168d24cda695cbb9a3d86ad8d1eb97d8/src/int_math_stubs.c#L56-L92">src/int_math_stubs.c</a> 中:</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">static</span> <span class="type">int64_t</span> <span class="title function_">int_pow</span><span class="params">(<span class="type">int64_t</span> base, <span class="type">int64_t</span> exponent)</span> {</span><br><span class="line"> <span class="type">int64_t</span> ret = <span class="number">1</span>;</span><br><span class="line"> <span class="type">int64_t</span> mul[<span class="number">4</span>];</span><br><span class="line"> mul[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"> mul[<span class="number">1</span>] = base;</span><br><span class="line"> mul[<span class="number">3</span>] = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">while</span> (exponent != <span class="number">0</span>) {</span><br><span class="line"> mul[<span class="number">1</span>] *= mul[<span class="number">3</span>];</span><br><span class="line"> mul[<span class="number">2</span>] = mul[<span class="number">1</span>] * mul[<span class="number">1</span>];</span><br><span class="line"> mul[<span class="number">3</span>] = mul[<span class="number">2</span>] * mul[<span class="number">1</span>];</span><br><span class="line"> ret *= mul[exponent & <span class="number">3</span>];</span><br><span class="line"> exponent >>= <span class="number">2</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> ret;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>这是一个四分快速幂的实现，它是二分快速幂的一种变种。二分快速幂将指数分为两部分，然后递归地计算每一部分的结果。<br>
而四分快速幂将指数分为四部分，然后递归地计算每一部分的结果。<br>
这里通过将指数右移2位（相当于除以4）和使用位与操作来实现，进一步减少了乘法次数。</p>
<p>主要步骤：</p>
<ul>
<li>初始化返回值ret为1，和一个包含4个元素的数组mul, mul[0]和mul[3]被初始化为1， mul[1]被初始化为基数</li>
<li>当指数不为0时，执行循环, 在每次循环中，首先更新mul数组的值
<blockquote>
<p>mul[1]是基数和mul[3]的乘积，mul[2]是mul[1]的平方，mul[3]是mul[2]和基数的乘积</p>
</blockquote>
</li>
<li>然后，将ret乘以mul数组中的一个元素, 这个元素的索引是指数和3的位与运算的结果
<blockquote>
<p>这样做的目的是为了选择正确的乘数，因为指数被分解为4的倍数</p>
</blockquote>
</li>
<li>最后，将指数右移2位，相当于将指数除以4</li>
<li>当指数变为0时，循环结束，返回ret</li>
</ul>
<p>这个实现的优点是它可以在对数时间内计算出幂运算，而且每次循环只需要4次乘法。这比标准的二分快速幂算法需要的乘法次数更少。</p>
</div>
<script>
window.onload = detectors();
</script>
<div class="post-footer">
<div class="h-line-primary"></div>
<nav class="post-nav">
<div class="prev-item">
<div class="icon arrow-left"></div>
<div class="post-link">
<a href="/2023/10/22/%E5%86%AC%E5%AD%A3%E5%92%B3%E5%97%BD%E8%BE%A8%E5%88%AB%E6%8C%87%E5%8D%97/">Prev</a>
</div>
</div>
<div class="next-item">
<div class="icon arrow-right"></div>
<div class="post-link">
<a href="/2023/10/13/%E8%82%9D%E5%8A%9F%E8%83%BD%E6%A3%80%E6%9F%A5%E5%8C%96%E9%AA%8C%E5%8D%95/">Next</a>
</div>
</div>
</nav>
</div>
<div class="post-comment">
</div>
</article>
</div>
</div>
<div class="footer">
<div class="flex-container">
<div class="footer-text">
韩暮秋 |
希望路过的人可以添点柴火让这里暖和点
</div>
</div>
</div>
</div>
<script src="/js/mermaid-zoom.js"></script>
</body>
</html>
|
