This article was posted to the Usenet group alt.hackers in
1995; any technical information is probably outdated.
Parent
Re: Topten help!
Article: 8872 of alt.hackers From: 3ah21@qlink.queensu.ca (Hammond Andrew) Newsgroups: alt.hackers Subject: Re: Topten help! Date: 17 Oct 1995 18:18:03 GMT Organization: Queen's University, Kingston Lines: 100 Approved: rich.meister@attitude.org Message-ID: 460s0r$61m@knot.queensu.ca NNTP-Posting-Host: qlink.queensu.ca X-Newsreader: TIN [version 1.2 PL2] Status: RO
Christopher Thompson (thompson@scapa.cs.ualberta.ca) thoughtfully declared:
: Okay, folks, I've been assigned the unenviable task of coming up with
: a topten list for some t-shirts that the undergrad compsci association
: is going to make. I've searched *all over* the web and various
: newsgroups looking for such a beast. I know I *used* to have a couple
: of lists but I must have deleted them.
: Anyway, if anyone out there has a (humorous) topten (or top 100) list
: of reasons to be in CompSci, *please* pass them along to me. I'd really
: appreciate it. The list was due in last Friday [sigh].
Have you tried ARCHIE and VERONICA yet? What about one of the web
searcher sites?
: ObHack: [Apologies, it's kind of lame] A friend of mine was trying to
: learn cgi stuff for his web page. He decided to steal a friend's
: mail-to-me cgi script. Not a problem. Except that it was marked
: world-readable but *not* group readable. We tried every method we could
: to read this thing (including a netscape ftp). No go.
: Luckily, I had an account that wasn't in the same group. Not a problem.
That's not a hack! Or, if it is, then it's really pushing the no hack is
too small boundary. You could have just done an anonymous ftp, no?
: Acck. That really was lame. Okay, here's another one.
: ObHack2: My alarm clock keeps on failing. It's a real pain. It either
: doesn't go off or, more likely, goes off hours late. I missed tons of
: classes and I needed to do something about it.
: I wrote a small alarm clock program in C. Really small. All it does
: is to check the time against the time I've set it to go off. However,
: if all it did was that, I'd probably learn how to turn it off in my
: sleep (!). So I have to answer a simple arithmetic question (random)
: to shut off the alarm. That leaves the reset button.
What's wrong with tcsh's sched or cron? Or don't you run UNIX
on your home box? If you're at all CS oriented, you might want to
consider dedicating a little HD space to set it up.
: Now, I'm a very different person when I wake up. I don't become
: conscious for about five minutes. I know I'd just hit the reset or the
: power button. So when the alarm goes off, it creates a temporary file
: and outputs some junk to it. Now, if I was to turn off the computer,
: this would leave me with lost clusters. Easily fixable, of course, but
: my subconscious won't allow me to shut off the power. It won't let me
: "damage" the computer.
Well, if you're running a real OS, say, Linux on your machine then this is
the case all the time. ;)
: The result? Well, I made my psychology class this morning for the
: first time in two weeks.
Now I need a hack. Me and my (symbolic) mouth. How about
How about a nice little recursive base 2 multiplication algorithm?
Since PEP-5 assembly (PEP-5 is a PDP-5 simulator which they use to teach
assembly language with here at Queen's) doesn't have a multiplication
instruction. So, in order to do any kind of multiplication, you need to
use addition instead. Well, being the geek that I am, I decided that
this just wasn't fast enough for me. So, I thought to myself: If I just
use a bitshift, then I can effectivly multiply by 2 or divide by 2.
ANDing to a 0000 0000 0000 0001 will return the same result as modulus
2. Hmmm. Furthermore, these operations are pretty cheap.
I'll write the alg in C, since it's more readable and pretty close to
assembly anyhow.
int Multiply (int A, int B) /* A x B */
/* This function recursivly calculates A x B using only addition,
bitshifts, and the AND function. For maximum efficiency, be sure that
A < B. It works by dividing by A by two, calculating A/2 x B and
then doubling the result and adding B if A modulo B = 1.
{
int Part; /* Accumulator variable */
if (A == 2) return (B<<1); /* Bitshift left 1 doubles the number */
if (A == 1) return (B); /* simple recursive case #2 */
else{ /* recursive case */
Part = Multiply ((A>>1), B); /* divide A by two and multiply B */
Part<<1 /* bitshift left 1 doubles the number */
if (A & 0x0001) Part += B /* gets remainder of A / B */
return Part;
};
}
I probably have munged up the syntax, and I might have screwed up WRT
sideffects in the recursive call. I'm doing this from memory and my C is
still somewhat shakey. Practice makes perfect though. Anyhow, when this
runs right, it takes on the order of log(base 2) A calculations as
opposed to A calculations required by a simple iterative solution.
Anyhow, this one is neater.
--
Andrew Hammond 3AH21@QLINK.QUEENSU.CA
"To know recursion, you must first know recursion."
-unknown
Parent