Modular exponentiation: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
|||
Line 972: | Line 972: | ||
{{out}} |
{{out}} |
||
<pre>1527229998585248450016808958343740453059</pre> |
<pre>1527229998585248450016808958343740453059</pre> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Also works with gojq, the Go implementation of jq, and with fq.''' |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
<syntaxhighlight lang=jq> |
|||
# To take advantage of gojq's arbitrary-precision integer arithmetic: |
|||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
|||
# Returns (. ^ $exp) % $mod |
|||
# where $exp >= 0, $mod != 0, and the input are integers. |
|||
def modPow($exp; $mod): |
|||
if $mod == 0 then "Cannot take modPow with modulus 0." | error |
|||
elif $exp < 0 then "modPow with exp < 0 is not supported." | error |
|||
else . as $x |
|||
| {r: 1, base: ($x % $mod), exp: $exp} |
|||
| until( .exp <= 0 or .emit; |
|||
if .base == 0 then .emit = 0 |
|||
else if .exp%2 == 1 |
|||
then .r = (.r * .base) % $mod |
|||
| .exp |= (. - 1) / 2 |
|||
else .exp /= 2 |
|||
end |
|||
| .base |= (. * .) % $mod |
|||
end ) |
|||
| if .emit then .emit else .r end |
|||
end; |
|||
def task: |
|||
2988348162058574136915891421498819466320163312926952423791023078876139 as $a |
|||
| 2351399303373464486466122544523690094744975233415544072992656881240319 as $b |
|||
| (10|power(40)) as $m |
|||
| $a | modPow($b; $m) ; |
|||
task |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
1527229998585248450016808958343740453059 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |