Arndt - Algorithms for Programmers (523138), страница 47
Текст из файла (страница 47)
The first and last words have to match:....1...11.1.11.1111..111..1.1A Gray code can now be obtained by appending rotated versions of the block like this (at each stage, theblock is left-rotated by two):....1...11.1.11.1111..111..1.1..1...11...11.1111.1111..1.1..1....1...11.1.11.1111..111..1....1...11.1.11.1111..111.CHAPTER 12. SHIFT REGISTER SEQUENCES275.1.1..1...11...11.1.11.1111..1.1..1By construction the number of zero-one transitions is equal for each track. The given sequence omits thetwo words we discarded above. The zero could of course be prepended, the all-ones word, however, doesnot fit in.
One exception is n = 3 were a monotonic Gray code is obtained:.....1.11.1.11.1..1.1111A complementary (the second half of the code is the inverted first half) 4-bit code is easily obtained:.......1..11..1..11..1...1.1.1111111111.11..11.11..11.111.1.1...The construction works only if the word length is prime, only then it is guaranteed that the n cyclicshifts of the block contain all different words.Here is how it fails for composite n: the construction with necklaces for n = 4 gives...1.1.1.111..11..1.1.1.111..11..1...1.1(!)11.111..1...1.1.(!)1.111..1Note all hope is lost.
Deleting the elements where they appear for the second time, reordering andinserting the zero and the word of ones we get.......1.1.1.111..11..1.1.1.111..11..1..11..11.111111.111..11...0123212321234321Transition counts are equal for each track. The numbers of the right column are bit counts.For n = 7 one can use one of these (handwoven) blocks of length 18......1....1.1..1.1.1..111.1...11.1...1..1...1.11.1.1.11.1.1111...1111....111..1.111.11.111.111111..11111..11.11..1..11.....111......11.....11..1..11.11..11.1...1111...11111..111111.1111.1..111.1..111.11.111..1.111....1.1....1.1.1.11.1.1.11...1..1...1.CHAPTER 12. SHIFT REGISTER SEQUENCES276and six consecutive copies that are rotated left by one (right by one for the right block).A degree of freedom that can be use is that the words in the basic block can be rotated at will.
Forexample, for n = 5 one could use either of....11...111..1111.11.1.1..1.1....1...11..111.1111.1.11.1..1....1...11.1.11.1.1..111.1111.Now use the elements of the third basic block in pairs that match to get a3 monotonic Gray code:.........1...11...1...11...1...11...1...11...1....1...11.1.11.1..1.11.1..1.11.1..1.1..1.11.1..1.11.1..1.1..111.1111.111.1111.111..111.111..111.111..111.11111111012345678910111213141516171819202122232425262728293031.........1...11.1.11..1.1..111.111111111The first appearance of the necklaces is indicated on the right. Reordering slightly (not separating theruns of necklaces) we get a Gray code that is monotonic in two ways. The code on the right side is the‘unwrapped’ version:012345678910111213141516171819202122232425262728293031.....1....11....1....11....1....11....1....11....11...11.1.11.1..1.11.1..1.11.1..1.1..1.11.1..1.11.1..1.1..1111.1111..1111.1111..1111.1111..1111..111..111111111098765432110111213141516171819202130292827262524232231.........1...11.1.11..1.1..111.111111111098765432110111213141516171819202130292827262524232231.....1....11....1....11....1....11....1....11....1...11.11.1..1.1.1.11.1..1.11.1..1.1.1.11.1..1.11.1..1.1..111.1111..111.1111..111.1111..111.1111..111.111111111The negated sequence in reversed order is (if bit positions are taken as [01234]) identical to the originalwhen the bits are reordered as [04321] (that is, permuted as if indices multiplied with minus one modulofive).An analogue basic block for a 7-bit monotone Gray code would be:3 Thisactually is the Savage-Winkler Gray code for n = 5, I constructed it by hand using my editor.CHAPTER 12.
SHIFT REGISTER SEQUENCES........1.....11.....11..1..1...1..1...1.1....1.1...11.1..111.1..1.1.1..1.111....111...1111.1.1111.1.1.11.111.11..11.11..11111.111111111111101232323434345454567277.............1.....11..1..11...1..1...1.11....1.1...11.1..111.1..1.1.1..1.111....111...1111.1.1111.1.1.11.11.111..11.11..11111.1111111111111A slight reordering gives the (reversed-negated) symmetry we have seen for n = 5:........1.....11.....11..1..1...1..1...1.1....1.1....111..1.111..1.1.11.1.1.11.1...1111...1111.1.1111.1..111.11.11..11.11..11111.1111111111101232323434345454567.............1.....11..1..11...1..1...1.11....1.1....111..1.111..1.1.1.1.1.11...11.1...1111.1.1111..111.1.11.111..11.11..11111.1111111111111The right column gives the cyclic minimum (necklace). However, it is not possible to build a monotonicGray code for n > 5 where pairs of necklaces appear interlaced in all their cyclic shifts.
The reason is,that the pairs have to match in two ways. Take, as an example the two necklaces ..1.1 and .1.11 andn = 5:1.1.11.1..1.11.1..1.11.1..1.1..1.11.1..1.11.1..1.1.11.1..1.1.1.11.1..1.11.1..1.1.1.11.1..1.11.1..1.1The same two necklaces match in just one way with n = 7.When we sort the necklaces by their bit-count and tabulate the ways necklace k matches with necklacej we get the following matrix for n = 5:0:1:2:3:4:5:6:7:^k01234567 < j01223345 < bit_count(necklace[j])p=0 .*......
00.....p=1 *.22.... 12....1p=2 .2..12.. 22...11p=2 .2..21.. 32..1.1p=3 ..12..2. 4211.1.p=3 ..21..2. 52111..p=4 ....22.* 621111.p=5 ......*. 7011111p=^^^^bitcountknumber ofnecklacetwos in rowperiod15555551Here a dot is used for zero and an asterisk is used when all cyclic shifts match. The matrix for n = 7 is0101234567890123456789012223333344444555670:0 .*..................1:1 *.222...............2:2 .2...2111...........012(!)v0 .......3 ......12 .....11p= 1p= 7p= 7CHAPTER 12. SHIFT REGISTER SEQUENCES3:24:25:36:37:38:39:310:411:412:413:414:415:516:517:518:6.2...111.2...........2....1121............21........112.......111.....111.1.......111.....11.11.......1.2......211.........21.....2.11............11.2.....12.........112......2.1.......11.11.....111.......1.111.....111.......211........12............1211....2...........2.111...2............1112...2................222.*34567891011121314151617182220022220022223....1.1...1..1....111...1.11...11.1..1..11..1.1.111.1.1.11.11..111..1.111.1..1111...111.11.1111.1.11111..111111.p=p=p=p=p=p=p=p=p=p=p=p=p=p=p=p=2787777777777777777There are four necklaces that have no ‘double-match’ with, the non-terminal entries that have a zero inthe column marked with (!).
These stay alone for all n > 7 as no possible matches enter.Still, some interesting structures can be found. Choosing the 3-element sequences from the basic blockfor n = 7 gives a minimal-change sequence of 3-combinations out of 7:...1.11..1..11..1.1.1...11.1....111..1.11..1..11..1.1.1...11.1....111..1.11..1..11..1.1.1...11.1....111..1.11.....11..1.1.1..111.1....111....11...1.11..1.1.1..1.1.1...1111....11...1.11..1...1..1.1.1...1111....11...1.11..1..11..1.1.1...11.1....11Chapter 13Arithmetical algorithms13.1Asymptotics of algorithmsAn important feature of an algorithm is the number of operations that must be performed for thecompletion of a task of a certain size N .
The quantity N should be some reasonable quantity that growsstrictly with the size of the task. For high precision computations one will take the length of the numberscounted in decimal digits or bits. For computations with square matrices one may take for N the numberof rows. An operation is typically a (machine word) multiplication plus an addition, one could also simplycount machine instructions.An algorithm is said to have some asymptotics f (N ) if it needs proportional f (N ) operations for a taskof size N .Examples:• Addition of an N -digit number needs proportional N operations (here: machine word addition plussome carry operation).• Ordinary multiplication needs ∼ N 2 operations.• The Fast Fourier Transform (FFT) needs ∼ N log(N ) operations (a straight forward implementation of the Fourier Transform, i.e.
computing N sums each of length N would be ∼ N 2 ).• Matrix multiplication (by the obvious algorithm) is ∼ N 3 (N 2 sums each of N products).The algorithm with the ‘best’ asymptotics wins for some, possibly huge, N . For smaller N anotheralgorithm will be superior. For the exact break-even point the constants omitted elsewhere are of courseimportant.Example: Let the algorithm mult1 take 1.0 · N 2 operations, mult2 take 8.0 · N log2 (N ) operations. Then,for N < 64 mult1 is faster and for N > 64 mult2 is faster. Completely different algorithms may beoptimal for the same task at different problem sizes.13.2Multiplication of large numbersOrdinary multiplication is ∼ N 2 . Computing the product of two million-digit numbers would require≈ 1012 operations, taking about 1 day on a machine that does 10 million operations per second (MIPS).But there are better ways .
. .279CHAPTER 13. ARITHMETICAL ALGORITHMS13.2.1280The Karatsuba algorithmSplit the numbers U and V (assumed to have approximately the same length/precision) in two piecesUV= U0 + U1 B= V0 + V1 B(13.1)Where B is a power of the radix1 (or base) close to the half length of U and V .Instead of the straight forward multiplication that needs 4 multiplications with half precision for onemultiplication with full precision= U0 V0 + B(U0 V1 + V0 U1 ) + B 2 U1 V1UV(13.2)use the relationUV(1 + B)U0 V0 + B(U1 − U0 )(V0 − V1 ) + (B + B 2 )U1 V1=(13.3)which needs 3 multiplications with half precision for one multiplication with full precision.Apply the scheme recursively until the numbers to multiply are of machine size. The asymptotics of thealgorithm is ∼ N log2 (3) ≈ N 1.585 .For squaring useU2(1 + B)U02 − B(U1 − U0 )2 + (B + B 2 )U12=(13.4)or= (1 − B)U02 + B(U1 + U0 )2 + (−B + B 2 )U12U2(13.5)One can extend the above idea by splitting U and V into more than two pieces each, the resultingalgorithm is called Toom Cook algorithm.Computing the product of two million-digit numbers would require ≈ (106 )1.585 ≈ 3200 · 106 operations,taking about 5 minutes on the 10 MIPS machine.See [11], chapter 4.3.3 (‘How fast can we multiply?’).13.2.2Fast multiplication via FFTMultiplication of two numbers is essentially a convolution of the sequences of their digits.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
