My friends have often joked around about me being a robot due to the logical and calculated methods I often use in trying to solve problems. Now in approaching the challenges I face in CSC148, I’m definitely seeing that side of me as an asset.

 

Since starting to study CS, questions that seemed easy to answer in the past feel like they require new and more precise answers. To solve a problem using Python, I need to answer not only the what question, but also the how question. And then, before continuing, ideally I should also ask, “Is this the most efficient way?”

 

For example, I decided to see if I could make a function that returned all prime numbers in a specified range. Here is my code:

 

def prime_numbers(num1, num2):
    """
    Return a list of all prime numbers between num1 and num2

    @param int num1: the smallest number to check
    @param int num2: the largest number to check
    @return: all the prime numbers between num1 and num2 inclusive
    @rtype: list of int

    >>> prime_numbers(2, 20)
    [2, 3, 5, 7, 11, 13, 17, 19]
    >>> prime_numbers(-5, 1)
    []
    >>> prime_numbers(23, 23)
    [23]
    """
    prime_accum = []
    if num1 < 2:
        num1 = 2
    if num2 - num1 > 10000:
        raise Exception('Number range too large, maximum range 10,000')
    for n in range(num1, num2 + 1):

        # Pull current testing number as n
        prime = True
        for test_n in range(2, n - 1):
            # Looking for remainder 0 for counter-example to prime.
            if not n % test_n:
                prime = False
                break  # Do not run extraneous tests.
        if prime:
            prime_accum.append(n)

    return prime_accum

 

If we were to ask ourselves the questions above:

 

“What’s a prime number?”
It’s a natural number that is only divisible by itself and 1.

 

“How do you determine if a number is prime?”
Divide it by every number from 2 up to but not including itself. If any of these attempts produce 0 remainder, the number is not prime.

 

“Is this the most efficient way?”
I’m sure that it’s not, and there are two factors that determine the efficiency of such a function.

 

The first is the math. As in, is my verbose answer to the how question ideal? In hindsight, I can see that it’s not. Because you don’t have to try your number against every number up to itself, but rather only other primes. Once the number is not divisible by 2, there’s no sense trying any other even number again. I have realized at least one way to improve on the math, so it is time to move on to the second part of the efficiency equation.

 

The implementation.Once you’ve thought through the math and come up with the best answer to how, you still have the power to make your computer work harder than it has to. For example, my first iteration did not have the break in the inner for loop which meant that even if a number was proven to be not prime, it unnecessarily kept checking until n – 1. This one word increased the efficiency of my script by several 100 percent.

 

But how to implement our realization that we need only check for primes within a range if we know all the primes in that range? If my range is (2, 10,000), then I can skip over every number found not prime up to the current one, but if my range is (10,000, 15,000), is it more or less efficient to first find the primes from 2 to 9,999? Perhaps I could have a library of primes up to 10,000 in an outside file that I then import if the range is above that. Then again for 100,000. And again for 1,000,000? Perhaps it can even be writing to a file within the loop and also reading from that file so that each time you rerun the function with higher numbers, it’s faster than before… but of course then you’ll eventually run out of space. So now it’s a matter of priorities and resource management in addition to efficiency.

 

A while after writing this code, I was thinking about the classes we were discussing in lecture and thought that this prime code but be used to make a somewhat efficient simplify method in class Rational.

 

def simplify(self):
    """
    Find the simplest form of the rational expression and set the rational
    self to that value.
    
    @type self: Rational
    @rtype: Rational

    >>> Rational.simplify(10, 12))
    (5, 6)
    >>> Rational.simplify(25, 75))
    (1, 3)
    """
    divisor = 1
    primes = prime.prime_numbers(2, min(self.num, self.denom))

    for number in primes:
        if number > min(self.num, self.denom):
            break
        while self.num % number == 0 and self.denom % number == 0:
            divisor *= number
            self.num = self.num / number
            self.denom = self.denom / number

    if divisor != 1:
        print('divided numerator and denominator by {}'.format(divisor))
    else:
        print('cannot be simplified')
    return self

A first method I considered was to create a list of factors for the numerator as well as for the denominator and then find like terms, remove them, and then multiply the remaining numbers. Though that’s surely less efficient, it does mean that I could easily implement a factor method that shows all the factors of both num and denom.

 

It’s funny that the prime numbers function gave me the idea of making this simplify function, though it isn’t really necessary… I just imagine it expedites the process. Though I now see that making a list of primes all the way to the smallest of the numerator and denominator may be a huge waste of time for large numbers since it might just divide by 2, 3, and 5 a bunch of times first. Probably better to have some sort of prime checker for a single number at a time rather than making this whole primes list ahead of time. It looks like I still have a long way to go. But it also looks like just writing about my ideas helps me see ways to improve them. Perhaps this SLOG idea is a pretty good one after all.