Ticket #1720 (closed bug: fixed)

Opened 4 years ago

Last modified 3 years ago

fdiv_i_i_i and fdiv_i_i ops don't work correctly.

Reported by: tcurtis Owned by: NotFound
Priority: normal Milestone:
Component: core Version: 2.6.0
Severity: low Keywords:
Cc: Language:
Patch status: Platform:

Description

fdiv is documented to be flooring division: "The result is the floor() of the division i.e. the next whole integer towards -inf."

The num variants of fdiv correctly perform flooring division.

The int variants of fdiv floor the result of C integer division of the arguments, and C integer division truncates towards zero. Therefore, fdiv_i_i_i is currently equivalent to div_i_i_i.

Attachments

intfdiv.patch Download (468 bytes) - added by tcurtis 4 years ago.
An as-yet-untested patch that SHOULD fix the problem.

Change History

Changed 4 years ago by tcurtis

An as-yet-untested patch that SHOULD fix the problem.

Changed 4 years ago by kurahaupo

On Tue, 27 Jul 2010, Parrot wrote:
> #1720: fdiv_i_i_i and fdiv_i_i ops don't work correctly.
> ---------------------+------------------------------------------------------
>  Reporter:  tcurtis  |       Owner:
>      Type:  bug      |      Status:  new
>  Priority:  normal   |   Milestone:
> Component:  core     |     Version:  2.6.0
>  Severity:  low      |    Keywords:
>      Lang:           |       Patch:
>  Platform:           |
> ---------------------+------------------------------------------------------
>  fdiv is documented to be flooring division: "The result is the floor() of
>  the division i.e. the next whole integer towards -inf."
>
>  The num variants of fdiv correctly perform flooring division.
>
>  The int variants of fdiv floor the result of C integer division of the
>  arguments, and C integer division truncates towards zero. Therefore,
>  fdiv_i_i_i is currently equivalent to div_i_i_i.


This will work, although it's horribly inefficient:

Index: src/ops/math.ops
===================================================================
--- src/ops/math.ops    (revision 47439)
+++ src/ops/math.ops    (working copy)
@@ -289,7 +289,7 @@
 =cut

 inline op fdiv(inout INT, in INT) :base_core {
-    INTVAL   den = $2;
+    FLOATVAL den = $2;
     FLOATVAL f;

     if (den == 0) {
@@ -327,7 +327,7 @@
 }

 inline op fdiv(out INT, in INT, in INT) :base_core {
-    INTVAL   den = $3;
+    FLOATVAL den = $3;
     FLOATVAL f;

     if (den == 0) {


Changed 4 years ago by NotFound

  • status changed from new to assigned
  • owner set to NotFound

Changed 4 years ago by NotFound

  • status changed from assigned to closed
  • resolution set to fixed

Fixed and test added in r48214

Changed 3 years ago by kurahaupo

  • status changed from closed to reopened
  • resolution fixed deleted

The given fix imposes an unreasonable run-time overhead of converting divisors from integer to float, and then converting the FLOATVAL remainder back to an INTVAL.

A more efficient approach would be to use the native integer operations, but check that the result has the desired properties:

 INTVAL dividend = $1;
 INTVAL divisor = $2;
 INTVAL quotient = dividend / divisor;
 if ( ( dividend - quotient * divisor ^ divisor ) < 0 ) {
     quotient--;
 }

Of course, neither deals with integer underflow of ((-MAX_INT-1) / -1)

Changed 3 years ago by kurahaupo

The quick fix is fairly simple: change the declaration of the "den"
temporary from INTVAL to FLOATVAL. However that imposes an unreasonable
run-time overhead of converting divisors from integer to float, and then
converting the FLOATVAL remainder back to an INTVAL.

A better approach would be to use the native integer operations, but
check that the result has the desired properties:

	INTVAL dividend = $1;
	INTVAL divisor = $2;
	INTVAL quotient = dividend / divisor;
	if ( ( dividend - quotient * divisor ^ divisor ) < 0 ) {
		quotient--;
	}

Generally one wants to choose the handling negative numbers in truncating
division based on the definition of the remainder. In all cases the absolute
value of the remainder must be less than the absolute value of the divisor,
and but then one would choose either:

(A) the sign of the remainder matches the sign of the dividend; or
(B) the sign of the remainder matches the sign of the divisor.

Then round the quotient in the direction that ensures that

	quotient = (dividend - remainder) ÷ divisor

Type (A) is the usual choice for implementing in hardware (and thus is
what the "div" operator provides), and I gather the intention is that
type (B) is what the "fdiv" operator should produce.

	x	y	x/y	x div y, x mod y
				(A)	(B)	
	+7	+5	+1.4	+1,+2	+1,+2	
	-7	+5	-1.4	-1,-2	-2,+3	
	+7	-5	-1.4	-1,+2	-2,-3	
	-7	-5	+1.4	+1,-2	+1,-2	


On Tue, 27 Jul 2010, Parrot wrote:
>  fdiv is documented to be flooring division: "The result is the floor() of
>  the division i.e. the next whole integer towards -inf."
>
>  The num variants of fdiv correctly perform flooring division.
>
>  The int variants of fdiv floor the result of C integer division of the
>  arguments, and C integer division truncates towards zero. Therefore,
>  fdiv_i_i_i is currently equivalent to div_i_i_i.


Changed 3 years ago by bacek

  • status changed from reopened to closed
  • resolution set to fixed

Hello.

Parrot is so far-far away in terms of speed to worry about int-to-float-to-int conversion overhead. Mark ticket as fixed.

-- Bacek

Note: See TracTickets for help on using tickets.