Greatest Common Factor
I'm working on a PHP class to, given two given points (x1,y1) and (x2,y2), create the standard form equation of the line containing the two points. I have all of the computation worked out, but I need to simplify the equation by finding the greatest common factor of the three numbers. For instance, the greatest common factor of 8, 20, and 36 is 4. I understand how to do this with two values (a and b), something like this:
do
{
$rest=$a%$b;
$a=$b;
$b=$rest;
}
while($rest!==0);
$gcd = $a;Like I said, however, I need to do something like this with three given values (a, b, and c). The only thing I can currently think of is to do something like the following:
for ($n=2;$n<=100;$n++) {
if (($a%$n) == 0) && ($b%$n) == 0) && ($c%$n) == 0)) {
$a /= $n;
$b /= $n;
$c /= $n;
}
}Surely (and hopefully) there is a more efficient way to go about this. This current method takes quite a long time and only ends at 100 to make it stop at a reasonable time. Anyone have any ideas?
Kurtis
kazimmerman posted this at 04:23 — 9th November 2008.
He has: 698 posts
Joined: Jul 2005
I hate to answer my own question, but after asking I had an epiphany and checked some things mathematically before stumbling upon this truth:
gcd(a,b,c) = gcd(gcd(a,b),c)
Therefore, the following can be done in PHP:
function gcd($x,$y) {do
{
$rest=$x%$y;
$x=$y;
$y=$rest;
}
while($rest!==0);
return $x;
}
$gcd = gcd(gcd($a,b),$c);
Perhaps that will help someone else in the future, but just posting the question seemed to help me think of an answer.
Kurtis
teammatt3 posted this at 06:17 — 9th November 2008.
He has: 2,102 posts
Joined: Sep 2003
Yuck! I hate the standard form of a line. Math junkies just created form that because mx+b was too easy for regular people to understand
Anyway, here's the code I use in my fraction class. I don't understand it at all, but it probably has a faster runtime than your current algo. I got it from the Wikipedia.
<?php
// returns the greatest common factor of two integers, got it from the wikipedia
function gcf($u, $v)
{
$u = abs($u);
$v = abs($v);
/* GCD(0,x) := x */
if ($u == 0 || $v == 0)
return $u | $v;
/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
for ($shift = 0; (($u | $v) & 1) == 0; ++$shift)
{
$u >>= 1;
$v >>= 1;
}
while (($u & 1) == 0)
$u >>= 1;
/* From here on, u is always odd. */
do
{
while (($v & 1) == 0) /* Loop X */
$v >>= 1;
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
if ($u < $v)
{
$v -= $u;
}
else
{
$diff = $u - $v;
$u = $v;
$v = $diff;
}
$v >>= 1;
}
while ($v != 0);
return $u << $shift;
}
?>
kazimmerman posted this at 18:18 — 9th November 2008.
He has: 698 posts
Joined: Jul 2005
Alright, so I didn't mean this to turn into this, but I'm wondering if anyone can kind of critique my code. I've been trying to figure out the purpose behind and uses of OOP with PHP, and I created a script that will find the greatest common factor (or divisor) of a list of numbers, and this is what I came up with. It's worked with every example I've tried, so the accuracy seems fine, and it works quickly, but is my syntax and basic design okay? Does this kind of script even need to use OOP?
<?php//Finds the GCF of a list of numbers, each value separated by a comma; 1 means there is no GCF
class gcf {
public $num,$gcf;
function __construct($numbers) {
$this->num = explode(",",$numbers);
}
function gcf() {
$this->gcf = $this->num[0];
for ($n=1;$n<count($this->num);$n++) {
if (($this->gcf == 0) || ($this->num[$n] == 0)) {
$this->gcf = 0;
}
else {
do
{
$rest=$this->gcf%$this->num[$n];
$this->gcf=$this->num[$n];
$this->num[$n]=$rest;
}
while($rest!==0);
}
}
return $this->gcf;
}
}
if ($_POST['submit'] == "Submit") {
echo "<p>L = ".$_POST['values']."</p>";
$gcf = new gcf($_POST['values']);
echo "<p>GCF: ".$gcf->gcf()."</p>";
}
?>
<form method="post" action="<?php echo $_SERVER['PHP_SELF']; ?>">
<label for="values">Values: </label><br />
<input type="text" name="values" size="100" /><br />
<input type="submit" name="submit" value="Submit" />
</form>
Kurtis
teammatt3 posted this at 19:19 — 9th November 2008.
He has: 2,102 posts
Joined: Sep 2003
I'm no OOP expert, but I don't really see a need for a class here. Why is it necessary to store the numbers in the object? You could simply provide the arguments to a gcf function as gcf(explode(",",$numbers)) and eliminate the need for the class members, and the constructor. Gcf is something I'd put in a larger math class, not a class of its own.
A little inefficiency I see is in the for loop. Every time the condition in the loop is tested, it has to run out to count(), and determine the number of elements in $this->num. I think it is better to create a variable like num_count and set it to count($this->num). Function calls in most languages are expensive.
When you run this logic, shouldn't you immediately break out of the loop (or return 0 from inside the loop)? There isn't any need to continue on is there?
if (($this->gcf == 0) || ($this->num[$n] == 0)) {$this->gcf = 0;
// you should break out, or return 0 from here
}
Just my 2 cents
kazimmerman posted this at 19:36 — 9th November 2008.
He has: 698 posts
Joined: Jul 2005
Yeah, I completely understand that a class isn't needed here. In my opinion, it seems classes are for a series of functions or several functions that share variables or use the same variables...
I'm not really sure either...
I've always been horrible about reusing count() over and over; I always forget to set a variable and use that; besides that and the returning 0 problem you brought up, I think this will be good if I just reduce it to the one gcf() function.
Thanks for your help.
Kurtis
Want to join the discussion? Create an account or log in if you already have one. Joining is fast, free and painless! We’ll even whisk you back here when you’ve finished.