Chapter 2

Writing Efficient Code

Problem I: Computing GCD

The Greatest Common Divisor (GCD) of two numbers is a foundational concept in mathematics and computer science. It refers to the largest integer, k, that divides both numbers without leaving a remainder. For instance:

• The GCD of 8 and 12 is 4, as 4 is the largest number that divides both 8 and 12.

• The GCD of 18 and 25 is 1, since 1 is the only number that divides both, making them coprime.

Another term used interchangeably with GCD is Highest Common Factor (HCF). It’s important to note that for any pair of numbers m and n, a GCD always exists because 1 is always a common divisor.

In this chapter, we will focus on how to compute the GCD of two numbers, explore different approaches, and examine how to write the code for computing GCD efficiently.

Approach 1: List of Common Factors

The first approach to calculating the GCD is straightforward:

1. Compute all the common factors of m and n by checking every number from 1 to min(m, n).

2. Store all these factors in a list.

3. Return the largest (last) factor in the list.

Let’s look at the Python code for this approach:

def gcd(m, n):
    cf = []  # List of common factors
    for i in range(1, min(m, n) + 1):
        if (m % i) == 0 and (n % i) == 0:
            cf.append(i)
    return cf[-1]  # Return the last element in the list (largest common factor)

How It Works:

• The function checks for every number from 1 to min(m, n) if it divides both m and n.

• If it does, it is added to the list cf.

• Finally, the largest common divisor (which is the last element in the list) is returned.

Points to Note:

• List Initialization: We need to initialize cf as an empty list to store common factors.

• Variable Types: Variables derive their type from the values they hold, so cf is a list because it holds multiple values.

• Control Flow: The if condition inside the for loop checks for divisibility, and range(1, min(m, n) + 1) iterates over all numbers between 1 and the smaller of the two numbers.

Efficiency Considerations:

The code is simple, but storing all common factors in a list adds unnecessary memory overhead. In most cases, we don’t need to store all the common factors—just the last one (the largest) is enough.

Approach 2: Optimized without List

We can improve on the previous solution by eliminating the list entirely. Instead of storing all common factors, we can keep track of the most recent common factor (mrcf) and return it after the loop finishes:

def gcd(m, n):
    for i in range(1, min(m, n) + 1):
        if (m % i) == 0 and (n % i) == 0:
            mrcf = i  # Update the most recent common factor
    return mrcf

How It Works:

• The loop works similarly to the first approach, checking for divisibility for all numbers between 1 and min(m, n).

• Instead of appending to a list, we update the variable mrcf each time a new common factor is found. By the end of the loop, mrcf holds the largest common divisor.

Efficiency Considerations:

This version improves memory usage by not maintaining a list. Only the last common factor is stored, which is more efficient in terms of space. Both versions, however, take time proportional to min(m, n) because we check every number up to min(m, n). Both approaches compute the GCD by iterating through all numbers between 1 and min(m, n), resulting in a time complexity of O(min(m, n)). While this is reasonable for small inputs, it can become inefficient for larger numbers.

Can We Do Better?

Yes, there is a more efficient method for computing GCD: Euclid’s Algorithm. This algorithm significantly reduces the number of steps required to compute the GCD by using the property:

gcd(m,n)=gcd(n,m%n)

Here’s the basic idea:

• If m is divisible by n, then n is the GCD.

• Otherwise, replace m with n and n with m % n, and repeat the process until n becomes zero. At that point, m is the GCD.

This algorithm reduces the time complexity to O(log(min(m, n))), which is far better than the previous approaches.

Conclusion: Computing GCD

Writing efficient code involves not only ensuring correctness but also optimizing both time and space complexity. In the case of computing the GCD:

• The first approach using a list is simple but inefficient in terms of memory.

• The second approach, which eliminates the list, improves memory efficiency but doesn’t improve the time complexity.

• For optimal performance, Euclid’s algorithm is the best choice, significantly reducing the time complexity.

When writing code, always aim for efficiency by analyzing the problem's requirements, examining potential bottlenecks, and selecting the best algorithm for the task at hand.

Problem II: Sum of Squares of Numbers in a List

Let’s consider another classic problem: finding the sum of squares of numbers in a list.

Given a list of integers, compute the sum of the squares of each number in the list. For example, for the list [1, 2, 3, 4], the sum of squares would be:

$$1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30$$

We’ll look at two approaches for solving this, one less efficient and one optimized.

---

Approach 1: Using a Loop (Basic Approach)

In this first approach, we loop through the entire list, square each element, and sum the results manually. Here's how we would code it:

def sum_of_squares(nums):
    total = 0
    for num in nums:
        total += num ** 2  # Square each number and add it to the total
    return total

How it Works:

• We initialize total to zero.

• We iterate over each number in the list nums, square it (num ** 2), and add it to total.

• Finally, we return the sum.

Time Complexity:

• Time complexity: The time complexity is O(n), where n is the number of elements in the list, since we process each element exactly once.

• Space complexity: The space complexity is O(1), as we use only a few extra variables (constant space).

Efficiency Considerations:

This approach works well for small to medium-sized lists, but for extremely large lists, the looping operation can become expensive in terms of time, particularly when working with very large datasets in a performance-critical application.

---

Approach 2: Using List Comprehension and Built-In Functions (Optimized)

Python provides several ways to optimize code for both readability and performance. In this approach, we use a list comprehension combined with Python’s built-in sum() function, which can optimize internal operations.

def sum_of_squares(nums):
    return sum(num ** 2 for num in nums)  # Using list comprehension and built-in sum()

How it Works:

• The expression num ** 2 for num in nums generates each squared number in the list.

• The built-in sum() function takes this generator and efficiently computes the total sum of squares.

• This approach eliminates the need for manual looping and accumulation of results.

Efficiency Considerations:

• Time complexity: Like the first approach, this approach has a time complexity of O(n) because it still needs to process each element in the list.

• Space complexity: O(1), but with a slightly smaller memory footprint since we’re using a generator expression, which doesn’t require creating an intermediate list.

While both approaches have the same time complexity, this second approach is often faster in practice due to Python’s built-in functions, which are optimized at a lower level (C implementation). In addition, using a list comprehension is typically faster than manual looping in Python.

---

Further Optimizations and Considerations

Both approaches above have the same theoretical time complexity, O(n), but the second approach is more Pythonic and typically runs faster because it leverages built-in functions optimized at the core level of Python. This highlights a critical concept: efficient code is not just about reducing time complexity, but also about leveraging optimized tools and writing concise, readable code.

Scenario Example: Large Datasets

Let’s say you are working with a list of 10 million numbers. The difference between these two approaches may not be visible for smaller datasets but becomes significant for larger datasets due to overhead.

Manual Looping:

• Iterates through each number and performs operations individually.

List Comprehension:

• Allows Python’s optimized internal mechanisms to handle iterations and summing.

Why Efficiency Matters:

• For small datasets, the difference between the two approaches may not be noticeable, and you might prioritize readability.

• For large datasets, using built-in functions and more concise syntax improves both performance and readability.

• Optimized code can lead to lower memory usage, shorter execution time, and faster results when working with large datasets.

Conclusion : Sum of Squares of Numbers in a List

Writing efficient code involves not only ensuring correctness but also optimizing both time and space complexity. In the case of computing the GCD:

• The first approach using a list is simple but inefficient in terms of memory.

• The second approach, which eliminates the list, improves memory efficiency but doesn’t improve the time complexity.

• For optimal performance, Euclid’s algorithm is the best choice, significantly reducing the time complexity.

When working on real-world problems, especially with large datasets, using optimized, built-in solutions wherever possible can significantly improve your code’s performance and maintainability. Efficiency in writing code is not just about minimizing time complexity but also involves writing clean, readable, and maintainable code. In the second example of calculating the sum of squares:

• Approach 1 is more traditional but less optimized.

• Approach 2 leverages Python's built-in functions and list comprehensions, making it both more efficient and more Pythonic.

When writing code, always aim for efficiency by analyzing the problem's requirements, examining potential bottlenecks, and selecting the best algorithm for the task at hand.

Problem III: Checking Primality and Generating Prime Numbers

This code introduces a variety of techniques for checking primality and generating lists of prime numbers, with multiple versions and approaches presented to highlight different levels of efficiency and complexity. The explanations below will walk through the logic behind each code block, comparing the different methods and explaining how they improve or optimize primality checking and counting primes.

A prime number is an integer greater than 1 that has no divisors other than 1 and itself. Efficiently checking if a number is prime and generating prime numbers is important in many fields, including cryptography.

Key Concepts:

1. Primality Test: Checking whether a number is prime.

2. Listing Primes: Generating lists of primes up to a certain number, or listing the first N primes.

3. Optimizing Efficiency: Reducing time complexity by minimizing the number of checks needed to confirm primality.

---

Code Block 1: Factor-Based Primality Test

Code:

def factors(n):
    fl = []  # factor list
    for i in range(1, n+1):
        if (n % i) == 0:
            fl.append(i)
    return fl

def prime(n):
    return factors(n) == [1, n]

Explanation:

• Factors Function: This function generates a list of factors of n by checking all numbers from 1 to n.

