Re: new algorithm for wilcoxon signed-rank test

[John Darrington]

On Thu, Feb 05, 2009 at 07:21:27AM -0800, Ben Pfaff wrote:
     John Darrington <address@hidden> writes:
     
     > One small point about the implementation: It seems that array[0] is
     > never used.  So it count be one int smaller.
     
     It's true, but then all the array references would have to be of
     the form "array[x - 1]".  I figured that the simplicity of
     reference was worth one "int" worth of storage.


It's your call, of course.  But this version is algebraically
identical, and requires only one such index (array[W] --> array[W-1]).

int
ranksum7 (int N, int W)
{
  int *array;
  int max;
  int total;

  assert (N >= 0);
  if (N == 0)
    return 0;
  else if (W <= 0)
    return 1 << N;
  else if (W > N * (N + 1) / 2)
    return 0;
  else if (N == 1)
    return 1;

  array = calloc (sizeof *array, W);
  array[W-1] = 1;

  max = W;
  total = 0;
  for (; N > 1; N--)
    {
      int max_sum = N * (N + 1) / 2;
      int i;

      if (max_sum < max)
        max = max_sum;

      for (i = 0; i < max; i++)
          if (array[i] != 0)
            {
              int new_W = i - N ;
              if (new_W < 0)
                total += array[i] * (1 << (N - 1));
              else
                array[new_W] += array[i];
            }
    }
  total += array[0];
  free (array);
  return total;
}



-- 
PGP Public key ID: 1024D/2DE827B3 
fingerprint = 8797 A26D 0854 2EAB 0285  A290 8A67 719C 2DE8 27B3
See http://pgp.mit.edu or any PGP keyserver for public key.

signature.asc
Description: Digital signature