About ultra-sort - and God
So, as I was saying, I recently wrote the LARGEST SINGLE PIECE OF CODE I have ever written in my life. I estimate that it is larger than all of the software I have written in over 30 years of serious industrial experience, also including all the comparatively minor things I did during my academic life. Just to give you a way of comparing things, it takes up the same amount of space as the ENTIRE collection of Chesterton's works - roughly fifty megabytes.
But I neglected to mention that this thing is just one single subroutine - or if you prefer the term, "procedure" or "function" or subprogram. It is merely an extremely efficient sorting routine, which is built to sort 9 items using the minimal number of comparisons, which of course is 19. Note: there are NO OTHER comparisons, such as indices, or other tricky bits of code.... but if you don't know how this is done, or can't quite figure out what is going on, I would advise you to take a course in algorithm design or perhaps read the third of the great texts of Donald Knuth on The Art of Computer Programming.
The other thing I neglected to mention is that I did not write the actual code myself. I am not adverse to spending a lot of time in order to make a computer do work for me, so I wrote a program which computes the specific SOURCE CODE to accomplish this little task. It was fun, and mildly interesting, and it got more interesting as I continued deeper into the study. It is worth telling you about, not only because of the insights into software and algorithms, but into some much deeper matters.
A few weeks back, another topic induced me to ask myself: what really is the "best" sorting algorithm? Granted a correct answer differs based on the use to which one is going to apply that algorithm - but you can find books to treat that topic. For now, I wil merely state that I was led to wonder what the minimum number of COMPARES would be for a given number of items-to-be-sorted. It seemed easy enough: four items would require five compares; five items would require seven compares...
An aside: to get the number of compares to sort n items, find the smallest integer k such that 2^k is greater than n! Behold:
n n! k 2^k
2 2 1 2
3 6 3 8
4 24 5 32
5 120 7 128
6 720 10 1024
7 5040 13 8192
8 40320 16 65536
9 362880 19 524288
10 3628800 22 4194304
11 39916800 26 67108864
12 479001600 29 536870912
13 6227020800 33 8589934592
14 87178291200 37 137438953472
15 1307674368000 41 2199023255552
16 20922789888000 45 35184372088832
17 355687428096000 49 562949953421312
18 6402373705728000 53 9007199254740992
19 121645100408832000 57 144115188075855872
20 2432902008176640000 62 4611686018427387904
I worked out the code for three and four by hand. Here, for your consideration and amusement, is the sort for n=3:
void Sort(int * q,int * r)
{
if(q[0] < q[1]) // depth 0 makes 6 tests yield 3 else 3
{
if(q[0] < q[2]) // depth 1 makes 3 tests yield 2 else 1
{
if(q[1] < q[2]) // depth 2 makes 2 tests yield 1 else 1
{
// 3 ifs to get here
r[0]=q[0];
r[1]=q[1];
r[2]=q[2];
}
else
{
// 3 ifs to get here
r[0]=q[0];
r[1]=q[2];
r[2]=q[1];
}
}
else
{
// 2 ifs to get here
r[0]=q[2];
r[1]=q[0];
r[2]=q[1];
}
}
else
{
if(q[0] < q[2]) // depth 1 makes 3 tests yield 1 else 2
{
// 2 ifs to get here
r[0]=q[1];
r[1]=q[0];
r[2]=q[2];
}
else
{
if(q[1] < q[2]) // depth 2 makes 2 tests yield 1 else 1
{
// 3 ifs to get here
r[0]=q[1];
r[1]=q[2];
r[2]=q[0];
}
else
{
// 3 ifs to get here
r[0]=q[2];
r[1]=q[1];
r[2]=q[0];
}
}
}
}
Then I began to do five, but decided it made more sense to let the machine do such busy work for me. And hence after some pleasant entertainment of software development, I had a program which would produce the SOURCE CODE which (given a particular small integer n) would accomplish the specific SORT of n items with the minimum number of compares. Incidentally, I ought to state that even for EIGHT items the compiler refused to handle the program - it was just too large for it to process. I was delighted; I have faced many goofy and difficult and tedious limitations of computers - some which were not computational, but human - and yet I had never encountered THAT limitation, that the program was too large for it to process. (Of course I easily transcended that limit (it's what engineers do), and went on to other matters... but that is not of interest here.)
This ultra-sort thing is a fascinating topic, since the COMPLEXITY of the result is (according to Knuth) still n*lg(n) as the best sorts are. (There is more to say on this matter, but I won't say it here; there is something more important to get at.) That is nice, but one has to pay the price: the SIZE OF THE CODE grows as n!, which is a bit tedious. Hence the nearly astronomical chunk of code which I mentioned at the beginning. Although any given sort of nine items requires no more than 19 compares to correctly sort, there are a huge number of actual IF statements in order to accomplish this sort! Yes: for almost all of these IFs contain nested IFs in both the THEN-clause and the ELSE-clause... it is huge. Simple, boring to do by hand; impressive to contemplate - and quite efficient, but gargantuan in its immensity of trivial code.
Yet, there was something being hinted at here, and - now, as I think back - I probably spent MORE time thinking about its MEANING than I spent on construction and investigation of the code and algorithm. Because this strange trade-off, converting (as it were) TIME into CODE - trading off a larger amount of INSTRUCTIONS in order to acquire a faster SPEED - began to suggest something about algorithms, and about getting solutions.
Quite some time ago, one of my co-workers gave me a RUBIK's Cube. We talked about it a lot - and at one point someone commented about the "God Algorithm" which provided the exact shortest sequence of twists required to return ANY given disrangement back to the homogeneous state. Of course this is nothing remarkable: God already knows the solution to all possible math problems, as well as all possible physics problems - not to mention all possible HUMAN problems. If you would rather read someone else's comments about this, hunt up Charles Babbage's Ninth Bridgewater Treatise where he argues that his own work in software development had revealed to him a little about the amazing foresights of the Creator, and the fathomless Wisdom which could arrange the ALL as He should ordain... just as a software developer does! (Note, this is explored in some detail in Jaki's Brain, Mind, and Computers, which is available here.
Indeed, it would appear that if one was permitted an unbounded amount of "memory" in which to store code, it suggests that one could gain an arbitrarily fast algorithm - at least up to the innate nature of the question at hand. (I defer the philosophy for the present; this is just a sort of slovenly meditation with some engineering seasoning, and not a term paper, hee hee!) But such a view surely indicates something hinting at the omnipotence of God - Who - as not being physical and hence bounded - has no limitations related to "code size". He knows every answer without requiring to "process through" as if He was performing an algorithm to acquire it.
It is quite fascinating, and I have barely begun to ponder the matter, but I felt it was worth jotting something down and letting you know about it.
posted by Dr. Thursday @ 1/22/2013 04:55:00 PM
6 comments
