Bibliography

[AES]

Advanced Encryption Standard (AES), National Institute of Standards and Technology, FIPS PUB 197 (November 2001). Available at http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.

[Agrell]

Agrell, Erik. http://webfiles.portal.chalmers.se/s2/research/kit/bounds/, table last updated July 2004.

[Allen]

Allen, Joseph H. Private communication.

[Alv]

Alverson, Robert. “Integer Division Using Reciprocals.” In Proceedings IEEE 10th Symposium on Computer Arithmetic, June 26–28, 1991, Grenoble, France, 186–190.

[Arndt]

Arndt, Jörg. Matters Computational: Ideas, Algorithms, Source Code. Springer-Verlag, 2010. Also available at http://www.jjj.de/fxt/#fxtbook.

[Aus1]

Found in a REXX interpreter subroutine written by Marc A. Auslander.

[Aus2]

Auslander, Marc A. Private communication.

[Baum]

D. E. Knuth attributes the ternary method to an unpublished memo from the mid-1970s by Bruce Baumgart, which compares about 20 different methods for bit reversal on the PDP10.

[Bern]

Bernstein, Robert. “Multiplication by Integer Constants.” Software—Practice and Experience 16, 7 (July 1986), 641–652.

[BGN]

Burks, Arthur W., Goldstine, Herman H., and von Neumann, John. “Preliminary Discussion of the Logical Design of an Electronic Computing Instrument, Second Edition” (1947). In Papers of John von Neumann on Computing and Computing Theory, Volume 12 in the Charles Babbage Institute Reprint Series for the History of Computing, MIT Press, 1987.

[Black]

Black, Richard. Web site www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/crc.html. University of Cambridge Computer Laboratory Systems Research Group, February 1994.

[Bonz]

Bonzini, Paolo. Private communication.

[Brou]

Brouwer, Andries E. http://www.win.tue.nl/~aeb/codes/binary-1.html, table last updated January 2012.

[CavWer]

Cavagnino, D. and Werbrouck, A. E. “Efficient Algorithms for Integer Division by Constants Using Multiplication.” The Computer Journal 51, 4 (2008), 470–480.

[CC]

Caldwell, Chris K. and Cheng, Yuanyou. “Determining Mills’ Constant and a Note on Honaker’s Problem.” Journal of Integer Sequences 8, 4 (2005), article 05.4.1, 9 pp. Also available at http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Caldwell/caldwell78.pdf.

[CJS]

Stephenson, Christopher J. Private communication.

[Cohen]

These rules were pointed out by Norman H. Cohen.

[Cplant]

Leung, Vitus J., et. al. “Processor Allocation on Cplant: Achieving General Processor Locality Using One-Dimensional Allocation Strategies.” In Proceedings 4th IEEE International Conference on Cluster Computing, September 2002, 296–304.

[Cut]

Cutland, Nigel J. Computability: An Introduction to Recursive Function Theory. Cambridge University Press, 1980.

[CWG]

Hoxey, Karim, Hay, and Warren (Editors). The PowerPC Compiler Writer’s Guide. Warthman Associates, 1996.

[Dalton]

Dalton, Michael. Private communication.

[Danne]

Dannemiller, Christopher M. Private communication. He attributes this code to the Linux Source base, www.gelato.unsw.edu.au/lxr/source/lib/crc32.c, lines 105–111.

[DES]

Data Encryption Standard (DES), National Institute of Standards and Technology, FIPS PUB 46-2 (December 1993). Available at http://www.itl.nist.gov/fipspubs/fip46-2.htm.

[Dewd]

Dewdney, A. K. The Turing Omnibus. Computer Science Press, 1989.

[Dietz]

Dietz, Henry G. http://aggregate.org/MAGIC/.

[Ditlow]

Ditlow, Gary S. Private communication.

[Dubé]

Dubé, Danny. Newsgroup comp.compression.research, October 3, 1997.

[Dud]

Dudley, Underwood. “History of a Formula for Primes.” American Mathematics Monthly 76 (1969), 23–28.

[EL]

Ercegovac, Miloš D. and Lang, Tomás. Division and Square Root: Digit-Recurrence Algorithms and Implementations. Kluwer Academic Publishers, 1994.

[Etzion]

