|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
SlickEdit: Code in over 40 languages across 7 platforms. SlickEdit’s unmatched power, speed, and flexibility allows even the most accomplished developers to write better code faster. Download a free trial today! |
|
#1
June 25th, 2003, 11:27 PM
|
|||
|
|||
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.
|
|
#2
June 26th, 2003, 10:23 AM
|
||||
|
||||
|
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.
|
|
#3
June 26th, 2003, 01:01 PM
|
|||
|
|||
|
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
|
|
#4
June 26th, 2003, 02:52 PM
|
|||
|
|||
|
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
|
|
#5
July 23rd, 2003, 05:07 AM
|
|||
|
|||
|
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
|
|
#6
July 23rd, 2003, 12:18 PM
|
||||
|
||||
|
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 Puzzle of the Month solved by sizeablegrin, etienne141 and L7Sqr, superior C/C++ programmers of the month
|
|
| Viewing: Dev Shed Forums > Programming Languages > Python Programming > need some help optimizing a function to reduce fractions... |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
