Subject: Why Assembler is perfect for Algorithms book

From: Chen Shapira <[email-masked]>
Date: Mon, 18 Nov 2002 19:10:43 +0200

> No, talk to them about their work, bug-fixes to what they do etc. Tell
> Linus he should hit himself with a bus, so to speak, tell Don 
> Knuth why I
> think Assembler is awful for an algorithms book, etc. If I am 
> introduced
> to them that is.

Since I believe that Knuths decision to use Assembler in his book was the
smartest CS decision I saw, I'd like to defend the position.

1. Knuth's book is not an introductory book of the field. Cormen, Ullman and
others do that job well enough. Knuth's book is a deep review of the field.
This means that ease of read, and friendliness should not be the highest
ranking considerations.

2. Talking about O(n) run-times, some people have problems defining a "basic
operation", one that can be counted as O(1). A friend of mine made the
mistake of assuming that array copy is O(1), some people consider power(x,y)
to be O(1), others don't.
Using assembly clearly defines the basic operations - everything that the
CPU does in one command.

3. Using assembly allowed Knuth to make interesting observations. When I
studied Data Structures, we had a joke about "Knuth Numbers". The lecturer
often mentioned that for very small datasets bubble-sort is faster than
quicksort, and he said that Knuth recommends to use bubble sort on arrays
with 9 elements or less (IIRC). To arrive at that number, you must use
assembly, since every constant counts.
He also gives good boundry numbers for hash tables and such.

---

From: Muli Ben-Yehuda <[email-masked]>
Date: Mon, 18 Nov 2002 19:49:00 +0200

> Using assembly clearly defines the basic operations - everything that the

Ah, but no too commands are created equal. an integer add and a
floating point div, will not take the same ammount of time. If I
remember correctly, most asm commands are actually implemented in
terms of "micro code", and are actually several micro code
instructions each. I'm sure someone will correct me if I'm wrong.

Anyway, while your reasons are sound, I believe that the best reason
to use a make believe language is to keep the books relevant
regardless of the latest fad current computer language or
architecture. Imagine TAOCP in Java, TAOCP in CPP, TAOCP in
JavaScript, TAOCP.NET. 
-- 
Muli Ben-Yehuda				    http://www.mulix.org/
[email-masked]:~$ sctrace strace /bin/foo  http://syscalltrack.sf.net/
Quis custodes ipsos custodiet?

---

From: Shlomi Fish <[email-masked]>
Date: Tue, 19 Nov 2002 09:10:19 +0200 (IST)

> instructions each. I'm sure someone will correct me if I'm wrong.

Well, when we built the MAYBE as part of the "Logic Design" course, we had
a predefined ALU (Arithmetical and Logical Unit) that did most of the job
for us. But I think you can calclulate the complexities of various
operations based on Al-Huarizmi's Algorithms:

(n is the number of bits)

1. Increment/Decrement : O(log(n)).
2. Addition O(log(n)^2))
3. Shift: O(log (n))

And so on. For floating points it is a bit trickier because of the mantisa
and exponent and stuff but still possible.

I still think Knuth should have given the algorithms in Pseudo-code so
people can understand and then expand them into Assembler.

Oh and I'll spend the time thinking about profound things to say.

Regards,

	Shlomi Fish

> [email-masked]:~$ sctrace strace /bin/foohttp://syscalltrack.sf.net/
> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"