PSPP-BUG: [bug #25466] Compile problem on wilcoxon.c

[Ben Pfaff]

Follow-up Comment #4, bug #25466 (project pspp):

>Unless anyone has any better ideas, I suggest that we just compile
>out support for the TIMER subcommand on platforms which don't have
>a SIGALRM.

The real problem, I think, is that LevelOfSignificanceWXMPSR is astoundingly
inefficient.  The core of it is essentially this:


int ranksum1(int N, unsigned long W)
{
  unsigned long NumberOfPossibilities = 1 << N;
  int CountLarger = 0;
  unsigned long i;

  /* Generate all distributions of sign over ranks as bit-patterns (i). */
  for(i=0; i < NumberOfPossibilities; ++i)
  {
    unsigned long RankSum = 0;
    int j;

    /*
       Shift "sign" bits out of i to determine the Sum of Ranks (j).
    */
    for(j=0; j < N; ++j)
    {
      if((i >> j) & 1)RankSum += j + 1;
    };
    /*
    * Count the number of "samples" that have a Sum of Ranks larger than
    * or equal to the one found (i.e., >= W).
    */
    if(RankSum >= W)++CountLarger;
  }
  return CountLarger;
}


But that can be reimplemented in a much more efficient fashion as:


int ranksum2(int N, int W)
{
  if (N > 0 && W > 0)
    {
      unsigned long int total = 0;
      while (N >= W && N > 0)
        total += 1 << --N;
      return total + ranksum2(N - 1, W - N) + ranksum2(N - 1, W);
    }
  else
    return 0;
}


For N=30, W=120 ranksum1() takes 6 minutes 9 seconds on my system, ranksum2()
takes 0.4 seconds.  And they both return the same result.

(Am I missing anything here?  This seems too easy.)

With dynamic programming I think I can do even better; there's a lot of
redundant calculation in ranksum2().  But that's still a big improvement, and
good enough to get rid of the timer entirely I think.

I'm attaching a test program that can be used to verify that both functions
return the same result and to benchmark.

(file #17392)
    _______________________________________________________

Additional Item Attachment:

File name: ranksum.c                      Size:1 KB


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?25466>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/