General Information

Topic: Number Systems and Computer Arithmetic

Course number & title: Math/CS 394, Advanced Topics in Discrete Mathematics and Computer Science

Class schedule & room: Time: MWF 9:30-10:30 Room: INSC L310

Instructor: Professor Steven Lindell Office: INSC L308

Telephone: (610) 896-1203 E-mail: slindell@haverford.edu

Consultation hours: Friday TBA

Main Text: Computer Arithmetic Algorithms, by Israel Koren, Prentice Hall 2nd ed. ©2001.

Supplementary reading: Computer Number Systems and Arithmetic, by Norman R. Scott, Prentice Hall ©1985.

Computer Arithmetic: Algorithms and Hardware Designs, by Behrooz Parhami, OUP ©2000.

Prerequisites: Math 231 (Discrete Mathematics), or another 200-level mathematics course that includes proofs.

Course Description: The mathematical theory of discrete systems used for numerical representation, including their arithmetic algorithms, with an emphasis on modern techniques for high-speed computing. Included will be radix and residue systems, integer and floating-point representation, detailed coverage of the standard arithmetic operations, and the fast fourier transform.

Classwork: Since this is an advanced seminar, participation in class discussions is expected, and attendance is factored into your grade. Homework will be assigned in lecture, and collected about every two weeks. The problems will contain both calculations and proofs. Clarity of exposition in solutions will be expected and highly valued. The examination is take-home with no collaboration allowed. Each student will be expected to choose a topic covered in class for in-depth exploration in a term paper, a brief overview of which will be presented at the board by the student towards the end of the semester. There is no final examination.

Grading: Class attendance & participation 25%

Homework exercises 25%

Exam, take-home 25%

Term Paper & oral presentation 25%

Rules and regulations: Everything turned in for a grade must be your own work. Ideas on how to solve homework problems may be exchanged (orally, or at a chalkboard), but not specific detailed solutions (written on paper). There is no collaboration or help allowed on the examinations.

Syllabus

List of Topics (in rough order):

· overview of numbers (both whole and fractional, positive and negative)

· history of conventional (radix) representation systems

· discrete vs. analog conception

· basic integer arithmetic operations

· Peano's axioms

· magnitude comparison

· the binary number system

· basic computer hardware and boolean operations

· negative numbers

· serial algorithms for addition and subtraction

· parallel circuits for addition and subtraction

· floating-point numbers

· serial algorithms for multiplication and division

· parallel circuits for multiplication and division

· computation of elementary functions

· unconventional (residue) representation (using modular arithmetic)

· on-line arithmetic (bit-serial computations)

· DFT (discrete fourier transform)