Algorithm for reducing fractions

[Squintz]

I need an algorithm for reducing fractions. There is a little twist to the problem. I am not viewing the problem as a fraction. For example:

 

a = 2

b = 4

 

I know that a and b will eventually be combined to produce a a/b string. But I need to keep them seperate for this particular problem. So knowing the values for a and b I need an algorithm that will reduce it.

 

Something like a = 2 / 2 = 1

and b = 4 / 2 = 2

 

I understand the prime factors plays a roll in the reduction of fractions but is the only way to find the prime numbers of a given number by looking it up in a table? Is there an equation for obtaining the prime numbers of a given number?

 

This is a learning exercise for a computer programmin class. It's not homework but I figure I would let you know my limitations. Please move this if you think its better suited in the computer science forum. It was more a math problem then a computer problem which is why I put it here.

 

The computer science equivalent question would be: How do I reduce a string representation of a fraction?

[timo]

There is no "equation" giving you the primefactors of a number. As a matter of fact, many encryption methods base on the fact that you need algorithms to determine the prime factors which take quite long.

A simple algorithm (non-optimized, just the first and most straightforward thing that comes to my mind right now) for getting the prime factors of a number would be something like this:

 

remnant = number->value

div = 2

while remnant > 1:

if (remnant modulo div = 0): remnant := remnant / div, number->AddPrimeFactor(div)

else : increase div by one

end of while loop

 

 

Reducing the string representation is then quite straightforward and will work the way you already proposed: Look for common primefactors and divide nominator and denominator by it.

[BigMoosie]

I wrote this a while ago and just adjusted it and commented it up for easy viewing. It will take an array of as many numbers as you want and will find the highest common factor. Hope you understand javaScript:

 

function getHCF(numArray){
var len = numArray.length; // how many values entered
var smallest=0; // stores the index of the smallest number in numArray

for (var i=0; i<len; i++)
	if (numArray[i] < numArray[smallest]) smallest=i; // find smallest number

// this test here checks if the HCF is the smallest number:
for (i=0; i<len; i++) if (numArray[i] % numArray[smallest] != 0) break;
if (i==len) return numArray[smallest];

// max stores the maximum number we will have to check as a factor
var max = Math.sqrt(numArray[smallest]);

// test stores the current number being check for division
var test=2;

// HCF stores the highest common factor found
var HCF = 1;

// iteration:
while (true){
	for (i=0; i<len; i++) if (numArray[i]%test!=0) break; // if this ever "break"s then i will be < len,
	if (i==len){ //'test' is a factor of each 'numArray' value
		for (i=0; i<len; i++) numArray[i]/=test;
		HCF*=test;
		max = Math.sqrt(numArray[smallest]);
	}
	else {
		if (test>max) break;
		test+=test>4?2:1;
	}
}
return HCF;
}

alert(getHCF([200,600,300]));

[timo]

EDIT: Forget it, I didn´t see that you don´t count up if you found a common factor.

[cosine]

I need an algorithm for reducing fractions. There is a little twist to the problem. I am not viewing the problem as a fraction. For example:

 

a = 2

b = 4

 

I know that a and b will eventually be combined to produce a a/b string. But I need to keep them seperate for this particular problem. So knowing the values for a and b I need an algorithm that will reduce it.

 

Something like a = 2 / 2 = 1

and b = 4 / 2 = 2

 

I understand the prime factors plays a roll in the reduction of fractions but is the only way to find the prime numbers of a given number by looking it up in a table? Is there an equation for obtaining the prime numbers of a given number?

 

This is a learning exercise for a computer programmin class. It's not homework but I figure I would let you know my limitations. Please move this if you think its better suited in the computer science forum. It was more a math problem then a computer problem which is why I put it here.

 

The computer science equivalent question would be: How do I reduce a string representation of a fraction?

 

have you heard of the Euclidean algorithm? That would give you the greatest common factor of two numbers a and b.

The algorithm basically says to subtract the lesser of the two numbers from the bigger number. Compare this difference to the lesser of the original numbers, subtract the lesser of those two from the larger, etc. Just don't subtract so much that you wind up with a 0 or negative number. So once you've gotten this number, that is the greatest common factor.

Example, find the GCF of 23 and 81:

1) 81-23 = 58

2) 58-23 = 35

3) 35-23 = 12

4) 23-12 = 11

5) 12-11 = 1

6) 11-1 = 10

7) 10-1 = 9

...

15) 2-1 = 1

16) 1-1 = 0

 

So the greatest common factor is 1.

 

Here is an example of numbers that aren't coprime: 16 and 56

1) 56-16 = 40

2) 40-16 = 24

3) 24-16 = 8

4) 16-8 = 8

5) 8-8 = 0

 

So the greatest common factor is 8.

 

Hope this helps.

[BigMoosie]

Gee that algorithm is much better than the one I used.

[cosine]

Gee that algorithm is much better than the one I used.

 

Yeah its really nifty. I couldn't give you the proof off hand, but you can verify that it seems to work. For a proof you could check Euclid's number theory chapters in the elements. Internet search Euclid's Elements, then somewhere from books 7-10 I think. Or you may be able to search "Euclidean algorithm" for a proof. But in any case it works.

[BigMoosie]

The algorith you specified would be:

 

 function gcd(a, b)
    while a ≠ b
        if a > b
            a := a - b
        else
            b := b - a
    return a

 

According to wiki a more efficient algorith is:

 

function gcd(a, b)
 while b ≠ 0
   var t := b
   b := a modulo b
   a := t
 return a

 

Though I would be inclined to initialise the variable t before entering the loop.