Rosetta Code

Modular exponentiation: Difference between revisions

← Older editNewer edit →
Content deleted Content added
adding lambdatalk
m →‎{{header|REXX}}: added/changed whitespace and comments, optimized the function, simplified the function code, added wording in the REXX section header and the output section header.
Line 1,214:
=={{header|REXX}}==
===version 1===
This REXX program attempts to handle &nbsp; ''any'' <big> &nbsp; '''a''', &nbsp; '''b''', &nbsp; or &nbsp; '''m''', </big> &nbsp; but there are limits for any computer language.
<br>For some REXXes, it's around eight million digits for any arithmetic expression or value, which puts limitations on the ▼
<br>values of &nbsp; <big>a<sup>2</sup></big> &nbsp; or &nbsp; <big>10<sup>m</sup></big>.▼
 
▲<br>For some REXXes, it's around eight million digits for any arithmetic expression or value, which puts limitations on the
There is REXX code (below) to automatically adjust the number of digits to accommodate huge numbers which are ▼
▲<br>the values of &nbsp; <big>a<sup>2</sup></big> &nbsp; or &nbsp; <big>10<sup>m</sup></big>.
<br>computed when raising large numbers to some arbitrary power. ▼
 
<lang rexx>/*REXX program displays the modular exponentiation of: a**b mod M */▼
▲There isThis REXX program code (below)has code to &nbsp; automatically &nbsp; adjust the number of decimal digits to accommodate huge numbers which are
parse arg a b mm /*obtain optional args from the CL*/▼
▲<br>numbers which are computed when raising large numbers to some arbitrary power.
if a=='' | a=="," then a=2988348162058574136915891421498819466320163312926952423791023078876139▼
▲<lang rexx>/*REXX program displays the modular exponentiation of: a**b mod Mm */
if b=='' | b=="," then b=2351399303373464486466122544523690094744975233415544072992656881240319▼
ifparse arg a b m mm='' | mm="," then mm=40 /*MM notobtain specified?optional args from Usethe default.CL*/
▲if a=='' | a=="," then a= 2988348162058574136915891421498819466320163312926952423791023078876139
say 'a=' a; say " ("length(a) 'digits)' /*display the value of A. */▼
▲if b=='' | b=="," then b= 2351399303373464486466122544523690094744975233415544072992656881240319
say 'b=' b; say " ("length(b) 'digits)' /* " " " " B. */
if m ='' | m ="," dothen jm=1 40 for words(mm); y= word(mm, j) /*use one of the MM powers (list) /*Not specified? Then use default.*/
say copies('═a=', linesize()a - 1) " ("length(a) 'digits)' /*showdisplay athe nicevalue separatorof fenceA line(&length)*/
▲say 'ab=' a;b say " " ("length(ab) 'digits)' /* " /*display the value" of A. " " B " */
say 'a**b (mod 10**'y")=" powerMod(a,b,10**y) /*display the answer ───► console.*/▼
do j=1 for words(m); y= word(m, j) /*use one of the MM powers (list).*/
end /*j*/▼
exit say copies('═', linesize() - 1) /*stickshow a forknice in it, we'reseparator done.fence line*/
▲ say 'a**b (mod 10**'y")=" powerMod(a,b,10**y) /*display the answer ───► console.*/
▲ end /*j*/
▲parseexit 0 arg a b mm /*obtainstick a fork optionalin argsit, fromwe're thedone. CL*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
powerMod: procedure; parse arg x,p,m mm /*fast modular exponentiation code*/
parse value max(x*x, p, mmm)'E0' with "E" e /*obtain the biggest of the three.*/
numeric digits max(20, e+e) /*ensure big enough to handle A². */
$= 1 /*use this for the first value. */
do whileuntil p\==0 /*perform while until P is equal isn'tto zero.*/
if p // 2 then $= $ * x // m mm /*is P odd? (is ÷ remainder≡1remainder ≡ 1?).*/
p= p % 2; x= x * x // m mm /*halve P; calculate x² mod n */
end /*whileuntil*/; return $ /* [↑] keep mod'ing 'til equaluntil 0P=zero.*/</lang>
This REXX program makes use of &nbsp; '''LINESIZE''' &nbsp; REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console).
<br>The BIF is used to determine the width of a line separator &nbsp; (which are used to separate different outputs).
<br>The &nbsp; '''LINESIZE.REX''' &nbsp; REXX program is included here &nbsp; ──► &nbsp; [[LINESIZE.REX]].<br>
 
{{out|output|text=&nbsp; when using the inputs of: &nbsp; <tt> &nbsp; , &nbsp; , &nbsp; 40 &nbsp; 80 &nbsp; 180 &nbsp; 888 </tt>}}
<pre>
a= 2988348162058574136915891421498819466320163312926952423791023078876139 (70 digits)
b= 2351399303373464486466122544523690094744975233415544072992656881240319 (70 digits)▼
(70 digits)
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
▲b= 2351399303373464486466122544523690094744975233415544072992656881240319
(70 digits)
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**40)= 1527229998585248450016808958343740453059
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**80)= 53259517041910225328867076245698908287781527229998585248450016808958343740453059
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**180)= 31857295076204937005344367438778481743660325586328069392203762862423884839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
a**b (mod 10**888)= 261284964380836515397030706363442226571397237057488951313684545241085642329943676248755716124260447188788530017182951051652748425560733974835944416069466176713156182727448301838517000343485327001656948285381173038339073779331230132340669899896448938858785362771190460312412579875349871655999446205426049662261450633448468931573506876255644749155348923523680730999869785472779116009356696816952771965930728940530517799329942590114178284009260298426735086579254282591289756840358811
a**b (mod 10**888)= 261284964380836515397030706363442226571397237057488951313684545241085642329943676248755716124260447188788530017182951051652748425560733974835944416069466176713156182727448301838517
822151307479352856856983393715348870715239020037962938019847992960978849852850613063177471175191444262586321233906926671000476591123695550566585083205841790404069511972417770392822283604206143472509425391114072344402850867571806031857295076204937005344367438778481743660325586328069392203762862423884839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
00034348532700165694828538117303833907377933123013234066989989644893885878536277119046031241257987534987165599944620542604966226145063344846893157350687625564474915534892352368073099986978547277911600
and took 5.97 seconds.
93566968169527719659307289405305177993299425901141782840092602984267350865792542825912897568403588118221513074793528568569833937153488707152390200379629380198479929609788498528506130631774711751914442
62586321233906926671000476591123695550566585083205841790404069511972417770392822283604206143472509425391114072344402850867571806031857295076204937005344367438778481743660325586328069392203762862423884
839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
</pre>
 
===version 2===
This REXX version handles only up to 100 decimal digits.
<lang rexx>/* Modular exponentiation */
/* REXX Modular exponentiation */
 
numeric digits 100
Retrieved from "https://rosettacode.org/wiki/Modular_exponentiation"