How to resolve the algorithm Modular exponentiation step by step in the ObjectIcon programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Modular exponentiation step by step in the ObjectIcon programming language
Table of Contents
Problem Statement
Find the last 40 decimal digits of
a
b
{\displaystyle a^{b}}
, where
A computer is too slow to find the entire value of
a
b
{\displaystyle a^{b}}
. Instead, the program must use a fast algorithm for modular exponentiation:
a
b
mod
m
{\displaystyle a^{b}\mod m}
. The algorithm must work for any integers
a , b , m
{\displaystyle a,b,m}
, where
b ≥ 0
{\displaystyle b\geq 0}
and
m
0
{\displaystyle m>0}
.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Modular exponentiation step by step in the ObjectIcon programming language
Source code in the objecticon programming language
# -*- ObjectIcon -*-
#
# This program is close to being an exact copy of the Icon.
#
import io # <-- Object Icon requires this for I/O.
procedure main()
local a, b # <-- Object Icon forces you to declare your variables.
a := 2988348162058574136915891421498819466320163312926952423791023078876139
b := 2351399303373464486466122544523690094744975233415544072992656881240319
# You could leave out the "io." in the call to "write" below,
# because there is some "compatibility with regular Icon" support in
# the io package.
io.write("last 40 digits = ", mod_power(a,b,(10^40)))
end
procedure mod_power(base, exponent, modulus)
local result
result := 1
while exponent > 0 do
{
if exponent % 2 = 1 then
result := (result * base) % modulus
exponent /:= 2
base := base ^ 2 % modulus
}
return result
end
You may also check:How to resolve the algorithm Command-line arguments step by step in the Pure programming language
You may also check:How to resolve the algorithm Factorial step by step in the Wrapl programming language
You may also check:How to resolve the algorithm Comments step by step in the Logo programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the Nyquist programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the BlitzMax programming language