c20-2 (779624)
Текст из файла
894Chapter 20.Less-Numerical Algorithms}Some typical values returned by machar are given in the table, above. IEEEcompliant machines referred to in the table include most UNIX workstations (SUN,DEC, MIPS), and Apple Macintosh IIs. IBM PCs with floating co-processorsare generally IEEE-compliant, except that some compilers underflow intermediateresults ungracefully, yielding irnd = 2 rather than 5. Notice, as in the case of a VAX(fourth column), that representations with a “phantom” leading 1 bit in the mantissaachieve a smaller eps for the same wordlength, but cannot underflow gracefully.CITED REFERENCES AND FURTHER READING:Goldberg, D. 1991, ACM Computing Surveys, vol.
23, pp. 5–48.Cody, W.J. 1988, ACM Transactions on Mathematical Software, vol. 14, pp. 303–311. [1]Malcolm, M.A. 1972, Communications of the ACM, vol. 15, pp. 949–951. [2]IEEE Standard for Binary Floating-Point Numbers, ANSI/IEEE Std 754–1985 (New York: IEEE,1985).
[3]20.2 Gray CodesA Gray code is a function G(i) of the integers i, that for each integer N ≥ 0is one-to-one for 0 ≤ i ≤ 2N − 1, and that has the following remarkable property:The binary representation of G(i) and G(i + 1) differ in exactly one bit. An exampleof a Gray code (in fact, the most commonly used one) is the sequence 0000, 0001,0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, and1000, for i = 0, .
. . , 15. The algorithm for generating this code is simply to formthe bitwise exclusive-or (XOR) of i with i/2 (integer part). Think about how thecarries work when you add one to a number in binary, and you will be able to seewhy this works. You will also see that G(i) and G(i + 1) differ in the bit position ofthe rightmost zero bit of i (prefixing a leading zero if necessary).The spelling is “Gray,” not “gray”: The codes are named after one Frank Gray,who first patented the idea for use in shaft encoders. A shaft encoder is a wheel withconcentric coded stripes each of which is “read” by a fixed conducting brush. Theidea is to generate a binary code describing the angle of the wheel.
The obvious,but wrong, way to build a shaft encoder is to have one stripe (the innermost, say)conducting on half the wheel, but insulating on the other half; the next stripe isconducting in quadrants 1 and 3; the next stripe is conducting in octants 1, 3, 5,Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).point at extreme right of mantissa.if (*ibeta == 2 && !i) --(*maxexp);if (i > 20) --(*maxexp);if (a != y) *maxexp -= 2;*xmax=one-(*epsneg);if ((*xmax)*one != *xmax) *xmax=one-beta*(*epsneg);*xmax /= (*xmin*beta*beta*beta);i=(*maxexp)+(*minexp)+3;for (j=1;j<=i;j++) {if (*ibeta == 2) *xmax += *xmax;else *xmax *= beta;}89520.2 Gray CodesMSB43XOR32XOR21XOR10LSBXOR0G(i)(a)MSB43G (i)210LSB43XOR2XORi1XORXOR0(b)Figure 20.2.1.
Single-bit operations for calculating the Gray code G(i) from i (a), or the inverse (b).LSB and MSB indicate the least and most significant bits, respectively. XOR denotes exclusive-or.and 7; and so on. The brushes together then read a direct binary code for theposition of the wheel.The reason this method is bad, is that there is no way to guarantee that all thebrushes will make or break contact exactly simultaneously as the wheel turns.
Goingfrom position 7 (0111) to 8 (1000), one might pass spuriously and transiently through6 (0110), 14 (1110), and 10 (1010), as the different brushes make or break contact.Use of a Gray code on the encoding stripes guarantees that there is no transient statebetween 7 (0100 in the sequence above) and 8 (1100).Of course we then need circuitry, or algorithmics, to translate from G(i) to i.Figure 20.2.1 (b) shows how this is done by a cascade of XOR gates. The idea isthat each output bit should be the XOR of all more significant input bits. To doN bits of Gray code inversion requires N − 1 steps (or gate delays) in the circuit.(Nevertheless, this is typically very fast in circuitry.) In a register with word-widebinary operations, we don’t have to do N consecutive operations, but only ln2 N .The trick is to use the associativity of XOR and group the operations hierarchically.This involves sequential right-shifts by 1, 2, 4, 8, .
. . bits until the wordlength isSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).i4896Chapter 20.Less-Numerical Algorithmsexhausted. Here is a piece of code for doing both G(i) and its inverse.if (is >= 0)This is the easy direction!return n ^ (n >> 1);ish=1;This is the more complicated direction: In hierarchicalans=n;stages, starting with a one-bit right shift, cause eachfor (;;) {bit to be XORed with all more significant bits.ans ^= (idiv=ans >> ish);if (idiv <= 1 || ish == 16) return ans;ish <<= 1;Double the amount of shift on the next cycle.}}In numerical work, Gray codes can be useful when you need to do some taskthat depends intimately on the bits of i, looping over many values of i.
Then, if thereare economies in repeating the task for values differing by only one bit, it makessense to do things in Gray code order rather than consecutive order. We saw anexample of this in §7.7, for the generation of quasi-random sequences.CITED REFERENCES AND FURTHER READING:Horowitz, P., and Hill, W. 1989, The Art of Electronics, 2nd ed.
(New York: Cambridge UniversityPress), §8.02.Knuth, D.E. Combinatorial Algorithms, vol. 4 of The Art of Computer Programming (Reading,MA: Addison-Wesley), §7.2.1. [Unpublished. Will it be always so?]20.3 Cyclic Redundancy and Other ChecksumsWhen you send a sequence of bits from point A to point B, you want to knowthat it will arrive without error.
A common form of insurance is the “parity bit,”attached to 7-bit ASCII characters to put them into 8-bit format. The parity bit ischosen so as to make the total number of one-bits (versus zero-bits) either alwayseven (“even parity”) or always odd (“odd parity”). Any single bit error in a characterwill thereby be detected. When errors are sufficiently rare, and do not occur closelybunched in time, use of parity provides sufficient error detection.Unfortunately, in real situations, a single noise “event” is likely to disrupt morethan one bit. Since the parity bit has two possible values (0 and 1), it gives, onaverage, only a 50% chance of detecting an erroneous character with more than onewrong bit.
That probability, 50%, is not nearly good enough for most applications.Most communications protocols [1] use a multibit generalization of the parity bitcalled a “cyclic redundancy check” or CRC. In typical applications the CRC is 16bits long (two bytes or two characters), so that the chance of a random error goingundetected is 1 in 216 = 65536. Moreover, M -bit CRCs have the mathematicalSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).unsigned long igray(unsigned long n, int is)For zero or positive values of is, return the Gray code of n; if is is negative, return the inverseGray code of n.{int ish;unsigned long ans,idiv;.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
