LETTERS

   F(n) = (bⁿ - cⁿ)/a
   where a = Sqrt (5)
   b = (1 + a)/2 = Golden Ratio,
   c = (1 - a)/2 = 1 - b = -1/b

Since the magnitude of cⁿ/a is less than 1/2 for n >= 0, an efficient method of computing Fibonacci numbers is the evaluation of the equation:

  F(n) = Round(bⁿ/a).

In C this can be programmed as:

  #include <math.h>
  fib = floor(0.5 + pow(b,n)/a);

A program based on this method runs 15 to 20 times faster than Victor's matrix method.

Harry J. Smith

Saratoga, California

Dear DDJ,

I read "Efficiently Raising Matrices to an Integer Power" with great interest. Mr. Duvanenko's points are very well considered and illustrated.

Although it is not the major point of the article, I would like to add another method to compute Fibonacci numbers as an illustration of a more general point. The point is that there are frequently direct analytic methods that yield closed-form solutions. In fact, the Golden Ratio is not just the ratio of F(n) and f(n - 1) as n approaches infinity, but can be expressed more accurately as the (sqrt(5) + 1)/2. Frequently, the Golden Ratio is referred to as the Golden Number and is expressed as a nonrepeating decimal with an approximate value of 0.6180339.

You may find it interesting to note that the GN has some other interesting properties. For example, (GN - 1) = (1/GN).

A source of the closed form comes from discrete difference equations. The following is a short form solution:

   F(n) = F(n - 1) + F(n - 2)
   F(n - 2) + F(n - 1) + F(n) = 0

When the del operator is defined as del(Fn)) = F(n - 1), then the general solution is a(b)ⁿ. Using the quadratic formula on the characteristic equation:

  del del + del - 1 = 0

yields a general solution of

  f(n) = 1/sqrt(5) ((1 + sqrt(5))/2)ⁿ
  -f(n) = 1/sqrt(5) ((1 - sqrt(5))/2)ⁿ

Using the closed form solution implemented with static constants yields a solution that computes in fixed time. This approach can be used with a variety of other functions, as shown in Example 1.

