git.distorted.org.uk Git - u/mdw/catacomb/blob - fibrand.h

   1 /* -*-c-*-
   2  *
   3  * $Id: fibrand.h,v 1.2 2000/06/17 10:54:59 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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: fibrand.h,v $
  33  * Revision 1.2  2000/06/17 10:54:59  mdw
  34  * Typesetting fixes.
  35  *
  36  * Revision 1.1  1999/12/10 23:15:27  mdw
  37  * Noncryptographic random number generator.
  38  *
  39  */
  40
  41 /*----- Notes on the Fibonacci generator ----------------------------------*
  42  *
  43  * The generator was originally suggested by G. J. Mitchell and D. P. Moore
  44  * in 1957, and publicized by D. E. Knuth as Algorithm 3.2.2A in volume 2 of
  45  * his work `The Art of Computer Programming'.  The generator is simple: at
  46  * each stage it emits %$x_n = (x_{n - 55} + x_{n - 24}) \bmod 2^{32}$%.  The
  47  * period is proven to be greater than %$2^{55}$%, and statistical properties
  48  * appear to be good.
  49  */
  50
  51 #ifndef CATACOMB_FIBRAND_H
  52 #define CATACOMB_FIBRAND_H
  53
  54 #ifdef __cplusplus
  55   extern "C" {
  56 #endif
  57
  58 /*----- Header files ------------------------------------------------------*/
  59
  60 #include <mLib/bits.h>
  61
  62 #ifndef CATACOMB_GRAND_H
  63 #  include "grand.h"
  64 #endif
  65
  66 /*----- Magic constants ---------------------------------------------------*/
  67
  68 #define FIB_SZ 55
  69 #define FIB_TAP 24
  70
  71 /*----- Data structures ---------------------------------------------------*/
  72
  73 typedef struct fibrand {
  74   unsigned i;
  75   uint32 x[FIB_SZ];
  76 } fibrand;
  77
  78 /*----- Functions provided ------------------------------------------------*/
  79
  80 /* --- @fibrand_step@ --- *
  81  *
  82  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  83  *
  84  * Returns:     Next output from generator.
  85  *
  86  * Use:         Steps the generator.  Returns
  87  *              %$x_{i - 24} + x_{i - 55} \bmod 2^{32}$%.
  88  */
  89
  90 extern uint32 fibrand_step(fibrand */*f*/);
  91
  92 /* --- @fibrand_seed@ --- *
  93  *
  94  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
  95  *              @grand *r@ = random number generator to extract words from
  96  *
  97  * Returns:     ---
  98  *
  99  * Use:         Initializes a Fibonacci generator using word outputs from the
 100  *              given random number source @r@.
 101  */
 102
 103 extern void fibrand_seed(fibrand */*f*/, grand */*r*/);
 104
 105 /* --- @fibrand_lcseed@ --- *
 106  *
 107  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
 108  *              @uint32 seed@ = seed value
 109  *
 110  * Returns:     ---
 111  *
 112  * Use:         Initializes a Fibonacci generator using outputs from the
 113  *              @lcrand@ generator seeded from @seed@.  This is faster than
 114  *              using a generic @lcrand@-based generator and @fibrand_rseed@
 115  *              because it uses raw outputs rather than uniformly distributed
 116  *              32-bit words.
 117  */
 118
 119 extern void fibrand_lcseed(fibrand */*f*/, uint32 /*seed*/);
 120
 121 /* --- @fibrand_range@ --- *
 122  *
 123  * Arguments:   @fibrand *f@ = pointer to Fibonacci generator context
 124  *              @uint32 m@ = limit
 125  *
 126  * Returns:     A uniformly distributed pseudorandom integer in the interval
 127  *              %$[0, m)$%.
 128  */
 129
 130 extern uint32 fibrand_range(fibrand */*f*/, uint32 /*m*/);
 131
 132 /* --- @fibrand_create@ --- *
 133  *
 134  * Arguments:   @uint32 seed@ = initial seed
 135  *
 136  * Returns:     Pointer to a generic generator.
 137  *
 138  * Use:         Constructs a generic generator interface over a Fibonacci
 139  *              generator.  The generator is seeded using @fibrand_lcseed@.
 140  */
 141
 142 extern grand *fibrand_create(uint32 /*seed*/);
 143
 144 /*----- That's all, folks -------------------------------------------------*/
 145
 146 #ifdef __cplusplus
 147   }
 148 #endif
 149
 150 #endif