Sort algorithm choice is immaterial for small numbers

I was debating with myself whether I should do a time comparison for the sort algorithms. Then I decided other people had already explained it much better than I could (and the real reason was that I was too lazy to code it and measure it. But you didn’t hear it from me…). So I’ll tell you a story instead.

Manager at desk
[image by diane39]

It was a few years back. I was just a rookie programmer back then. My manager didn’t understand why his superiors hired me. I didn’t even have a proper degree in computer science. He seemed to think my degree in applied mathematics and computational science was irrelevant. In fact, I think he’s afraid of me on some level.

Every day, I walked into my cubicle, sat in my chair, and waited for the phone to ring off its hook. It was a boring existence, doing small maintenance code changes to the C source code, helping users with their queries and basically making sure the System continues to stand on its rickety feet.

I was too “lowly” to be given work in the frontend, the web programming parts, the “high value” work.

One senior colleague, relieved of the maintenance duties by me, got the chance to work on higher level design stuff. A new project arrived, Highly Perceptible Project Opportunity or HiPPO for short. The manager got 3 more new staff to help out. The backend programs would be done by one of the new staff and the senior colleague (since the business processing logic was entrenched there), and the frontend web application would be handled by the rest of the team.

Me? I was given the task of making sure the System continues to stand on its rickety feet. I was considered too “lowly” to handle high level design work or web application development, yet too senior and knowledgeable about the System to remove me from the System.

One day, while I was looking at an email trying to figure out what the user wanted, one of the web application developers came over to me. Let me repeat that. One of the web application developers came into my cubicle to talk to me! I barely even get to see anyone from the HiPPO team.

Anyway, Tyler (as I’ll call him) asked me if I knew anything about sorting. In particular, how to implement a sorting algorithm. What? I went over to Tyler’s computer (wow, I’ve never been in that area…) and took a look at his code, and what he needed to implement. I told him to send me the source code, and I’ll try something out first before getting back to him.

I went back to my desk, elated that I had something to work on other than update statements and Excel spreadsheets. Tyler sent me the source code (we didn’t have source control, and even if we had, I doubt I’d be given access), and I tried sorting using bubble sort.

After testing the results, the bubble sort implementation worked fine for the requirements, so I sent the code file back to Tyler. Tyler’s happy that the sort worked, and I went back to my boring existence.

The next day, my manager called me to go into his office. I went in, and he gestured me to sit down. He looked at me for a few seconds, a furrow forming between his eyebrows.

“Vincent, I heard from Tyler from this morning’s HiPPO project update that you helped him with his sorting implementation.”

“Yes.”

He looked at me wordlessly for another few seconds.

“Is it fast? Have you looked at other sorting algorithms? There’s quicksort and heapsort I believe.”

My manager had obviously done his homework.

“Yes, I know of the other algorithms. I have chosen bubble sort because it’s easy to implement, and based on the requirements, it’s also fast enough.”

“I’m concerned about the speed. It has to be fast.”

“I’ve already tested with the higher ranges of the number of expected records. The performance is good. Tyler had also tested with the records from the test database, and it works fine.”

“But I’m worried about the user finding the web application slow.”

Now it’s my turn to look at him for a few seconds. I took a deep breath.

“We only need to sort maybe 3 or 4 records. Bubble sort is fast enough.”

[Story had been unbelievably distorted and exaggerated to make it interesting.]

Solving the Resident Evil Zero game math puzzle

Previously,

On the screen is shown a “00/81”. A number pad with number keys 1 to 9 is on the right. When a number key is entered, a knob is lit in red and the value of the number is added to the numerator of the displayed ratio. There are 10 unlit knobs.

The puzzle should be obvious. Match the numerator and the denominator with 10 entries.

So how would I solve it? My hint as stated, was:

the last entry is the most important

The first 9 entries are to get you as close to the required number as possible. This is actually similar to blackjack, a card game where you try to get as close to 21 points as possible without going over. The difference is that you don’t get to choose your next number (or card value) in blackjack. You do here.

