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

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