Re: how to rotate an array

From: Nikolai Borissov (n.borissov_at_sympatico.ca)
Date: 03/21/04 

Date: Sun, 21 Mar 2004 10:24:13 -0500

Siemel Naran wrote:

> "Nikolai Borissov" <date4cpp@sympatico.ca> wrote in message
> news:1Fz6c.30229$E71.1829457@news20.bellglobal.com...
>
> > int array_rotation(char* arr, int arr_size, int rot)
> > {
> > // Parameter check
> > if(!(arr&&arr_size>0))
> > return -1;
> >
> > // Normalization of rotation value
> > rot = rot%arr_size;
> > rot = rot<0?rot+arr_size:rot;
> >
> > // Rotation
> > if(rot!=0)
> > { int gcd; // greatest common divisor
> > { int n=arr_size,m=rot;
> > while((gcd=n%m)&&(n=m%gcd)&&(m=gcd%n));
> > gcd = gcd ? n ? n : gcd : m;
> > }
> > int mvs = arr_size/gcd;
> > while(gcd--)
> > { int ind = gcd;
> > char c = arr[ind];
> > int i = mvs;
> > while(--i) { int ind_prev = ind;
> > if( (ind+=rot) >= arr_size )
> > ind-=arr_size;
> > arr[ind_prev] = arr[ind];
> > }
> > arr[ind] = c;
> > }
> > }
> > return 0;
> > }
>
> What's going on with the gcd part? Also, without parenthesis it's hard to
> read
>
> > gcd = gcd ? n ? n : gcd : m;

This is just an implementation of well-known Euclidean algorithm for
obtaining a greatest common divisor.
You can easily find the explanation of Euclidean algorithm on the Internet.
Simply put, when we have 2 integer positive numbers _a_ and _b_, we should
perform the series of the followng calculations:

a%b -> c, b%c -> a, c%a -> b, a%b -> c, and so on

The chain ends when the result of division is 0, with the denominator of
this division being the greatest common divisor of a,b or gcd(a,b). For
example, if the result computed into _b_ is 0 then current value of _a_ is a
gcd of original a,b values.
In the program I use while() statement to organize this chain of
calculations. According to while() logic this chain breaks as soon as the
result of any division is 0. After that all we need to do is to examine
values for 0 and pick a gcd from the related variable:
    gcd = gcd ? n ? n : gcd : m; <==> gcd ? (n ? n : gcd ) : m

>
> What is the running time of the above algorithm? Your algorithm looks
> correct for arr_size is 0 or 1.

For 0 value gcd does not make sense. Besides, arr_size here cannot be 0,
because is't a parameter mistake.
Running time is absolutely negligible. Euclidean algorithm is very fast and
it's not a issue at all.

>
> Here's my attempt. Consider ABCDEF which have to shift right two notches
to
> EFABCD. Start with ABCDEF. It has length 6. Start at array[0]. Copy
> array[0] into array[2] to yield ABADEF. Copy the old character at
array[2]
> to array[4] to yield ABADCF. Copy the old character at array[4] to
> array[6], but array[6] should be array[0] to yield EBADCF. We're back
where
> we started, so we're done with this series of 0-2-4. Now go on to series
> 1-3-5 and repeat. Copy array[1] to array[3] to yield EBABCF. Copy the
old
> character at array[3] to array[5] to yield EBABCD. Copy the old character
> at array[5] to array[7] which is array[1] to yield EFABCD. We're back
where
> we started and completed both series and performed 6 copies, so we're
done.
> It may not be the most efficient algorithm.
>
> There will be an outer loop that loops through the number of series, in
our
> example 2 series 0-2-4-0 and 1-3-5-1. There will be an inner loop that
> loops through the number of elements in the series, so for the 1st series
> 0-2-4-0 it loops through 0 then 2 then 4 then 0.
>
> Algorithmically, the outer loop 'series' is from [0, infinity); and the
> inner loop 'indx' starts at 'series', then increments 'indx' by 'shift'
> until we reach the 'series'. So for series=0 we'll have in the inner loop
> indx=0,2,4,0 and it copies char[0] to char[2], char[2] to char[4], char[4]
> to char[6 or 0] for a total of 3 copies. As we have not performed size=6
> copies we still have some more work to do. Now increment series and
repeat.
> So for series=1 we'll have in the inner loop indx=1,3,5,1 and it copies
> char[1] to char[3], char[3] to char[5], char[5] to char[7 or 1] for a
total
> of 3 copies. As we have performed size=6 copies we're all done. Variable
> 'j' counts the number of copies performed, so when 'j' equals 'size' we're
> done.
>
> Furthermore, in the inner loop where for example we copy char[1] to
char[3],
> char[3] to char[5], char[5] to char[7 or 1] there is a danger that we run
> past the bounds of the array as in char[7] whereas the array has length 6.
> We can solve this by guarding each increment of 'indx' with modulo, so
> instead of indx+=shift we have to say indx=(indx+shift)%size, as you do
> above. But for the first few copies like char[1] to char[3], char[3] to
> char[5], we don't need the check, and index+=shift will suffice, and could
> yield better performance.