Blackjack
[image by pavlen]

So my first instinctual thought was to finish up the first 9 entries to get to the last entry. My second instinctual thought was to make these 9 entries all the same number value. It’s a timed effort. I don’t have time to go figure out different combinations of sums.

Based on those thoughts, my next (instinctual) step was to divide the required number by 9, rounding down to nearest integer. Don’t ask me why at this point, because I’ll know the reason only after thinking it through, and I’m not thinking it through at this point.

So we have 81 divide by 9, and rounded down, we get 9. We have a problem. It’s not just 9. It’s exactly 9. There’s no number value 0 for the final entry. So we use 8 (1 less than 9).

Then we multiply 8 by 9 (entries) to get 72. And then 81 (required number) – 72 is 9, the final entry. So the answer is 8,8,8,8,8,8,8,8,8,9.

This method gives the simplest of combinations (only 2 distinct numbers used) and is the fastest to get you to the end point, the final entry. It’s the final entry that “corrects” the sum to the required number.

I have to say, the changing of 9 to 8 is (I’m starting to use the word generously) instinctive. I don’t know how changing 9 to 8 would solve the problem. I just know.

Let’s use this method on the second part of the puzzle: 67.

67 divide by 9 rounded down gives 7. 7 multiplied by 9 is 63. 67 – 63 is 4. So the answer is 7,7,7,7,7,7,7,7,7,4.

There you have it, the algorithm to solving the math puzzle. The second puzzle uses the “normal” mode of the algorithm. The first puzzle tested the edge case of the algorithm.

Hmm… can we write a function that spits out the combination using the above algorithm? Can we write a function that spits out all possible combinations?

Floating point errors – Sine X Taylor series

Stop rolling your eyes. I actually have a point to make, and the Taylor series (from math) is the best candidate to illustrate it. Think of it as expanding your education.

In simple terms, the Taylor series is a polynomial approximating another function. For example, the Taylor series for the trigonometry function sin(x) is
x – x^3/3! + x^5/5! – x^7/7! …
(x^3 means x to the power of 3, or x*x*x. 5! means 5 factorial, or 1*2*3*4*5)

As you can see, the series is infinite. You’ll also note that if you leave only the first term, sin(x) = x. Remember my warning about the pitfall.

So, that’s about all the math knowledge you need. That was easy, right? Our problem is in calculating that series. Suppose you don’t have a math library in your code base, then you’ll need to resort to the Taylor series to help approximate the sine function.

In an ideal world, the math logic you implement in code will evaluate exactly in value. Because of the finiteness of representing numbers in computers, you will get an approximate answer. And it’s more “approximaty” if you come up with the wrong algorithm for implementation too.

Note that factorial values can grow very big. 12! is 479001600, which is the limit for a 32-bit integer (13! is 6227020800, exceeding 2147483648 = 2^31). Suppose we want to stick to 32-bit integer variables, then this means the Taylor series for sin(x) can only go up to
x – x^3/3! + x^5/5! – x^7/7! + x^9/9! – x^11/11!

6 terms only. It doesn’t feel very accurate… What if we could “remove” the factorial? Note that
x^5/5! = x/1 * x/2 * x/3 * x/4 * x/5
Then we could have more terms when we reduce the factorials into floating point values.

And I’m going to let you in on another secret. The direction in which you add the terms together yields different results! So your calculation for
x – x^3/3! + x^5/5! – x^7/7! + x^9/9! – x^11/11!
gives a slightly different answer for
– x^11/11! + x^9/9! – x^7/7! + x^5/5! – x^3/3! + x

This happens because of the limitation of the variable type you use to store intermediate results. Generally speaking, you should start with the smallest intermediate values and work your way up. So this:
– x^11/11! + x^9/9! – x^7/7! + x^5/5! – x^3/3! + x
is preferred. The factorial in the denominator increases faster than the exponential in the numerator, so higher order terms are smaller in value.

In a following code sample, I’ve labelled sections A, B, C, D, E, and F.

Sections A, C and E contain code where the for loops are in ascending order. Sections B, D and F contain code where the for loops are in descending order.

