| Date: | January 26, 2005 / year-entry #24 |
| Tags: | other |
| Orig Link: | https://blogs.msdn.microsoft.com/oldnewthing/20050126-00/?p=36593 |
| Comments: | 38 |
| Summary: | In a previous life, I wrote database software. A customer complained that one of their reports was taking an unacceptably long amount of time to generate, and I was asked to take a look at it even though it wasn't my account. The report was a vacation-days report, listing the number of vacation days taken... |
In a previous life, I wrote database software. A customer complained that one of their reports was taking an unacceptably long amount of time to generate, and I was asked to take a look at it even though it wasn't my account. The report was a vacation-days report, listing the number of vacation days taken and available for each employee. Vacation days accrued at a fixed rate but were granted only in quarter-day increments. For example, if you earned 15 vacation days per year and the year was 32% complete, then you had accrued 32% × 15 = 4.8 vacation days, of which 4.75 were available to use. The existing code to round the number of accrued days down to the nearest quarter-day went something like this: * assume that at this point, ACCRUED is the number * of accrued days. PRIVATE S,F * STR(ACCRUED,6,2) converts ACCRUED to a 6-character * string: 3 integer digits, a decimal point, and two * fractional digits. Excess fractional digits are rounded. STORE STR(ACCRUED,6,2) TO S STORE RIGHT(S,2) TO F && extract digits after decimal IF F < "25" F = "00" && 00 to 24 becomes 00 ELSE IF F < "50" F = "25" && 25 to 49 becomes 25 ELSE IF F < "75" F = "50" && 50 to 74 becomes 50 ELSE F = "75" && 75 to 99 becomes 75 ENDIF ENDIF ENDIF ROUNDED = VAL(LEFT(S,4) + F) && reconstruct value and convert In other words, the code converted the number to a string, extracted the digits after the decimal point, did string comparisons to figure out which quartile the fraction resided in, then created a new string with the replacement fraction and converted that string back to a number. And all this in an interpreted language. This code fragment was repeated each time rounding-down was needed because the language supported only 32 subroutines, and this procedure wasn't important enough to be worth kicking out one of the other existing subroutines. I replaced this seventeen-line monstrosity with the one-line equivalent each time it occurred, and the report ran much faster. (This is nowhere near the strangest way of implementing rounding. There are far worse examples.) Exercise: What is the one-line equivalent? Exercise: What is the double-rounding bug in the original code? |
Comments (38)
Comments are closed. |
Not sure about the syntax, but:
ROUNDED = TRUNCATE(ACCRUED * 4) / 4
Well, it rounds at the beginning when it does a
STR(ACCRUED,6,2)
So 4.246 gets first rounded to 4.25, which stays 4.25 after the second rounding, which allows more vacation than has actually been earned.
What about simply
rounded = (accrued*4) div 4
Make that
rounded = (int(accrued*4))/4
I don’t know how that language stores numbers or what bitwise operations you may have available to you, but you could truncate/mask off all but the first two binary digits after the decimal point, if you can bitwise manipulate a float.
This is possible because .0, .25, .5, and .75 are the exact (decimal) values that can be stored in the two most significant fractional bits, and truncate always rounds down.
Double rounding: If the STR function is implemented with the rounding we learned about in school (.5+, round up, else round down), the true boundaries for the fractions are .245, .495, and .745, instead of .25, .5, and .75?
Even if you can do bitwise operations on floats in this language, you need to know how many bits above the binary point there are before you can mask. Or you could just take the fractional part and do that. That’s probably slower and certainly more difficult to read than the simple arithmetic method.
And truncation doesn’t always round down, but hopefully the cases where it doesn’t wouldn’t happen here.
Well, I guess that does depend on your definition of "down"…
That reminds of my favorite hunk of code I’ve ever found in a production system. The name of the method was "moveDecimalPoint" or something like that, and it took a string that was a floating point number. In about 5-6 lines of awful looking looping code it searched through the string, manually split on the decimal point, then created a new string with the point moved 2 spaces to the right.
Most work I’ve ever seen anyone do to multiply a number by 100. Involved a 5 line loop, a couple of string creations, a string buffer creation, and a horrible method name.
Yes, one would hope that your earned vacation time is never negative. But perhaps at EA…
I didn’t know you once wrote Fox applications! You should go see what the Fox team is up to now.
Fox? Sounds like dBaseII or III to me. I remember an project I worked on where the numbers were more than 4,294,967,296. I had to add and subtract by writing decimal math routines.
this can be done in excel as
= ceiling(cellvalue,0.25)
Once, an intern attempted to do bitwise operations (it was in BPW, or maybe Delphi 1.0 at the time).
Yes, me posting in this thread is enough of a clue, so you guessed what he did. He first converted the integers into a string of ‘0’ and ‘1’, performed the bitwise operation on the chars, and finally converted back to an integer (actually, we caught him as he called for help converting the string of, uh, bits, into an integer)
At least interns are cheap.
/thanks Raymond, Larry, Michael and the feedback community(ies). You’re part of my daily insight influx.
wouldn’t
value -= fmod(value, 0.25);
work?
ROUNDED = VAL(LEFT(S,4)+((F/25)*25))
e.g., if F=49, F/25*25 = 49/25*25 = 1*25 = 25
Since you’re rouding *down*, and converting a number to a string presumably rounds normally, 4.749 would round to 4.75 when it should round to 4.5.
My favourite is the rotated drawString() from com.ms.fx.FxGraphics. The algorithm used is
– render the string into a bitmap (actually an int[])
– for each white pixel in the bitmap, rotate the coordinates (calling sin() and cos() twice each, once for the x and once for the y coordinate), and add them to a list
– pass that list of pixels to the optimized drawPixels() function
rounded=0.25f * (float) ( (int)(accrued*4.0f+0.5f) );
In the past, I’ve always gone with the int*4/4 method myself. I just added my point because it wasn’t covered, and the coincidence of wanting a rounding that happens to work that way (most don’t) was too much to pass up, plus the int*4/4 method was already covered.
As for speed, both int*4/4 and a mask will be so much faster than the original method as to make no difference. Which will be faster depends on how fast float->ints convert, which I have to confess I honestly don’t know. It’s going to be hard to beat suggestion I made if done directly in machine language, though, because it never really does <i>math</i> on the float, the slow stuff with floats, it just some masking, shifting, and a single simple addition. How fast it would go implemented in that language, I have no idea, and if it is interpreted int*4/4 would almost certainly cream it unless some wild optimizations took place.
Mostly I suggested it as an interesting idea, but there’s a chance it’s right :-)
double rounded = (int) x + (int)( ( x – (int) x ) / 0.25) * 0.25;
in Foxpro 2.6. . .
rounded = ((int(((accrued – int(accrued)) * 100) / 25) * .25) + int(accrued)
it’s amazing what you can do with that question mark!
oops
store ((int(((accrued – int(accrued)) * 100) / 25) * .25) + int(accrued) to rounded
sigh
Here’s an improved more generic version, however written in C# from my blog.
class Test
{
public static double RoundToUnit(double d, double unit, bool roundDown)
{
if (roundDown)
{
// Round down.
return Math.Round(Math.Round((d / unit) – 0.5, 0) * unit, 2);
}
else
{
// Round up
return Math.Round(Math.Round((d / unit) + 0.5, 0) * unit, 2);
}
}
[STAThread]
static void Main()
{
double d1 = RoundToUnit(2.413, 0.25, true); // d1 = 2.25.
double d2 = RoundToUnit(2.413, 0.25, false); // d2 = 2.50.
double d3 = RoundToUnit(2.413, 0.30, true); // d3 = 2.40.
double d4 = RoundToUnit(2.413, 0.30, false); // d4 = 2.70.
}
}
lazybones » All about rounding
Math isn’t my strongest point, but here goes…
ACCRUED = ACCRUED – (ACCRUED % 0.25)
whats the problem with:
FLOOR( ACCRUED * 4 ) / 4
??
lf: I’ve actually written code like that back in my high school game programming days. Performance issues aside, that algorithm is flawed (it might work alright for text). There are usually more pixels in the rotated bitmap, so you end up with holes in the result. You have to rotate the destination pixel backwards to find the correct source pixel.
Using 3 casts and a mod op:
(verified works)
double rounded = x – (x – (int)x) + (((x – (int)x) * 100) – (((x – (int)x) * 100) % 25))/100;
slightly better…
double rounded = (int)x + (((x – (int)x) * 100) – (((x – (int)x) * 100) % 25))/100;
Aaaahhh… Foxpro. Those were the days.
Oh, wait, my company still uses it! D’oh!
Where does Raymond get the maximum of 32 for the number of subroutines? Consulting my Foxpro for DOS 2.6 help file, I see it says:
"Max. # of procedures per file: unlimited"
Perhaps Raymond is referring to:
"Max. # of nested DO calls: 32"
But that would only affect recursion (or really big programs). Or, maybe Raymond is talking about an even older version of Foxpro (Foxbase+?)…
Basil: Maybe Raymond will enlighten us as to the software he was using. I’m betting on DbaseIII or IV (for DOS).
There have been a number of interesting solutions presented, but few under the contraints that Raymond placed.
The Highest Level, is course
"number of vacation days taken and available for each employee. Vacation days accrued at a fixed rate but were granted only in quarter-day increments."
Personally, I’d write a couple of lines in C and let the compiler take care of the optimizations.
Perhaps Raymond can give us his solution somewhere down the road.
I love this blog. I can’t pretend to understand much of what is going on. . . but it’s easy to see that the general level of comprehension in the community is inversely proportional to the amount of feedback on each topic.
Охуенно!!!
Vi vse tupiue pidarasi!
Hello from Russia, fucking lamers!
A tip from abstract algebra.