mirror
/
RosettaCodeData
mirror of https://github.com/acmeism/RosettaCodeData.git
1
0
Fork 0
Code Issues Packages Projects Releases Wiki Activity
RosettaCodeData/Task/Modular-exponentiation/Phix/modular-exponentiation.phix

36 lines
7.6 KiB
Plaintext
Raw Permalink Blame History

(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mpz_mod_exp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">exponent</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">modulus</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">result</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">exponent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">_exp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">exponent</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (use a copy)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">odd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">_exp</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">odd</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">_exp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">_exp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_fdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">_exp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">_exp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">mpz_mod_exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">_exp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">modulus</span><span style="color: #0000FF;">,</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">_exp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">_exp</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">odd</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">modulus</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">base</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"2988348162058574136915891421498819466320163312926952423791023078876139"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">exponent</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"2351399303373464486466122544523690094744975233415544072992656881240319"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">modulus</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">mpz_mod_exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">exponent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">modulus</span><span style="color: #0000FF;">,</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- check against the builtin:</span>
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">exponent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">modulus</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)</span>
<!--
Reference in New Issue View Git Blame Copy Permalink