Re: What's Your Interest in Integer Division Traits?

From: Bill Seymour (bsey_at_[hidden])
Date: 2001-03-08 09:37:26

I wrote:
>
> ...my round functionalways rounds to the nearest integer except
> in the special case where the remainder is exactly half of the
> divisor, so there is no "nearest" integer.
>
and Daryle Walker responded:
>
> The previous statement sounds like you have no policy, and have
> the rounding routine return a "n + 1/2" value, which breaks
> assumptions of an "integer rounding" routine.  (It returns 'X'
> rounded to an integer, except when it doesn't!)  If your rounding
> routines always return an integer, even in a "n/1" rational form,
> then you need some sort of policy for handling 1/2 cases.
>

I think we might be talking past each other here; and because I'm
not a mathematician, I'm probably the one using the wrong terminology.

I think of functions like floor and ceil as doing "truncation,"
not "rounding," because they choose an answer based on criteria
other than "nearness" of the answer to the mathematical quotient.

The "policy" of my round function is "round to nearest" except
in what you have called the "1/2 cases."  In those cases, the
rounding mode kicks in, and the "policy" is chosen by the user,
not dictated by me.

One the matter of the second template argument:
>
> I'm not sure that slight efficiency for routines using all-positive
> values is worth making a separate templates for them.
>

What does run-time efficiency have to do with "coding-time" efficiency?

Anyway, consider the expression that decides whether the ceil function
needs to adjust the quotient:

    remainder != 0 && dividend < 0 == divisor < 0

If we know that the divisor is greater than zero, then that becomes

    remainder != 0 && dividend > 0

That doesn't seem to be much of a speedup; but I'd like to let the
user decide whether it's worth it.  For all I know, someone has a
call to the ceil function inside nested loops that work on thousands
of values.

>
> Some of the routines may not need separate versions anyway, ...
>

And so don't have them.

>
> ... e.g. I think the GCD routine is automatically APV-efficient.
>

I haven't heard the term, "APV-efficient" before.  What does it
mean?

If you mean that your gcd routine (which you call gcf) automatically
handles negative arguments correctly, then I disagree.  IAW the
"principle of least surprise" (I'm not sure where I learned that...
probably from Stroustrup), I believe it should work as specified
in Knuth, Vol. 2, 4.5.2, and always return a non-negative value.

--Bill Seymour