About performance, I'm not sure that it's worth the effort in this case.
And, actually, you need it not for performance, rather to be able to check
if 'series' is complete when we wrap.

>
> So as an optimization we pre-compute the number of copies 'within' we can
do
> without running past the end of the array. Consider the series 1-3-5-1
> where series=1. We start at indx=1, and after 'within' increments pass
the
> end of the array, so indx+within*shift>=size, for which
> within>=(size-indx)/shift. In our example, for indx=1 and size=6 and
> shift=2, within>=2.5; which means we can only perform 2 copies before
> running past the end of the array. For the series 0-2-4-0 for which
> series=0 things are more complicated. We have within>=3, and note that
> within is exactly equal to 3, which means 3 copies from char[0] to
char[2],
> char[2] to char[4], char[4] to char[6]. But the last copy from char[4] to
> char[6] runs past the end of the array too. So we ought to perform only 2
> copies. In other words, if 'within' has no fractional part then it means
> we'll eventually hit the one-past-end element of the array and so we
should
> decrease 'within' by 1.
>
> I ran a few tests, but there may be sideline test cases for which my
> algorithm fails.

You idea is clear and program looks fine.
About performance again. I'm sure that with precalculated gcd the
performance will be better in any case. GCD is nothing more than the number
of 'series' to perform. So we know exactly number of series, as well as
number of steps for each series and can use these numbers in loops without
any additional checks. In your case, when number of series in not known, you
have to increment special *j* variable with every step, and then check it to
determine the end of loop.

Nikolai Borissov

>
>
> #if defined(__BORLANDC__)
> #include <vcl.h>
> #endif
>
> #include <cstdio>
> #include <iterator>
>
> template <class Iter>
> void rotate(
> const Iter begin,
> const Iter end,
> typename std::iterator_traits<Iter>::difference_type shift
> )
> {
> using std::swap;
>
> typedef typename std::iterator_traits<Iter>::difference_type Int ;
> typedef typename std::iterator_traits<Iter>::value_type Value;
>
> const Int size = end-begin;
> if (!size) return;
> shift %= size;
> if (!shift) return;
> if (shift<0) shift = size+shift;
>
> Int series = 0;
> Int j = 0;
> Iter seriesbegin = begin;
>
> while (true)
> {
> Iter iter = seriesbegin;
> Int indx = series;
>
> Value value = *iter;
>
> while (true)
> {
> const Int diff = size-indx;
> const bool exact = bool(!(diff%shift));
> const Int within = diff/shift;
> for (Int k=exact; k<within; ++k)
> {
> iter += shift;
> indx += shift;
> swap(*iter, value);
> ++j;
> }
> indx = (indx+shift)%size;
> iter = begin+indx;
> swap(*iter, value);
> ++j;
> if (indx == series) break;
> }
>
> if (j==size) break;
> ++series;
> ++seriesbegin;
> }
> }
>
>
>
> int main(int argc, char * * argv)
> {
> using std::printf;
> const char originalarray[] = "ABCDEF";
> const int length = sizeof(originalarray)-1;
> for (int r=-length; r<=length*2; ++r)
> {
> char array[length+1];
> std::strcpy(array, originalarray);
> printf("%s\n", array);
> printf("rotate=%d\n", r);
> rotate(array, array+length, r);
> printf("%s\n", array);
> printf("\n");
> }
> }
>
>
>

Relevant Pages

  • Re: I was right, surrogate factoring proof
    ... >> factor 9 via gcd. ... > There's a proof that the method does not work for primes squared. ... To prove that, mess with the algorithm. ... No, I'm not estimating anything. ...
    (sci.crypt)
  • Re: GCD(0,0)
    ... >>>You're justifying an exception to the name GCD by pointing out that 0 ... >>>my point of view the G in GCD says it all. ... But the definition that works in a PID ... Euclidean algorithm, which means that it has a size function ...
    (sci.math)
  • Re: euclidean algorithm over Q[i]
    ... Z, the Gaussian integers, may be what you remember seeing. ... written a pretty simplistic algorithm in java that carries out polynomial ... GCD, just using polynomial long division and the euclidean algorithm. ... GCD's of univariate polynomials over Q? ...
    (sci.math.symbolic)
  • Re: euclidean algorithm over Q[i]
    ... apart from the final value for the gcd. ... Are you using the Euclidean algorithm to compute ... GCD's of univariate polynomials over Q? ... advantage to using 'pseudo division' to avoid large ...
    (sci.math.symbolic)
  • Re: Math question [polynomial division]
    ... >At the end of the algorithm I've multiplied P by G to form the quotient. ... when computing the gcd I use the characteristic ... you are operating over a finite field and therefore the result ...
    (sci.crypt)