Subject: Re: Java is really convenient. Re: Sun thinks about switching Java to S-expression syntax: Lava
From: (Rob Warnock)
Date: 1999/02/21
Newsgroups: comp.lang.lisp
Message-ID: <7ap587$>
Johan Kullstam  <> wrote:
| (Rob Warnock) writes:
| > to multiply, look up the "logs" of the numbers, > add them mod 256...
| the logtable is good.  however, you need to mod by 255 since GF(256)
| without 0 under multiplication is isomorphic to Z_255 and not Z_256.

Oops! Yes, of course! (*blush*)

And you need to special-case check if either of the args are zero, too,
since that log won't be in the (presumably finite) table.  ;-}

| fastest to take logs, add them, subtract 255 if the sum exceeds 254...

Yes, *lots* faster than "mod 255".

| for multiplying many non-zero elements of GF(256), take log on the lot
| (gotta love mapcar!), add them, run a while-loop subtraction of 255
| until you get something in the range 0-254 then antilog.

And this will, of course, cost *at most* one subtraction per element
being multiplied (less one).


p.s. Which reminds me of the way people often do IP checksums
(which are a 16-bit *1's*-complement sum) on 2's-complement machines...
Accumulate 16-bit elements into a 32-bit sum (which accumulates
into the upper half all of the "end-around-carries" that would
have occured with a 16-bit 1's-complement adder), then:

	  while (> sum 65535)
	  do (setf sum (+ (ldb (byte 16 16) sum) (ldb (byte 16 0) sum))))

or in C [assuming "u_int32_t sum"]:

	while (sum > 65535)
	  sum = (sum >> 16) + (sum & 0xFFFF);

This carry-normalization can at *most* loop twice.

[Warning: Only works for packets < 128 KB in length (but all IP pkts are).]

Rob Warnock, 8L-855
Applied Networking
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA