1. Reducing fractions
- Posted by "Juergen Luethje" <j.lue at gmx.de> May 23, 2005
- 417 views
Hi all, I'm looking for a special way to reduce several fractions. Say I want to multiply e.g. the fractions 3/8, 2/4 and 2/6. Of course I could do: numerator = 3*2*2 denominator = 8*4*6 and then calculate the GCD and reduce the fraction. But in order to avoid overflow for big numbers, the routine should reduce the fractions *before* it multiplies their numerators and denominators. Below you'll find my function 'reduced_fractions()', which looks at all pairs of numerators and denominators, and tries to reduce them (e.g. {3,8} means the fraction 3/8). It works fine, but can take a considerable amount of time. So I wonder whether the function actually has to look at all the pairs, or whether there is a faster way to achieve the same result.
global type bigint (object x) -- This type can hold bigger integers than Euphoria's built-in -- integer type (> 1073741823). -- It is technically an atom, but mathematically an integer. if atom(x) then return x = floor(x) end if return 0 end type global function gcd2 (bigint p, bigint q) -- return the greatest common divisor of p and q (Euclidean Algorithm) -- in : p, q: integers -- out: nonnegative integer (>= 0) bigint r while q do r = remainder(p, q) p = q q = r end while -- return abs(p) if p < 0 then p = -p end if return p end function global function reduced_fractions (sequence s) -- in: list of fractions to be reduced, -- of the form {{3,8}, {2,4}, {2,6}} bigint div for numerator = 1 to length(s) do for denominator = 1 to length(s) do div = gcd2(s[numerator][1], s[denominator][2]) if div > 1 then s[numerator] [1] /= div s[denominator][2] /= div end if end for end for return s end function ? reduced_fractions({{3,8}, {2,4}, {2,6}})
Regards, Juergen -- Have you read a good program lately?
2. Re: Reducing fractions
- Posted by Matt Lewis <matthewwalkerlewis at gmail.com> May 23, 2005
- 395 views
Juergen Luethje wrote: > > Hi all, > > I'm looking for a special way to reduce several fractions. > > Say I want to multiply e.g. the fractions 3/8, 2/4 and 2/6. > Of course I could do: > numerator = 3*2*2 > denominator = 8*4*6 > > and then calculate the GCD and reduce the fraction. But in order to > avoid overflow for big numbers, the routine should reduce the fractions > *before* it multiplies their numerators and denominators. > > Below you'll find my function 'reduced_fractions()', which looks at > all pairs of numerators and denominators, and tries to reduce them > (e.g. {3,8} means the fraction 3/8). > It works fine, but can take a considerable amount of time. So I wonder > whether the function actually has to look at all the pairs, or whether > there is a faster way to achieve the same result. As a first step optimization, you could ignore when the number is less than the square root of whatever your precision limit is. Assuming you're using doubles, then you can go up to 51 or 52 bits, which give you up to 2,251,799,813,685,250 or 4,503,599,627,370,500 as your max integers before you start losing precision. That means that you can safely ignore numbers up to either 47,453,132 or 67,108,864 (check the spec for a 64-bit floating point number--you'll get 1 additional digit over whatever the mantissa size is). Of course, you may well find that one large factoriztion takes longer than a few small factorizations, so you may have to be more clever in deciding when factoring is worth it. Beyond that, you'll probably need to investigate faster factoring methods. Algoritms you could investigate include: Quadratic Sieve General Number Field Sieve Lenstra Elliptic Curve Factorization Google will give you lots of results for these, but implementing them seems far from simple (and will likely include needing a good matrix library). Matt Lewis
3. Re: Reducing fractions
- Posted by "Juergen Luethje" <j.lue at gmx.de> May 23, 2005
- 408 views
- Last edited May 24, 2005
Matt Lewis wrote: <snip> > As a first step optimization, you could ignore when the number is less > than the square root of whatever your precision limit is. Assuming you're > using doubles, then you can go up to 51 or 52 bits, which give you up to > 2,251,799,813,685,250 or 4,503,599,627,370,500 as your max integers before > you start losing precision. That means that you can safely ignore numbers > up to either 47,453,132 or 67,108,864 (check the spec for a 64-bit floating > point number--you'll get 1 additional digit over whatever the mantissa size > is). I see. Should have thought of that myself ... > Of course, you may well find that one large factoriztion takes longer > than a few small factorizations, so you may have to be more clever in > deciding when factoring is worth it. I recognized that Ricardo's "genfunc.e" library contains PrimeFactors(), a basic function for factorization. I'll play with it a little. > Beyond that, you'll probably need > to investigate faster factoring methods. Algoritms you could investigate > include: > > Quadratic Sieve > General Number Field Sieve > Lenstra Elliptic Curve Factorization > > Google will give you lots of results for these, but implementing them > seems far from simple (and will likely include needing a good matrix > library). This seems to be a bit over my head, so I'll probably have to wait until someone provides an Eu library for it. Well, currently I don't need it for a real application. Thanks, Juergen
4. Reducing fractions
- Posted by "Christian Cuvier" <christian.cuvier at agriculture.gouv.fr> May 24, 2005
- 399 views
> Date: Mon, 23 May 2005 16:48:18 +0200 > From: "Juergen Luethje" <j.lue at gmx.de> > Subject: Reducing fractions > > > Hi all, > > I'm looking for a special way to reduce several fractions. > > Say I want to multiply e.g. the fractions 3/8, 2/4 and 2/6. > Of course I could do: > numerator = 3*2*2 > denominator = 8*4*6 > > and then calculate the GCD and reduce the fraction. But in order to > avoid overflow for big numbers, the routine should reduce the fractions > *before* it multiplies their numerators and denominators. > > Below you'll find my function 'reduced_fractions()', which looks at > all pairs of numerators and denominators, and tries to reduce them > (e.g. {3,8} means the fraction 3/8). > It works fine, but can take a considerable amount of time. So I wonder > whether the function actually has to look at all the pairs, or whether > there is a faster way to achieve the same result. > > }}} <eucode> > global type bigint (object x) > -- This type can hold bigger integers than Euphoria's built-in > -- integer type (> 1073741823). > -- It is technically an atom, but mathematically an integer. > if atom(x) then > return x = floor(x) > end if > return 0 > end type > > global function gcd2 (bigint p, bigint q) > -- return the greatest common divisor of p and q (Euclidean Algorithm) > -- in : p, q: integers > -- out: nonnegative integer (>= 0) > bigint r > > while q do > r = remainder(p, q) > p = q > q = r > end while > > -- return abs(p) > if p < 0 then > p = -p > end if > return p > end function [snip] You can optimize the gcd2 function in several ways:
function gcd2_notest(bigint p,bigint q) -- return the greatest common divisor of p and q (Euclidean Algorithm) -- in : p, q: integers, p>q>0 -- out: nonnegative integer (> 0) --internally used by gcd2, same algo as above but faster --as most tests are made only at the time they may fail, ie with raw args bigint r while q>1 do --this shaves an iteration off r=remainder(p,q) if r=0 then return q end if --q divides p p=q q=r --nonzero end while return 1 --p and q were relatively prime end function
global function gcd2(bigint p,bigint q) return the greatest common divisor of p and q (Euclidean Algorithm)
And don't forget to switch type checking off. I didn't try defining r as a local var instead, so as not to create and destroy it a zillion times on the stack. Depends on whether Eu relies on the stack to store private vars.
HTH CChris }}}
5. Re: Reducing fractions
- Posted by "Juergen Luethje" <j.lue at gmx.de> May 24, 2005
- 380 views
Christian Cuvier wrote: >> From: "Juergen Luethje" <snip> >> }}} <eucode> >> global type bigint (object x) >> -- This type can hold bigger integers than Euphoria's built-in >> -- integer type (> 1073741823). >> -- It is technically an atom, but mathematically an integer. >> if atom(x) then >> return x = floor(x) >> end if >> return 0 >> end type >> >> global function gcd2 (bigint p, bigint q) >> -- return the greatest common divisor of p and q (Euclidean Algorithm) >> -- in : p, q: integers >> -- out: nonnegative integer (>= 0) >> bigint r >> >> while q do >> r = remainder(p, q) >> p = q >> q = r >> end while >> >> -- return abs(p) >> if p < 0 then >> p = -p >> end if >> return p >> end function > > [snip] > > You can optimize the gcd2 function in several ways: > > }}} <eucode> > function gcd2_notest(bigint p,bigint q) > -- return the greatest common divisor of p and q (Euclidean Algorithm) > -- in : p, q: integers, p>q>0 > -- out: nonnegative integer (> 0) > --internally used by gcd2, same algo as above but faster > --as most tests are made only at the time they may fail, ie with raw args > bigint r > while q>1 do --this shaves an iteration off > r=remainder(p,q) > if r=0 then return q end if --q divides p > p=q > q=r --nonzero > end while > return 1 --p and q were relatively prime > end function > > global function gcd2(bigint p,bigint q) > -- return the greatest common divisor of p and q (Euclidean Algorithm) > -- in : p, q: integers, p>q>0 > -- out: nonnegative integer (>= 0) > --actually normalizes (p,q) and returns gcd2_notest's result > --returns 0 if p or q is 0 > if not (p and q) then return 0 end if > if p<0 then p=-p end if > if q<0 then q=-q end if > if p<q then p-=q q+=p p=q-p end if --swap arguments > return gcd2_notest(p,q) > end function > > And don't forget to switch type checking off. Thank you for looking into this issue. I made several tests with big integers, and your gcd2() function was always significantly slower than mine (Windows 98, exw.exe 2.5). > I didn't try defining r as a local var instead, so as not to create and > destroy it a zillion times on the stack. Depends on whether Eu relies on > the stack to store private vars. I don't think that calculating the Greatest Common Divisor itself is the time critical part of the whole program <http://www.listfilter.com/EUforum/m12539.html> anyway, since the Euclidean Algorithm is rather fast ( O(log(n)) ). For deteils see e.g. <http://mathworld.wolfram.com/EuclideanAlgorithm.html>. I believe most effective would be any attempt to reduce the number of iterations in the function reduced_fractions() ( currently O(n^2) ). Regards, Juergen