Etzion, Tuvi. “Constructions for Perfect 2-Burst-Correcting Codes,” IEEE Transactions on Information Theory 47, 6 (September 2001), 2553–2555.

[Floyd]

Floyd, Robert W. “Permuting Information in Idealized Two-Level Storage.” In Complexity of Computer Computations (Conference proceedings), Plenum Press, 1972, 105–109. This is the earliest reference I know of for this method of transposing a 2ⁿ × 2ⁿ matrix.

[Gard]

Gardner, Martin. “Mathematical Games” column in Scientific American 227, 2 (August 1972), 106–109.

[Gaud]

Gaudet, Dean. Private communication.

[GGS]

Gregoire, Dennis G., Groves, Randall D., and Schmookler, Martin S. Single Cycle Merge/Logic Unit, US Patent No. 4,903,228, February 20, 1990.

[GK]

Granlund, Torbjörn and Kenner, Richard. “Eliminating Branches Using a Superoptimizer and the GNU C Compiler.” In Proceedings of the 5th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), July 1992, 341–352.

[GKP]

Graham, Ronald L., Knuth, Donald E., and Patashnik, Oren. Concrete Mathematics: A Foundation for Computer Science, Second Edition. Addison-Wesley, 1994.

[GLS1]

Steele, Guy L., Jr. Private communication.

[GLS2]

Steele, Guy L., Jr. “Arithmetic Shifting Considered Harmful.” AI Memo 378, MIT Artificial Intelligence Laboratory (September 1976); also in SIGPLAN Notices 12, 11 (November 1977), 61–69.

[GM]

Granlund, Torbjörn and Montgomery, Peter L. “Division by Invariant Integers Using Multiplication.” In Proceedings of the ACM SIGPLAN ’94 Conference on Programming Language Design and Implementation (PLDI), August 1994, 61–72.

[Gold]

The second expression is due to Richard Goldberg.

[Good]

Goodstein, Prof. R. L. “Formulae for Primes.” The Mathematical Gazette 51 (1967), 35–36.

[Gor]

Goryavsky, Julius. Private communication.

[GSO]

Found by the GNU Superoptimizer.

[HAK]

Beeler, M., Gosper, R. W., and Schroeppel, R. HAKMEM, MIT Artificial Intelligence Laboratory AIM 239, February 1972.

[Ham]

Hamming, Richard W., “Error Detecting and Error Correcting Codes,” The Bell System Technical Journal 26, 2 (April 1950), 147–160.

[Harley]

Harley, Robert. Newsgroup comp.arch, July 12, 1996.

[Hay1]

Hay, R. W. Private communication.

[Hay2]

The first expression was found in a compiler subroutine written by R. W. Hay.

[Hil]

Hilbert, David. “Ueber die stetige Abbildung einer Linie auf ein Flächenstück.” Mathematischen Annalen 38 (1891), 459–460.

[Hill]

Hill, Raymond. A First Course in Coding Theory. Clarendon Press, 1986.

[HilPat]

Hiltgen, Alain P. and Paterson, Kenneth G. “Single-Track Circuit Codes.” IEEE Transactions on Information Theory 47, 6 (2001) 2587-2595.

[Hop]

Hopkins, Martin E. Private communication.

[HS]

Hillis, W. Daniel and Steele, Guy L., Jr. “Data Parallel Algorithms.” Comm. ACM 29, 12 (December 1986) 1170–1183.

[Hsieh]

Hsieh, Paul. Newsgroup comp.lang.c, April 29, 2005.

[Huef]

Hueffner, Falk. Private communication.

[H&P]

Hennessy, John L. and Patterson, David A. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 1990.

[H&S]

Harbison, Samuel P. and Steele, Guy L., Jr. C: A Reference Manual, Fourth Edition. Prentice-Hall, 1995.

[H&W]

Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, Fourth Edition. Oxford University Press, 1960.

[IBM]

From an IBM programming course, 1961.

[Irvine]

Irvine, M. M. “Early Digital Computers at Bell Telephone Laboratories.” IEEE Annals of the History of Computing 23, 3 (July–September 2001), 22–42.

[JVN]

von Neumann, John. “First Draft of a Report on the EDVAC.” In Papers of John von Neumann on Computing and Computing Theory, Volume 12 in the Charles Babbage Institute Reprint Series for the History of Computing, MIT Press, 1987.

