Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | cri@tiac.net (Richard Harter) |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: My latest magnum opus! |
| Date | 2011-09-02 13:39 +0000 |
| Message-ID | <4e60da12.934177667@text.giganews.com> (permalink) |
| References | <4E60142A.575D@mindspring.com> <j3palv$5tj$1@dont-email.me> <4e60666e.904572982@text.giganews.com> <j3qhpi$mdg$1@dont-email.me> |
On Fri, 02 Sep 2011 08:21:35 -0400, Eric Sosman <esosman@ieee-dot-org.invalid> wrote: >On 9/2/2011 1:39 AM, Richard Harter wrote: >> On Thu, 01 Sep 2011 21:13:32 -0400, Eric Sosman >> <esosman@ieee-dot-org.invalid> wrote: >> [...] >>> Given an array A...FR...Z, to arrive at R...ZA...F: >>> Reverse the A...F sequence byte for byte >>> Reverse the R...Z sequence byte for byte >>> Reverse the entire array byte for byte >>> >>> I have not examined your code closely -- in truth, I have not >>> even examined it cursorily. The very fact that it's longer than >>> Bentley's solution tells me it's almost certainly inferior; Bentley's >>> is certainly easier to analyze for correctness. >> >> Back in 2004 I did an analysis. Let n be the number of bytes. Then >> the reversal trick requires 3n data moves and 3n/u loop tests where u >> is the loop unrolling factor. > > Where do you get "3?" Looks like "2" from here. (Consider what >happens to one particular byte, Q: One of the partial passes moves >it from its original location to a temporary home, the other partial >pass never even looks at it, and the full pass moves it to its final >spot. When all is done, Q has moved twice, not three times.) In a reversal you have to swap bytes which requires moving one of them to a temporary location. Reversing "ab" is move a from old loc to temp loc move b to a's old loc move a from temp to b's old loc
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 19:24 -0400
Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 21:13 -0400
Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:29 -0400
Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:58 -0400
Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:41 -0400
Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:53 -0400
Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 05:39 +0000
Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 02:59 -0400
Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 08:21 -0400
Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 13:39 +0000
Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 20:53 -0400
Re: My latest magnum opus! James Dow Allen <jdallen2000@yahoo.com> - 2011-09-03 03:18 -0700
Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-03 17:16 +0000
Re: My latest magnum opus! Andrey Tarasevich <andreytarasevich@hotmail.com> - 2011-09-02 09:21 -0700
Re: My latest magnum opus! ImpalerCore <jadill33@gmail.com> - 2011-09-06 06:51 -0700
Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-06 18:36 -0400
Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-06 21:04 -0400
csiph-web