chiark - git - mdw - catacomb/blob - fibrand.h

   1 /* -*-c-*-
   2  *
   3  * $Id: fibrand.h,v 1.3 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Fibonacci generator
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Notes on the Fibonacci generator ----------------------------------*
  31  *
  32  * The generator was originally suggested by G. J. Mitchell and D. P. Moore
  33  * in 1957, and publicized by D. E. Knuth as Algorithm 3.2.2A in volume 2 of
  34  * his work `The Art of Computer Programming'.  The generator is simple: at
  35  * each stage it emits %$x_n = (x_{n - 55} + x_{n - 24}) \bmod 2^{32}$%.  The
  36  * period is proven to be greater than %$2^{55}$%, and statistical properties
  37  * appear to be good.
  38  */
  39
  40 #ifndef CATACOMB_FIBRAND_H
  41 #define CATACOMB_FIBRAND_H
  42
  43 #ifdef __cplusplus
  44   extern "C" {
  45 #endif
  46
  47 /*----- Header files ------------------------------------------------------*/
  48
  49 #include <mLib/bits.h>
  50
  51 #ifndef CATACOMB_GRAND_H
  52 #  include "grand.h"
  53 #endif
  54
  55 /*----- Magic constants ---------------------------------------------------*/
  56
  57 #define FIB_SZ 55
  58 #define FIB_TAP 24
  59
  60 /*----- Data structures ---------------------------------------------------*/
  61
  62 typedef struct fibrand {
  63   unsigned i;
  64   uint32 x[FIB_SZ];
  65 } fibrand;
  66
  67 /*----- Functions provided ------------------------------------------------*/
  68
  69 /* --- @fibrand_step@ --- *
  70  *
  71  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  72  *
  73  * Returns:     Next output from generator.
  74  *
  75  * Use:         Steps the generator.  Returns
  76  *              %$x_{i - 24} + x_{i - 55} \bmod 2^{32}$%.
  77  */
  78
  79 extern uint32 fibrand_step(fibrand */*f*/);
  80
  81 /* --- @fibrand_seed@ --- *
  82  *
  83  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  84  *              @grand *r@ = random number generator to extract words from
  85  *
  86  * Returns:     ---
  87  *
  88  * Use:         Initializes a Fibonacci generator using word outputs from the
  89  *              given random number source @r@.
  90  */
  91
  92 extern void fibrand_seed(fibrand */*f*/, grand */*r*/);
  93
  94 /* --- @fibrand_lcseed@ --- *
  95  *
  96  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  97  *              @uint32 seed@ = seed value
  98  *
  99  * Returns:     ---
 100  *
 101  * Use:         Initializes a Fibonacci generator using outputs from the
 102  *              @lcrand@ generator seeded from @seed@.  This is faster than
 103  *              using a generic @lcrand@-based generator and @fibrand_rseed@
 104  *              because it uses raw outputs rather than uniformly distributed
 105  *              32-bit words.
 106  */
 107
 108 extern void fibrand_lcseed(fibrand */*f*/, uint32 /*seed*/);
 109
 110 /* --- @fibrand_range@ --- *
 111  *
 112  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
 113  *              @uint32 m@ = limit
 114  *
 115  * Returns:     A uniformly distributed pseudorandom integer in the interval
 116  *              %$[0, m)$%.
 117  */
 118
 119 extern uint32 fibrand_range(fibrand */*f*/, uint32 /*m*/);
 120
 121 /* --- @fibrand_create@ --- *
 122  *
 123  * Arguments:   @uint32 seed@ = initial seed
 124  *
 125  * Returns:     Pointer to a generic generator.
 126  *
 127  * Use:         Constructs a generic generator interface over a Fibonacci
 128  *              generator.  The generator is seeded using @fibrand_lcseed@.
 129  */
 130
 131 extern grand *fibrand_create(uint32 /*seed*/);
 132
 133 /*----- That's all, folks -------------------------------------------------*/
 134
 135 #ifdef __cplusplus
 136   }
 137 #endif
 138
 139 #endif