Warning! This site is under development.
This class will be recorded! Its use will be limited to members of the class. Please do not share with others.
Approximate overview
expmod, our new exampleWe have four class sessions left. In addition to some random smallish topics, I have two big topics left to cover: Command-line processing and debugging. What else would you like to cover? (Yes, I have other things up my sleeve; I’d just like to give you some options.)
Goal: Compute (x^n) mod m, where x, n, and m are all non-negative long
values.
Assume: x < m and m < sqrt(LONG_MAX).
Obvious solution:
long
expmod(long x, long n, long m)
{
long result = 1;
for (i = 0; i < n; i++)
{
result = (result * x) % m;
} // for
return result;
} // expmod
mod each time through so that we don’t overflow.Can we do a more efficient solution?
long
expmod (long x, long n, long m)
{
if (0 == n) // x^0 = 1
{
return 1;
}
else if ((n % 2) == 0) // even
{
long tmp = expmod (x, n/2, m); // x^(2k) = x^k * x^k
return (tmp * tmp) % m;
} // even
else // odd
{
long tmp = expmod (x, n-1, m); // x^(k+1) = x^k * x
return (x * tmp) % m;
} // odd
} // expmod
Let’s put things together into a project. What files will you create?
expmod.h, declares long expmod (long x, long n, long m);expmod-recursive.c, declares our recursive version of expmodexpmod-slow.c, declares our iterative, correct, and slow version
of `expmod.expmod-bad.c, declares the incorrect iterative version.expmod-iterative.c, declares the (not-yet-developed) correct iterative
version.Why doesn’t Teams tell you it’s downloading?
How can we make sure that this code (or any code) is correct?
I’ve claimed this version is more efficient in terms of calls to multiplication, division, and exponentation. How can we check that (other than just manually)?
time command or graphing the time for different
inputs.How do we define MULTIPLY so that it can both increment a counter
and return a value?
#define MULTIPLY(X,Y) do { ++MULTIPLICATIONS; ((X)*(Y)); } while (0)
Doesn’t work because it doesn’t return a value.
#define MULTIPLY(X,Y) ((++_MULTIPLICATIONS * 0) + ((X)*(Y)))
How can we turn that wonderful recursive solution into a slightly-less-wonderful, but somewhat-more-efficient iterative solution?
Here’s an incorrect solution submitted by a student.
long
expmod_iterative(long x, long n, long m)
{
long result = 1;
for (size_t i = 0; i < n; i++)
{
if (!(n % 2)) // n is even
{
long tmp = (result * x) % m; // calculate x^k
result = (tmp * tmp) % m; // x^(2k) = x^k + x^k
n /= 2; // now we can halve n
} // n is even
else // n is odd
{
result = (result * x) % m;
} // n is odd
} // for
return result;
} // expmod_iterative
How can we tell it’s incorrect? How can we fix it?
Manually use this to compute 2^8.
Initially
Maybe we’ll try again next time.
long
expmod (long x, long n, long m)
{
if (0 == n) // x^0 = 1
{
return 1;
}
else if ((n % 2) == 0) // even
{
return expmod (x*x % m, n/2, m); // x^(2k) = (x^2)^k; k = n/2
} // even
else // odd
{
long tmp = expmod (x, n-1, m); // x^(k+1) = x^k * x; k = n - 1
return (x * tmp) % m;
} // odd
} // expmod
How would our code change if we just wanted to compute x^n, where x
is a double and n is a non-negative long value?