[Karat]

Karatsuba, A. and Ofman, Yu. “Multiplication of multidigit numbers on automata.” Soviet Physics-Doklady 7, 7 (January 1963), 595–596. They show the theoretical result that multiplication of m-bit integers is O(m^log₂3) ≈ O(m^1.585), but the details of their method are more cumbersome than the method based on Gauss’s three-multiplication scheme for complex numbers.

[Karv]

Karvonen, Vesa. Found at “The Assembly Gems” web page, www.df.lth.se/~john_e/fr_gems.html.

[Keane]

Keane, Joe. Newsgroup sci.math.num-analysis, July 9, 1995.

[Ken]

Found in a GNU C compiler for the IBM RS/6000 that was ported by Richard Kenner. He attributes this to a 1992 PLDI conference paper by him and Torbjörn Granlund.

[Knu1]

Knuth, Donald E. The Art of Computer Programming, Volume 1, Third Edition: Fundamental Algorithms. Addison-Wesley, 1997.

[Knu2]

Knuth, Donald E. The Art of Computer Programming, Volume 2, Third Edition: Seminumerical Algorithms. Addison-Wesley, 1998.

[Knu3]

The idea of using a negative integer as the base of a number system for arithmetic has been independently discovered by many people. The earliest reference given by Knuth is to Vittorio Grünwald in 1885. Knuth himself submitted a paper on the subject in 1955 to a “science talent search” for high-school seniors. For other early references, see [Knu2].

[Knu4]

Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Section 7.1.1. Addison-Wesley, 2011.

[Knu5]

Ibid, Section 7.1.3. Knuth attributes the equality relation to W. C. Lynch in 2006.

[Knu6]

Ibid, Section 7.2.1.1, Exercise 80.

[Knu7]

Knuth, Donald E. The Art of Computer Programming, Volume 1, Fascicle 1: MMIX—A RISC Computer for the New Millennium. Addison-Wesley, 2005.

[Knu8]

Knuth, Donald E. Private communication.

[KRS]

Kruskal, Clyde P., Rudolph, Larry, and Snir, Marc. “The Power of Parallel Prefix.” IEEE Transactions on Computers C-34, 10 (October 1985), 965–968.

[Kumar]

This figure was suggested by Gowri Kumar (private communication).

[Lamp]

Lamport, Leslie. “Multiple Byte Processing with Full-Word Instructions.” Communications of the ACM 18, 8 (August 1975), 471–475.

[Lang]

Langdon, Glen G. Jr., “Subtraction by Minuend Complementation,” IEEE Transactions on Computers C-18, 1 (January 1969), 74–76.

[LC]

Lin, Shu and Costello, Daniel J., Jr. Error Control Coding: Fundamentals and Applications. Prentice-Hall, 1983.

[Lomo]

Lomont, Chris. Fast Inverse Square Root. www.lomont.org/Math/Papers/2003/InvSqrt.pdf.

[LPR]

Leiserson, Charles E., Prokop, Harald, and Randall, Keith H. Using de Bruijn Sequences to Index a 1 in a Computer Word. MIT Laboratory for Computer Science, July 7, 1998. Also available at http://supertech.csail.mit.edu/papers/debruijn.pdf.

[LSY]

Lee, Ruby B., Shi, Zhijie, and Yang, Xiao. “Efficient Permutation Instructions for Fast Software Cryptography.” IEEE Micro 21, 6 (November/December 2001), 56–69.

[L&S]

Lam, Warren M. and Shapiro, Jerome M. “A Class of Fast Algorithms for the Peano-Hilbert Space-Filling Curve.” In Proceedings ICIP 94, 1 (1994), 638–641.

[MD]

Denneau, Monty M. Private communication.

[MIPS]

Kane, Gerry and Heinrich, Joe. MIPS RISC Architecture. Prentice-Hall, 1992.

[MM]

Morton, Mike. “Quibbles & Bits.” Computer Language 7, 12 (December 1990), 45–55.

[Möbi]

Möbius, Stefan K. Private communication.

[MS]

MacWilliams, Florence J. and Sloane, Neil J. A. The Theory of Error-Correcting Codes, Part II. North-Holland, 1977.

