[SGVLUG] Linux based web-server appliance

[Dustin Laurence]

On Fri, May 19, 2006 at 12:57:42PM -0700, David Lawyer wrote:
> [snip]
> Consider transmitting the number 0xABC.  If A is sent first, what does
> it mean?  10, 160, 2560, etc.?  In order to decipher it you need to
> scan to C and note that there are 3 hex digits.  But if C, the low order
> byte is sent first (little endian) then you know what it means: just C
> (12).  So little endian does make sense, even though we don't write
> number that way and thus have to scan to the end of a number before
> we know what the 1st digit represents.

Quite to the contrary, the provably optimal algorithm is inherently
big-endian, and the obvious little-endian algorithm is both expensive
and numerically unstable (when approximate floating-point numbers are
being represented--obviously this is irrelevant in the usual computer
case of exact integers, but as a physicist I felt it necessary to
stipulate good numerical behavior).  And it's interesting, if you're the
sort of person that finds these things interesting.

Re-constructing a number from its digits is the problem of evaluating a
polynomial, since a positional notation simply writes the coefficients
of the unique canonical form where they have values 0 <= a_i < b for the
known base b.  Since you say "transmitting" we have the constraints that
we want the evaluation algorithm to be serial, i.e. to be able to work
with one digit (bit, digit, word, byte, it doesn't matter for this
purpose since all of them can be viewed as digits in an appropriate
base) at a time without backing up.  Given that, we also want to need to
remember as little state as possible for simplicity and efficiency.  And
of course we want it to a good algorithm in the same sense as for any
polynomial evaluation, sequential or not: we require numerical stability
and computational efficiency.

By lucky chance the provably optimal general solution, Horner's rule, is
serializable and needs no state.  It is very familiar to those of us who
keep an RPN calculator with great fondness and live in terror of the day
it fails and we can't replace it.  It is written inside-out on paper,
but that is because that is how you denote big-digit-first evaluation.
It is also simple: start with the value of the first digit, and then for
each successive digit multiply the current value by the base (with fast
shift instructions unless a moron chose the base) and add the new digit.

You specified that it's nice not to know how many digits there are
beforehand--this means there is a terminator and this is the best case
for Horner's rule since the current value is the only required state.
The naive little-endian algorithm requires an additional piece of state
in this case, the current digit count.  It also requires O(n^2)
multiplications rather than the O(n) of Horner's rule.  With numbers
known to fit in a machine register this is irrelevant because the
multiplies are shifts and probably cost less than anything else (and
will be O(n) even for naive little-endian), but with arbitrarily large
numbers and bignum style representations this can really matter.

> they are stored in memory since the computer will always interpret
> them correctly.  But it does matter for the Internet which transmits
> bits in a serial manner, one at a time.

Hmm.  The internet does no such thing; it's too high in the stack to
know about bit transmission or, indeed, whether the transmission is
serial or parallel.  Do you mean ethernet?  It certainly cares about
byte-order, though, and specifies big-endian.

> > Even a Pentium or Pentium II can consume 200 W, so I'd have expected a
> > 486 to consume more.
> 
> There's a page that shows how, as speeds increased from the 486 to
> Pentium I to Pentium ... to Pentium IV, the power kept going up.  And
> within for example Pentium I's the power went up as speed increased.

Of course it does--for a given design the power consumed is proportional
to the clock speed (well, to zeroeth order).  And there is a
thermodynamic minimum cost which is also proportional to clock speed
because every copy that overwrites a value creates entropy, and the
faster the copies the faster the inherent power.

Anyway, nobody cared about CPU consumption in that era and so it wasn't
optimized.  If you take your favorite speed rating per watt you'll find
that a 486, or any x86 chip (at the very least before the Pentium-M), is
utterly blown away by chips engineered for low power.

> > Anyway, a NSLU2 apparently consumes less than 10 W
> 
> Amazing, but by itself it has no HD, serial port, cd, etc.  It does
> have USB where you can put USB HDs.

"All" you need for a webserver is a USB drive and ethernet.  Serial
port: pfui.  Well, until you break ssh....

> ...But it's tricky to take apart
> and has no screws to make disassembly easy.  On the Internet, it tells
> how to take it apart so as to install a serial port.  Think I'll stick
> with Pentium I :-) until NSLU2's are being given away.

If
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.sgvlug.net/pipermail/sgvlug/attachments/20060519/1c87efd6/attachment.bin