Malcolm's new book

[Malcolm McLean]

The webpages for my new book are now up and running.

The book, Basic Algorithms, describes many of the fundamental algorithms
used in practical programming, with a bias towards graphics. It includes
mathematical routines from the basics up, including floating point
arithmetic, compression techniques, including the GIF and JPEG file formats,
hashing, red black trees, 3D and 3D graphics, colour spaces, machine
learning with neural networks, hidden Markov models, and fuzzy logic,
clustering, fast memory allocators, and expression parsing.

(Follow the links)

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Eric Sosman]

Malcolm McLean wrote On 07/24/07 16:18,:

The webpages for my new book are now up and running.

The book, Basic Algorithms, describes many of the fundamental algorithms
used in practical programming, with a bias towards graphics. It includes
mathematical routines from the basics up, including floating point
arithmetic, compression techniques, including the GIF and JPEG file formats,
hashing, red black trees, 3D and 3D graphics, colour spaces, machine
learning with neural networks, hidden Markov models, and fuzzy logic,
clustering, fast memory allocators, and expression parsing.

I read only the two sqrt() replacements. The first
is bad, but at least the text says as much. The second,
supposedly superior version is broken in at least three
ways: First, it won't compile. Second, when the obvious
bug is fixed it still won't compile under C99 and won't
link under C90. And when *that* bug is fixed, a third
bug will become apparent. Sloppy workmanship.

--
Er*********@sun .com

[Keith Thompson]

Eric Sosman <Er*********@su n.comwrites:

Malcolm McLean wrote On 07/24/07 16:18,:

>The webpages for my new book are now up and running.

The book, Basic Algorithms, describes many of the fundamental
algorithms used in practical programming, with a bias towards
graphics. It includes mathematical routines from the basics up,
including floating point arithmetic, compression techniques,
including the GIF and JPEG file formats, hashing, red black trees,
3D and 3D graphics, colour spaces, machine learning with neural
networks, hidden Markov models, and fuzzy logic, clustering, fast
memory allocators, and expression parsing.

I read only the two sqrt() replacements. The first
is bad, but at least the text says as much. The second,
supposedly superior version is broken in at least three
ways: First, it won't compile. Second, when the obvious
bug is fixed it still won't compile under C99 and won't
link under C90. And when *that* bug is fixed, a third
bug will become apparent. Sloppy workmanship.

A couple more comments. The layout on the web page makes the code
nearly unreadable. And try squareroot(1.0e 6).

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Flash Gordon]

Keith Thompson wrote, On 24/07/07 22:27:

Eric Sosman <Er*********@su n.comwrites:

>Malcolm McLean wrote On 07/24/07 16:18,:

>>The webpages for my new book are now up and running.

The book, Basic Algorithms, describes many of the fundamental

<snip>

A couple more comments. The layout on the web page makes the code
nearly unreadable. And try squareroot(1.0e 6).

The book also confuses the concepts of integers and pointer by talking
about malloc being able to return zero. In fact, malloc cannot return
zero because that is a number, what it can return is a null pointer.

It goes on to assume that int is at least 32 bits.

Uses a non-portable method of finding out the size of a binary file
implying the only problem with the method is whether the length might be
too long to represent as a long, when in fact it is non-portable for
other more basic reasons (see the comp.lang.c FAQ).

Uses lower case names for macros. I will admit that the standard does
not mandate upper case, but it is a well known convention.

Seems to recommend against keeping library functions in separate source
files and headers. To quote:
| And we are ready to go. However often if you intend code to be passed
| about, it is not a good idea to include stdsup.h. Cut and paste the
| function into your source instead and declare it static.

It at the very least implies that everything does and always has used
IEEE format when it says:
| ... In small embedded systems, or older computers, they were often
| done in software. Whether hardware or software operations are chosen,
| the memory format is the same.
Oh, and don't forget that a UK person should reference either the UK
standard or the ISO standard in preference to the American standard.
--
Flash Gordon

[pete]

Eric Sosman wrote:

>
Malcolm McLean wrote On 07/24/07 16:18,:

The webpages for my new book are now up and running.

The book, Basic Algorithms, describes many of the fundamental algorithms
used in practical programming, with a bias towards graphics. It includes
mathematical routines from the basics up, including floating point
arithmetic, compression techniques, including the GIF and JPEG file formats,
hashing, red black trees, 3D and 3D graphics, colour spaces, machine
learning with neural networks, hidden Markov models, and fuzzy logic,
clustering, fast memory allocators, and expression parsing.

I read only the two sqrt() replacements. The first
is bad, but at least the text says as much. The second,
supposedly superior version is broken in at least three
ways: First, it won't compile. Second, when the obvious
bug is fixed it still won't compile under C99 and won't
link under C90. And when *that* bug is fixed, a third
bug will become apparent. Sloppy workmanship.

I'm pretty sure that the assert expression
in squareroot(), was an untested afterthought.

I didn't like the arbitrary termination conditions
invlolving magic numbers like 10 iterations in squareroot(),
or 0.000001 in exponent(), or 0.00000001 in logarithm().

The exponent and logarithm functions
could have been terminated through conditions
involving DBL_EPSILON.

A Newton-Raphson square root algorithm,
can be terminated more logically:

double sq_rt(double x)
{
if (x 0) {
const double c = x;
double y = c / 2 + 0.5;

do {
x = y;
y = (c / x + x) / 2;
} while (x y);
}
return x;
}

Page 55 shows pi at 3.1415926535897 931160
The "1160" part, is wrong.

I uploaded some math functions written
in completely portable freestanding C code, to:

http://www.mindspring.com/~pfilandr/C/fs_math/

/* BEGIN fs_math.h */
/*
** Portable freestanding code
*/
#ifndef H_FS_MATH_H
#define H_FS_MATH_H

double fs_sqrt(double x);
double fs_log(double x);
double fs_log10(double x);
double fs_exp(double x);
double fs_modf(double value, double *iptr);
double fs_fmod(double x, double y);
double fs_pow(double x, double y);
double fs_cos(double x);
/*
** C99
*/
double fs_log2(double x);
double fs_exp2(double x);
long double fs_sqrtl(long double x);
long double fs_logl(long double x);
long double fs_expl(long double x);
long double fs_cosl(long double x);
long double fs_fmodl(long double x, long double y);

#endif

/* END fs_math.h */

This is the output from fslog_10 on my machine:

/* BEGIN fs_log10.c output */

fs_log10(10000) - 4 is 0.000000e+000
fs_pow(0.0001, -0.25) - 10 is 3.552714e-015
fs_cos(DEGREES_ TO_RADIANS(-3540)) - 0.5 is 9.992007e-016
fs_sqrt(2) * fs_sqrt(2) - 2 is -4.440892e-016

log10(10000) - 4 is 0.000000e+000
pow(0.0001, -0.25) - 10 is 0.000000e+000
cos(DEGREES_TO_ RADIANS(-3540)) - 0.5 is -1.060133e-015
sqrt(2) * sqrt(2) - 2 is 4.440892e-016

/* END fs_log10.c output */

--
pete

[pete]

pete wrote:

A Newton-Raphson square root algorithm,
can be terminated more logically:

double sq_rt(double x)
{
if (x 0) {
const double c = x;
double y = c / 2 + 0.5;

do {
x = y;
y = (c / x + x) / 2;
} while (x y);
}
return x;
}

The extra bit of analysis here is that for any positive N
and any positive Guess,
((N / Guess + Guess) / 2) is ***greater than or equal to***
the square root of N.
So, if the first Guess is greater than or equal
to the square root of N,
then each subsequent Guess will be lower,
until at some point the Guess will be low enough so that
((N / Guess + Guess) / 2) isn't less than Guess;
And when that happens,
then Guess is the greatest double value
that is less than or equal to the square root of N.
The choice for first guess being (N / 2 + 0.5), follows from this:
The square root of N, is somewhere between N and 1.0,
so the first two candidates for first guess are N and 1.0.

