Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #9872

Re: My latest magnum opus!

Show all headers | View raw

On Thu, 01 Sep 2011 21:13:32 -0400, Eric Sosman
<esosman@ieee-dot-org.invalid> wrote:

>On 9/1/2011 7:24 PM, pete wrote:
>> /* BEGIN block_swap_test.c */
>> [...]
>
>     Jon Bentley tackled this problem in one of his "Programming
>Pearls" columns in CACM, years and years ago.  IIRC, he reported
>that he had seen manymanymany attempts to solve it "efficiently"
>with clever analysis of which block was the larger, and by how much,
>and so on and so forth.  He also reported that every such solution
>he'd seen was either bug-ridden or actually slower than
>
>	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.  It turns out that if you treat the swap
and a permutation and process each cycle separately you can reduce the
number of data moves and the number of loop tests each to n+d where d
is the gcd of the lengths of the two segments.  In terms of primitive
operations that is the best that can be done.

It was a fun exercise, but I never went to the trouble of coding it up
and timing it.  I assume it would be slower than the reversal code.
The URL is http://home.tiac.net/~cri/2004/frotate.html if anyone wants
to give it a try.

 

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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