PHP Memory Exhausted Error with simple fractions

Question

I am using this library to work with fractions in PHP. This works fine but sometimes, I have to loop over a lot of values and this results in the following error:

Allowed memory size of 134217728 bytes exhausted

I can allocate more memory using PHP ini but that is a slippery slope. At some point, I am going to run out of memory when the loops are big enough.

Here is my current code:

for($q = 10; $q <= 20; $q++) {
    for($r= 10; $r <= 20; $r++) {
        for($p = 10; $p <= 20; $p++) {
            for($s = 10; $s <= 20; $s++) {
                for($x = 50; $x <= 100; $x++) {
                    for($y = 50; $y <= 100; $y++) {

                        $den = ($q + $r + 1000) - ($p + $s);
                        $num = $x + $y;
                        $c_diff = new Fraction($num, $den);
                    }
                }
            }
        }
    }
}

I used memory_get_peak_usage(true)/(1024*1024) to keep track of the memory the script is using. The total memory used was just 2MB until I added the line that creates a new fraction.

Could anyone please guide me on how to get rid of this error. I went through the code of the library posted on GitHub here but can't figure out how to get rid of the exhausted memory error. Is this because of the static keyword? I am beginner so I am not entirely sure what's going on.

The library code is about a 100 lines after removing the empty lines and comments. Any help would be highly appreciated.

UPDATE:

1. The script exhausts its memory even if I use just this block of code and nothing else. I definitely know that creating a new Fraction object is the cause of exhausting memory.
2. I thought that there was not need to unset() anything because the same one variable to store the new fractional value over and over again.
3. This leads me to think that whenever I creating a new Fraction object something else happens which in the library code that takes up memory which is not released on rewriting the value in the $c_diff variable.
4. I am not very good at this so I thought it has something to do with the static keyword used at a couple of places. Could anyone confirm it for me?

If this issue can indeed be resolved by using unset(), should I place it at the end of the loop?

Answer 1

Various Possible fixes and efficiencies:

You have 6 for loops, each loop cycles a single integer value within various ranges.

But your calculation only uses 3 values and so it doesn't matter if $p = 10; $s = 14; or $p = 13; $s = 11; These are entirely equivilant in the calculation.

All you need is the sum; so once you've found that the value 24 works; you can find all the parts (over the minimum value of 10) that fit that value: ie (24 (sum) - 10 (min) = 14), then collect the values within the range; so there are 10,14, 11,13 , 12,12, 13,11, 14,10 valid values. savng yourself 80%+ processing work on the inner for loops.

 $pairs = "p,s<BR>"; //the set of paired values found
 $other = $sum - $min;
     if($other > $max){
        $other = $sum - $max;
     }
     $hardMin = $min;
     while ($other >= $hardMin && $min >= $hardMin && $min <= $max){
         $pairs .= $min.", ".$other."<BR>";
         $other--; // -1
         $min++;  // +1
     }
   
  print $pairs; 
  

Giving:

  p,s
10,14
11,13
12,12
13,11
14,10

So for this for loop already, you may only need to do ~10% of the total work cycling the inner loops.

---

Stop instantiating new classes. Creating a class is expensive. Instad you create one class and simply plug the values in:

Example:

$c_diff = new Fraction();

for(...){
    for(...){
        $c_diff->checkValuesOrWhateverMethod($num, $den)
    }
}

This will save you significant overhead (depending on the structure of the class)

---

The code you linked on GitHub is simply to turn the value into a fraction and seems to be highly inefficient.

All you need is this:

function float2frac($n, $tolerance = 1.e-6) {
    $h1=1; $h2=0;
    $k1=0; $k2=1;
    $b = 1/$n;
    do {
        $b = 1/$b;
        $a = floor($b);
        $aux = $h1; $h1 = $a*$h1+$h2; $h2 = $aux;
        $aux = $k1; $k1 = $a*$k1+$k2; $k2 = $aux;
        $b = $b-$a;
    } while (abs($n-$h1/$k1) > $n*$tolerance);

    return $h1."/".$k1;
}

Taken from this excellent answer.

Example:

for(...){
    for(...){
        $den = ($q + $r + 1000) - ($p + $s);
        $num = $x + $y;
        $value = $num/den;

        $c_diff = float2frac($value);
        unset($value,den,$num);
    }
}

---

If you need more precision you can read this question and update PHP.ini as appropriate, but personally I would recommend you use more specialist maths languages such as Matlab or Haskell.

---

Putting it all together:

• You want to check three values, and then find the equivilant part of each one.
• You want to simply find the lowest common denominator fraction (I think).

So:

/***   
 * to generate a fraction with Lowest Common Denominator
 ***/
function float2frac($n, $tolerance = 1.e-6) {
    $h1=1; $h2=0;
    $k1=0; $k2=1;
    $b = 1/$n;
    do {
        $b = 1/$b;
        $a = floor($b);
        $aux = $h1; $h1 = $a*$h1+$h2; $h2 = $aux;
        $aux = $k1; $k1 = $a*$k1+$k2; $k2 = $aux;
        $b = $b-$a;
    } while (abs($n-$h1/$k1) > $n*$tolerance);

    return $h1."/".$k1;
}

 /***
  * To find equivilants
  ***/
 function find_equivs($sum = 1, $min = 1, $max = 2){
    $value_A = $sum - $min;
    $value_B = $min;
    if($value_A > $max){
        $value_B = $sum - $max;
        $value_A = $max;
    }
    $output = "";
    while ($value_A >= $min && $value_B <= $max){
        if($value_A + $value_B == $sum){
            $output .= $value_A . ", " . $value_B . "<BR>";
        }
        $value_A--; // -1
        $value_B++;  // +1
    }
    return $output;
}

 /***
  * Script...
  ***/     
 $c_diff = []; // an array of results. 
 for($qr = 20; $qr <= 40; $qr++) {
     for($ps = 20; $ps <= 40; $ps++) {
         for($xy = 100; $x <= 200; $xy++) {
              $den = ($qr + 1000) - $ps;
              $num = $xy;
              $value = $num/$den; // decimalised  
              $c_diff[] = float2frac($num, $den);
              /*** 
               What is your criteria for success?
               ***/ 
              if(success){
                 $qr_text = "Q,R<BR>";
                 $qr_text .= find_equivs($qr,10,20);
                 $sp_text = "S,P<BR>";
                 $sp_text .= find_equivs($sp,10,20);
                 $xy_text = "X,Y<BR>"; 
                 $xy_text .= find_equivs($sp,50,100);
               }
             }
         }
      }

 

• This should do only a small percentage of the original looping.

Answer 2

I guess this isn't the entire block of code you are using.

This loop creates 50*50*10*10*10*10 = 25.000.000 Fraction objects. Consider using PHP's unset() to clean up memory, since you are allocating memory to create objects, but you never free it up.

editing for clarification

When you create anything in PHP, be it variable, array, object, etc. PHP allocates memory to store it and usually, the allocated memory is freed when script execution ends.

unset() is the way to tell PHP, "hey, I don't need this anymore. Can you, pretty please, free up the memory it takes?". PHP takes this into consideration and frees up the memory, when its garbage collector runs.

It is better to prevent memory exhaustion rather than feeding your script with more memory.

Answer 3

Allowed memory size of 134217728 bytes exhausted

134217728 bytes = 134.218 megabytes

Can you try this?

ini_set('memory_limit', '140M')
/* loop code below */