GCD function gets stuck in a loop

[atrum]

Hello everyone.

 

So in my programing class which is starting out doing flow charts. We were asked to do a flow chart that shows the process of calculating the GCD from 2 numbers.

 

I wanted to try it out for real in php.

The issue I am having is that after the first time its used, any attempt to use it after that results in a never ending loop that ends up tanking my server, and I have to restart apache to fix the problem.

 

I am trying to come up with a solution to prevent that but I am drawing a blank.

Looping is still somewhat new to me. At least when dealing with just numbers.

 

Here is my code,. If anyone can offer any advice I would appreciate it.

 

<?php
//Initialize Variables
if($_POST['num1']!=="" || $_POST['num2']!==""){
$num1 = $_POST['num1'];
$num2 = $_POST['num2'];
}else{
die("Both fields require a number");
}
//Function calulates the Greatest Common Factor from 2 given numbers.
function gcd($num1,$num2){
while($num1 !== $num2){
	if($num1 > $num2){ //While $num1 is equal $num2
		$num1 = $num1 - $num2; //Subtract $num1 from $num2
		$gcd = $num1;
	}else{
		$num2 = $num2 - $num1; //Subtract $num1 from $num2
		$gcd = $num2;
	}
}
$result = "The GCD of ".$_POST['num1'] ." and ". $_POST['num2']." is : ".$gcd;
return $result;
}
echo gcd($_POST['num1'],$_POST['num2']);

?>

[atrum]

I got it figured out.

 

So far it works out exactly the same when I manually work out the numbers.

 

 

<?php
//Initialize Variables
if($_POST['num1']!=="" || $_POST['num2']!==""){
$num1 = $_POST['num1'];
$num2 = $_POST['num2'];
}else{
die("Both fields require a number");
}
//Function calulates the Greatest Common Factor from 2 given numbers.
function gcd($num1,$num2){
while($num1 !== $num2){
	if($num1 > $num2){ //While $num1 is equal $num2
		$num1 = $num1 - $num2; //Subtract $num1 from $num2
		$gcd = $num1;
	}else{
		$num2 = $num2 - $num1; //Subtract $num1 from $num2
		$gcd = $num2;
	}
	if($gcd <=1){ //Checks if the gcd is lower than 1. if it is, then stop the loop and make gcd equal to the number before we hit 0
	$gcd = $num1;
	break;
	}
}
$result = "The GCD of ".$_POST['num1'] ." and ". $_POST['num2']." is : ".$gcd;
return $result;
}
echo gcd($_POST['num1'],$_POST['num2']);

?>

[xyph]

A few things I've noticed.

 

For one

if($_POST['num1']!=="" || $_POST['num2']!==""){

 

Should be && rather than ||. With OR, if EITHER one is true, the code will be executed. If you want to make sure both are non-empty, you would use an AND

 

Also, with user-submitted variables like that, you should make sure they exist before comparing them. If they don't exist, PHP will throw a NOTICE error. You should add that check in there.

if( isset($_POST['num1'], $_POST['num2']) && $_POST['num1']!=="" && $_POST['num2']!=="" ){

 

Thankfully though, PHP has an even BETTER way of checking this. The empty() command will check if a variable exists, and then check if it's value is FALSE, empty, 0, NULL, etc. This may not be what you want in other math functions, but luckily you never want to find the GCD of 0 I would rewrite that to simply

if( !empty($_POST['num1']) && !empty($_POST['num2']) ){

The !empty($var) is identical to empty($var) == FALSE

 

Now I've done the rest of the function using the Euclidean algorithm

 

<?php

$gcd = gcd(11,7);
echo 'GCD is '. $gcd;

//Function calulates the Greatest Common Factor from 2 given numbers.
function gcd($num1,$num2){
$num1 = (int) $num1; $num2 = (int) $num2; // Typecast, force the variable to be an integer
if( $num1 == $num2 ) return $num1; // If the numbers are equal, the GCD is the number itself

while( $num1 != $num2 ) { // We want the loop to stop once $a and $b are equal - this will be our GCD
	if( $num1 > $num2 ) $num1 = $num1 - $num2; // This follows the sumtraction version of the Euclidean algorithm
	if( $num2 > $num1 ) $num2 = $num2 - $num1; // Normally, I'd use an elseif here, but by using two seperate
	                                           //conditional statments, I can avoid extra loops.
}
return $num1;
}

?>

[atrum]

Hey man, thanks a lot for the help on that. That is a much cleaner way of doing this.

[xyph]

The only thing I didn't add was to make sure both values were above 0.

 

You can also take away the line

if( $num1 == $num2 ) return $num1;

 

Because this will be done at the end of the function anyways (the while loop won't execute, and $num1 will be returned.

 

You could change that to

if( $num1 <= 0 || $num2 <= 0 ) return 1;

 

I'm not sure how you'd want to handle that one, as the real GCD between a number and 0 is that number.

 

You could also find the GCD of negative numbers by using abs() on both values.