Question

Louis Reasoner is having great difficulty doing exercise \(1.24\). His fast- prime? test seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the expmod procedure to use an explicit multiplication, rather than calling square: (define (expmod base exp m) (cond \(((=\exp 0) 1)\) \(((\) even? exp) \((\) remainder \((*(\) expmod base \((/ \exp 2) \mathrm{m})\) \((\) expmod base \((/ \exp 2) \mathrm{m}))\) \((\) else \(\quad\) m)) \((\) remainder \((*\) base \((\) expmod base \((-\exp 1) \mathrm{m}))\) \(\quad\) m) \())\) "I don't see what difference that could make," says Louis. "I do." says Eva. "By writing the procedure like that, you have transformed the \(\Theta(\log n)\) process into a \(\Theta(n)\) process." Explain.

Short answer

Louis's code uses linear operations instead of logarithmic squaring, making it slower.

Step-by-step solution

Understanding Exponential Modulo

The `expmod` function calculates \((\text{{base}}^\text{{exp}}) \mod m\) using efficient methods like exponentiation by squaring, which should ideally run in logarithmic time complexity, \(\Theta(\log n)\). This involves reducing the number of multiplications needed by squaring the base whenever the exponent is even.

Analyzing the Provided Code

The given code replaces the squaring method with explicit multiplication. In the rewritten function, when the exponent is even, two \(\text{{expmod}}\) calls are made to halve the exponent, followed by multiplication of their results. Such a setup results in linear time complexity, \(\Theta(n)\), because it performs a multiplication for every decremented exponent, losing the advantage of squaring.

Comparing Time Complexities

In the original implementation using squaring, each squaring operation reduces the exponent size rapidly, leading to a logarithmic number of steps, \(\Theta(\log n)\). In contrast, the current explicit multiplication method involves repeatedly reducing the exponent by one or two, causing the function to be called \(n\) times instead of \(\log n\). This results in \(\Theta(n)\) complexity.

Understanding the Impact

The difference in implementation drastically changes execution time. With squaring, the number of multiplications required decreases significantly, while repeated multiplications based on conditional checks, as implemented here, increase the number of operations linearly with respect to the exponent, making it much slower. Eva understands this difference, thereby explaining the inefficiency.

Key concepts

Exponentiation by Squaring

Exponentiation by squaring is a powerful method for fast computation of large power values, especially in the context of modular arithmetic. This technique is used in algorithms where we need to compute \((\text{base}^\text{exp})\mod m\) efficiently. Rather than multiplying the base by itself exp times, which is computationally expensive, exponentiation by squaring uses the property that \(x^a\) multiplied by \(x^a\) equals \(x^{2a}\).
This reduces the number of operations significantly, especially when the exponent is large.

• When the exponent is even, we can square the base and halve the exponent.
• If the exponent is odd, we multiply the result by the base and reduce the exponent by one.

By structuring the calculation this way, the number of multiplications needed is minimized, and the function runs much faster with significantly reduced computational load compared to straightforward multiplication methods.

Logarithmic Complexity

Logarithmic complexity, often denoted as \(\Theta(\log n)\), is performance scaling where the running time grows logarithmically with the input size. In the case of exponentiation by squaring, each operation reduces the problem size substantially by halving the exponent.
This means that the time it takes to complete the algorithm is proportionally less than the size of the input, making the technique exceptionally fast for large numbers.

• At each step, the exponent is divided by 2, cutting down the number of operations exponentially.
• Logarithmic complexity results in fewer computational steps as opposed to a linear or quadratic approach.

This is why using exponentiation by squaring efficiently solves problems within a logarithmic framework. It is ideal for scenarios where quick, efficient power calculation is needed, such as cryptographic algorithms.

Linear Complexity

Linear complexity, represented as \(\Theta(n)\), characterizes algorithms whose running time increases directly with the size of the input. In Louis's incorrect implementation, the `expmod` function relied on a more repetitive approach where each decrease in the exponent led to multiple function calls and multiplications.

• Rather than leveraging the squaring technique, the function reduced the problem size by only small fractions.
• This approach results in a time complexity that increases proportionally with the exponent value.

As a consequence, the desired efficiency of an algorithm is compromised, becoming significantly slower with larger inputs, because every step involves as much processing as the size of the input. Fixed iterative calls multiply unnecessary layers of complexity, causing the algorithm to slow down considerably compared to the exponential by squaring which uses logarithmic steps.