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

Groups > comp.lang.c > #9873

Re: My latest magnum opus!

Show all headers | View raw

Richard Harter wrote:
> 
> 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.

The way that I did it, was to move the bigger half
to its final location. If the bigsize % the smallsize == 0,
then there was no problem, but if not, 
then the smaller half would be out of order 
after the bigger half was moved.
So, instead I moved the bigger half minus (bigsize % smallsize) bytes.
That results in most of the bigger half being in its final place,
with the remnants of the bigger half becoming the new smaller half.
That gets repeated until eventually (bigsize % smallsize == 0)
and then it's done.

-- 
pete

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