Custom flooring

snuffles1

I just saw this when optimizing some code. rat_num is a very expensive class to copy because it holds an eight byte numerator and denominator. Here is a method that is supposed to implement floor for rationals, as original written:

rat_num
RoundDown(const rat_num& value, const rat_num& increment)
{
    if (value.sign() < 0)
        //    (1)      (1)
        return -RoundUp(-value, increment);

    rat_num count(value / increment);

    if (count.integral())
        return value;

    //             (3)                         (2)
    return rat_num(nint(floor(value.to_double() / increment.to_double()))) * increment;
}

Some loveliness to note

If the value is negative, the programmer makes 2 extra copies (operator-() returns a copy)
The useless extra double division after performing a rational division
The needless call to nint after floor. When confronted, programmer proceeds to display a complete misunderstanding of floating point; "What if floor returns 0.99999? It could happen!".
There is a RoundUp function that was copy/pasted with the only difference being a call to ceil instead of floor.

This can be simplified to

rat_num
RoundDown(const rat_num& value, const rat_num& increment)
{
    const rat_num quotient(value / increment);

    if (quotient.integral())
        return value;

    const int quotientFloor = static_cast<int>(floor(quotient.to_double()));
    return rat_num(quotientFloor) * increment;
}

DrPepper

putting the return type on the previous line
Naming the variable "count" when it's not counting anything.
providing a constructor for rat_num that takes a (presumably) floating point number, and converting it to a numerator/denominator pair.
Providing a operator-/ that divides one rat_num by another; when the language has a perfectly good implementation of / that divides two floats.
Creating a rat_num object just to see if x/y is an int;
Not checking to see if increment is 0
Thinking that this implements "floor", which typically operates on a single value. Rather, it's "find the number closest to, but not less than, value, which when divided by increment, yields an integer. "
Not making this a method of the rat_num object
The usefulness of this method escapes me completely. Something like, for value=1200/7, and increment=8/5, "reduce value to a number y, where y = x * increment, where x is an integer. What does that actually accomplish?

TheCPUWizard

14 - worries about object copies when there is no evidence of a performance specification being violated by the implementation, or a use-case demonstrated where recurring calls actually aggregate enough to cause such a violation.

Mcoder

@DrPepper said:

8. Providing a operator-/ that divides one rat_num by another; when the language has a perfectly good implementation of / that divides two floats.

The float operator loses precision. There is probably some need of dividing rat_nums without precision loss, because they are numbers, and people normaly want to divide numbers.

Within the 13 WTFs you listed, I think you were wrong once.

communist_goatboy

I am struggling to figure out how having the floor of the quotient of the numerator and denominator of a rational number is in any way useful. It smells like rationals are just being used as containers for two integral types (they are integral types, aren't they?).

If rationals are really needed, why not just wrap up std::ratio if using C++11 or boost::rational if C++2003?

Ben L.

Also, if arbitrary precision is needed, why convert to doubles at all?

snuffles1

@DrPepper said:

5. putting the return type on the previous line

6. Naming the variable "count" when it's not counting anything.

7. providing a constructor for rat_num that takes a (presumably) floating point number, and converting it to a numerator/denominator pair.

8. Providing a operator-/ that divides one rat_num by another; when the language has a perfectly good implementation of / that divides two floats.

9. Creating a rat_num object just to see if x/y is an int;

10. Not checking to see if increment is 0

11. Thinking that this implements "floor", which typically operates on a single value. Rather, it's "find the number closest to, but not less than, value, which when divided by increment, yields an integer. "

12. Not making this a method of the rat_num object

13. The usefulness of this method escapes me completely. Something like, for value=1200/7, and increment=8/5, "reduce value to a number y, where y = x * increment, where x is an integer. What does that actually accomplish?

5) the coding standard here

6) yep; non-native english speaker choosing variable names

7) To construct you need one integer or two doubles (value and increment).

8) absolutely necessary due to float rounding.

9) absolutely necessary due to float rounding.

10) It does that, I just forgot to put it in here. Also checks for NaN equivalent.

11) This is a generalization of floor, equivalent when increment = 1

12) not allowed to touch the class

13) suppose value=3712 and increment=5, you want 3710. Or if value = 3/4 and increment = 1/3, you want 2/3. value has to be in multiples of increment, and depending on the situation you have to go up or down.

snuffles1

@communist_goatboy said:

If rationals are really needed, why not just wrap up std::ratio if using C++11 or boost::rational if C++2003?

Because we use c++98.

snuffles1

@Ben L. said:

Also, if arbitrary precision is needed, why convert to doubles at all?