[Mycro]

Mycroft, Alan. Newsgroup comp.arch, April 8, 1987.

[Neum]

Neumann, Jasper L. Private communication.

[NZM]

Niven, Ivan, Zuckerman, Herbert S., and Montgomery, Hugh L. An Introduction to the Theory of Numbers, Fifth Edition. John Wiley & Sons, Inc., 1991.

[PeBr]

Peterson, W. W. and Brown, D. T. “Cyclic Codes for Error Detection.” In Proceedings of the IRE, 1 (January 1961), 228–235.

[PHO]

Oden, Peter H. Private communication.

[PL8]

I learned this trick from the PL.8 compiler.

[PuBr]

Purdom, Paul Walton Jr., and Brown, Cynthia A. The Analysis of Algorithms. Holt, Rinehart and Winston, 1985.

[Reiser]

Reiser, John. Newsgroup comp.arch.arithmetic, December 11, 1998.

[Rib]

Ribenboim, Paulo. The Little Book of Big Primes. Springer-Verlag, 1991. An earlier source of this technique, described in considerable detail, is Crocker, Steve. “A Note on Padding.” In Network Working Group Request for Comments (RFC) #70, 15 October 1970, UCLA. Available on the web.

[RND]

Reingold, Edward M., Nievergelt, Jurg, and Deo, Narsingh. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, 1977.

[Roman]

Roman, Steven. Coding and Information Theory. Springer-Verlag, 1992.

[Sagan]

Sagan, Hans. Space-Filling Curves. Springer-Verlag, 1994. A wonderful book, thoroughly recommended to anyone even slightly interested in the subject.

[Seal1]

Seal, David. Newsgroup comp.arch.arithmetic, May 13, 1997. Harley was the first known to this writer to apply the CSA to this problem, and Seal showed a particularly good way to use it for counting the bits in a large array (as illustrated in Figures 5–8 and 5–9), and also for an array of size seven (similar to the plan of Figure 5–10).

[Seal2]

Seal, David. Newsgroup comp.sys.acorn.tech, February 16, 1994.

[Shep]

Shepherd, Arvin D. Private communication.

[Stall]

Stallman, Richard M. Using and Porting GNU CC. Free Software Foundation, 1998.

[Strach]

Strachey, Christopher. “Bitwise Operations.” Communications of the ACM 4, 3 (March 1961), 146. This issue contains another paper that gives two methods for bit reversal (“Two Methods for Word Inversion on the IBM 709,” by Robert A. Price and Paul Des Jardins; there is a small correction on page A13 of the March 1961 issue). These methods are not discussed in this book because they rely on the somewhat exotic Convert by Addition from the MQ (CAQ) instruction of that machine. That instruction does a series of indexed table lookups, adding the word fetched from memory to the accumulator. It is not a RISC instruction.

[Tanen]

Tanenbaum, Andrew S. Computer Networks, Second Edition. Prentice Hall, 1988.

[Taro]

The author of this program seems to be lost in history. One of the earliest people to use it and to tweak the constant a bit was Gary Tarolli, probably while he was at SGI. He also helped to make it more widely known and says it goes back to 1995 or earlier. For more on the history see http://www.beyond3d.com/content/articles/8/.

[Voor]

Voorhies, Douglas. “Space-Filling Curves and a Measure of Coherence.” Graphics Gems II, AP Professional (1991).

[War]

Warren, H. S., Jr. “Functions Realizable with Word-Parallel Logical and Two’s-Complement Addition Instructions.” Communications of the ACM 20, 6 (June 1977), 439–441.

[Weg]

The earliest reference to this that I know of is: Wegner, P. A. “A Technique for Counting Ones in a Binary Computer.” Communications of the ACM 3, 5 (May 1960), 322.

[Wells]

Wells, David. The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, 1997.

[Will]

Willans, C. P. “On Formulae for the nth Prime Number.” The Mathematical Gazette 48 (1964), 413–415.

[Wood]

Woodrum, Luther. Private communication. The second formula uses no literals and works well on the IBM System/370.

[Wor]

Wormell, C. P. “Formulae for Primes.” The Mathematical Gazette 51 (1967), 36–38.

[Zadeck]

Zadeck, F. Kenneth. Private communication.