Re: new algorithm for wilcoxon signed-rank test

[John Darrington]

I think it's quite amazing!  I remember thinking when I first put that
routine into pspp, that there was some redundant calculations here,
but then thought that if there was a better way somebody would have
already come up with it ...

One small point about the implementation: It seems that array[0] is
never used.  So it count be one int smaller.

J'

     ----- Forwarded message from Ben Pfaff <address@hidden> -----
     
     To: Ben Pfaff <address@hidden>, John Darrington <address@hidden>,
        Michel Boaventura <address@hidden>,
        address@hidden
     From: Ben Pfaff <address@hidden>
     ...
     Actually, here's a solution that is even better.  A test program using it
     calculates (correctly) and prints *all* the values for 1 <= N <= 30, 1 <= 
W <=
     N*(N+1)/2, in under .2 seconds *total*.
     
     The runtime of this algorithm is O(N*W) and it uses O(W) space.
     
     
     int ranksum6(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 + 1);
       array[W] = 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 = 1; 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[1];
       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