Lecture Notes on Ints 15 122 Principles of Imperative Computation Frank Pfenning Lecture 2 August 26 2010 1 Introduction Two fundamental types in almost any programming language are booleans and integers Booleans are comparatively straightforward they have two possible values true and false and conditionals to test boolean values We will return to their properties in a later lecture Integers 2 1 0 1 2 are considerably more complex because there are infinitely many of them Because memory is finite only a finite subrange of them can be represented in computers In this lecture we discuss how integers are represented how we can deal with the limited precision in the representation and how various operations are defined on these representations 2 Binary Representation of Natural Numbers For the moment we only consider the natural numbers 0 1 2 and we do not yet consider the problems of limited precision Number notations have a base b To write down numbers in base b we need b distinct digits Each digit is multiplied by an increasing power of b starting with 20 at the right end For example in base 10 we have the ten digits 0 9 and the string 9380 represents the number 9 103 3 102 8 101 0 100 We call numbers in base 10 decimal numbers Unless it is clear from context that we are talking about a certain base we use a subscript b to indicate a number in base b L ECTURE N OTES A UGUST 26 2010 Ints L2 2 In computer systems two bases are of particular importance Binary numbers use base 2 with digits 0 and 1 and hexadecimal numbers explained more below use base 16 with digits 0 9 and A F Binary numbers are so important because the basic digits 0 and 1 can be modeled inside the computer by two different voltages usually off for 0 and on for 1 To find the number represented by a sequence of binary digits we multiply each digit by the appropriate power of 2 and add up the results In general the value of a bit sequence bn 1 b1 b0 2 bn 1 2 n 1 1 0 b1 2 b0 2 n 1 X bi 2i i 0 For example 10011 2 represents 1 24 0 23 0 22 1 21 1 20 16 2 1 19 We can also calculate the value of a binary number in a nested way exploiting Horner s rule for evaluating polynomials 10011 2 1 2 0 2 0 2 1 2 1 19 In general if we have an n bit number with bits bn 1 b0 we can calculate bn 1 2 bn 2 2 bn 3 2 b1 2 b0 For example taking the binary number 10010110 2 write the digits from most significant to least significant calculating the cumulative value from left to right by writing it top to bottom 1 2 4 9 18 37 75 2 2 2 2 2 2 2 1 0 0 1 0 1 1 0 1 2 4 9 18 37 75 150 Reversing this process allows us to convert a number into binary form Here we start with the number and successively divide by two calculating the remainder At the end the least significant bit is at the top L ECTURE N OTES A UGUST 26 2010 Ints L2 3 For example converting 198 to binary form would proceed as follows 198 99 49 24 12 6 3 1 99 49 24 12 6 3 1 0 2 2 2 2 2 2 2 2 0 1 1 0 0 0 1 1 We read off the answer from bottom to top arriving at 11000110 2 3 Modular Arithmetic Within a computer there is a natural size of words that can be processed by single instructions In early computers the word size was typically 8 bits now it is 32 or 64 In programming languages that are relatively close to machine instructions like C or C0 this means that the native type int of integers is limited to the size of machine words In C0 we decided that the values of type int occupy 32 bits This is very easy to deal with for small numbers because the more significant digits can simply be 0 According to the formula that yields their number value these bits do not contribute to the overall value But we have to decide how to deal with large numbers when operations such as addition or multiplication would yield numbers that are too big to fit into a fixed number of bits One possibility would be to raise overflow exceptions This is somewhat expensive since the overflow condition must be explicitly detected and has other negative consequences For example n n n is no longer equal to n n n because the former can overflow while the latter always yields n and does not overflow Another possibility is to carry out arithmetic operations modulo the number of representable integers which would be 232 in the case of C0 We say that the machine implements modular arithmetic In higher level languages one would be more inclined to think of the type of int to be inhabited by integers of essentially unbounded size This means that a value of this type would consist of a whole vector of machine words whose size may vary as computation proceeds Basic operations such as addition no longer map directly onto machine instruction but are L ECTURE N OTES A UGUST 26 2010 Ints L2 4 implemented by small programs Whether this overhead is acceptable depends on the application Returning to modular arithmetic the idea is that any operation is carried out modulo 2p for the precision p Even when the modulus is not a power of two many of the usual laws of arithmetic continue to hold which makes it possible to write programs confidently without having to worry for example about whether to write x y z or x y z We have the following properties of the abstract algebraic class of rings which are shared between ordinary integers and integers modulo a fixed number n Commutativity of addition x y y x Associativity of addition x y z x y z x 0 x Additive unit Additive inverse x x 0 Cancellation x x Commutativity of multiplication x y y x Associativity of multiplication x y z x y z Multiplicative unit x 1 x Distributivity x y z x y x z Annihilation x 0 0 Some of these laws such as associativity and distributivity do not hold for so called floating point numbers that approximate real numbers This significantly complicates the task of reasoning about programs with floating point numbers which we have therefore omitted from C0 4 An Algorithm for Binary Addition In the examples we use arithmetic modulo 24 with 4 bit numbers Addition proceeds from right to left adding binary digits modulo 2 and using a carry if the result is 2 or greater For example 1 0 1 1 1 0 1 01 1 1 0 1 0 0 11 9 20 4 mod 16 …