Page 1 of 1

Lowest Common Denominator

Posted: Sun Oct 24, 2004 7:05 pm
by Grim...
This is for a simple ratio calculation, but I'm stuck (more on the maths than the PHP, my maths sucks).

Basically, I want a ratio function - feed it two values, and it works out the ratio, without any decimals.

For example:
a = 50
b = 100
r = 1 : 2

or

a = 7
b = 942
r = 7 : 942 (because 7 doesn't go into 942)

I've searched this site and Google and I can't find anything :(
Any ideas?

Posted: Sun Oct 24, 2004 8:24 pm
by scorphus
Does it have to return always integer numbers? Like 7:942 instead of 1:134.571429 ([google]942/7[/google]) or 3:4 instead of 1:1.33333333 ([google]4/3[/google])?

-- Scorphus

Posted: Sun Oct 24, 2004 8:33 pm
by scorphus
Try this one:

Code: Select all

<?php
$a = 21;
$b = 336;
$ratio = ($b % $a) ? "$a:$b" : '1:' . $b/$a;
echo $ratio;	
?>
-- Scorphus

[edit]
Hummm... this will not solve the problem for all cases...
Lemme try again...
[/edit]

Posted: Sun Oct 24, 2004 9:05 pm
by scorphus
Aha! Great is the Wikipedia.

Hope this helps:
  • Read the theory;
  • Understand the Extended Euclidean algorithm;
  • Code: Select all

    &lt;?php
    // This program works only for non-negative inputs.
    // Set two integers.
    $a = 21;
    $b = 342;
    
    // Save original values.
    $a0 = $a;
    $b0 = $b;
    
    // Initializations. We maintain the invariant p*a0 + q*b0 = a and r*a0 + s*b0 = b.
    $p = 1;
    $q = 0;
    $r = 0;
    $s = 1;
    
    // The algorithm:
    while ($b != 0) { 
    	$c = $a % $b;
    	$quot = floor($a/$b);
    	$a = $b;
    	$b = $c;
    	$new_r = $p - $quot * $r;
    	$new_s = $q - $quot * $s;
    	$p = $r;
    	$q = $s;
    	$r = $new_r;
    	$s = $new_s;
    }
    
    // Show result.
    
    echo "gcd($a0,$b0) = $p*$a0+($q)*$b0 = $a";
    ?&gt;
    Output:[syntax=php]gcd(21,342) = 49*21+(-3)*342 = 3[/syntax]
    [*]Apply it for your problem.[/list]Nice thread, I had a unique interest on this matter.
    
    Regards,
    Scorphus.