It's not arbitrary precision; it's precision specified by increment.

dkf

@snuffles said:

rat_num is a very expensive class to copy because it holds an eight byte numerator and denominator.

That's not that expensive; it should fit in one L1 cache line with plenty of room left over. (Yeah, ten million of them would be something else.)

snuffles1

I should also mention that yes, I profiled the code and this function was a hotspot.

Planar

@snuffles said:

I should also mention that yes, I profiled the code and this function was a hotspot.

Then you can optimize it further, because callint [code]quotient.integral()[/code] and [code]floor(quotient.to_double())[/code] is basically doing twice the same work. What you should do is decompose [code]quotient[/code] into its numerator [code]num[/code] and denominator [code]dem[/code] and compute [code]rem = num % dem[/code], then if that is not 0, make a new rat_num from [code]num - rem[/code] and [code]dem[/code], and multiply it by [code]increment[/code].

This way, you save one integer division and a round-trip through floats.

Assuming of course that you can get the numerator and denominator (i.e. that the rat_num class is not a complete WTF).

anotherusername

@Planar said:

Then you can optimize it further, because callint quotient.integral() and floor(quotient.to_double()) is basically doing twice the same work.

I caught that, and I'm not convinced that the extra return is any faster than just leaving those two lines out entirely.@DrPepper said:

The usefulness of this method escapes me completely. Something like, for value=1200/7, and increment=8/5, "reduce value to a number y, where y = x * increment, where x is an integer. What does that actually accomplish?

You've never heard of a floor function that took more than one argument? It returns the largest-valued multiple of increment that is equal to or less than the value of the first argument. I.e. floor(value, increment) returns increment * n where n is an integer that satisfies these two inequalities:

n ≥ 0
|value| - |increment| < |increment * n| ≤ |value|

floor(1200/7, 8/5) should return the largest multiple of 8/5 less than or equal to 1200/7, i.e. n = 107 and it should return 856/5.

1200/7 - 8/5 < 8/5 * 107 ≤ 1200/7
5944/35 < 5992/35 ≤ 6000/35

It makes the most sense when increment is an integer or when its reciprocal is an integer, but it's still going to work regardless of what increment is (except zero, because that will result in division by zero... I assume the rational class has code in place to deal with that).

anotherusername

@anotherusername said:

|value| - |increment| < |increment * n| ≤ |value|

In hindsight, a more sensible way of writing that would've probably been this:

Pick whichever you find to be clearer; either one will work.

snuffles1

@Planar said:

Then you can optimize it further, because callint quotient.integral() and floor(quotient.to_double()) is basically doing twice the same work..

Not really; integral() just returns denominator == 1 && numerator != 0, no need for modular arithmetic.

@Planar said:

What you should do is decompose quotient into its numerator num and denominator dem and compute rem = num % dem, then if that is not 0, make a new rat_num from num - rem and dem, and multiply it by increment.

All that is already done when the euclidean algorithm is called during division to simplify numerator/denominator.

Planar

@snuffles said:

Not really; integral() just returns denominator == 1 && numerator != 0, no need for modular arithmetic.

What? 0 is not an integer?

@snuffles said:

@Planar said:
What you should do is decompose quotient into its numerator num and denominator dem and compute rem = num % dem, then if that is not 0, make a new rat_num from num - rem and dem, and multiply it by increment.

All that is already done when the euclidean algorithm is called during division to simplify numerator/denominator.

Good point. Then it's the division that you should merge with the rest of the code. I really don't like going through floats: not only it's slow, but on a 64-bit machine it'll give the wrong result for some large inputs.

flabdablet

@snuffles said:

This can be simplified to

rat_num
RoundDown(const rat_num& value, const rat_num& increment)
{
    const rat_num quotient(value / increment);

    if (quotient.integral())
        return value;

    const int quotientFloor = static_cast(floor(quotient.to_double()));
    return rat_num(quotientFloor) * increment;
}

Why wouldn't this work?

rat_num
RoundDown(const rat_num& value, const rat_num& increment)
{
    return value - value % increment;
}

Is operator % not implemented for rat_nums?

flabdablet

@snuffles said:

integral() just returns denominator == 1 && numerator != 0

What's the point of the numerator != 0 part? Since when is 0 non-integral?

Ben L.

@flabdablet said:

@snuffles said:
integral() just returns denominator == 1 && numerator != 0
What's the point of the numerator != 0 part? Since when is 0 non-integral?

Wolfram|Alpha says that

Let's plug in t=-1.

Yes, this formula is 0 for all integers, and 1 for zero. Therefore, zero is not an integer.