In the lab, Shannon followed the process of linear incremental development of the program. The word linear here means sequential, no part of work was done indepentently. However, analysing the final product, one can notice that it was possible to develop the mathematical part completely independently from input/output, validation, etc. which constitute the skeleton of the robust and user-friendly code.
From a project manager's point of view, making use
of the possibility to share work would be a much
preferred approach. It would not only reduce
time, but also allow to hire programmers with particular
expertise.
We can imagine that work
is assigned to two programmers: one responsible for user interface (UI)
and the other for mathematical functionality.
The interface programmer must, of course, know some mathematics in order to be able to identify and properly handle special situation, provide necessary conversion of units etc.
Now, suppose our two programmers have completed their tasks and
presented the following codes:
/* Fake Math. */ /* Real computation of sum must be put here. The sum depends on x and N */ sum = 1.234567;Morever, the inteface program doesn't declare the loop counter i, since the need in such a variable never arises. And the only reason it includes <math.h> is the existing reference to the constant M_PI.
That done, let us assemble the program. It can, of course,
be done by just copy-and-paste from math file to the interface file,
which will become the ultimate program. But there are some hurdles.
For once, the interface programmer might not be aware of the math
programmer's need in some extra variables (like the loop counter i);
tracing all such details can be an unnecessary burden.
So there is a better approach: functions. Everybody is assigned
a new quick task. Moreover, it is even possible the two programmers
work on their files independently and not to copy-and-paste a single
line from one file to another! (Instead, we'll have the preprocessor
do it.)
The final project consists of two files. The principal is
mt_q2.c, formerly known as
interface.c. The other one, called
sumsin.c contains
only the definition of the function sumSines.
To compile the project, type
gcc -lm mt_q2.c
The file sumsin.c will be automatically substituted by
preprocessor instead of line #include "sumsin.c";
Note: Our sumsin.c is not a standard library file. In this case, the delimiters in #include "sumsin.c"; must be quotation marks rather than angle brackets.
Comparing just the file sizes, one can conclude that the interface part is more sophisticated than math. That's true ... generally, in many cases ... to a certain limit.
To demonstrate what I mean, let us copy the file
mt_q2.c to file mt_q2fast.c, replace the line
sum=sumSines(x,N)
in the main program by the line
sum=fastSines(x,N)
and the line
#include "sumsin.c"
by the line
#include "fastsin.c"
The function defined in "fastsin.c" can compute
the sum faster!
To make comparative study of the two codes easy, let us use the following
form of gcc command:
gcc -lm mt_q2fast.c -o b.out
This creates a new executable program named b.out
(The option -o in gcc allows the programmer
to assign a desired name to the executable.)
Now we can run both programs, a.out (standard version) and b.out (faster version) and compare their performance. The difference becomes noticeable only for very large values of N. For N=100000000 (100 millions) I observed the time spent by program a.out being approximately 6 seconds, while program b.out spent approximately 2 seconds. Times may vary depending on the system, but the version b will usually lead the race.
Those interested in this performance difference should
read comments (and possibly code) in file "fastsin.c".
Instead, I want to turn your attention to a new fascinating
fact: try the same sum (with N=108) on Maple:
> evalf(sum(sin(i*x),i=1..10^8));
(The value for x must be assigned in advance.)
The calculation is instant and nothing changes if you replace
set N equal 109, 10100, 101000.
Is Maple's summation algorithm so incredibly fast that it can
somehow add up 1 with 1000 zeros terms in an eye's blink?
No. There is indeed an unexpected turn, a miracle, but in a different
direction. Maple is aware of many series that can be summed exactly,
and our series - believe it or not - is of this kind.
This very non-obvious fact can be understood without much trouble by
those who are familiar with complex numbers and the celebrated Euler's
formula
eix = sin(x) + i cos(x).
Thus, sin(x) is the imaginary part of the exponent eix.
Our sum is the imaginary part of the sum
eix
+ e2ix +
...+ eiNx,
which is nothing else but a geometric series in which both the first term
and the quotient are equal to ix. The sum of the
geometric series is
(ei(N+1)x - eix) /
(eix -1).
Our sum is the imaginary part of it.
It can be simplified down to
sin ((N+1)x/2) sin(Nx/2) /
sin(x/2).
It makes sense to include this formula in our C codes to enable
analytical verification of the direct summation.
Here
is the shortest (Math only) version with this added feature.