((N / N + N) / 2) and ((N / 1.0 + 1.0) / 2)
happen to both be equal to (N / 2 + 0.5),
and (N / 2 + 0.5) is greater than or equal
to the square root of any positive N,
making (N / 2 + 0.5) be a good value for first guess.

--
pete

[Ben Bacarisse]

"Malcolm McLean" <re*******@btin ternet.comwrite s:

The webpages for my new book are now up and running.

Did you compile and test the code? Is the code in the book the same
as that on the web pages? I am worried by a book that contains:

if(x & 0x7FFFFFFFF < y & 0x7FFFFFFF)

I'd have thought that all compilers would tell you about the
(probable) extra F and that the simplest testing would have shown up
the missing parentheses (I don't think you really meant what you
wrote).

--
Ben.

[Ben Bacarisse]

"Malcolm McLean" <re*******@btin ternet.comwrite s:

The webpages for my new book are now up and running.

Since there seem to be significant errors, I decided to have another
look. I do not want to be unkind, but I can't see how, as an
academic, you can publish a book you are clearly not qualified to
write. The smattering of typographical errors is unfortunate (and not
really forgivable since I'd have thought that most publishers will
take your actual compilable source code) but to claim that queue might
be implemented like this:

int queue[100];
int head;
int tail;

void add(int x)
{
if(tail == 100]
tail = 0;
queue[tail++] = x;
}

int remove(void)
{
int answer = queue[head];
head++;
if(head == 100)
head = 0;
return answer;
}

is absurd. I have improved the formatting but left in the silly
mistakes like ] closing the first 'if'.

I have been reticent in the past to post bad code from online lecture
notes because I am sympathetic to some of the pressures that teachers
are, at times, put under[1], but you are asking that people, who want
to learn, should pay over £16 for this kind of stuff. You chose to
write and publish it.

This is may be the biggest howler, but there are so many, I would hope
that you consider withdrawing it and correcting the worst of them
before put this before the public. I note that it is privately
published (by you) so this would not be a problem for you.

[1] "Last one in teaches the programming for accountants course. You
don't know C? -- well you've got a couple of days before the course
starts!"

--
Ben.

[mstorkamp]

On Jul 24, 3:18 pm, "Malcolm McLean" <regniz...@btin ternet.comwrote :

The webpages for my new book are now up and running.

It may be I've actually leaned something new from the sample pages of
the book. To quote:

Note that strlen() is a "pure function". It performs no input or
output, and all the information it requires is contained in the
parameters. One of the features of C is that there is no distinction
between a "function", which calculates something, and a "procedure" ,
which performs IO.

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.
But I could be wrong.

[osmium]

<ms*******@yaho o.comwrote:

On Jul 24, 3:18 pm, "Malcolm McLean" <regniz...@btin ternet.comwrote :

>The webpages for my new book are now up and running.

It may be I've actually leaned something new from the sample pages of
the book. To quote:

Note that strlen() is a "pure function". It performs no input or
output, and all the information it requires is contained in the
parameters. One of the features of C is that there is no distinction
between a "function", which calculates something, and a "procedure" ,
which performs IO.

Now I had always had in my mind (going back to the days of learning
BASIC in the '70s) that the difference between a function and
procedure is that a function returns a value and a procedure doesn't.
But I could be wrong.

I had been holding an open mind on the book.

But I now join the people who think the book is awful. There is no
justification for the statement you quote; at best, it is terribly clumsy.
A procedure has side effects, a function does not, one *possible* side
effect is I/O. There are tons of other side effects which do not involve
I/O.

Yes, a pure function returns a value with no side effects.