|
250 | 250 |
|
251 | 251 | <span class="kw">fn</span> <span class="ident">new</span>(<span class="ident">m</span>: <span class="ident">u64</span>) -> <span class="self">Self</span>;
|
252 | 252 | <span class="kw">fn</span> <span class="ident">modulus</span>(<span class="kw-2">&</span><span class="self">self</span>) -> <span class="ident">u64</span>;
|
253 |
| - <span class="kw">fn</span> <span class="ident">from_u64</span>(<span class="kw-2">&</span><span class="self">self</span>, <span class="ident">n</span>: <span class="ident">u64</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span>; |
| 253 | + <span class="kw">fn</span> <span class="ident">to_mod</span>(<span class="kw-2">&</span><span class="self">self</span>, <span class="ident">n</span>: <span class="ident">u64</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span>; |
254 | 254 | <span class="kw">fn</span> <span class="ident">to_u64</span>(<span class="kw-2">&</span><span class="self">self</span>, <span class="ident">n</span>: <span class="ident"><span class="self">Self</span>::ModInt</span>) -> <span class="ident">u64</span>;
|
255 | 255 | <span class="kw">fn</span> <span class="ident">add</span>(<span class="kw-2">&</span><span class="self">self</span>, <span class="ident">a</span>: <span class="ident"><span class="self">Self</span>::ModInt</span>, <span class="ident">b</span>: <span class="ident"><span class="self">Self</span>::ModInt</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span>;
|
256 | 256 | <span class="kw">fn</span> <span class="ident">mul</span>(<span class="kw-2">&</span><span class="self">self</span>, <span class="ident">a</span>: <span class="ident"><span class="self">Self</span>::ModInt</span>, <span class="ident">b</span>: <span class="ident"><span class="self">Self</span>::ModInt</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span>;
|
|
281 | 281 | }
|
282 | 282 |
|
283 | 283 | <span class="kw">fn</span> <span class="ident">one</span>(<span class="kw-2">&</span><span class="self">self</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span> {
|
284 |
| - <span class="self">self</span>.<span class="ident">from_u64</span>(<span class="number">1</span>) |
| 284 | + <span class="self">self</span>.<span class="ident">to_mod</span>(<span class="number">1</span>) |
285 | 285 | }
|
286 | 286 | <span class="kw">fn</span> <span class="ident">minus_one</span>(<span class="kw-2">&</span><span class="self">self</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span> {
|
287 |
| - <span class="self">self</span>.<span class="ident">from_u64</span>(<span class="self">self</span>.<span class="ident">modulus</span>() <span class="op">-</span> <span class="number">1</span>) |
| 287 | + <span class="self">self</span>.<span class="ident">to_mod</span>(<span class="self">self</span>.<span class="ident">modulus</span>() <span class="op">-</span> <span class="number">1</span>) |
288 | 288 | }
|
289 | 289 | <span class="kw">fn</span> <span class="ident">zero</span>(<span class="kw-2">&</span><span class="self">self</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span> {
|
290 |
| - <span class="self">self</span>.<span class="ident">from_u64</span>(<span class="number">0</span>) |
| 290 | + <span class="self">self</span>.<span class="ident">to_mod</span>(<span class="number">0</span>) |
291 | 291 | }
|
292 | 292 | }
|
293 | 293 |
|
|
347 | 347 | <span class="self">self</span>.<span class="ident">n</span>.<span class="ident">as_u64</span>()
|
348 | 348 | }
|
349 | 349 |
|
350 |
| - <span class="kw">fn</span> <span class="ident">from_u64</span>(<span class="kw-2">&</span><span class="self">self</span>, <span class="ident">x</span>: <span class="ident">u64</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span> { |
| 350 | + <span class="kw">fn</span> <span class="ident">to_mod</span>(<span class="kw-2">&</span><span class="self">self</span>, <span class="ident">x</span>: <span class="ident">u64</span>) -> <span class="ident"><span class="self">Self</span>::ModInt</span> { |
351 | 351 | <span class="comment">// TODO: optimise!</span>
|
352 | 352 | <span class="macro">debug_assert!</span>(<span class="ident">x</span> <span class="op"><</span> <span class="self">self</span>.<span class="ident">n</span>.<span class="ident">as_u64</span>());
|
353 | 353 | <span class="kw">let</span> <span class="ident">r</span> <span class="op">=</span> <span class="ident">T::from_double_width</span>(
|
|
423 | 423 | <span class="kw">let</span> <span class="ident">n</span> <span class="op">=</span> <span class="number">2</span> <span class="op">*</span> <span class="ident">n</span> <span class="op">+</span> <span class="number">1</span>;
|
424 | 424 | <span class="kw">let</span> <span class="ident">m</span> <span class="op">=</span> <span class="ident">Montgomery</span>::<span class="op"><</span><span class="ident">A</span><span class="op">></span><span class="ident">::new</span>(<span class="ident">n</span>);
|
425 | 425 | <span class="kw">for</span> <span class="ident">x</span> <span class="kw">in</span> <span class="number">0</span>..<span class="ident">n</span> {
|
426 |
| - <span class="kw">let</span> <span class="ident">m_x</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">from_u64</span>(<span class="ident">x</span>); |
| 426 | + <span class="kw">let</span> <span class="ident">m_x</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">to_mod</span>(<span class="ident">x</span>); |
427 | 427 | <span class="kw">for</span> <span class="ident">y</span> <span class="kw">in</span> <span class="number">0</span>..<span class="op">=</span><span class="ident">x</span> {
|
428 |
| - <span class="kw">let</span> <span class="ident">m_y</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">from_u64</span>(<span class="ident">y</span>); |
| 428 | + <span class="kw">let</span> <span class="ident">m_y</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">to_mod</span>(<span class="ident">y</span>); |
429 | 429 | <span class="macro">println!</span>(<span class="string">"{n:?}, {x:?}, {y:?}"</span>, <span class="ident">n</span> <span class="op">=</span> <span class="ident">n</span>, <span class="ident">x</span> <span class="op">=</span> <span class="ident">x</span>, <span class="ident">y</span> <span class="op">=</span> <span class="ident">y</span>);
|
430 | 430 | <span class="macro">assert_eq!</span>((<span class="ident">x</span> <span class="op">+</span> <span class="ident">y</span>) <span class="op">%</span> <span class="ident">n</span>, <span class="ident">m</span>.<span class="ident">to_u64</span>(<span class="ident">m</span>.<span class="ident">add</span>(<span class="ident">m_x</span>, <span class="ident">m_y</span>)));
|
431 | 431 | }
|
|
439 | 439 | <span class="kw">let</span> <span class="ident">n</span> <span class="op">=</span> <span class="number">2</span> <span class="op">*</span> <span class="ident">n</span> <span class="op">+</span> <span class="number">1</span>;
|
440 | 440 | <span class="kw">let</span> <span class="ident">m</span> <span class="op">=</span> <span class="ident">Montgomery</span>::<span class="op"><</span><span class="ident">A</span><span class="op">></span><span class="ident">::new</span>(<span class="ident">n</span>);
|
441 | 441 | <span class="kw">for</span> <span class="ident">x</span> <span class="kw">in</span> <span class="number">0</span>..<span class="ident">n</span> {
|
442 |
| - <span class="kw">let</span> <span class="ident">m_x</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">from_u64</span>(<span class="ident">x</span>); |
| 442 | + <span class="kw">let</span> <span class="ident">m_x</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">to_mod</span>(<span class="ident">x</span>); |
443 | 443 | <span class="kw">for</span> <span class="ident">y</span> <span class="kw">in</span> <span class="number">0</span>..<span class="op">=</span><span class="ident">x</span> {
|
444 |
| - <span class="kw">let</span> <span class="ident">m_y</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">from_u64</span>(<span class="ident">y</span>); |
| 444 | + <span class="kw">let</span> <span class="ident">m_y</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">to_mod</span>(<span class="ident">y</span>); |
445 | 445 | <span class="macro">assert_eq!</span>((<span class="ident">x</span> <span class="op">*</span> <span class="ident">y</span>) <span class="op">%</span> <span class="ident">n</span>, <span class="ident">m</span>.<span class="ident">to_u64</span>(<span class="ident">m</span>.<span class="ident">mul</span>(<span class="ident">m_x</span>, <span class="ident">m_y</span>)));
|
446 | 446 | }
|
447 | 447 | }
|
|
454 | 454 | <span class="kw">let</span> <span class="ident">n</span> <span class="op">=</span> <span class="number">2</span> <span class="op">*</span> <span class="ident">n</span> <span class="op">+</span> <span class="number">1</span>;
|
455 | 455 | <span class="kw">let</span> <span class="ident">m</span> <span class="op">=</span> <span class="ident">Montgomery</span>::<span class="op"><</span><span class="ident">A</span><span class="op">></span><span class="ident">::new</span>(<span class="ident">n</span>);
|
456 | 456 | <span class="kw">for</span> <span class="ident">x</span> <span class="kw">in</span> <span class="number">0</span>..<span class="ident">n</span> {
|
457 |
| - <span class="kw">let</span> <span class="ident">x_</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">from_u64</span>(<span class="ident">x</span>); |
| 457 | + <span class="kw">let</span> <span class="ident">x_</span> <span class="op">=</span> <span class="ident">m</span>.<span class="ident">to_mod</span>(<span class="ident">x</span>); |
458 | 458 | <span class="macro">assert_eq!</span>(<span class="ident">x</span>, <span class="ident">m</span>.<span class="ident">to_u64</span>(<span class="ident">x_</span>));
|
459 | 459 | }
|
460 | 460 | }
|
|
0 commit comments