About this title This text explains the fundamental principles of algorithms available for performing arithmetic operations on digital computers. These include basic arithmetic operations like addition, subtraction, multiplication, and division in fixed-point and floating-point number systems as well as more complex operations such as square root extraction and evaluation of exponential, logarithmic, and trigonometric functions. The algorithms described are independent of the particular technology employed for their implementation. From the Publisher: An explanation of the fundamental principles of the algorithms available for performing arithmetic operations in digital computers. From the Back Cover: Key Benefit: Including numerical examples to illustrate the workings of the algorithms presented, this new text explains the fundamental principles of the algorithms available for performing arithmetic operations in digital computers.
|Published (Last):||7 June 2007|
|PDF File Size:||3.33 Mb|
|ePub File Size:||1.58 Mb|
|Price:||Free* [*Free Regsitration Required]|
Preface The context of computer arithmetic Advances in computer architecture over the past two decades have allowed the performance of digital computer hardware to continue its exponential growth, despite increasing technological difficulty in speed improvement at the circuit level.
This phenomenal rate of growth, which is expected to continue in the near future, would not have been possible without theoretical insights, experimental research, and tool-building efforts that have helped transform computer architecture from an art into one of the most quantitative branches of computer science and engineering.
Better understanding of the various forms of concurrency and the development of a reasonably efficient and user-friendly programming model have been key enablers of this success story. The down side of exponentially rising processor performance is an unprecedented increase in hardware and software complexity. The trend toward greater complexity is not only at odds with testability and certifiability but also hampers adaptability, performance tuning, and evaluation of the various tradeoffs, all of which contribute to soaring development costs.
A key challenge facing current and future computer designers is to reverse this trend by removing layer after layer of complexity, opting instead for clean, robust, and easily certifiable designs; to devise novel methods for gaining performance and ease-of-use benefits from simpler circuits that can be readily adapted to application requirements. It is one of oldest subfields of computer architecture. Many of the ingenious design methods that we use today have their roots in the bulky, power-hungry machines of years ago.
In fact computer arithmetic has been so successful that it has, at times, become transparent. Correctness and high performance of arithmetic circuits is routinely expected and episodes such as the Intel Pentium division bug are indeed rare.
The preceding context is changing due to several factors. First, at very high clock rates, the interfaces between arithmetic circuits and the rest of the processor become critical. Arithmetic units can no longer be designed and verified in isolation. Rather, an integrated design optimization is required which makes the development even more complex and costly. Second, optimizing arithmetic circuits to meet design goals by taking advantage of the strengths of new technologies, and making them tolerant to the weaknesses, requires a reexamination of existing design paradigms.
Finally, Incorporation of higher-level arithmetic primitives into hardware makes the design, optimization, and verification efforts highly complex and interrelated. This is why computer arithmetic is alive and well today. Designers and researchers in this area produce novel structures with amazing regularity. A case in point is carry-lookahead adders. We used to think, in the not so distant past, that we know all there is to know about carry-lookahead fast adders.
Yet, new designs, improvements, and optimizations are still appearing as of this writing. Given the arithmetic-intensive nature of many novel application areas such as encryption, error checking, and multimedia , computer arithmetic will continue to thrive for years to come.
The goals and structure of this book The field of computer arithmetic has matured to the point that a dozen or so texts and reference books have been published. Each of these books has its unique strengths and has contributed to the formation and fruition of the field. The current text, Computer Arithmetic: Algorithms and Hardware Designs, is an outgrowth of lecture notes that the author has developed and refined over many years.
Here are the most important features of this text in comparison to the listed books: a. Division of material into lecture-size chapters: In my approach to teaching, a lecture is a more or less self-contained module with links to past lectures and pointers to what will transpire in future. Each lecture must have a theme or title and must proceed from motivation, to details, to conclusion.
In designing the text, I have strived to divide the material into chapters, each of which is suitable for one lecture hours. A short lecture can cover the first few subsections while a longer lecture can deal with variations, peripheral ideas, or more advanced material near the end of the chapter. To make the structure hierarchical, as opposed to flat or linear, lectures are grouped into seven parts, each composed of four lectures and covering one aspect of the field Fig.
Emphasis on both the underlying theory and actual hardware designs: The ability to cope with complexity requires both a deep knowledge of the theoretical underpinnings of computer arithmetic and examples of designs that help us understand the theory.
Such designs also provide building blocks for synthesis as well as reference points for cost-performance comparisons. This viewpoint is reflected, e. Linking computer arithmetic to other subfields of computing: Computer arithmetic is nourished by, and in turn nourishes, other subfields of computer architecture and technology. Examples of such links abound. The design of carry-lookahead adders became much more systematic once it was realized that the carry computation is a special case of parallel prefix computation which had been extensively studied by researchers in parallel computing.
The residue number system has provided an invaluable tool for researchers interested in complexity theory and limits of fast arithmetic as well as to the designers of fault-tolerant systems. Coverage of unconventional number representation methods Chapters , arithmetic by table-lookup Chapter 24 , which is becoming increasingly important, multiplication and division by constants Chapters 9 and 13 , errors and certifiable arithmetic Chapters , and the topics in Part VII Chapters do not all appear in other textbooks.
For example, r always stands for the number representation radix and s for the remainder in division or square-rooting. While other authors have done this in the basic parts of their texts, there is a tendency to cover more advanced research topics by simply borrowing the notation and terminology from the reference source. Such an approach has the advantage of making the transition between reading the text and the original reference source easier, but it is utterly confusing to the majority of the students who rely on the text and do not consult the original references except, perhaps, to write a research paper.
Summary of topics The seven parts of this book, each composed of four chapters, have been written with the following goals: Part I sets the stage, gives a taste of what is to come, and provides a detailed perspective on the various ways of representing fixed-point numbers.
Included are detailed discussions of signed numbers, redundant representations, and residue number systems. Part II covers addition and subtraction that form the most basic arithmetic building blocks and are often used in implementing other arithmetic operations. Included in the discussions are addition of a constant counting , various methods for designing fast adders, and multi-operand addition.
Part III deals exclusively with multiplication, beginning with the basic shift-add algorithms and moving on to high-radix, tree, array, bit-serial, modular, and a variety of other multipliers. The special case of squaring is also discussed. Part IV covers division algorithms and their hardware implementations, beginning with the basic shift-subtract algorithms and moving on to high-radix, pre-scaled, modular, array, and convergence dividers. Part VI covers function evaluation, beginning with the important special case of square-rooting and moving on to CORDIC algorithms followed by general convergence and approximation methods, including the use of lookup tables.
Part VII deals with broad design and implementation topics, including pipelining, low-power arithmetic, and fault tolerance. This part concludes by providing historical perspective and examples of arithmetic units in real computers.
Pointers on how to use the book For classroom use, the topics in each chapter of this text can be covered in a lecture of duration hours. In my own teaching, I have used the chapters primarily for 1. But the modular structure of the text lends itself to other lecture formats, self-study, or review of the field by practitioners.
In the latter two cases, the readers can view each chapter as a study unit for one week, say rather than as a lecture. Ideally, all topics in each chapter should be covered before moving to the next chapter. However, if fewer lecture hours are available, then some of the subsections located at the end of chapters can be omitted or introduced only in terms of motivations and key results.
Problems of varying complexities, from straightforward numerical examples or exercises to more demanding studies or mini-projects, have been supplied for each chapter.
These problems form an integral part of the book and have not been added as afterthoughts to make the book more attractive for use as a text. A total of problems are included per chapter. A large number of classical papers and important contributions in computer arithmetic have been reprinted in [Swar90]. New ideas in the field of computer arithmetic appear in papers presented at bi-annual conferences, known as ARITH-n, held in odd-numbered years [Arit]. The text has benefited greatly from keen observations, curiosity, and encouragement of my many students in these courses.
A sincere thanks to all of them! This series began with a one-day workshop in and was subsequently held in , , , and in odd-numbered years since The 32nd conference in this series was held on November , This series of symposia began in , with the 41st in the series held on August , , in Notre Dame, IN. Occasionally devotes entire special issues or sections to computer arithmetic, e.
COMPUTER ARITHMETIC ALGORITHMS ISRAEL KOREN PDF
Request an e-inspection copy. Product pricing will be adjusted to match the corresponding currency. Open Preview See a Problem? There are no discussion topics on this book yet. Trivia About Computer Arithmet New algorithms and implementations have been added to almost all chapters. Books by Israel Koren. Sophie Smithburg marked it as to-read Jan 07, Kore for beautiful books?
ISBN 13: 9781568811604
Computer arithmetic algorithms
Computer Arithmetic Algorithms: Second Edition / Edition 2