More on Fractal Rulers
Dear DDJ,
I was interested by the "Algorithm Alley" column about fractal rulers (DDJ, June 1994), particularly because Tom Swan sped up the algorithm by replacing recursion with an explicit stack. I was not convinced that this was the best way, especially as recursion may be faster than implementing the stack manually.
I noticed that the pattern of the lengths of the markings of the ruler is the same as the number of 0s on the right-hand end of a binary number; see Example 1(a).
You can clear all but the least significant set bit of a number by calculating n and --n. This leaves you with a power of two, but the ruler markings should increase in size linearly. You could take the logarithm of n and --n, but this isn't very fast; you could test each bit in turn until you find one that's set, but that isn't very elegant; or you could consult alt.hackers on Usenet. Somebody will reply, reminding you that for such a small problem size, you can't beat a lookup table. (Thanks to David Jones at [email protected] for that one!) So the ruler algorithm is like that in Example 1(b). This should be more efficient, but instead of demonstrating recursion elimination, it shows that you should look for a better algorithm before optimizing.
Anthony Finch
Bristol, England
Dear DDJ,
I enjoyed Tom Swan's "Algorithm Alley" column on drawing a ruler, but I should point out that he took the hard approach. If you number the ticks starting with 1, then it can be seen that the length of each tick (up to a maximum) is simply one more than the number of low-order 0 bits in the tick number. Taking that observation, and using C instead of Pascal (shudder), the routine could have been written as Example 2, which does not involve either recursion or stack usage. The code uses line() and label(). The line() function is the same as in Tom's article; label() was not mentioned there, but something had to draw the numbers! Also, I have assumed that both line() and label() are zero relative and that the top variable and the charHeight variable are set elsewhere. As you can also see, there is substantially less code than in the Pascal version, although there are additional variable definitions (some of which were left undefined in the Pascal version).
Michael Lee Finney
Lynchburg, Virginia
The Fuzzy-Logic Language Model
Dear DDJ,
The trouble with fuzzy logic is that it isn't--logic, that is. Fuzzy, maybe. Calling it "logic" at best confuses the issue, and at worst sounds like scammery.
Fuzzy logic, at least the way it seems to be used today, is much more like a computer language--a translation product that allows the programmer to produce a program in high-level constructs, which are then translated into actual machine codes. Even when assembly language is used, this is still the approach, except that translation is done manually.
Briefly, the fuzzy-logic language model is as follows:
- Inputs are characterized in real quantities as fuzzy things: The sensor range from 70 to 100 might be "fast," and a range from 0 to 80 might be "slow." The degree of fast and slow is variable, and both can be somewhat true at the same time. These things are controlled by relatively simple input functions which, apparently, come in different flavors.
- A set of fuzzy "rules" is used to combine these fuzzy inputs and produce fuzzy outputs, somewhat analogously to ordinary logic, except that the exact method used is not fixed. Apparently there are varying strategies available, which have their fans and likely applications. "Fast" and "heavy" inputs might trigger a fuzzy "brakes" output, for instance.
- The fuzzy outputs are "de-fuzzified." "Hi-power" might signify that a value of 200 should be applied to a digital-to-analog converter that controls a motor.
I am not antifuzzy. To emphasize my initial point, I feel referring to this stuff as "logic" or "a logic" is confusing at best, and misleading at worst. As a language tool, this thing is probably quite useful for the embedded-control applications for which it is in fact used. Will it or something like it also solve the mysteries of consciousness and the future of mankind? I don't think so.
Gregor Owen
CompuServe 71121,625
NT Services
Dear DDJ,
I enjoyed reading Marshall Brain's article "Inside Windows NT Services" (DDJ, May 1994). However, I did want to alert Marshall and DDJ readers to a typographical error in the Windows NT SDK concerning NT services. The prototypes for the ServiceMain and ControlHandler functions in the include file WINSVC.H should be prototyped to use the WINAPI (or CALLBACK) calling convention. See Example 3.
The WINAPI and CALLBACK macros are defined in the NT SDK as __stdcall. The ServiceMain and ControlHandler functions must use the __stdcall calling convention. Failure to use the correct calling conventions will result in an improperly functioning service. The next version of the NT SDK will correctly prototype these functions.
Peter Santoro
Microsoft Consulting Service
Example 1: An alternative fractal-ruler algorithm.
(a)
0 = 0000 -> 4 -> -----
1 = 0001 -> 0 -> -
2 = 0010 -> 1 -> --
3 = 0011 -> 0 -> -
4 = 0100 -> 2 -> ---
5 = 0101 -> 0 -> -
6 = 0110 -> 1 -> --
7 = 0111 -> 0 -> -
8 = 1000 -> 3 -> ----
9 = 1001 -> 0 -> -
10 = 1010 -> 1 -> --
11 = 1011 -> 0 -> -
12 = 1100 -> 2 -> ---
13 = 1101 -> 0 -> -
14 = 1110 -> 1 -> --
15 = 1111 -> 0 -> -
(b)
void ruler(double length, /*of ruler (screen units) */
int subdivs, /* in an inch (power of 2) */
double step, /* for each subdivision (screen units) */
double min_mark_len, /* length of smallest mark (ditto) */
double mark_incr, /* difference in length of marks (ditto) */
double long_mark_len,/* length of the inch markers (ditto) */
double num_size /* for the inch numbers (do I really need to
say it again?) */
{
double mark_pos, mark_len;
int counter, inch;
const char zeros[64] = {
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
};
assert(subdivs == 1
|| subdivs == 2
|| subdivs == 4
|| subdivs == 8
|| subdivs == 16
|| subdivs == 32
|| subdivs == 64);
inch = 0;
counter = subdivs;
for(mark_pos = 0; mark_pos < length; mark_pos += step)
{
if(counter == subdivs)
{
line(mark_pos, 0, mark_pos, long_mark_len);
plot_num(inch, mark_pos, long_mark_len, num_size);
counter = 1;
++inch;
}
else
{
mark_len = min_mark_len + zeros[counter] * mark_incr;
line(mark_pos, 0, mark_pos, mark_len);
++counter;
}
}
}
Example 2: More on fractal rulers.
// assumed variables and functions...
extern unsigned top;
extern unsigned charHeight;
void line(unsigned x1, unsigned y1, unsigned x2, unsigned y2);
void label(usigned x, unsigned y, char *s);
void ruler(
unsigned segments, // Number of complete segments
unsigned partialTicks) // Must be in range 0..ticksPerSegment-1
{
unsigned const tickIncrement = 1;
unsigned const ticksPerSegment = 16; // Must be power of two.
unsigned const tickLength[ticksPerSegment] =
{1 * tickIncrement,
2 * tickIncrement, 0,
3 * tickIncrement, 0, 0, 0,
4 * tickIncrement, 0, 0, 0, 0, 0, 0, 0,
5 * tickIncrement};
unsigned ticks = ticksPerSegment * segments + partialTicks;
unsigned length;
char s[16];
for (unsigned i = 0; i < ticks; i++)
{
length = tickLength[min(x ^ (unsigned long)(x + 1),
ticksPerSegment - 1)];
line(i, top, i, top - length);
if (i && (i % ticksPerSegment == 0))
label(i, top - length - charHeight, itoa(i / ticksPerSegment,
s, 10));
}
}
Example 3: NT services.
// Function Prototype for the Service Main Function typedef VOID(WINAPI*LPSERVICE_MAIN_FUNCTIONW)( DWORD dwNumServicesArgs, LPWSTR*lpServiceArgVectors ); typedef VOID(WINAPI*LPSERVICE_MAIN_FUNCTIONA)( DWORD dwNumServicesArgs, LPSTR*lpServiceArgVectors ); //Prototype for the Service Control Handler //Function typedef VOID(WINAPI*LPHANDLER_FUNCTION)( DWORD dwControl );
Copyright © 1994, Dr. Dobb's Journal
