Linked - Softouch Information Services
Contents
1. a c a 0c z 0 This expression multiplies each number by the factor a and then adds It produces series of numbers en differences are given by the expression l h a M tc We call the process mapping because it carries the integer to I from one point to the next in a one dimensional space as shown in figure 1 Suppose a 2 and I then you have 1 3 7 15 As it stands this series doesn t look random To create a series that looks random you need a method of scrambling the output perhaps by cutting off the upward run One way to achieve this appearance is to imagine you ve subdivided the number line representing the space into segments of length m If you make the multiplier a in the LCG suf continued on page 442 Charles A Whitney is a physicist at the Harvard Smithsonian Center for Astrophysics 60 Garden St Cambridge MA 02138 and is a professor of astronomy at Harvard OCTOBER 1984 BYTE continued from page 129 ficiently large compared with the seg ment length m the mapping will take the point out of the current segment at each jump The successive posi tions of the point within each seg ment will then be an erratic function You can consider these successive positions pseudorandom numbers if 159 00 179 00 Best Price Best Price Amdek Color Amdek Color II PGS HX 12 PGS MAX 12 PGS SR 12 IBM Monochrome Display IBM Color Display Epson FX2. 010 This series starts off with a hap hazard appearance but since it repeats itself every 8 terms it is said to have a period of 8 It is not hard to see why this is the period First the modulus of the series is 8 so the series cannot have more than 8 inte gers You remove larger integers by subtracting the modulus Second the series is deterministic Each ap pearance of a particular integer must be followed by a uniquely determined integer That is each appearance of 2 must be followed by 5 As a result the series must repeat itself with a period no longer than its modulus This reasoning suggests adopting a large modulus if you want a long period But it isn t the only possibil ity Some generators will skip many of the possible numbers and give an in continued complete set of random numbers A series that generates all of the m distinct integers 0 lt n lt m 1 dur ing each period is called a full period Whether a series will have a full period or not depends in large measure on the values you choose for the parameters a m Table 1 il lustrates some of the series with a RANDOM NUMBERS 5 and m 8 for various values of the additive constant c Take the first series as an example If you use a seed 6 you obtain the pseudoran dom series 6 7 4 5 2 If you use the seed 5 you get 5 2 3 0 I Because several of the series in table do not have a full period they
3. Graphics with Gray Matter New GRAPHICS PLUS GP 29 Big Features Little Cost The GP 29 delivers the graphics and text versatility of powerful expensive terminals at significant cost savings And you can buy the GP 29 as a ready to use termi nal or as a retrofit board for the Zenith Z29 Expand your applications with dual plane graphics Create images with shades of gray Overlay two separate images Animate the images Store multiple images in local memory The GP 29 gives you low cost graphics you never imagined possi ble 1024 x 500 hi res and 512 x 250 lo res selectable resolution 128k of display memory And our dedi cated graphics processor provides selective vector erase area erase area fill area move arc drawing pan and zoom You also get Tektronix 4014 com patibility as well as DEC VTIOO and VT220 compatibility Enhanced Text Too The GP 29 offers four selectable display formats 80 and 132 col umns with 24 or 49 lines Off screen scrolling memory Storage for pages and pages of text Off line editing capability Double high and double wide characters and much much more Plus you get operator conven ience features like plain English set up menu easy to use program mable keys local function keys transparent mode and non volatile memory And a serial printer port is standard Call or write today to place your order Digital Systems P O Box 15288 Seattle WA 98115 206 524
4. 0014 GP 19 board for the Zenith ZI9 terminal is also available for 695 444 BYTE OCTOBER 1984 Circle 252 on inquiry card generate subsets of integers with many useful properties In the first place the sum of the periods of the subsets equals the modulus of the series This property helps you decide whether you have found all the subsets Second if the series does not have a full period different seeds start each subset For example the series with c 4 has six subseries of periods 1 or 2 and the seed you use will determine which subseries you generate When you set up a random number generator look for a long and full period because it will produce the richest set of numbers Several estab lished rules for selecting the param eters will achieve a full period These rules are discussed in Donald Knuth s The Art of Computer Programming referenced at the end of this article One rule is that the modulus m and the constant c must have no factors in common Another rule is that a must be greater than the square root of m a gt Vm to avoid the serial cor relation that upward runs produce This rule ensures that the mapping quickly takes the number out of the current segment the same condition mentioned earlier Finally you will get the longest possible periods if the modulus is a prime number equal to or less than the largest integer your computer can handle For a 16 bit processor this condition implies
5. 80 Epson FX 100 Okidata 92 A Okidata 93 A Okidata ML 84 Okidata 2410 Okidata 2350 Toshiba P1351 amp 1340 NEC Spinwriters 3550 NEC Spinwriters 7730 C Itoh Starwriter 40CPS C Itoh Printmaster 55CPS Gemini 10X 290 00 Gemini 15X 399 00 Also available DX 15 HR 25 HR 35 amp Silver Reed Best Price 265 00 590 00 699 00 465 00 699 00 899 00 2085 00 1925 00 Best Price 1699 00 1799 00 Best Price Best Price DRIVES Tandon TM 100 2 205 00 Slimline Drives Your Choice Toshiba Hitachi Panasonic 175 00 RANDOM NUMBERS you suppose each segment is renum bered from 0 to m 1 as in figure 2 You can accomplish such a subdivi sion of the space by introducing the modulus function mod m m m where m is the integer part of the quotient derived by truncation IBM Personal Computer 256KB Memory DS DD Drive FDC Color Card Amdek 300 Monitor with 10MB Hard Disk Sub System 2899 We configure and test the system for you at no extra cost MULTIFUNCTION BOARDS AST I 0 Ser amp Par 179 00 AST Six Pack 64K AST Mega Plus 64K AST Combo 64K Quadboard 64K IBM Color Graphic Adapter IBM Mono Printer Adapter Hercules Graphic 359 00 Plantronics Best Price Paradise Multifunction Card Best Price Orchid Blossom Best Price 64K Ram Upgrade Kit 50 00 Hayes Smart Modem 1200 Hayes Smart Modem 300 Hayes 1200B Plug in Modem Card 429 00 HARD DISK FOR IBM
6. looks like it was generated by a random pro cess I will call it random and will put off the question of how to judge ap pearances until discuss methods of testing random number generators To carry out a Monte Carlo calcula tion you need to work with random numbers inside a computer But you are faced with the fact that a purely digital computer is a deterministic machine except on its off days and such a device cannot truly generate a random process You have to be satisfied with deterministic algorithms that imitate random pro cesses You can thus generate numbers with some of the earmarks of randomness Naturally some random number generators work better than others and you must be wary LINEAR CONGRUENTIAL GENERATORS Mathematicians have suggested many methods for generating pseudoran dom numbers with a digital computer Happily the most common and powerful one involves simple arith metic This method is the linear con gruential generator or LCG for short An LCG produces a series of numbers l where the subscript i indicates the location of the number i indicates the first number i 3 is the third and so on Since each successive term is computed from its predecessor you can see right away that this series is not truly random because it has memory That is why the LCG is called a pseudoran dom number generator To understand the LCG look at the following linear expression I
7. that m lt 32 768 Two additional examples of LCGs with short full periods follow l mod 7l 5 9 l mod 7l 7 9 In practice you develop a pseudo random number generator in a cut and try process testing and modify ing various possibilities In describing the LCG assumed that the coefficients were all integers You can increase the series apparent period by taking real decimal values For example if you substitute 5 1 and 3 111 for the coefficients in the series above the terms won t repeat precise ly after a period of eight terms But the terms in successive cycles will continued show only a slight shift and the over all pattern of the cycle will be the same except for occasional jumps when the fractional parts accumulate sufficiently Thus the increase of period is only illusory and since don t want to fool you with this illu sion will restrict myself to integer coefficients STATISTICAL TESTS FOR RANDOMNESS Often you can look at a series and see that it was probably not gener ated by a random process For exam ple who would claim that a real coin would lead to a series of heads H and tails T such as HTHHTTHHHTT THHHHTTTTHHHHHTTTTT It could happen with a probability of about 1 2 22 0 000000001 but you wouldn t expect it in your lifetime But some series are not so obvious and you need a more reliable test than the eyeball and a hunch For this you must compare s
8. way They will exhibit a tendency to clump just as the flips of a real coin will show runs of more than one head or tail in stead of HTHTHT continued Figure 3 A random walk generated with a pseudorandom number generator of the type in table 1 with a period of 127 Each step upward or downward was determined by simulated flip of a coin This diagram illustrates the repetitive pattern of some random number generators Figure 4 Similar to figures and 2 this walk was generated with the RND function of the Microsoft Advanced BASIC supplied with the IBM PC operating under MS DOS 2 0 It shows an approximate periodicity of about 18 000 steps although the rigorous period is about 64 000 Using such a function for Monte Carlo simulations requiring more than 8000 steps could produce misleading results 480 RANDOM NUMBERS walk generated by one of the LCGs in table 1 You can easily spot the peri odicity and you wouldn t want it as the imitation of a very long random walk This walk was generated from a normalized LCG by stepping upward if x 0 5 and downward if x 0 5 When applied this test to the pseudorandom number generator supplied with the Advanced BASIC In terpreter of the IBM Personal Com puter PC it showed a period of 65 535 This result was as good as could have hoped but a detailed plot of a walk shows that it also has a much shorter wave like cycle super posed Figure 4 shows
9. 83001 and leads to a pseudorandom series 307 733 9315 44 E RANDOM NUMBERS Table 2 Sample bin populations the results for N 1000 numbers in 100 bins computed with the BASICA RND The observed values cluster about the ex pected mean lt NB gt N O 10 Sample Bin Populations with BASICA RND 121 9 9 12 9 11 13 8 12 9 18 10 7 11 5 8 fo o O ro QD O O0 You can test the distribution of numbers by setting up Q bins and putting each member of the series into one of the bins For example if the numbers are restricted to the in terval 0 lt x lt 1 each can be put SEEKER S1 BOARD SEEKER S2 BOARD EE For Information writ rca 452 BYTE OCTOBER 1984 INTERNAL WINCHESTER 12 10 11 12 1t 735 10 9 8 10 17 11 10 13 17 9 13 10 12 11 7 11 8 19 10 8 a i C O QD QD COON into bin where is computed from J int Qxx 0 Q 1 On each occurrence of J the bin count NB J is incremented so that NB NB I EXPANDABILITY EXTERNAL WINCHESTERS T COmDEM Fall 84 WESTERN AUTOMATION LABORATORIES INC 5595 Arapahoe Road Boulder CO 80303 49 64 Circle 375 on inquiry card Table 2 shows the result for N 1000 numbers in 100 bins computed with the BASICA RND The observed values cluster about the expected mean lt NB gt N Q 10 When you run the test several times the ex cesses and deficiencies
10. 95 00 upto six times faster than MACRO 80 For additional information call or write s E5 317 255 6476 E3 6413 N College Ave Indianapolis Indiana 46220 WALTZ LISP The one and only adult Lisp system for CP M users Waltz Lisp is a very powerful and complete implementa tion of the Lisp programming longuage It includes features previously available only in large Lisp systems In fact Waltz is substantially compatible with Franz the Lisp running under Unix and is similar to MacLisp Waltz is perfect for Artificial Intelligence programming It is also most suitable for general applications Much foster thon other microcomputer Lisps Long integers up to 611 digits Selectable radix True dynamic choracter strings Full string operations including fast matching extraction Flexibly implemented random file access Binary files Stondord CP M devices Access to disk directories Functions of type lambdo expr nlambda fexpr lexpr macro Splicing and non splicing character macros User control over oll aspects of the interpreter Built in prettyprinting and formatting facilities Complete set of error handling and debugging functions including user programmable processing of undefined function references Virtual function definitions Optional automatic loading of initialization file Powerful CP M command line parsing Fast sorting merging using user defined comparison predi
11. GENERATING AND TESTING PSEUDORANDOM NUMBERS BY CHARLES A WHITNEY TT NS dd 4 N M SS ue NES N D mE et I BER 1984 ILLUSTRATED BY MACIEK ALBRECHT Analyze haphazard occurrences with linear congruential generators F A DRUNKARD starts from a lamppost and randomly stag gers away how far will he have progressed in one thousand steps Expressed in varying forms the drunkard s walk has become a staple of mathematical physics How far will an impurity atom migrate in a crystal lattice How many steps will be required for a photon to emerge from a foggy atmosphere They are all the same question and they can be treated with Monte Carlo calcula tions These calculations are finding increasing applications in business as well For example they provide an analysis of how best to serve customers arriving haphazardly at a counter Carrying out such calcula tions depends on being able to imi tate randomly generated numbers and this is not easy It has been said that more time has been spent gen erating and testing random numbers than using them You can find numerical examples of random series all around you The final integers in a list of telephone numbers gives a good random series in the range O to 9 The face values of cards drawn from a well shuffled deck and the final digits in license plate numbers on passing cars are usually quite reliable But the fi
12. PC 10MB Hard Disk Sub System includes Software Controller Cables Etc Internal 875 00 External 1025 00 489 00 209 00 Many other products available Please call for low low Prices 2640 Walnut Ave Unit K Tustin CA 92680 714 838 7530 Prices amp availaility subject to change without notice IBM is a registered trademark of IBM Corp 442 BYTE OCTOBER 1984 Circle 232 on inquiry card When for example mod 11 3 2 the result always lies between 0 and m I In some forms of BASIC this is writ ten 11 MOD 3 Now rewrite the mapping as l mod al c m This equation is a general form for the LCG and it produces a series of inte gers in the range 0 lt I lt m l Three parameters describe this map ping the multiplier a the difference and the modulus m Often it is convenient to normalize the values dividing each by the modulus The result is a series in the range 0 to m 1 m lt 1 which can be written as X1 v FLOAT I FLOAT m Note that the smallest nonzero dif ference between terms is 1 m which means the numbers the LCG pro duces comprise a set of m equally spaced rational fractions in the range 0 x lt m 1 m To see some of the properties of series that are generated this way look at the following series I mod 51 3 8 By starting with an arbitrary value the seed and taking I 1 you find 10 8 2 5 4 756 1 0 3 2 5
13. XT IK RETURN RAND drawing from piles without replacement 1X2 IX2 IA2 IC2 JJ INT IX2 IM2 IX2 IX2 IX2 JJ IM2 ICELL INT NPILES IX2 IM2 1 RAND IXS ICELL IM1 RETURN END 4G 2 ___ The best best value best reliability RANDOM NUMBERS y or best feature on sale OFFERING THE BEST FOR LESS IBM PC BEST graphic card BEST VALUE word processing BEST VALUE spreadsheet BEST VALUE diskettes DS DD 5 10 STB Super Rio 64 K Quadram Expanded Quadboard Hayes Smartmodem 12008 PRINTERS Oki 92 par Brothers HR 25 Epson Diablo Call Ricoh Call BEST PC Compatible Package including a BEST VALUE computer system and a BEST VALUE word processing 2189 COMPUTER SALES co 619 576 9185 Mon Fri 9 a m 5 p m Pacific Time z 6 m a 8 199 Claremont Mesa Bvd A Visa MasterCard P O Bos 112425 Prices San Diego CA 92111 D NJ ar Lifetime Guarantee gt a yess oY DISKS STEP NUMBER Figure 7 A random walk with shuffling tailored to a 16 bit computer In the absence of shuffling this generator would be limited to a period of several hundred With E shuffling the period is longer than 50 000 This walk was generated with an IBM PC _ M APO Call Disk Works for our latest prices Fuji and M diskettes 1 800 292 1492 Nationwide or 312 368 0359 in Illinois 5 1 4 SSDD 1 79 each 5 1 4 DSDD 2 29 each 1 1 5 D DD 3 80 each Price
14. appear in dif ferent bins As a result no evidence appears that any particular bins con sistently receive more than 1 O of the counts A quantitative measure of perfor mance is the conventional chi square test which evaluates a measure of the spread see The Chi Square Test on page 446 This test estimates how likely it is that the actual value will be different from the expected value in a randomly generated series If you look at table 2 you find no bins with less than 5 two bins with NB 5 seven with NB 6 and so on The chi square test examines all the bin populations and tells how often you can expect this particular distribution of populations from a randomly gen erated series where you expect NB 10 on the average Applying the chi square test to the bin populations of table 2 and then for much longer runs using the BASICA generator you will find that if the random number generator is pushed to 30 000 terms it still per forms well The story changes as soon as you get close to the full period of about 65 000 terms There all bins are more or less equally filled and the histogram of bin populations NB J becomes tightly peaked about the mean value NB because all pos sible values have been achieved The generator has displayed its entire full period Near this extreme limit the generator fails the chi square test because the chances are small that actual values will be any different from the exp
15. ated by the simple LCG in figure 3 The sharply peaked pattern indicates a highly repetitive pattern 45 7 DISK DRIVES Qume 142A 199 Teac 0558 169 Tandon IM100 2 199 Tandon TM100 4 295 CDC 9409 219 Case and PS 45 PC EXPANSIONS Maynard Disk Controller Sandstar Senes Interna 10MB systems WS VV52 Quadboard 64k 114 call ww wen oc up oo Quadboard 348K Quadcolor AST SixPakPius 64K SixPakPius 384K MegaPlus 64 VO Plus AST 3780 PCnet starter kit MonoGraphP us HERCULES graphics board HAYES Modems 300 Smartmodem 1200 Smartmodem 12008 Set of 9 chips 64K VLM Computer Electronics 10 Park Place Morristown NJ 07960 201 267 3268 Visa MC Check or COD n en oo o n o o n o on o b Circle 373 on inquiry card INTRODUCING mHecvpher Mt A COMPLETE 68000 amp Z 80 SINGLE BOARD COMPUTER SYSTEM WITH ULTRA HIGH RES GRAPHICS SOLDM Call Free 800 235 4137 for prices and information Dealer inquiries invited and COD s accepted 800 592 5935 or 805 543 1037 Circle 381 on inquiry card If your computers are not on speaking terms LA j CI de introduce them to MO VE ITS n3 Si and data between computers When adding a new computer data and programs from one system can be transferred to another with MOVE IT even if the two have different disk formats and use different operating systems A mini network can be set up by equippi
16. ating series 6754 ETON AVE EA ica 818 703 8112 shuffled deck must follow some COPYRIGHT 1884 WOOLF SOFTWARE SYSTEMS INC well defined rule of my own choosing and when have gone through the deck I can start again Before continu ing however must put the cards back into their original order Since cannot shuffle the deck in the usual way if merely start over will have come to the end of the deck and the series will repeat What can I do with the other deck Here is one procedure and you can invent others that will work just as well or better They are analogs for shuf fling in the LCG The two decks cor respond to the two LCGs Lay the cards in the unshuffled deck into five piles Then remove a few cards from the shuffled deck so that it will not have the same number as the unshuf fled deck Then draw a card from the shuffled deck and take its value modulo 5 to compute a number des ignating one of the five piles Select the first card from that pile and put it into a discard pile Continue draw ing cards from the shuffled deck computing the number of their piles and selecting a card from that pile until you exhaust the shuffled deck Then start again with the cards in the same order When the five piles from the unshuffled deck are exhausted pick up the discard pile put the cards back into their original order and lay out five piles again Continue as before You will probably find that th
17. cates Full suite of mapping functions iterators etc Assembly language interface e Over 250 functions in total The best documentation ever produced for a micro Lisp 300 full size pages hundreds of illustrative exomples Waltz Lisp requires CP M 2 2 780 and 48K RAM more recommended All common 5 and 8 disk formats available 2 Q TM Now includes Tiny Prolog RO ODE Manual only 30 refundable with My All sss INTERNATIONAL em 15930 SW Colony PI Portland OR 97224 Unix Bell Laboratories CP M Digital Reseorch Corp 464 BYTE OCTOBER 1984 Version 4 4 1 69 written in Waltz Lisp foreign orders add 5 for surface mail 20 for airmail COD add 3 Apple CP M and hard sector formats add 15 Call free 1 800 LIP 4000 Dept 12 In Oregon and outside USA coll 1 503 684 3000 Circle 288 on inquiry card RANDOM NUMBERS FOURIER SPECTRUM amed for the French mathemati cian J B J Fourier 1768 1830 the Fourier series is a representation of a series of data points Fit as a sum of harmonic terms in the form Fit E a sin nwt 6 cos nwt When Fit is specified at a discrete set of points such as the displace ments in a random walk at uniformly spaced times the coefficients a and 6 can be found by summing prod ucts of the data and the trigonometric functions These coefficients comprise the amplitude spectrum and the quan tity sqrt a is a meas
18. e SEE US AT COMDEX Series 36 35 cps ali purpose interface 630 API 40 cps all purpose interface A Treat your personal computer to famous Diablo letter quality printing Don t settle for less your choice of hundreds of printwheel styles fully formed characters interfaces with IBM Apple Radio Shack Commodore IEEE 488 Centronics Parallel and RS232C Serial In MTI s opinion the best letter quality printers on the market Whether you lease or buy you ll find MTI is the one source for all the computer and data communications equipment applications ex pertise and service you ll ever need At hard to beat prices Call us New York 516 621 6200 212 767 0677 518 449 5959 New Jersey 201 227 5552 Pennsylvania 412 931 9351 Ohio 216 464 6688 513 891 7050 Outside N Y S 800 645 6530 Computer amp Data Communications Equipment Distribution Systems Integration Maintenance DEC Intel Texas Instruments Hewlett Packard Dataproducts Diablo Lear Siegler Esprit C Itoh Racal Vadic MICOM Ven Tel Develcon PCI U S Design Digital Eng Cipher MicroPro Microsoft Polygon amp Select QED Discounts VISA amp MasterCard 458 BYTE OCTOBER 1984 Circle 244 on inquiry card C 72 T e RANDOM NUMBERS order is quite different the second time and in succeeding sequences The success of this method depends on having an appropriate number of piles and taking an appropriate number of cards ou
19. ected value What happens when a random number generator comes to the end of its period is similar to what happens in a game of blackjack when the cards are not collected into the deck after each hand When 51 cards have been laid out there is no doubt what the next card will be You pro continued Of course POWER saves will mako your your Bad Disk to keep your js in line EVERYTHING YOU ALWAYS WANTED TO DO BUT WERE AFRAID TO TRY Unlike some utility programs that are a headache touse POWER is engineered to spoil you with 55 features simple and uniform commands and utter simplicity of use POWER automatically alpha betizes and numbers your files You select by the number and never type file names again Need to COPY RENAME ERASE or RUN Just type in their menu number ER also locks out your disk s bad sectors TEST without destroy ing files a critical difference from other utilities that search and destroy without informing you what they ve done leaving you to ud your programs won t run And POW 50 commands to go POWER ONE PROGRAM DOES IT ALL You may own a few utility programs for your com puter eng each with its own commands to memorize R has all the programs rolled into one 16K integrated package so you do things you ve never tried before every day Save sen sitive data from prying eyes with tect move a block of memory or compere files CHECK POWER also makes easy w
20. en erated from BASICA RND shows clear signs of waves The Fourier amplitude spectrum lets you quantitatively measure the waves size see Fourier Spectrum on page 464 You can derive this spectrum from the fun damental definition of the Fourier coefficients that you ll find in introduc tory books on applied mathematics Or you can derive it from the fast Fourier transform subroutines in some software packages As an exam ple figure 5 shows the frequency spectrum of the random walk in figure 3 which was generated with an LCG with a period of 127 This spectrum shows the relative amplitudes of waves of various frequencies You plot the frequencies in terms of the walk s full length namely 1000 steps so that the primary period of 127 shows as a peak in the spectrum at about 8 cycles 1000 127 on this spectrum Because it quickly becomes repeti tious you can t use such an LCG for simulations involving more than a few dozen steps and the Fourier spec trum puts you on your guard Figure 6 shows the amplitude spectrum for the BASICA RND pseudorandom number generator that comes with RANDOM NUMBERS the IBM PC s MS DOS 2 0 operating system In this diagram the frequen Cy is the number of peaks in every 64 000 step run For example signifi cant waves show 4 12 21 28 and 37 peaks per 64 000 steps The most pro minent is the wave with frequency 4 which accounts for the main random walk plot pattern The fact that y
21. leads to the approximate re lationship a m VI For a 16 bit computer Imas 32 768 which implies a m 181 Thus you can construct a shuffled LCG from a pair of LCGs with periods less than 181 I then wrote a program to run through the output of an LCG and test for full period After some experimenting found that the following pair of LCGs have full periods mod 11l II 151 and mod 113 13 137 Finally the choice of the number of piles did not seem to me to be critical and settled on NPILES 121 Figure 7 shows a 50 000 step ran dom walk generated on an IBM PC by continued Listing 1 A program in BASIC for generating pseudorandom sequence from two LCGs with shuffling PROGRAM RANWALKS with shuffling MS BASICA OPEN RANWALKS OUT FOR OUTPUT AS 2 DIM IXS 200 INPUT NPILES NPILES INPUT SEED IS IM2 137 1A2 113 1C2 13 1M1 151 1A1 111 1C1 11 GOSUB 1010 TO INITIALIZE RAND INPUT STEPS PER GROUP NS Use NPILES 121 for secondary list LCGs INPUT NUMBER OF GROUPS NG PRINT 2 RANWALKS LOG 111 11 151 LOGC 113 13 137 NS NG NPILES ICOUNT 0 FOR I 1 TONG FOR J 1 TONS GOSUB 2010 TO COMPUTE RAND ICOUNT ICOUNT 1 IF ICOUNT NPILES 1 THEN GOSUB 1010 ICOUNT 0 reset piles IF RAND 50 THEN MD 1 ELSE MD 1 FOR IK 1 TO NPILES IX1 IXT IA1 IC1 JJ INT XT IMT DXT IXI IMT UJ IXS IK 1X1 NE
22. mark to any section or even groups of paragraph ou think you may want to use again WER automatically indexes them for you and at the same time extracts a com ment description from your text up to 40 characters long NOW YOU CAN WRITE BY NUMBER To create your new text simply scroll POWER i your DOCU X you have instant window into any text hg free apo Anatas can awa to on else DOCU POWER pulls together all the pieces of text and gets it ready for or editing with your own word processor CK GUARANTEE AND A 10 DAY TRIAL DOCU POWER is available by mail or through your software dealer for only teg edt aion est Me pine iin 580030 m For Reine PC or e CPM The company that earns its exclamation point 2519F Greenwich San Francisco CA 94123 TOLLS FREE 800 428 7825 Ext 96F In CA 800 428 7824 Ext 96F WordStar is a trademark of MicroPro Circle 77 on inquiry card RANDOM NUMBERS You can probably use a generator out to one half of its period For small simulations this limit should be good enough gressively lose randomness as the dealer approaches the end of the deck if you keep track The upshot is that you can probably use a generator out to one half of its period For small simulations this limit should be good enough AMPLITUDE SPECTRUM FROM FOURIER TRANSFORM I ve already remarked that the random walk pattern in figure 4 g
23. ng each computer with MOVE IT increasing utilization by sharing information freely between machines Error Free A 16 bit error checking technique assures accurate and error free data transmission even at high speeds and over dirty telephone lines or long cable runs MOVE IT is the ideal program for telephone line use with modems as well as direct wire applications If you have ever faced the problem of intercomputer communication MOVE IT is what you need The simplest dependable solution the lowest in cost No expensive circuit boards to install Easiest to set up No programming knowledge necessary Over 17 000 programs sold and operating Also MOVE IT puts you in touch with information networks such as The Source CompuServe Dow Jones and News Net With MOVE IT you can communi cate with over 120 different makes of computers using PC DOS CPM 86 and CP M systems Retail price is 125 for all CP M systems and 150 for all CPM 86 and MS DOS systems including the IBM PC Available from your local dealer or from RANDOM NUMBERS An LCG s period has two limitations only integers less than the modulus are generated and the series is deterministic early repetition of the pattern Another way to think of this manip ulation is in terms of a fictitious game of solitaire Suppose have two decks of cards One of them has been shuf fled but am asked to produce the longest possible nonrepe
24. o IL Mem 100 Certified FREE amp DELIVERY eg me EAD SE EE 24 Hour Order Desk 1 800 634 2248 Free on mannu orders of 50 more 82 v 56 M Services 1326 25th St S Suite H Fargo ND 8103 1 701 280 0121 Buy Sell Used Hardware Without Risk In addition to receiving a monthly newsletter containing latest com puter information and sales membership allows you 1 plus addit ads at prices Buyer selects ad E pur chase price to Computer Swap Shop who holds same in escrow and notifies seller who ships to buyer Buyer has 7 days to examine the equipment and if satisfied seller receives sales price less 8 small commission otherwise money is refunded You must be a member to buy or sell with Com puter Swap Shop Inc NO RISK BONDED Send 20 subscription fee to Computer Swap Shop Inc Box 2988 Delray Beach FL 33444 up Varese ET Ae 1 a RANDOM NUMBERS Imax 32 768 the largest integer my computer can handle first needed an expression for the largest integer that will be computed by a particular LCG It is approxi mately axm c before it is reduced modulo m This integer must satisfy axm e lt Ls The condition a gt m also con strains the multiplier to avoid serial correlations These two constraints suggest taking a small value for the additive constant c and setting a m which
25. ome statistical properties of the series with some theoretical predictions you make after assuming that the series was gener ated by a truly random process When refer to a statistical property I m talk ing about one that is independent of the seed you used to start the series including those tests that are obliv GANG MULTIPROGRAMMER 446 BYTE OCTOBER 1984 RANDOM NUMBERS THE CHI SQUARE TEST his test is commonly used for agreement between a series of values O and expected values E In this case the observa tions are the actual bin populations listed in table 2 and the expected value is the average 1000 100 IO There are n 100 observations and because M gt gt I the test can be ex pressed in a simplified form as follows For each bin compute the difference O E square these values divide by the corresponding value of E and sum the quotients over all the obser vations Divide the result by the number of observations obtaining X IIMIX O EJ E If this quantity lies between 0 5 and 2 0 the scatter of the observations is consistent with random numbers If X lt 0 5 the observations are suspiciously close to average values if X gt 2 0 they are too far from the average This test is applicable only to quantities that are expected to obey the classic law of errors and this is often a debatable point For the numbers in table 2 X 0 79 there fore the populations have
26. onds to the wavy pattern evident in figure 4 45 d KEE Cirle 305 on inquiry card C IF YOU PROVE BUSINESS lt 7 50 USE PROTECT YOUR DEDUCTION DEDUCT YOUR COMPUTER New tax laws require proof of 50 business use The PYD Prove Your Deduction program records and reports use on most CP M and MS DOS computers Only 24 95 Call BCD COMPUTERS 800 223 5369 EXT 242 Circle 41 on inquiry card WHY PAY MORE ORDER DIRECT AND SAVE 1 YEAR WARRANTY ON ALL ITEMS IBM KYB 1 83 Key Keyboard for PC PX IV Jimm Pitch RGB 13 Monitor w Green Text amp Tilt Swivel CGA Color Graphics Adoptor ComboPX IV CGA PCB 201 Light Pen APPLE MAK 1 99 loy IL wi 149 1179 COD VISA MC ACCEPTED eds Station Square Bergenfield N J 07621 201 387 1109 Circle 209 on inquiry card OK WRITER LETTER QUALITY Enhancement for Dot Matrix Printers Easy to install Plug in module Okidata printers Letter Quality 30 cps Draft Quality 120cps 10 12 17 cpi Full dot addressable graphics Front panel access to all features Proportional spacing bold double width underlining self test etc Serial and parallel interfaces retained HELP mode Diagnostic HEX dump And many other features Designed for upgrading your current or new ML82A 83A printer Q RAINBOW tcocoois MC P O Box 7200 Costa Mesa CA 92628 714 241 0565 Telex 386078 imer ss
27. ork of patching DISPLAY SUBSTITUTE customizing software LOAD SAVE Among the other commands are SIZE STAT 106 DUMP vet FIL SET and the CP M version lets you restore erased files even when you don t remember the filename at a flick of the ER RECLAIM command Still 31 commands to go POWER NOW FOR IBM s PC DOS AS WELL AS CP M We first developed POWER for CP M two years An and a stack of testimonials from FORD to ROX testify to its excellence For IBM PC users special features like managing sub direc tories and a separate creation of up to 8 simultaneous on screen WINDOWS have been MONEY BACK GUARANTEE AND A 10 DAY TRIAL POWER has the Seal of Approval from the Pro fessional Software Programmers Association and you too must be happy with POWER or your money back ee once aou ey m control of your computer Call 91001 y 415 567 1634 or your local dealer For IBM PC or any CP M machine Please specify disk format TO ORDER CALL 800 TOLLFREE IBM and IBM PC are International Business red trademarks of achines Corporation 456 BYTE OCTOBER 1984 CREATE NEW TEXT WITHOUT RETYPING DOCU POWER turns your existing text tiene meque n qme ts s y picking sections a the DOCU POWER master index You never have to retype the same words again DOCU POWER WORKS WITH ANY WORD PROCESSOR At your leisure you set up your library files and then give a DOCU R
28. ou can divide two of the higher frequen cies 12 and 28 by 4 accounts for the repeated pattern of details on the waves This test is a clear call for cau tion in using BASICA RND and it im plies that you need an improved generator SHUFFLING A GENERATOR How can you extend the period As mentioned earlier an LCG s period has two limitations only integers less than the modulus m are generated and the series is deterministic mean ing a particular number always has a amp particular sequel For a computer cap able of handling integers smaller than a fixed limit lma you can do nothing about the first restriction You can however alleviate the second restric tion and alter the simple determinism of the series using a technique called shuffling Consider an LCG with a period of 8 Each member of the series is an in teger from 0 to 7 and if the selection is purely sequential the period inevit ably will be 8 But suppose you set up a secondary list of five numbers and use a second LCG to select the next member of the series from one of them Then after each five selec tions you replace the five numbers in the secondary list with a randomly selected set By using two LCGs you can shuffle the series and extend the effective period You do not increase the possible integers but prevent an continued FREQUENCY CYCLES PER PERIOD Figure 5 Amplitude spectrum for the random walk gener
29. rst digits of such numbers are often far from random The property that defines a ran domly generated series is that each number is independent of all earlier numbers In other words the process that generates the random series has no memory Therefore even if you know all the previous numbers you cannot predict with certainty the next one And if you have been losing at a truly random game you have no reason to think you will start winning That s why flipping a coin is such a 9009 method of generating a random series of zeros and ones Each flip is entirely independent of the others Before going further should try to clarify a point of language that can lead to confusion Strictly speaking no such thing as a random number exists only a random process The number 12345 is neither less nor more random than the number 32719 In a series of 100 000 random ly generated numbers both of these would have the same chance of oc curring The idea that 12345 is less random comes from comparing it with a simple pattern of ascending digits Thus instead of saying you are trying to produce random numbers you should say you are trying to con struct a method that will produce a series of numbers that imitates the results of a random process But for the purpose of this article will use the word random more loosely to refer to a random sequence or a ran dom number without worrying about the niceties If a sequence
30. s are per disk in quantity 2 boxes of 10 Add 2 KO shipping and handling Call for quantity and All orders same day via U ground DISK WORKS 11 LaSalle St Suite 2601 Chicago IL 60603 W AMPLITUDE Prevents damage from liquid spills dust ashes etc Fits like a second skin excellent feel Homerow and numeric locators Available for IBM PC Apple Ile Radio Shack Model 100 Commodore 64 Send 29 95 check or M O Visa amp MC include exp date 7 Figure 8 Amplitude spectrum of the random walk in figure 7 showing absence of Dealer are init Pine ec significant periodicities and indicating that the shuffled pair of LCGs passes this test available FREQUENCY CYCLES PER PERIOD MERRITT Computer Products Inc successfully 2925 LBJ 180 Dallas Texas 75234 214 942 1142 465 fa Circle 123 on inquiry card Eco C Compiler Release 3 0 We think Rel 3 0 of the Eco C Compiler is the fastest full C available for the Z80 environment Consider the evidence Benchmarks Seconds Benchmark Times courtesy of Dr David Clark CNC Could Not Compile N A Does not support floating point We ve aiso expanded the library 120 func tions the users manual and compile time switches including multiple non fatal error messages The price is still 250 00 and includes Microsoft s MACRO 80 As an option we will supply Eco C with the SLR Systems assembler linker librarian for 2
31. such a plot and reveals a subcycle that is about 18 000 steps long DISTRIBUTION A random sequence ought to contain f representative numbers from all parts of the permitted range Some pro grams generate numbers that follow continued Table 1 Because several of these series do not have a full period they generate subsets of integers with several useful properties for example the sum of the periods of the subsets equals the modulus of the series Linear Congruential Generators mod 5l c 8 Expression I 1 0 0 C gt gt gt LOWEST PRICES GUARANTEED FIND A LOWER ADVERTIZED PRICE IN THIS MONTHS BYTE AND WE WILL BEAT IT BY 5 Figure 1 Schematic diagram of mapping in a linear congruential generator LCG Each successive term in the series is larger than the preceding This series does not imitate a random series but it is the first step in that direction See figure 2 STREAMING TAPE BACKUP 4 amp amp APPLE EXPANSIONS ULTRATERM 40 TO 160 COLUMNS 5 amp PRINTERS amp CPS Figure 2 Schematic of an LCG showing how the division of the number line into equal intervals m can produce pseudorandom numbers The location of each number inside the corresponding interval is haphazard IL results from using the modulus function TETON DIGITAL GROUP BOX 20320 JACKSON WY
32. t of the shuffled deck before starting In a similar way the success of the shuffled LCG depends on the two series having ap propriate relationships between them The efficiency of the shuffling tech nique is quite spectacular For in stance from a pair of LCGs with periods of only 8 and 9 you can generate a pseudorandom series with a period greater than 200 By tailor ing the pair of LCGs to the word length of the computer you can create shuffled LCGs with much longer periods Listing 1 is a BASIC shuffling pro AMPLITUDE 8 40 gram that generates a random walk consisting of NG groups of NS steps and prints the displacement after each group By analyzing this listing you can develop a random number subroutine suitable for virtually any computer Notice that subroutine 1010 initializes the program by filling the piles with numbers as in laying out the five piles of cards described above The program uses two distinct LCGs and their parameters are listed in statement 32 Before demonstrat ing the power of this program will describe how selected these parameters TAILORING A SHUFFLED LCG I looked for the largest modulus and the largest multiplier consistent with continued FREQUENCY Figure 6 Amplitude spectrum for the Advanced BASIC random number generator showing the prevalence of certain cycles Frequency is the number of cycles in 64 000 steps The peak at about 4 corresp
33. the proper ties of random numbers ious to the order of terms in the series The mean value is one such property These statistical tests reveal how likely it is that a random process generated a certain series No statistical test is a sure bet and few tests are reliable in themselves Some pseudorandom series will pass one test with flying colors only to fail miserably in another Therefore you have to apply several different tests will apply some tests to the LCG and the generator that the IBM PC s Ad vanced BASIC supplies Then I ll dis cuss how to develop a more power ful random number generator that anyone can use Lets start with the simplest test determining the period of the series PERIOD You can determine a period by noting a series first number and then step ping through it while computing one number after another until the first number recurs that is until x x Then 1 1 is the period of the series In order to ensure that x is indeed the start of a repeat cycle the first few values x X can be saved for comparison with x Xp Figure 3 shows the unfortunate ef fect of a short period on the random continued HIGH PERFORMANCE LEADER EPROM PROGRAMMERS amp UV ERASERS UV MULTIERASER Circle 43 on inquiry card 3M diskettes 9 9A 4 10 or 16 sector Price 10 90 Price 100 Single sided 190 1 75 double density Double sided 2 45 2 30 double densit
34. ure of the importance of harmonic frequency nw in the data Large values of a or in dicate that the data has a significant component of variation with a period 2XIV MVI using listing 1 and figure 8 shows the corresponding amplitude spectrum The spectrum shows a wide and fair ly smooth distribution of frequencies and the period of this shuffled LCG is evidently very long A walk of this length represents a satisfactory type of pseudorandom number generator for use with 16 bit computers When 32 bit machines come along chang ing the parameters to take advantage of the greater range of integers will be fairly straightforward CONCLUDING REMARKS If you want to pursue the art of mak ing new generators recommend Donald E Knuth s three volume classic The Art of Computer Programming Reading MA Addison Wesley Pub lishing Co Vol 1 2nd ed 1974 Vol 2 2nd ed 1981 Vol 3 1973 I ve tried to show that the testing of random number generators is impor tant but not difficult In fact develop ing your own tests is an interesting game There is no single right way but the listing for the program provided here works quite well on my 16 bit machine 8
35. y a s u Certified Check Money Order Personal Check Allow up to 2 weeks for personal checks to clear Add 3 00 per 100 or part to each order for UPS shipping charges NJ Residents add 696 sales tax EXCHANGE INC 178 Route 206 South PO Box 993 Somerville N J 08876 201 874 5050 Circle 93 on inquiry card WHOLESALE PRICES PLUS 6 Hardware Software Supplies Accessories SOFTWARE RENTAL RENT LOTUS 1 2 3 99 00 dBase IlI 99 00 Annual Membership 8 00 Software Rental Library 25 00 16 Shipmaster Clover SC 29710 CALL 1 800 334 3818 In SC 831 8502 8 30 5 00 ET Monday Friday ENT 232 Lines RS 232 INTERFACE TESTER connects in series with any RS 232 interface LED s clearly display status of 7 functions TD RD RTS CTS DSR CD OTR e 39 95 All cash orders postpaid IL res add 6 sales tax we accept MC Visa Free new illustrated catalog of RS 232 in terface and testing equipment Phone 815 434 0846 Make checks payable to B B electronics MANUFACTURING COMPANY P 0 Box 1008B OTTAWA IL 61350 RANDOM NUMBERS special distribution laws the normal distribution for example but will consider only the ones that are in tended to produce uniformly distrib uted numbers If normalize an LCG my program should produce numbers in the range 0 to 1 0 with equal prob C 5 a ability However the numbers won t arrive in a perfectly uniform
Download Pdf Manuals
Related Search