00001 /****************************************************************************/ 00002 /* */ 00003 /* This file is part of QSopt_ex. */ 00004 /* */ 00005 /* (c) Copyright 2006 by David Applegate, William Cook, Sanjeeb Dash, */ 00006 /* and Daniel Espinoza */ 00007 /* */ 00008 /* Sanjeeb Dash ownership of copyright in QSopt_ex is derived from his */ 00009 /* copyright in QSopt. */ 00010 /* */ 00011 /* This code may be used under the terms of the GNU General Public License */ 00012 /* (Version 2.1 or later) as published by the Free Software Foundation. */ 00013 /* */ 00014 /* Alternatively, use is granted for research purposes only. */ 00015 /* */ 00016 /* It is your choice of which of these two licenses you are operating */ 00017 /* under. */ 00018 /* */ 00019 /* We make no guarantees about the correctness or usefulness of this code. */ 00020 /* */ 00021 /****************************************************************************/ 00022 00023 /* RCSINFO $Id: urandom.c,v 1.2 2003/11/05 16:47:22 meven Exp $ */ 00024 /****************************************************************************/ 00025 /* */ 00026 /* This file is part of CONCORDE */ 00027 /* */ 00028 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */ 00029 /* Vasek Chvatal, and William Cook */ 00030 /* */ 00031 /* Permission is granted for academic research use. For other uses, */ 00032 /* contact the authors for licensing options. */ 00033 /* */ 00034 /* Use at your own risk. We make no guarantees about the */ 00035 /* correctness or usefulness of this code. */ 00036 /* */ 00037 /****************************************************************************/ 00038 00039 /****************************************************************************/ 00040 /* */ 00041 /* MACHINE INDEPENDENT RANDOM NUMBER GENERATOR */ 00042 /* */ 00043 /* TSP CODE */ 00044 /* */ 00045 /* */ 00046 /* Written by: DIMACS (modified for TSP) */ 00047 /* Date: February 7, 1995 (cofeb16) */ 00048 /* */ 00049 /* */ 00050 /* EXPORTED FUNCTIONS: */ 00051 /* */ 00052 /* void ILLutil_sprand (int seed, ILLrandstate *r) */ 00053 /* - Call once to initialize the generator. */ 00054 /* */ 00055 /* int ILLutil_lprand (QSrandstate *r) */ 00056 /* - Returns an integer in the range 0 to ILL_PRANDMAX - 1. */ 00057 /* */ 00058 /****************************************************************************/ 00059 00060 /****************************************************************************/ 00061 /* */ 00062 /* NOTES (from DIMACS): */ 00063 /* This file contains a set of c-language functions for generating */ 00064 /* uniform integers. This is a COMPLETELY PORTABLE generator. It will */ 00065 /* give IDENTICAL sequences of random numbers for any architecture with */ 00066 /* at least 30-bit integers, regardless of the integer representation, */ 00067 /* INT_MAX value, or roundoff/truncation method, etc. */ 00068 /* This Truly Remarkable RNG is described more fully in */ 00069 /* J. Bentley's column, ``The Software Exploratorium ''. It is based on */ 00070 /* one in Knuth, Vol 2, Section 3.2.2 (Algorithm A). */ 00071 /* */ 00072 /****************************************************************************/ 00073 00074 00075 #include "machdefs.h" 00076 #include "util.h" 00077 #ifdef USEDMALLOC 00078 #include "dmalloc.h" 00079 #endif 00080 00081 00082 00083 void ILLutil_sprand ( 00084 int seed, 00085 ILLrandstate * r) 00086 { 00087 int i, ii; 00088 int last, next; 00089 int *arr = r->arr; 00090 00091 arr[0] = last = seed; 00092 next = 1; 00093 for (i = 1; i < 55; i++) 00094 { 00095 ii = (21 * i) % 55; 00096 arr[ii] = next; 00097 next = last - next; 00098 if (next < 0) 00099 next += ILL_PRANDMAX; 00100 last = arr[ii]; 00101 } 00102 r->a = 0; 00103 r->b = 24; 00104 for (i = 0; i < 165; i++) 00105 last = ILLutil_lprand (r); 00106 } 00107 00108 00109 int ILLutil_lprand ( 00110 ILLrandstate * r) 00111 { 00112 int t; 00113 00114 if (r->a-- == 0) 00115 r->a = 54; 00116 if (r->b-- == 0) 00117 r->b = 54; 00118 00119 t = r->arr[r->a] - r->arr[r->b]; 00120 00121 if (t < 0) 00122 t += ILL_PRANDMAX; 00123 00124 r->arr[r->a] = t; 00125 00126 return t; 00127 } 00128 00129 00130 #ifdef TRY_CODE 00131 00132 /*-----------------------------------------------*/ 00133 /* This is a little driver program so you can */ 00134 /* test the code. */ 00135 /* Typing: a.out 0 3 1 */ 00136 /* should produce */ 00137 /* 921674862 */ 00138 /* 250065336 */ 00139 /* 377506581 */ 00140 /* Typing: a.out 1000000 1 2 */ 00141 /* should produce */ 00142 /* 57265995 */ 00143 /*-----------------------------------------------*/ 00144 00145 int main ( 00146 int ac, 00147 char **av) 00148 { 00149 int i; 00150 int j; 00151 int n; 00152 int m; 00153 int seed; 00154 ILLrandstate rstate; 00155 00156 if (ac < 4) 00157 { 00158 fprintf (stderr, "Usage: #discard #print #seed\n"); 00159 return 0; 00160 } 00161 m = atoi (av[1]); /* Number to discard initially */ 00162 n = atoi (av[2]); /* Number to print */ 00163 seed = atoi (av[3]); /* Seed */ 00164 00165 ILLutil_sprand (seed, &rstate); 00166 00167 for (i = 0; i < m; i++) 00168 j = ILLutil_lprand (&rstate); 00169 for (i = 0; i < n; i++) 00170 printf ("%ld\n", ILLutil_lprand (&rstate)); 00171 return 0; 00172 } 00173 00174 #endif /* TRY_CODE */
1.4.7