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

Dev Shed Forums Sponsor:

June 25th, 2003, 11:27 PM

Sparky the Fox

Junior Member

Join Date: Jun 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

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.

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.

June 26th, 2003, 10:23 AM

netytan

Hello World :)

Join Date: Mar 2003

Location: Hull, UK

Posts: 2,537

Time spent in forums: 1 Week 2 Days 18 h 17 m 47 sec
Reputation Power: 68

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).

Ta,
Mark.

June 26th, 2003, 01:01 PM

Sparky the Fox

Junior Member

Join Date: Jun 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

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:

reducefractions():
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

pfactor()
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

isprime()
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

June 26th, 2003, 02:52 PM

Strike

Contributing User

Join Date: Dec 2001

Location: Houston, TX

Posts: 383

Time spent in forums: 1 h 41 m 27 sec
Reputation Power: 12

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:

http://aspn.activestate.com/ASPN/Co...on/Recipe/52201

__________________
Debian - because life's too short for worrying.
Best. (Python.) IRC bot. ever.

July 23rd, 2003, 05:07 AM

Tio

Junior Member

Join Date: Jul 2003

Posts: 5

Time spent in forums: < 1 sec
Reputation Power: 0

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.

HTH
Tio

July 23rd, 2003, 12:18 PM

Scorpions4ever

Banned ;)

Dev Shed God 9th Plane (9000 - 9499 posts)

Join Date: Nov 2001

Location: Woodland Hills, Los Angeles County, California, USA

Posts: 9,389

Time spent in forums: 1 Month 4 Weeks 1 Day 22 h 1 m 11 sec
Reputation Power: 4080

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:
http://forums.devshed.com/showthrea...&threadid=44874

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:

Code:

#!/usr/bin/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
    else:
        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

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

Developer Shed Advertisers and Affiliates