Jump to content

Modular exponentiation: Difference between revisions

Modular exponentiation (view source)

Revision as of 05:25, 27 September 2020

589 bytes added ,  3 years ago
lambdatalk small change
m (→‎version 1: changed code to process with the minimum task's requirements (40 decimal digits).)
(lambdatalk small change)
Line 873:
=={{header|Lambdatalk}}==
<lang scheme>
 
{require lib_BN}
 
Using the lib_BN library for big numbers.
Note that {BN.compare a b} returns 1 if a > b, 0 if a = b and -1 of a < b.
 
{def power_mod
 
{lambda {:b :e :m :x}▼
{ifdef {= {BNpower_mod.compare :e 0} 1} r // erecursive loop >on 0x
▲ {lambda {:b :e :m :x}
then {power_mod {BN.% {BN.* :b :b} :m} // (b*b)%2▼
{if {BN.intPart= {BN./compare :e 20} 1} // if e//2 > 0
then {power_mod.r :m // then recurse with
{if {= {BN.compare% {BN.%* :eb 2:b} 0:m} 1} // eb = (b*b)%2 > 0
then {BN.%intPart {BN.*/ :be :x2} :m} // e = e // (b*x)%m2
:m else :x}} // m inchanged
{if {= {BN.compare {BN.% :e 2} 0} 1} // if e%2 > 0
else :x}}}
▲ then {power_mod then {BN.% {BN.* :b :bx} :m} // x = (b*bx)%2m
else :x}} // x inchanged
else :x}}} // else x
{lambda {:b :e :m}
{power_mod :b :e :m 1}}} // initialize x and loop
-> power_mod
 
1) we can use lib_BN for relatively small numbers
 
{BN.pow 2 100}
-> 1267650600228229401496703205376
{BN.% {BN.pow 2 100} 1000000}
-> 205376
 
2) we use power_mod for very big numbers
 
{power_mod
2988348162058574136915891421498819466320163312926952423791023078876139
2351399303373464486466122544523690094744975233415544072992656881240319
{BN.pow 10 40} 1}
-> 1527229998585248450016808958343740453059 // 2900ms
 
</lang>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/210362"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information