• Prime Function: It checks whether the list of factors of n is exactly [1, n]. If so, the number is prime.

Complexity and Efficiency:

• Time Complexity: O(n) for the factors() function, as it checks all numbers from 1 to n.

• Inefficiency: This approach is very inefficient because it checks all numbers from 1 to n to generate factors, even though only the first few factors are needed to determine if a number is prime. It also stores all factors in a list unnecessarily.

Improvement: Checking for Divisors

We can improve efficiency by directly checking if a number has any divisors between 2 and n-1, without generating all factors.

---

Code Block 2: Basic Primality Test (Brute Force)

Code:

def prime(n):
    result = True
    for i in range(2, n):
        if (n % i) == 0:
            result = False
    return result

Explanation:

• Instead of checking all factors, this function simply checks whether any number between 2 and n-1 divides n. If so, n is not prime.

Complexity and Efficiency:

• Time Complexity: O(n) because it checks all numbers from 2 to n-1.

• Improvement: This version is better than checking all factors, but it’s still inefficient because it checks every number up to n-1.

---

Code Block 3: Early Exit on First Factor

Code:

def prime(n):
    result = True
    for i in range(2, n):
        if (n % i) == 0:
            result = False
            break  # Abort loop
    return result

Explanation:

• This version adds an early exit (break) when a divisor is found, saving unnecessary iterations after the first factor is identified.

Complexity and Efficiency:

• Time Complexity: O(n) in the worst case (if no factors are found).

• Improvement: While this doesn't reduce the theoretical time complexity, it improves the average case by stopping early when a factor is found.

---

Code Block 4: Optimized Primality Test (Check Up to √n)

Code:

import math

def prime(n):
    result = True
    i = 2
    while result and i <= math.sqrt(n):
        if (n % i) == 0:
            result = False
        i += 1
    return result

Explanation:

• Instead of checking all numbers up to n-1, this version only checks divisors up to √n. This is based on the fact that if a number n is divisible by a number larger than √n, the corresponding divisor will be smaller than √n.

Complexity and Efficiency:

• Time Complexity: O(√n), a significant improvement over previous versions.

• Efficiency: This is much faster for large values of n, reducing the number of checks drastically, especially for larger numbers.

---

Code Block 5: Generating Lists of Prime Numbers

Code for Listing All Primes up to a Given Number:

def primesupto(m):
    pl = []  # prime list
    for i in range(2, m+1):
        if prime(i):
            pl.append(i)
    return pl

• This function generates all primes up to a number m by iterating through each number from 2 to m, checking for primality, and adding primes to the list.

Code for Listing the First N Primes:

def firstprimes(m):
    count, i, pl = 0, 2, []
    while count < m:
        if prime(i):
            count += 1
            pl.append(i)
        i += 1
    return pl

• This function generates the first m primes by counting primes one by one and adding them to a list until m primes have been found.

Complexity and Efficiency:

• Time Complexity: These functions have complexity proportional to the number of primality checks, which, if using the O(√n) primality test, results in an overall complexity of O(m * √n).

• Efficiency: These implementations benefit from the optimized primality test but can be further improved using advanced algorithms like the Sieve of Eratosthenes for generating primes up to a number m.

---

Code Block 6: Prime Differences

Code:

def primediffs(n):
    lastprime = 2
    pd = {}  # Dictionary for prime differences
    for i in range(3, n+1):
        if prime(i):
            d = i - lastprime
            lastprime = i
            if d in pd:
                pd[d] += 1
            else:
                pd[d] = 1
    return pd

Explanation:

• This function computes the differences between consecutive primes up to n. The differences are stored in a dictionary where the key is the difference, and the value is the count of how many times that difference occurs.

Complexity and Efficiency:

• Time Complexity: This depends on the efficiency of the primality test. Using the O(√n) primality test, the overall complexity is O(n * √n).

• Efficiency: The dictionary-based approach is efficient for counting differences, as dictionary lookups and updates are O(1) on average.

---

Conclusion: Optimizing Prime Computation

By progressively refining the approach:

1. Direct Factorization (Code Block 1) is very inefficient (O(n)), making it unsuitable for large numbers.

2. Basic Brute Force Primality Test (Code Block 2) improves on this but is still O(n).

3. Early Exit on First Factor (Code Block 3) optimizes the average case but does not reduce time complexity.

4. Optimized Primality Test up to √n (Code Block 4) greatly improves performance, reducing the number of checks to O(√n).

In practice, checking divisibility up to √n (Code Block 4) is the most efficient approach for primality testing, and it’s this technique that should be used in real-world scenarios. When generating large lists of primes, further improvements (like the Sieve of Eratosthenes) can be used for even greater efficiency.