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

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