From: Martin Str|mberg <ams AT ludd DOT luth DOT se>
Message-Id: <200007131729.TAA29926@father.ludd.luth.se>
Subject: Re: Quicker erand48 patch
In-Reply-To: <Pine.SUN.3.91.1000713092323.12595B-100000@is> from Eli Zaretskii at "Jul 13, 2000 09:24:00 am"
To: djgpp-workers AT delorie DOT com
Date: Thu, 13 Jul 2000 19:29:43 +0200 (MET DST)
X-Mailer: ELM [version 2.4ME+ PL54 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Reply-To: djgpp-workers AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: djgpp-workers AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk

According to Eli Zaretskii:
> Please use "diff -c" or "diff -u".  Without the switches, the diffs
> are very hard to read, and applying them is much more prone to
> failures (due to other changes that shift lines).

Yes, sorry about that, but I was confused because "cvs diff -ruN"
didn't work.

> More to the point, did you time the two versions, and if so, what were
> the results?

I sure did. Otherwise the patch wouldn't have been made.

Previos version took ~115 s, new version ~35 s on my PII
450MHz. Strangely if I changed 
"  ll = (signed long long)( state[0]
                          | ( (unsigned long)state[1] ) << 16
                          | ( (unsigned long long)state[2] ) << 32 );"
to
"  ll = (signed long long)( state[0]
                          | ( (unsigned long long)state[1] ) << 16
                          | ( (unsigned long long)state[2] ) << 32 );"

some 0.5 s was shaved off further. But as I thought (with an very
unassembly-aware mind) the assembly looked more efficient with the
posted patch and it didn't make sense and half a second (on 1UL<<26
calls) wasn't worth it so I rejected that one.

Note that the test program doesn't only use drand48() so the
improvement to drand48() is better than (115-35)/115.


Right,

								MartinS

Test program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define NTRY (1UL<<26)
#define RANGE 32
#define EXPECTED ((double)NTRY/RANGE)

int main(void)
{
  static unsigned long count[RANGE], count2[RANGE];
  unsigned long i;
  int j;
  double s, s2, d, t, t2;

  srand(time(NULL));
  srand48(time(NULL));
  for (i = 0; i < NTRY; i++)
  {
    count[(unsigned)(drand48()*RANGE)]++; /* drand48-Method */
    count2[(unsigned)((double)rand()*RANGE/(RAND_MAX+1.0))]++; /* FAQ
*/
  }
  printf("Expecting on average E=%f\n", EXPECTED);
  printf("  r fnd(drand48)  (E-f)^2/E    sum fnd(div)  (E-f)^2/E
 sum\n");
  s = s2 = 0.0;
  for (j=0; j<RANGE; j++)
  {
    d = EXPECTED - count[j];
    s += (t = d*d/EXPECTED);
    d = EXPECTED - count2[j];
    s2 += (t2 = d*d/EXPECTED);
    printf("%3d %8lu %10f %10f %8lu %10f %10f\n",
           j, count[j], t, s, count2[j], t2, s2);
  }
  printf("chi^2(drand48) = %f chi^2(div) = %f expecting %.0f +/- %.2f mostly\n",
         s, s2, RANGE-1.0, 2.0*sqrt(RANGE-1.0));
  return 0;
}