#include <stdio.h>
#include <math.h>
#include "util.h"

int K;

unsigned int hist[32768];

# define MAXHIST 1000000

# define S(n) s##n
# define D(n) unsigned short S##n[n]
# define I(n) { int i; for (i = 0; i < n; i++) S##n[i] = 0; }
# define H(n) { int i; double q; clear_hist(); \
                for (i = 0; i < n; i++) { \
		    unsigned short k = S##n[i]; hist[k] += (hist[k] < MAXHIST) ? 1 : 0;} \
                q = report_hist(n); qsum += q; if (q > qmax) qmax = q; }
# define U(n)  S##n[h % n]++

# define DO(M) \
M(255); M(257); M(1023); M(1024); M(1025); M(4095); M(4096); M(4097); M(16383); M(16384); M(16385); \
M(11); M(13); M(29); M(37); M(59); M(61); M(101); M(103); M(197); M(199); M(419); M(421); M(809); \
M(811); M(1607); M(1609); M(3251); M(3253); M(6449); M(6451); M(12821); M(12823)

DO(D);

clear_stats() 
{
  DO(I);
}

double report_hist(n)
{
  int i;
  double sum = 0;
  double sumsquared = 0;
  int max = 0;

  for (i = 0; i < 32768; i++) {
    unsigned int hi = hist[i];
    sum = sum + (double) hi * i;
    /* if (hi != 0) printf("i = %d, hi = %d, sum = %7.2f\n", i, hi, sum); */
    sumsquared += (double)i*i*hi;
    if (hi != 0) max = i;
  }
  
  {
    double avg = sum/n;
    double rms = sqrt(sumsquared / n);
    double quality = rms/avg - 1.0;

    printf("Mod%6d yields max =%6d, rms =%8.2f, avg =%8.2f, quality =%7.3f\n",
	   n, max,
	   rms,
	   avg,
	   quality);
    return quality;
  }

}

clear_hist()
{
  int i;
  for (i = 0; i < 32768; i++)
    hist[i] = 0;
}

main()
{
  int rc = scanf("%d", &K);

  while (rc == 1)
    {
      test_a_hash();
      rc = scanf("%d", &K);
    }

}

UINT   local_hash(s, n) unsigned char * s; int n; {
       UINT i = 0;
       UINT j = 0;
       for (j = 0; j < n; j++) {
	 i = i * K + s[j];
       }
       return i;
}

test_a_hash()
{
  int rc;
  FILE * fd = fopen("words", "r");
  char s[256];
  double qsum = 0.0, qmax = 0.0;

  clear_stats();

  rc = fscanf(fd, " %s", s+1);
  while (rc == 1)
    {
      int l = 1 + strlen(s+1);
      unsigned int h = local_hash(s+1, l-1);
      DO(U);
      s[0] = 'w'; h = local_hash(s,l); DO(U);
      s[0] = 'x'; h = local_hash(s,l); DO(U);
      s[0] = 'y'; h = local_hash(s,l); DO(U);
      s[0] = 'z'; h = local_hash(s,l); DO(U);
      s[0] = 'W'; h = local_hash(s,l); DO(U);
      s[0] = 'X'; h = local_hash(s,l); DO(U);
      s[0] = 'Y'; h = local_hash(s,l); DO(U);
      s[0] = 'Z'; h = local_hash(s,l); DO(U);
      rc = fscanf(fd, " %s", s+1);
    }
  fclose(fd);
  printf("For hash based on multiplication by %d:\n", K);
  DO(H);
  printf("Quality sum is %7.3f, max is %7.3f\n\n", qsum, qmax);
}

hash1(s) unsigned char * s; {
  unsigned int i = 0;
  while (*s != 0) {
    register unsigned int Rb, Ra = i;

    /* Rb = i * 270566475 */
    Rb = Ra + (Ra << 4); /* step 4, shift 4 */
    Rb = (Rb << 4) - Ra; /* step 5, shift 4 */
    Rb = (Rb << 6) + Rb; /* step 1, shift 6 */
    Rb = Ra + (Rb << 8); /* step 4, shift 8 */
    Rb = Ra + (Rb << 2); /* step 4, shift 2 */
    Rb = (Rb << 4) - Rb; /* step 2, shift 4 */
    
    i = Rb + *s++;
  }
  return i;
}

hash2(s) unsigned char * s; {
  unsigned int i = 0;
  while (*s != 0) {
    register unsigned int Rb, Ra = i;

    /* Rb = i * 1431655765 */
    Rb = Ra + (Ra << 2); /* step 4, shift 2 */
    Rb = (Rb << 4) + Rb; /* step 1, shift 4 */
    Rb = (Rb << 8) + Rb; /* step 1, shift 8 */
    Rb = (Rb << 16) + Rb; /* step 1, shift 16 */
    i = Rb + *s++;
  }
  return i;
}

hash3(s) unsigned char * s; {
  unsigned int i = 0;
  while (*s != 0) {
    register unsigned int Rb, Ra = i;

    Rb = Ra * 135283237;

    i = Rb + *s++;
  }
  return i;
}