Fractions and loops and whatnot...

[octavarium]

I have a bunch of variables, as shown below:

$quarter = 1/4;
$half = 1/2;
$whole = 1;
$eighth = 1/8;
$sixteenth = 1/16;

I want to create a loop or whatever to randomly generate sets of variables that add up to 1. For example, $eighth, $quarter, $eighth, $half. Not a clue where to start. Anyone?

[Installer]

I'd begin with this:

$fractions = array(array('quarter', 1/4), 
                   array('half', 1/2), 
                   array('whole', 1), 
                   array('eighth', 1/8), 
                   array('sixteenth', 1/16));

[justsomeone]

This mightn't be exactly right... no access to compiler here. But it should get you started at least

//important to order these biggest first
$fractions = array(array('half', '1/2', 0.5), 
                   array('quarter', '1/4', 0.25), 
                   array('eighth', '1/8', 0.125), 
                   array('sixteenth', '1/16', 0.0625));

$selectedFractions=array();

$total = 0;
$target = 1;
srand(make_seed());

while ($total < $target){

//rule out any fractions which are too big:
$limit = 0;
while ( $total + $fractions[$limit][2] > $target){
    $limit ++;
}

//now select one of the remaining
$i = rand($limit, sizeof($fractions));
$total += $fractions[$i][2];
$selectedFractions[] = $i;
}

///the selectedFractions array is now populated with a selection of random indices to the fractions which can be added to make up $target.  I hope!  You can now print it out, or do whatever you like with it