Example 1

  #include  <stdio.h>
  #include  <stdlib.h>
  #include  <math.h>
  #include  <string.h>

  static double  Invsqrt5;
  static double  Sqrt5plus;
  static double  Sqrt5minus;

  double fiber(int n);

  int main (void)
  {
  int    f_num;8
  char   f_str[80];
  Invsqrt5   = 1.0 / sqrt(5.0);
  Sqrt5plus  = (1.0 + sqrt(5.0)) / 2.0;
  Sqrt5minus = (1.0 - sqrt(5.0)) / 2.0;

  while (1)
    {
  fputs ("\nnumber: " , stdout);
    f_str[0] = '\';
    fgets(f_str, sizeof(f_str) , stdin);
    if (strlen(f_str) > 0)
      {
      f_num = atoi(f_str);
      printf("F(%5d) is %20.01f\n" ,
                   f_num , fiber(f_num));
      }
    }
  return (0);
  }

  double fiber(int n)
  {
    return((pow(Sqrt5plus , (double) n)
           - pow(Sqrt5minus , (double))
                             * Invsqrt5);
  }

Tom Carrington

Plano, Texas

Dear DDJ,

While Mr. Duvanenko's article was interesting, I thought it was inappropriately applied. If

individual Fibonacci numbers are required, they can be more economically computed using the

following formula:

  F(n)=Round(pⁿ/sqrt(5)),

where p = (1 + sqrt(5))/2, is the Golden Ratio.

p{n} can be evaluated using the repeated squaring method described in the article. Or even better, F(n) = trunc (0.5 + exp(n * ln(p) - 0.5 * ln(5))).

Both formulae are derived from the solution to the recursive definition of Fibonacci numbers, i.e.,

  F(n) = 1/sqrt(5) * [((1 + sqrt(5))/2)ⁿ -
                        ((1 - sqrt(5))/2)ⁿ]

As the absolute value of the second term is less than 0.5, we can neglect it and round to the nearest integer.

Jeremy Ottenstein

Elizabeth, New Jersey

Are Your Windows Running?

Dear DDJ,

Ben Myers's WINTHERE program ("Winthere," January 1991) is very useful if you need to know if Windows is running real, standard, or DPMI mode. But if you only need to know if Windows is running or not, there is an easier way. Windows is adding a new environment variable, the "windir," to keep track of the home directory. The variable is added by Windows in runtime and not, as usual, in the AUTOEXEC.BAT. Since any app spawned by DOS EXEC (int 21, function 4B), as programs normally are, inherits the environment block from its parent, windir will be available in all win- and oldapps started under Windows. Note that this is only available in Windows 3.0. Example 2 shows my environment in a DOS-box when running Windows.

Example 2: The DOS-box environment with Windows running

  C:\DOS>set
  PROMPT=$p$g
  PATH=C:\WINDOWS;C:\DOS;C:\PCT;C:\BORLANDC\BIN;C:\WINDEV; C:\T D;
  TEMP=C:\WINDOWS\TEMP
  COMSPEC=C:\DOS\COMMAND.COM
  windir=C:\WINDOWS

The program in Example 3 checks if the "windir" environment variable is present and if it is, the program exits with error code 0, otherwise with error code 255.

Example 3: Program to check for windir

  // CheckWin check if the environment variable "windir"
  // is present.
  #include <stdlib.h>

  int main(void)
  {
    if(getenv("windir") = = NULL) return 255; // windir didn't exist
    else return 0; // it did
  }

The program in Example 4 is very useful in .BAT files for checking if they are running with or without Windows present. This avoids the common problem when you forget that you are in a DOS-box and try to start Windows again, often ending up in a general protection fault destroying whatever was running under Windows. (I renamed WIN.COM to WINDOWS.COM.)

Example 4: Program to check whether .BAT files are running with or without Windows

  WIN.BAT
  @ECHO OFF
  CheckWin
  IF ERRORLEVEL 255 THEN GOTO W
  ECHO Windows is already running (Press Ctrl=Esc or Alt+Tab)
  GOTO END
  :W
  WINDOWS
  :END

Torgil Johnsson

Kista, Sweden

Ben responds: Mr. Johnsson has indeed found a simple way to determine whether Windows 3.0 is running. Just like my original and incomplete WINTHERE solution to the problem, Johnsson's CHECKWIN has advantages and disadvantages.

CHECKWIN relies on an apparently undocumented feature of Windows 3.0, though one that can readily be verified without resorting to reverse engineering methods. Since the windir environment variable is undocumented, Microsoft has no obligation to carry it forward to new releases of Windows. When I first broached this problem to Microsoft via their online service over a year ago, the Microsoft response suggested something similar to Mr. Johnsson's approach, but it was vaguely stated, and there was no mention of the windir environment variable.

The method in CHECKWIN is not robust. It does not guarantee that Windows is running. For example, I could set the windir variable with a C setenv function call made from a non-Windows program, and this would mislead any program that used the CHECKWIN method. In passing, note that the DOS SET command cannot be used to set an environment variable which contains any lower case characters, because SET converts both environment variable and environment string to upper case.

On the plus side, the CHECKWIN approach was properly both from Windows and DOS apps. I put a similar getenv function call into one of my Windows apps, and it returned the path from which Windows was launched. This implies that it would also work when used within device drivers and other system software that needs to know whether Windows is running or not. Also in passing, setting an environment variable is not a foolproof method for making known the path from which Windows is launched. Environment space in a PC is limited, and any software that uses environment variables always runs the risk of exceeding available environment space. Many Microsoft products use one or more environment variables. From a human factors standpoint this is not desirable, especially for novice users who may have real difficulty figuring out what did not work and why. There are several good techniques for keeping track of this sort of information without using environment variables.

I have reservations about using the CHECKWIN approach in commercial software. Until Microsoft defines a robust API for detecting the presence of Windows, I cannot offer a better solution other than combining my original WINTHERE code with the getenv function as used by CHECKWIN. The combined result still has holes in it, but it is better than nothing. Let's hope that Microsoft will address this issue with Windows 3.1, which is expected to be in beta testing in late June or early July 1991.