Improve automatic maximum precision determination for terminating fractions

m.stenta → credited jgaehring → .

The challenge is: how do we determine the precision of a terminating fraction?

Credit to @jgaehring for this solution (given the denominator of a terminating fraction, no numerator necessary):

function calcDecimalPlaces(int $denominator, int $exp = 1) {
  if (pow(10, $exp) % $denominator === 0) {
    return $exp;
  }
  return calcDecimalPlaces($denominator, $exp + 1);
}

Just for fun, I had a friend ask ChatGPT... :-)

Prompt:

Write a function in PHP that takes a numerator and denominator as parameters. If the numerator and denominator form a fraction that is terminating, the function should return the number of decimal places needed to represent the fraction as a decimal.

Response:

Here's a PHP function that takes a numerator and denominator as parameters and returns the number of decimal places needed to represent the fraction as a decimal if the fraction is terminating. If the fraction is non-terminating, the function returns -1.

function terminating_decimal_places($numerator, $denominator) {
  $gcd = gcd($numerator, $denominator);
  $denominator /= $gcd;
  while ($denominator % 2 == 0) {
    $denominator /= 2;
  }
  while ($denominator % 5 == 0) {
    $denominator /= 5;
  }
  if ($denominator == 1) {
    $n = $numerator / $gcd;
    $decimal_places = 0;
    while ($n > 0) {
      $n /= 10;
      $decimal_places++;
    }
    return $decimal_places;
  } else {
    return -1;
  }
}

function gcd($a, $b) {
  while ($b != 0) {
    $t = $b;
    $b = $a % $b;
    $a = $t;
  }
  return $a;
}

Here's how the function works:

1. First, we find the greatest common divisor (GCD) of the numerator and denominator using the gcd() function.
2. We divide both the numerator and denominator by the GCD to simplify the fraction.
3. Next, we check if the denominator is divisible only by 2 and/or 5. If it is, then the fraction is terminating.
4. If the denominator is divisible only by 2 and/or 5, we find the number of decimal places needed to represent the fraction as a decimal by dividing the numerator by 10 until it is less than or equal to 0.
5. If the denominator is not divisible only by 2 and/or 5, the fraction is non-terminating and we return -1.

You can use this function like this:

$numerator = 5;
$denominator = 8;

$decimal_places = terminating_decimal_places($numerator, $denominator);
if ($decimal_places == -1) {
  echo "The fraction is non-terminating.";
} else {
  echo "The fraction is terminating and requires $decimal_places decimal places.";
}

This will output "The fraction is terminating and requires 3 decimal places."

Sadly, this function always returns 324. 😂

(The reason for this is also interesting... it gets stuck in a loop dividing the numerator by 10 until it is essentially two small to pass the $n > 0 test. It takes 324 iterations to get there.)

The last test in Drupal\Tests\fraction\Functional\FractionFieldTest::testFractionWidgetFraction is failing, which reveals the boundaries of this logic, resulting in the following error:

Exception: Deprecated function: Implicit conversion from float 1.0E+19 to int loses precision
Drupal\fraction\Fraction->terminatingPrecision()() (Line: 383)

This happens when the denominator exceeds 2147483647 (note that I am testing on a 64-bit build of PHP with a PHP_INT_MAX of 9223372036854775807). When that happens, the $exponent required to satisfy pow(10, $exponent) % $denominator == 0 exceeds 18. PHP automatically converts the result of pow(10, 19) to a double, because it is larger than PHP_INT_MAX:

> pow(10, 18) > PHP_INT_MAX
= false

> pow(10, 19) > PHP_INT_MAX
= true

> gettype(pow(10, 18))
= "integer"

> gettype(pow(10, 19))
= "double"

Modulus operations in PHP cannot use floats/doubles, so they are implicitly converted to ints, which PHP warns will result in the loss of precision:

> 1.5 % 1

   DEPRECATED  Implicit conversion from float 1.5 to int loses precision.

= 0

So the question is: how should we handle cases where the denominator is larger than 2147483647?

So the question is: how should we handle cases where the denominator is larger than 2147483647?

Instead of testing pow(10, $exponent) % $denominator == 0, we could test bcmod(bcpow(10, $exponent), $denominator) === '0'.

This avoids the issue by using BCMath, which performs arithmetic on PHP strings instead of ints/floats/doubles. Tests pass!

However, this would add a hard dependency on BCMath, which thusfar we have avoided. Fraction uses BCMath when it is available, but always falls back to native PHP arithmetic operations when it isn't. In this case, if we fall back to native arithmetic, we encounter this error. Although, maybe that is true in other parts of the module and we just haven't encountered it yet (meaning we aren't hitting the boundaries like we are here with our current tests).

I refactored terminatingPrecision() to use BCMath if available, otherwise it falls back on native PHP arithmetic. I think that's enough to resolve the failing tests. If someone tries to work with high-precision Fractions without BCMath, they will encounter the deprecation error described above. I think that's enough of an edge case that we don't need to worry about supporting it right now. We can just tell them to use BCMath if they need that level of precision.

This is not working as expected for 1/6... it is treating that as a terminating Fraction when it shouldn't be.

My test for "is this fraction terminating?" was wrong. I adapted ChatGPT's method into a new isTerminating() method, added a test for 1/6 specifically, and everything is working properly now.

Just want to highlight this distinction (maybe we can edit the issue description so as to not confuse others/future selves):

It is possible to determine if a fraction is terminating (and not repeating) based on whether or not its denominator is divisible by 2 or 5.

This is incorrect. The denominator must be a multiple of 2 and/or 5. eg: 1 / (2^a * 5^b). Another reference: https://nrich.maths.org/14531/solution

Thanks @paul121! Updated in the issue summary.

Automatically closed - issue fixed for 2 weeks with no activity.