Rosetta Code

Modular exponentiation: Difference between revisions

Page Discussion

Modular exponentiation (view source)

Revision as of 18:35, 9 April 2020

5,204 bytes removed ,  4 years ago
m
→‎{{header|REXX}}: removed three tests that needn't be performed, used a template for the output..
m (→‎{{header|Haskell}}: Added variant defined in terms of `until`)
m (→‎{{header|REXX}}: removed three tests that needn't be performed, used a template for the output..)
Line 1,182:
There is REXX code (below) to automatically adjust the number of digits to accommodate huge numbers which are
<br>computed when raising large numbers to some arbitrary power.
<lang rexx>/*REXX program displays the modular exponentiation of: a**b mod M */
parse arg a b mm /*obtain optional args from the CL*/
if a=='' | a=="," then a=2988348162058574136915891421498819466320163312926952423791023078876139
Line 1,189:
say 'a=' a; say " ("length(a) 'digits)' /*display the value of A. */
say 'b=' b; say " ("length(b) 'digits)' /* " " " " B. */
do j=1 for words(mm); y= word(mm, j) /*use one of the MM powers (list).*/
 
dosay j=1copies('═', linesize() for- words(mm1); m=word(mm,j) /*useshow onea ofnice theseparator MMfence powers (list).line*/
say 'a**b (mod 10**'my")=" powerMod(a,b,10**my) /*display the answer ───► console.*/▼
say copies('─', linesize()-1) /*show a nice separator fence line*/
▲ say 'a**b (mod 10**'m")=" powerMod(a,b,10**m) /*display the answer ───► console.*/
end /*j*/
exit /*stick a fork in it, we're done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
powerMod: procedure; parse arg x,p,nm /*fast modular exponentiation code*/
if p==0 then return 1 parse value max(x*x, p, m)'E0' with "E" e /*specialobtain casethe biggest of the P being zerothree. */
if p==1 then return x numeric digits max(20, e+e) /*big enough to "handle A². " " " " unity.*/
if$= p<01 then do; say '***error*** power is negative:' p; exit 13; end /*use this for the first value. */
parse value max(x**2, do while p,n)'E0'\==0 with "E" e /*obtainperform the biggestwhile of the threeP isn't zero.*/
numeric digits max(20, e*2) if p//2 then $= $ * x // m /*big enough to handle A². /*is P odd? (is ÷ remainder≡1).*/
$=1 p= p % 2; x= x * x // m /*halve P; calculate x² mod /*use this for the first value. n */
end do /*while p\==0 */; return $ /*perform [↑] while keep mod'ing P'til equal isn't zero0.*/</lang>
if p//2 then $=$ * x // n /*is P odd? (is ÷ remainder≡1).*/
p=p%2; x=x * x // n /*halve P; calculate x² mod n */
end /*while*/ /* [↑] keep mod'ing 'til equal 0.*/
return $</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 &nbsp; '''LINESIZE.REX''' &nbsp; REXX program is included here &nbsp; ──► &nbsp; [[LINESIZE.REX]].<br>
 
'''{{out|output''' |text=&nbsp; when using the inputinputs of: &nbsp; <tt> &nbsp; , &nbsp; , &nbsp; 40 &nbsp; 80 &nbsp; 180 &nbsp; 888 </tt>}}
 
Note the REXX program was executing within a window of 600 characters wide, and even with that, the last result wrapped.
<pre>
a= 2988348162058574136915891421498819466320163312926952423791023078876139
Line 1,219 ⟶ 1,212:
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)= 261284964380836515397030706363442226571397237057488951313684545241085642329943676248755716124260447188788530017182951051652748425560733974835944416069466176713156182727448301838517
a**b (mod 10**888)= 2612849643808365153970307063634422265713972370574889513136845452410856423299436762487557161242604471887885300171829510516527484255607339748359444160694661767131561827274483018385170003434853270016569482853811730383390737793312301323406698998964489388587853627711904603124125798753498716559994462054260496622614506334484689315735068762556447491553489235236807309998697854727791160093566968169527719659307289405305177993299425901141782840092602984267350865792542825912897568403588118221513074793528568569833937153488707152390200379629380198479929609788498528506130631774711751914442
00034348532700165694828538117303833907377933123013234066989989644893885878536277119046031241257987534987165599944620542604966226145063344846893157350687625564474915534892352368073099986978547277911600
62586321233906926671000476591123695550566585083205841790404069511972417770392822283604206143472509425391114072344402850867571806031857295076204937005344367438778481743660325586328069392203762862423884839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
93566968169527719659307289405305177993299425901141782840092602984267350865792542825912897568403588118221513074793528568569833937153488707152390200379629380198479929609788498528506130631774711751914442
62586321233906926671000476591123695550566585083205841790404069511972417770392822283604206143472509425391114072344402850867571806031857295076204937005344367438778481743660325586328069392203762862423884
839076695547212682454523811053259517041910225328867076245698908287781527229998585248450016808958343740453059
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/210351"