math/mpreduce.h: Missing include files.

[u/mdw/catacomb] / rand / fibrand.h

/* -*-c-*-
 *
 * Fibonacci generator
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Notes on the Fibonacci generator ----------------------------------*
 *
 * The generator was originally suggested by G. J. Mitchell and D. P. Moore
 * in 1957, and publicized by D. E. Knuth as Algorithm 3.2.2A in volume 2 of
 * his work `The Art of Computer Programming'.  The generator is simple: at
 * each stage it emits %$x_n = (x_{n - 55} + x_{n - 24}) \bmod 2^{32}$%.  The
 * period is proven to be greater than %$2^{55}$%, and statistical properties
 * appear to be good.
 */

#ifndef CATACOMB_FIBRAND_H
#define CATACOMB_FIBRAND_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Header files ------------------------------------------------------*/

#include <mLib/bits.h>

#ifndef CATACOMB_GRAND_H
#  include "grand.h"
#endif

/*----- Magic constants ---------------------------------------------------*/

#define FIB_SZ 55
#define FIB_TAP 24

/*----- Data structures ---------------------------------------------------*/

typedef struct fibrand {
  unsigned i;
  uint32 x[FIB_SZ];
} fibrand;

/*----- Functions provided ------------------------------------------------*/

/* --- @fibrand_step@ --- *
 *
 * Arguments:	@fibrand *f@ = pointer to Fibonacci generator context
 *
 * Returns:	Next output from generator.
 *
 * Use:		Steps the generator.  Returns
 *		%$x_{i - 24} + x_{i - 55} \bmod 2^{32}$%.
 */

extern uint32 fibrand_step(fibrand */*f*/);

/* --- @fibrand_seed@ --- *
 *
 * Arguments:	@fibrand *f@ = pointer to Fibonacci generator context
 *		@grand *r@ = random number generator to extract words from
 *
 * Returns:	---
 *
 * Use:		Initializes a Fibonacci generator using word outputs from the
 *		given random number source @r@.
 */

extern void fibrand_seed(fibrand */*f*/, grand */*r*/);

/* --- @fibrand_lcseed@ --- *
 *
 * Arguments:	@fibrand *f@ = pointer to Fibonacci generator context
 *		@uint32 seed@ = seed value
 *
 * Returns:	---
 *
 * Use:		Initializes a Fibonacci generator using outputs from the
 *		@lcrand@ generator seeded from @seed@.  This is faster than
 *		using a generic @lcrand@-based generator and @fibrand_rseed@
 *		because it uses raw outputs rather than uniformly distributed
 *		32-bit words.
 */

extern void fibrand_lcseed(fibrand */*f*/, uint32 /*seed*/);

/* --- @fibrand_range@ --- *
 *
 * Arguments:	@fibrand *f@ = pointer to Fibonacci generator context
 *		@uint32 m@ = limit
 *
 * Returns:	A uniformly distributed pseudorandom integer in the interval
 *		%$[0, m)$%.
 */

extern uint32 fibrand_range(fibrand */*f*/, uint32 /*m*/);

/* --- @fibrand_create@ --- *
 *
 * Arguments:	@uint32 seed@ = initial seed
 *
 * Returns:	Pointer to a generic generator.
 *
 * Use:		Constructs a generic generator interface over a Fibonacci
 *		generator.  The generator is seeded using @fibrand_lcseed@.
 */

extern grand *fibrand_create(uint32 /*seed*/);

/*----- That's all, folks -------------------------------------------------*/

#ifdef __cplusplus
  }
#endif

#endif