$stop = sizeof($selectedFractions)
for ($i=0; $i<$stop; $i++){
    if ($i < ($stop - 1){
        print (" " . $fractions[$i][1]." +");
    }else{
        print (" " . $fractions[$i][1]." = " . $target);
    }
}



// seed with microseconds
function make_seed()
{
   list($usec, $sec) = explode(' ', microtime());
   return (float) $sec + ((float) $usec * 100000);
}

[Installer]

Sigh. This will do it:

function one()
{
    $fractions = array(array('whole',        1), 
                       array('half',      1/ 2), 
                       array('quarter',   1/ 4), 
                       array('eighth',    1/ 8), 
                       array('sixteenth', 1/16));
    $total = 0;
    $str = '';
    while ($total < 1) {
        $key = mt_rand(0, count($fractions) - 1);
        $tmp = $total + $fractions[$key][1];
        if ($tmp > 1) {
            continue;
        } else {
            $total = $tmp;
            $str .= 'one-' . $fractions[$key][0] . ' + ';
        }
    }
    $str = '(' . rtrim($str, ' +') . ') equals one';
    return $str;
}   

for ($i = 0; $i < 25; $i++) {
    echo one() . '<br />';
}

No need to seed if you use "mt_rand()".

[justsomeone]

<?
//important to order these biggest first
$fractions = array(array('one half', '1/2', 0.5),
                   array('one quarter', '1/4', 0.25),
                   array('one eighth', '1/8', 0.125),
                   array('one sixteenth', '1/16', 0.0625));

$selectedFractions=array();

$total = 0;
$target = 1;
srand(make_seed());

while ($total < $target){

//rule out any fractions which are too big:
$limit = 0;
while ( $total + $fractions[$limit][2] > $target) {
    $limit ++;
}

//now select one of the remaining
$i = rand($limit, (sizeof($fractions)-1));
$total += $fractions[$i][2];
$selectedFractions[] = $i;
}

///the selectedFractions array is now populated with a selection of random indices to the fractions which can be added to make up $target.  I hope!  You can now print it out, or do whatever you like with it

$stop = sizeof($selectedFractions);
for ($i=0; $i<$stop; $i++){
    if ($i < ($stop - 1)){
        print (" " . $fractions[$selectedFractions[$i]][0]." +");
    }else{
        print (" " . $fractions[$selectedFractions[$i]][0]." = " . $target);
    }
}



// seed with microseconds
function make_seed()
{
   list($usec, $sec) = explode(' ', microtime());
   return (float) $sec + ((float) $usec * 100000);
}
?>

Sample outputs:
one eighth + one half + one quarter + one sixteenth + one sixteenth = 1
one half + one half = 1
one eighth + one sixteenth + one eighth + one eighth + one quarter + one quarter + one sixteenth = 1

The code is a little more complicated than installer's, but it's just a smidgeon more intelligent too.

So, lucky you, you wanted an idea of how/where to start, and now you got two working examples to choose from.

[Installer]

...more intelligent ...

Why? Because it uses three loops instead of one? Because it calls an unnecessary seed function? Because it creates nine variables instead of four? Because it creates two arrays instead of one, the extra one three-dimensional? Because it accesses array indexes five times instead of twice? Because it's not a function, so not reusable? Because it does all this and produces the exact same result? I don't see that it does anything mine doesn't do in fewer steps. But, then, you're smarter than me, so I'll shut up.

[octavarium]

Good gravy, this is excellent. It's clear to me that I have a long, long way to go on my PHP knowledge.

Thanks a lot, guys.

[justsomeone]

Installer, the main thing I've gained with the extra complexity is that I've avoided the infinite loops which your code could fall into.

But your code is lovely. Much shorter than mine. Lighten up man/woman/boy/girl...

[Installer]

...infinite loops...

Good one. Off the top of your head, was that?

[justsomeone]

Originally posted by Installer
Good one. Off the top of your head, was that?

No.

    while ($total < 1) {
        $key = mt_rand(0, count($fractions) - 1);
        $tmp = $total + $fractions[$key][1];
        if ($tmp > 1) {
            continue; 

In the above snippet, on the third and subsequent iterations, wouldn't it be possible for $key to continually select too big a value?

Say, your first random fraction is 1/2, and the second is 1/4. It seems to me that it's possible for the random function above to generate 1/2 as the third value. This will be ignored, so it selects another. What if that's 1/2 again? and again? and again?

That's pretty unlucky, but it gets more and more possible as the thing is extended.

Suppose that the random sequence of
1/8, 1/4, 1/8, 1/4, 1/16, 1/8 is generated. The only valid next fraction in order to generate a value of 1 is 1/16. Assuming even distribution from the mt_rand function, and assuming my memory of these things is correct, it would take, on average, 2.5 iterations through the loop to fill that last slot. If you're lucky you might get it in the first shot. If you're unlucky, it might take you 10 goes. If you're very. very unlucky, you might never get it.

That's where the potential infinite loop comes from.

The algorithm I used takes the trouble to only make available for selection for any slot, the allowed values for that slot - ie the ones that won't take it over the target. So, if a random sequence of 1/8, 1/4, 1/8, 1/4, 1/16, 1/8 had been generated, only 1/16 would be available for selection, so you would be guaranteed to get it. No chance of an infinite loop taking you off.

I'm not saying it's likely, just possible. And my own experience is that if you make it possible for bad things to happen, they will eventually.

It's a small thing and I never wanted to overstate it, hence my original references to "just a smidgeon more intelligent" and "infinite loops which your code could fall into".

I do compliment the tightness of your code. I'm sure you could address the above and still not need as much code as I used.

One thing which I would change in my own code if I was to use it myself would be to remove the decimal element from each of the arrays in $fraction, and remove the quotes from the fractional element. The fractional elements are never needed as strings, and the overhead of calculating the decimal values from the fractional isn't hugely signifigant.

I would also wrap it up a bit nicer. Perhaps as a function as you suggest, or maybe as a method on an object. But the point of this was just to show how I would approach the logical problem.

Also, just FYI, if octavarium is using a version of PHP older than 4.2.0, then the random seeding should be used, even with mt_srand.

And speaking of octavarium, thanks for the interesting challenge. 🙂 I hope this thread has given you some good food for thought. Best of luck in your PHP adventures.

OK, I'm out of here. The world doesn't need another post from me on this topic.

[Installer]

justsomeone -

Thanks for your cogent response. I apologize for my words and my hard-headedness.

I don't see an infinite loop happening. Your point about limiting the available choices is well-taken, though. I incorporated your using the decimal value, and redid the function with your method. Then I tested over 100000 iterations of each version (PHP 5, my slowest machine).

The code:

function one_1() 
{ 
    $fractions = array(array('whole',    1.0),  

                       array('half',      .5),  

                       array('quarter',   .25),  

                       array('eighth',    .125),  

                       array('sixteenth', .0625)); 
    $total = 0; 
    $str = ''; 
    while ($total < 1) { 
        $key = mt_rand(0, count($fractions) - 1); 
        $tmp = $total + $fractions[$key][1]; 
        if ($tmp > 1) { 
            continue; 
        } else { 
            $total = $tmp; 
            $str .= 'one-' . $fractions[$key][0] . ' + '; 
        } 
    } 
    $str = rtrim($str, ' +') . ' = one'; 
    return $str; 
}    

function one_2()
{
    $fractions = array(array('whole',    1.0), 
                       array('half',      .5), 
                       array('quarter',   .25), 
                       array('eighth',    .125), 
                       array('sixteenth', .0625));
    $total = 0;
    $limit = 0; 
    $str = '';
    while ($total < 1) {
        while ($total + $fractions[$limit][1] > 1) {
            $limit ++; 
        } 
        $key = mt_rand($limit, count($fractions) - 1);
        $total = $total + $fractions[$key][1];
        $str .= 'one-' . $fractions[$key][0] . ' + ';
    }
    $str = '(' . rtrim($str, ' +') . ') equals one';
    return $str;
}   

$start_time = microtime(true);
for ($i = 0; $i < 100000; $i++) { 
    $result = one_1(); 
}
echo microtime(true) - $start_time . '<br />';

$start_time = microtime(true);
for ($i = 0; $i < 100000; $i++) { 
    $result = one_2(); 
}
echo microtime(true) - $start_time . '<br />';

The results:

8.9598360061646
8.6730320453644

(A third version using "arrary_shift()" was slightly slower.)

Thanks again.

Thanks, octavarium. I hope we've helped.