Path: utzoo!mnetor!uunet!husc6!cmcl2!brl-adm!umd5!purdue!i.cc.purdue.edu!j.cc.purdue.edu!pur-ee!uiucdcs!uiucdcsp!gillies
From: gillies@uiucdcsp.cs.uiuc.edu
Newsgroups: comp.sys.mac
Subject: Re: image rotation
Message-ID: <76000092@uiucdcsp>
Date: 21 Dec 87 18:07:00 GMT
References: <602@analog.UUCP>
Lines: 44
Nf-ID: #R:analog.UUCP:602:uiucdcsp:76000092:000:2111
Nf-From: uiucdcsp.cs.uiuc.edu!gillies    Dec 21 12:07:00 1987


In article <>, kim@analog.UUCP writes:
> I think you are the one with the fallacious argument.  Factors like
>16 or log(some constant) are irrelevant for purposes of analyzing
> CPU time requirements.
>
> My original analysis was sketchy, but here it is in a slightly expanded
> form:
>
>	Suppose that I wish to rotate an N X N bitmap.  If I do it the
> brute-force way, it will take N*N operations (where an operation is
> defined as a memory transfer with a masking operation thrown in somewhere (to
> get at the right bit of a particular byte.  Ok, have it your way--to get at
> the right bit of a long word).
>.....

When you analyze an algorithm whose running time is dominated by the
size of its output (n*n in the rotation algorithm), it is appropriate
to do a low-level Knuth-type analysis, or at least attempt to do it.

There are many ways to speed up a "hopelessly slow" bit algorithms by
exploiting the binary parallelism 16, 32, or 64-bit boolean and
arithmetic operations.  For instance, you can count the bits in a
32-bit computer word in 5 iterations of one loop (O(log(wordsize)) time).

Obviously, ANY algorithm that rotates an n*n bitmap must take O(n*n)
time to do its output, unless you use a degenerate representation
(like storing all 4 rotations of a bitmap, and just returning a
pointer in O(1) time).

You wanted some reasons why Atkinson's rotation algorithm might run so
fast.  You referred to a particular algorithm on a particular machine
with a particular screen size.  And things are not as it seems: Using
some elementary analysis for the particular case, it looks like the
BITBLT algorithm is still a win over the brute force method.

Of course, as another notewriter pointed out, you can get even more clever
in doing the rotation by breaking the screen into 8*8 blocks.  This
method *still* does not "sound" like its asymptotic performance equals
the dumb brute force algorithm, but I bet it runs faster on any particular
commercial processor you choose for a benchmark.  Constants count.

Don Gillies {ihnp4!uiucdcs!gillies} U of Illinois
            {gillies@p.cs.uiuc.edu}