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

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-03-10 23:33:15

on 3/8/01 8:37 AM, Bill Seymour at bsey_at_[hidden] wrote:

> 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'm not a mathematician either.

> 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.

OK, you were considering rounding as just being to "nearest," with floor and
ceil as completely separate forms of estimation, and I was considering them
all under the same umbrella of "rounding."  I guess part of the confusion
was that you didn't completely enumerate your rounding modes.  You only
showed nearest-even, I added nearest-with-half-up; what others are there
(besides nearest-odd or nearest-with-half-down)?  I mistakenly thought your
policy was the horrible nearest-with-half-as-is, which breaks the promise of
always returning an integer when rounding (when "x" is of a "n + 1/2" form).

As I stated, if you expanded from just the "nearest" when rounding, then
stuff like floor and ceil can be considered rounding.  That why I made up
extra modes for those cases and made floor an inline redirection call.

floor -> towards negative infinity (lower integer)
ceil -> towards positive infinity (higher integer)
trunc -> towards zero (absolutely lower integer)
no specific name for "leaving zero" (absolutely higher integer)

> 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?

I just made "APV" up because I was tired of typing "all positive values."

> 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.

The usual GCD algorithm returns a nonnegative result for nonnegative
arguments, but could return a negative result if an argument is negative.
If one insists on the GCD answer being nonnegative, then a sign check (and
possible sign change) has to be done.  What you want to do is to optimize
some GCD versions by eliminating the sign check when you know all the
arguments are positive, right?

Didn't Knuth write a series of computation programming books?  I guess I
should try to find them one day.  How many books were in the series?

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com