Sections A and B form the pair where the float variable type is used to store intermediate values.

Sections C and D form the pair where the double variable type is used.

Sections E and F still use the double variable type, and the implementation logic for x^n/n! is do x^n and n! separately, then divide x^n by n!. This reduces the number of floating point operations (by about half actually), and so reduces the calculation errors.

Because of the use of factorial, we’ll use a long (a 64-bit integer in C# and appropriate operating system) which has more capacity to store the intermediate factorial value.

We’ll be calculating sin(PI), so the Taylor series is
PI – PI^3/3! + PI^5/5! – …

Alright, a short lesson in math. Odd numbers can be represented in the form of (2n + 1), where n is an integer. Hence this part of the code

k = 2 * i + 1;

And this part does the alternating minus and plus sign of the series

if (i % 2 == 1) fBuffer = -fBuffer;

And here’s the code:

const int cnTerms = 9;
float floatx = (float)Math.PI;
double doublex = Math.PI;
float fAsc, fDesc, fBuffer;
double fAscInDouble, fDescInDouble, fBufferInDouble;
double fAscAlt, fDescAlt;
long iBuffer;
int i, j, k;
StreamWriter sw = new StreamWriter("taylorsinepi.txt");

fAsc = 0.0f;
for (i = 0; i < cnTerms; ++i)
{
	k = 2 * i + 1;
	fBuffer = 1.0f;
	for (j = 0; j < k; ++j)
	{
		fBuffer *= floatx / (float)(j + 1);
	}
	if (i % 2 == 1) fBuffer = -fBuffer;
	fAsc += fBuffer;
	sw.WriteLine("A {0,0:d2} {1,0:f8}", i, fBuffer);
}
sw.WriteLine();

fDesc = 0.0f;
for (i = cnTerms - 1; i >= 0; ----i)
{
	k = 2 * i + 1;
	fBuffer = 1.0f;
	for (j = k - 1; j >= 0; ----j)
	{
		fBuffer *= floatx / (float)(j + 1);
	}
	if (i % 2 == 1) fBuffer = -fBuffer;
	fDesc += fBuffer;
	sw.WriteLine("B {0,0:d2} {1,0:f8}", i, fBuffer);
}
sw.WriteLine();

fAscInDouble = 0.0;
for (i = 0; i < cnTerms; ++i)
{
	k = 2 * i + 1;
	fBufferInDouble = 1.0;
	for (j = 0; j < k; ++j)
	{
		fBufferInDouble *= doublex / (double)(j + 1);
	}
	if (i % 2 == 1) fBufferInDouble = -fBufferInDouble;
	fAscInDouble += fBufferInDouble;
	sw.WriteLine("C {0,0:d2} {1,0:f16}", i, fBufferInDouble);
}
sw.WriteLine();

fDescInDouble = 0.0;
for (i = cnTerms - 1; i >= 0; ----i)
{
	k = 2 * i + 1;
	fBufferInDouble = 1.0;
	for (j = k - 1; j >= 0; ----j)
	{
		fBufferInDouble *= doublex / (double)(j + 1);
	}
	if (i % 2 == 1) fBufferInDouble = -fBufferInDouble;
	fDescInDouble += fBufferInDouble;
	sw.WriteLine("D {0,0:d2} {1,0:f16}", i, fBufferInDouble);
}
sw.WriteLine();

fAscAlt = 0.0;
for (i = 0; i < cnTerms; ++i)
{
	k = 2 * i + 1;
	fBufferInDouble = 1.0;
	iBuffer = 1;
	for (j = 0; j < k; ++j)
	{
		fBufferInDouble *= doublex;
		iBuffer *= (j + 1);
	}
	if (i % 2 == 1) fBufferInDouble = -fBufferInDouble;
	fAscAlt += (fBufferInDouble / (double)iBuffer);
	sw.WriteLine("E {0,0:d2} {1,0:f16}", i, fBufferInDouble);
}
sw.WriteLine();

fDescAlt = 0.0;
for (i = cnTerms - 1; i >= 0; ----i)
{
	k = 2 * i + 1;
	fBufferInDouble = 1.0;
	iBuffer = 1;
	for (j = k - 1; j >= 0; ----j)
	{
		fBufferInDouble *= doublex;
		iBuffer *= (j + 1);
	}
	if (i % 2 == 1) fBufferInDouble = -fBufferInDouble;
	fDescAlt += (fBufferInDouble / (double)iBuffer);
	sw.WriteLine("F {0,0:d2} {1,0:f16}", i, fBufferInDouble);
}
sw.WriteLine();

sw.WriteLine("ASC     : {0}", fAsc.ToString("f16"));
sw.WriteLine("DESC    : {0}", fDesc.ToString("f16"));
sw.WriteLine("ASC   x2: {0}", fAscInDouble.ToString("f16"));
sw.WriteLine("DESC  x2: {0}", fDescInDouble.ToString("f16"));
sw.WriteLine("ASC  ALT: {0}", fAscAlt.ToString("f16"));
sw.WriteLine("DESC ALT: {0}", fDescAlt.ToString("f16"));

sw.Close();

And this is the output:

A 00 3.14159300
A 01 -5.16771300
A 02 2.55016400
A 03 -0.59926460
A 04 0.08214591
A 05 -0.00737043
A 06 0.00046630
A 07 -0.00002192
A 08 0.00000080

B 08 0.00000080
B 07 -0.00002192
B 06 0.00046630
B 05 -0.00737043
B 04 0.08214591
B 03 -0.59926460
B 02 2.55016400
B 01 -5.16771300
B 00 3.14159300

C 00 3.1415926535897900
C 01 -5.1677127800499700
C 02 2.5501640398773500
C 03 -0.5992645293207920
C 04 0.0821458866111282
C 05 -0.0073704309457144
C 06 0.0004663028057676
C 07 -0.0000219153534478
C 08 0.0000007952054001

D 08 0.0000007952054001
D 07 -0.0000219153534478
D 06 0.0004663028057676
D 05 -0.0073704309457144
D 04 0.0821458866111282
D 03 -0.5992645293207920
D 02 2.5501640398773400
D 01 -5.1677127800499700
D 00 3.1415926535897900

E 00 3.1415926535897900
E 01 -31.0062766802998000
E 02 306.0196847852810000
E 03 -3020.2932277767900000
E 04 29809.0993334462000000
E 05 -294204.0179738900000000
E 06 2903677.2706132800000000
E 07 -28658145.9693880000000000
E 08 282844563.5865330000000000

F 08 282844563.5865330000000000
F 07 -28658145.9693880000000000
F 06 2903677.2706132800000000
F 05 -294204.0179738900000000
F 04 29809.0993334462000000
F 03 -3020.2932277767900000
F 02 306.0196847852810000
F 01 -31.0062766802998000
F 00 3.1415926535897900

ASC     : -0.0000000102118100
DESC    : 0.0000000000000000
ASC   x2: 0.0000000224195107
DESC  x2: 0.0000000224195102
ASC  ALT: 0.0000000224195103
DESC ALT: 0.0000000224195102

I’ve printed the intermediate values for better comparison. And it looks beautiful that the section pairs appear symmetrical. So let’s see the first pair of results.
-0.0000000102118100 versus 0.0000000000000000

That don’t look very equal to me. I don’t know why we got zero for the second one (maybe the alternating sign code is wrong). I mean the correct answer is zero, just that it shouldn’t be from an approximation algorithm…

Anyway, the next pair looks promising:
0.0000000224195107 versus 0.0000000224195102
Except the last digit.

The last pair has different last digits too.

So what have we learnt? Use the correct variable type. And come up with a good algorithm. The most accurate variable type can’t save you if your algorithm is faulty. Change the cnTerms constant to something else, like 8 (which gives a more believable disparity for the first pair), to get a feel of the algorithm, code and results.

For your information, sin(PI) is zero, which is the value the algorithms are iteratively approaching.