1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Rep Power

    Arrow need some help optimizing a function to reduce fractions...

    i wrote a set of functions to reduce a fraction based on cancellation of prime factors in the nomenator and denomenator (are those the right terms? ). it works fine for small to medium-large fractions (e.g. 123456/654321), but as the numbers get bigger, it gets exponentially slower. i'm fairly certain that this is because of how the pfactor() function finds *every* factor (going down in steps of 1), and then sends the factor to isprime to test. the isprime function is already very speedy (0.004 cumtime for a 7-digit number), whereas the pfactor()... well, it leaves a lot to be desired (2-4 seconds for the same number). if anything, pfactor is what needs to be optimized. anyway, here's my code.

    from math import sqrt
    def isprime(c=12):
        """ Determines if a number is prime. Returns 1 for true, 0 for false. """
        c = abs(int(c))
        if c < 2: return 0
        for i in range(int(sqrt(c)) + 1)[2:]: # so 0 and 1 aren't counted
            if c % i == 0: return 0  # this means that c has prime factors, so it's not prime itself
        return 1  # if it made it this far, then it's prime
    def pfactor(c=20):
        """ Lists prime factors. Very slow when the numbers get larger. """
        list, i = [], c
        while c != 1:
            if c % i == 0 and isprime(i):
                while c % i == 0: c /= i; list.append(i)
            if i != 1: i -= 1
            elif i == 1: break
        return list
    def reduceFraction(n=16, d=2):
        """ Reduces a fraction.  """
        n, nmult, d, dmult = pfactor(n), 1, pfactor(d), 1
        for i in n:
            if i in d: n.remove(i); d.remove(i)
        for i in d: # i hate to do it twice, but  16/8 is *not* 4/2.
            if i in n: d.remove(i); n.remove(i)
        for i in n: nmult *= i
        for i in d: dmult *= i
        return [nmult, dmult]
    what might not be apparent about how pfactor works, is that it gets duplicate prime factors by dividing the original number by the prime factor until the modulus is no longer zero, each time appending the same number on. it then continues down the line until it finds another factor.

    can anyone suggest how to clean up the pfactor() so it produces the same results, but does so in a *much* faster way?

    oh and maybe someone can explain to me why i have to do the for i in array loop twice in the reduceFractions function. if i do it once, it can leave the factor arrays like [3, 3, 2],[2, 2] instead of what it should be doing, which is [3, 3],[2]

    thanks for any help
    Last edited by Sparky the Fox; June 25th, 2003 at 11:31 PM.
  2. #2
  3. Hello World :)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Mar 2003
    Hull, UK
    Rep Power

    Way, more maths

    Hey again Fox, can you post the maths to do each of these. i.e. work out a prime number and prime factor so i can work on it.

    Also when your doing things like this you might wana use a class (kinda a few inter-related functions).

  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Rep Power
    i dont know how to do a class

    i dont know the "official" algorithms for prime factors or prime numbers, but here's what my functions do (may require some jumping around with your reading! )
    prime factors:

    1. find the prime factors with pfactor()
    2. once the factors have been found, go through each item in the list and see if it's in the other list. if it is, remove it from both lists. for some reason, i had to do this both ways to remove all instances. this is equivalent when you cancel out common factors after you've written them out in a fraction.
    2. to get the new top and bottom numbers, multiply all of the left-over factors in the top by themselves, and do the same to the bottom.
    3. return the result

    1. take a variable and set it equal to the number to be factored.
    2. go down by one, each time testing for a modulus of zero, and if this is the case, test it for primeness with isprime()
    3. if it is prime, divide the original number by the prime factor until it can no longer be divided into a whole number, each time appending the same number to the list (e.g. 8 becomes 2, 2, 2).
    4. return this list

    1. take the square-root of the number and add one, put all numbers below this, except 0 and 1, into a range to be sorted through (square-root + 1 is an equivalent number when finding primes)
    2. for every number below this new value, test it for a modulus of zero. if it has one, then there are factors below this, so the number is not a prime.
    3. if it gets this far, it has no factors below it, so it is prime. return true.

    hope that helped clear things up =\ it's my method of testing *every* single number below the original value for a factor in pfactor that slows this down when the number gets huge. the other functions are sufficiently fast enough
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2001
    Houston, TX
    Rep Power
    I don't know what your input data looks like, but you could memoize your functions so that they store the results of past calls with the same arguments so that they don't have to compute them again. If you find that you calculate a few answers several times during the course of your program, then memoizing it may be a good idea. Here's a recipe:

    Debian - because life's too short for worrying.
    Best. (Python.) IRC bot. ever.
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Rep Power
    Hi sparky,
    I don't know well how python handle this, but in many languages it's not raccomended modyfing variables used to loop in the loop itself.
    This can produce strange effects like that one described by you in reduceFraction function, where you have to do the loop two times.
    I suggest try modifying the loop so u don't remove values from the two original lists, instead u can copy values which are not in both lists in two new lists used for result output.

  10. #6
  11. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Woodland Hills, Los Angeles County, California, USA
    Rep Power
    It's probably faster to compute the Highest Common Factor (or Greatest Common Divisor, as it is called by certain authorities). I explained how to do this in this thread:
    Fractions (int/int) question...

    The algorithm for computing the HCF of two numbers comes from Euclid. It is one of the oldest algorithms known to man:

    0. Given two numbers, call the smaller one divisor and the larger one dividee.
    1. Compute the reminder of dividee / divisor
    2. If reminder is 0, go to step 5
    3. Set dividee = divisor, divisor = reminder
    4. Go to step 1
    5. divisor is the highest common factor between the numbers

    So, all you need to do is compute the HCF between the two numbers. Then divide both numbers by the HCF and continue the process until the HCF between the two numbers is 1. The final values of the two numbers is the reduced fraction

    Here's the code translated into python:
    def reduce(x, y):
        num1 = x
        num2 = y
        divisor = hcf(num1, num2)
        while (divisor > 1):
            num1 = num1 / divisor
            num2 = num2 / divisor
            divisor = hcf(num1, num2)
        print "The fraction", x, "/", y, "can be reduced to", num1 , "/", num2
    def hcf(a, b):
        # First make sure that num1 is the greater of a and b
        if a >= b:
            num1 = a
            num2 = b
            num1 = b
            num2 = a
        if (num1 == 0 or num2 == 0):
            return 0
        remainder = num1 % num2
        while (remainder != 0):
            num1 = num2
            num2 = remainder
            remainder = num1 % num2
        return num2
    # Reduce the fraction
    x = 51848
    y = 62768
    reduce (x, y)
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo

IMN logo majestic logo threadwatch logo seochat tools logo