ilide.info-9618-cambridge-international-as-and-a-level-computer-science-pr_7996775bfd89080ba074443dd124436b (1).pdf

13 Data representation 13 DATA REPRESENTATION In this chapter, you will learn about user-defined data types...

13 Data representation 13 DATA REPRESENTATION In this chapter, you will learn about user-defined data types the definition and use of non-composite and composite data types the choice and design of an appropriate user-defined data type for a given problem methods of file organisation, such as serial, sequential and random methods of file access, such as sequential and direct access hashing algorithms binary floating-point real numbers converting binary floating-point real numbers into denary numbers converting denary numbers into binary floating-point real numbers the normalisation of binary floating-point numbers how underflow and overflow can occur how binary representation can lead to rounding errors. 13.1 User-defined data types WHAT YOU SHOULD ALREADY KNOW Try these two questions before you read the first part of this chapter. 1 Select an appropriate data type for each of the following. a) A name b) A student’s mark c) A recorded temperature d) The start date for a job e) Whether an item is sold or not 2 Write pseudocode to define a record structure to store the following data for an animal in a zoo. Name Species Date of birth Location Whether the animal was born in the zoo or not Notes 304 457591_13_CI_AS & A_Level_CS_304-327.indd 304 26/04/19 8:42 AM  Programmers use specific data types that exactly match a program’s Key terms 13 requirements. They define their own data types based on primitive data types User-defined data type provided by a programming language, or data types that they have defined – a data type based on previously in a program. These are called user-defined data types. an existing data type or User-defined data types can be divided into non-composite and composite other data types that data types. have been defined by a programmer. 13.1.1 Non-composite data types Non-composite data type – a data type that A non-composite data type can be defined without referencing another data 13.1 User-defined data types does not reference any type. It can be a primitive type available in a programming language or a other data types. user-defined data type. Non-composite user-defined data types are usually Enumerated data used for a special purpose. type – a non-composite data type defined by a We will consider enumerated data types for lists of items and pointers to data given list of all possible in a computer’s memory. values that has an implied order. Enumerated data type Pointer data type – a An enumerated data type contains no references to other data types when it is non-composite data defined. In pseudocode, the type definition for an enumerated data type has type that uses the this structure: memory address of where the data is TYPE = (value1, value2, value3,... ) stored. Set – a given list of unordered elements For example, a data type for months of the year could be defined as: that can use set theory operations such as intersection and union. Type names usually begin with T to aid the programmer TYPE Tmonth = (January, February, March, April, May, June, July, August, September, October, November, December) The values are not strings so are not enclosed in quotation marks Then the variables thisMonth and nextMonth of type Tmonth could be defined as: DECLARE thisMonth : Tmonth DECLARE nextMonth : Tmonth nextMonth is now set to February thisMonth ← January nextMonth ← thisMonth + 1 ACTIVITY 13A Using pseudocode, declare an enumerated data type for the days of the week. Then declare two variables today and yesterday, assign a value of Wednesday to today, and write a suitable assignment statement for tomorrow. 305 457591_13_CI_AS & A_Level_CS_304-327.indd 305 26/04/19 8:42 AM  Pointer data type 13 A pointer data type is used to reference a memory location. This data type needs to have information about the type of data that will be stored in the memory location. In pseudocode the type definition has the following structure, in which ^ shows that the type being declared is a pointer and is the type of data to be found in the memory location, for example INTEGER or REAL, or any user-defined data type. TYPE = ^ 13 DATA REPRESENTATION For example, a pointer for months of the year could be defined as follows: TYPE TmonthPointer = ^Tmonth Tmonth is DECLARE monthPointer : TmonthPointer the data type in the memory location that this pointer can be used to point to It could then be used as follows: monthPointer ← ^thisMonth If the contents of the memory location are required rather than the address of the memory location, then the pointer can be dereferenced. For example, myMonth can be set to the value stored at the address monthPointer is pointing to: DECLARE myMonth : Tmonth myMonth ← monthPointer^ monthPointer has been dereferenced ACTIVITY 13B Using pseudocode for the enumerated data type for days of the week, declare a suitable pointer to use. Set your pointer to point at today. Remember, you will need to set up the pointer data type and the pointer variable. 13.1.2 Composite data types A data type that refers to any other data type in its type definition is a composite data type. In Chapter 10, the data type for record was introduced as a composite data type because it refers to other data types. 306 457591_13_CI_AS & A_Level_CS_304-327.indd 306 26/04/19 8:42 AM  TYPE TbookRecord DECLARE title : STRING 13 DECLARE author : STRING DECLARE publisher : STRING DECLARE noPages : STRING DECLARE fiction : STRING Other data types 13.1 User-defined data types ENDTYPE Other composite data types include sets and classes. Sets A set is a given list of unordered elements that can use set theory operations such as intersection and union. A set data type includes the type of data in the set. In pseudocode, the type definition has this structure: TYPE = SET OF The variable definition for a set includes the elements of the set. DEFINE (value1, value2, value3,... ) : A set of vowels could be declared as follows: TYPE Sletter = SET OF CHAR DEFINE vowel ('a', 'e', 'i', 'o', 'u') : letters EXTENSION ACTIVITY 13A Many programming languages offer a set data type. Find out about how set operations are implemented in the programming language you are using. Classes A class is a composite data type that includes variables of given data types and methods (code routines that can be run by an object in that class). An object is defined from a given class; several objects can be defined from the same class. Classes and objects will be considered in more depth in Chapter 20. ACTIVITY 13C 1 Explain, using examples, the difference between composite and non-composite data types. 2 Explain why programmers need to define user-defined data types. Use examples to illustrate your answers. 3 Choose an appropriate data type for the following situations. Give the reason for your choice in each case. a) A fixed number of colours to choose from. b) Data about each house that an estate agent has for sale. c) The addresses of integer data held in main memory. 307 457591_13_CI_AS & A_Level_CS_304-327.indd 307 26/04/19 8:42 AM  13.2 File organisation and access 13 WHAT YOU SHOULD ALREADY KNOW Try these three questions before you read the a) Create a text file. second part of this chapter. b) Write several lines of text to the file. 1 Describe three different modes that files can c) Read the text that you have written to the be opened in. file. 13 DATA REPRESENTATION 2 Write pseudocode to carry out the following d) Append a line of text at the end of the file. operations on a text file. 3 Write a program to test your pseudocode. Key terms Serial file organisation – a method of file organisation in of the record; the result of the calculation gives the which records of data are physically stored in a file, one address where the record should be found. after another, in the order they were added to the file. File access – the method used to physically find a Sequential file organisation – a method of file record in the file. organisation in which records of data are physically Sequential access – a method of file access in which stored in a file, one after another, in a given order. records are searched one after another from the Random file organisation – a method of file physical start of the file until the required record is organisation in which records of data are physically found. stored in a file in any available position; the location Direct access – a method of file access in which of any record in the file is found by using a hashing a record can be physically found in a file without algorithm on the key field of a record. physically reading other records. Hashing algorithm (file access) – a mathematical formula used to perform a calculation on the key field 13.2.1 File organisation and file access File organisation Computers are used to access vast amounts of data and to present it as useful information. Millions of people expect to be able to retrieve the information they need in a useful form when they ask for it. This information is all stored as data in files, everything from bank statements to movie collections. In order to be able to find data efficiently it needs to be organised. Data of all types is stored as records in files. These files can be organised using different methods. Serial file organisation The serial file organisation method physically stores records of data in a file, one after another, in the order they were added to the file. First Second Third Fourth Fifth Sixth and so on record record record record record record Start of file Figure 13.1 New records are appended to the end of the file. Serial file organisation is often used for temporary files storing transactions to be made to more permanent files. For example, storing customer meter readings for gas or electricity before they are used to send the bills to all customers. As each transaction is added to the file in the order of arrival, these records will be in chronological order. 308 457591_13_CI_AS & A_Level_CS_304-327.indd 308 26/04/19 8:42 AM  Sequential file organisation The sequential file organisation method physically stores records of data in a file, one after another, in a given order. The order is usually based on the key field of the records as this is a unique identifier. For example, a file could 13 be used by a supplier to store customer records for gas or electricity in order to send regular bills to each customer. All records are stored in ascending customer number order, where the customer number is the key field that uniquely identifies each record. 13.2 File organisation and access Customer 1 Customer 2 Customer 3 Customer 4 Customer 7 Customer 8 and so on record record record record record record Start of file Figure 13.2 New records must be added to the file in the correct place; for example, if Customer 5 is added to the file, the structure becomes: Customer 1 Customer 2 Customer 3 Customer 4 Customer 5 Customer 7 Customer 8 and so on record record record record record record record Start of file Figure 13.3 Random file organisation The random file organisation method physically stores records of data in a file in any available position. The location of any record in the file is found by using a hashing algorithm (see Section 13.2.2) on the key field of a record. Customer 8 Customer 2 Customer 4 Customer 7 Customer 3 Customer 1 and so on record record record record record record Start of file Figure 13.4 Records can be added at any empty position. File access There are different methods of file access (the method used to physically find a record in the file). We will consider two of them: sequential access and direct access. Sequential access The sequential access method searches for records one after another from the physical start of the file until the required record is found, or a new record can be added to the file. This method is used for serial and sequential files. For a serial file, if a particular record is being searched for, every record needs to be checked until that record is found or the whole file has been searched and that record has not been found. Any new records are appended to the end of the file. For a sequential file, if a particular record is being searched for, every record needs to be checked until the record is found or the key field of the current record being checked is greater than the key field of the record being searched 309 457591_13_CI_AS & A_Level_CS_304-327.indd 309 26/04/19 8:42 AM  for. The rest of the file does not need to be searched as the records are sorted 13 on ascending key field values. Any new records to be stored are inserted in the correct place in the file. For example, if the record for Customer 6 was requested, each record would be read from the file until Customer 7 was reached. Then it would be assumed that the record for Customer 6 was not stored in the file. Customer 1 Customer 2 Customer 3 Customer 4 Customer 5 Customer 7 Customer 8 and so on record record record record record record record ↑ 13 DATA REPRESENTATION Customer 6 record not found Figure 13.5 Sequential access is efficient when every record in the file needs to be processed, for example, a monthly billing or payroll system. These files have a high hit rate during the processing as nearly every record is used when the program is run. Direct access The direct access method can physically find a record in a file without other records being physically read. Both sequential and random files can use direct access. This allows specific records to be found more quickly than using sequential access. Direct access is required when an individual record from a file needs to be processed. For example, when a single customer record needs to be updated when the customer’s phone number is changed. Here, the file being processed has a low hit rate as only one of the records in the file is used. For a sequential file, an index of all the key fields is kept and used to look up the address of the file location where a given record is stored. For large files, searching the index takes less time than searching the whole file. For a random access file, a hashing algorithm is used on the key field to calculate the address of the file location where a given record is stored. 13.2.2 Hashing algorithms In the context of storing and accessing data in a file, a hashing algorithm is a mathematical formula used to perform a calculation on the key field of the record. The result of the calculation gives the address where the record should be found. More complex hashing algorithms are used in the encryption of data. Here is an example of a simple hashing algorithm: If a file has space for 2000 records and the key field can take any values between 1 and 9999, then the hashing algorithm could use the remainder when the value of key field is divided by 2000, together with the start address of the file and the size of the space allocated to each record. In the simplest case, where the start address is 0 and each record is stored in one location. To store a record identified by a key field with value 3024, the hashing algorithm would give address 1024 as the location to store the record. Key field Remainder Address 3024 1024 1024 = 0 + 1 * 1024 Table 13.1 310 457591_13_CI_AS & A_Level_CS_304-327.indd 310 26/04/19 8:42 AM  Unfortunately, storing another record with a key field 5024 would result in 13 trying to use the same file location and a collision would occur. Key field Same remainder Same address 5024 1024 1024 = 0 + 1 * 1024 Table 13.2 This often happens with hashing algorithms for direct access to records in a file. There are two ways of dealing with this: 13.2 File organisation and access 1 An open hash where the record is stored in the next free space. 2 A closed hash where an overflow area is set up and the record is stored in the next free space in the overflow area. When reading a record from a file using direct access, the address of the location ACTIVITY 13E to read from is calculated using the hashing algorithm and the key field of the record stored there is read. But, before using that record, the key field must be 1 Explain, using checked against the original key field to ensure that they match. If the key fields examples, do not match, then the following records need to be read until a match is found the difference between serial (open hash) or the overflow area needs to be searched for a match (closed hash). and sequential files. 2 Explain the ACTIVITY 13D process of direct access to a A file of records is stored at address 500. Each record takes up five locations record in a file and there is space for 1000 records. The key field for each record can take using a hashing the value 1 to 9999. algorithm. The hashing algorithm used to calculate the address of each record is the 3 Choose an remainder when the value of key field is divided by 1000 together with the appropriate start address of the file and the size of the space allocated to each record. file type for the following Calculate the address to store the record with key field 9354. situations. If this location has already been used to store a record and an open hash is Give the reason used, what is the address of the next location to be checked? for your choice in each case. a) Borrowing Hashing algorithms can also be used to calculate addresses from names. For books from a example, adding up the ASCII values for every character in a name and dividing library. this by the number of locations in the file could be used as the basis for a b) Providing an hashing algorithm. annual tax statement for employees at EXTENSION ACTIVITY 13B the end of the year. Write a program to c) Recording find the ASCII value for each character in a name of up to 10 characters daily rainfall add the values together readings at divide by 1000 and find the remainder a remote multiply this value by 20 and add it to 2000 weather display the result. station to be collected If this program simulates a hashing algorithm for a file, what is the start every month. address of the file and the size of each record? 311 457591_13_CI_AS & A_Level_CS_304-327.indd 311 26/04/19 8:42 AM  13.3 Floating-point numbers, 13 representation and manipulation WHAT YOU SHOULD ALREADY KNOW Try these six questions before you c) –1200 read the third part of this chapter. d) 0.000000002341 1 Convert these denary numbers e) −0.0000124005 13 DATA REPRESENTATION into binary. 6 a) Standard form is sometimes a) +48 used to put denary improper b) +122 fractions into proper c) −100 14 fractions. For example, 5 d) −55 1.4 can be written as × 101, e) −2 112 5 and can be written as 2 Convert these binary numbers 3 into denary. 1.12 × 10 2. 3 a) 00110011 b) 01111110 Change the following improper fractions into c) 10110011 proper fractions using this d) 11110010 format: e) 11111111 21 i) 3 Use two’s complement to find 5 the negative values of these 117 binary numbers. ii) 4 a) 00110100 558 iii) b) 00011101 20 c) 01001100 b) When using binary, we d) 00111111 can convert improper e) 01111110 binary fractions into 4 Carry out these binary additions, proper fractions. For 7 showing all your working. example, 2 can be written a) 00110001 + 00011110 77 as ×× 4 (where 4 ≡ 22 ), b) 01000001 + 00111111 88 23 and can be written as c) 00111100 + 01000101 2 23 23 ≡ ≡ 2 ). 4 × 16 (where16 × d) 01111101 + 01011100 32 32 e) 11101100 + 01100000 Change the following f) 10001111 + 10011111 improper binary fractions into g) 01000101 + 10111100 proper binary fractions using h) 01111110 + 01111110 this format. i) 11111100 + 11100011 i) 11 2 j) 11001100 + 00011111 5 Write the following numbers in 41 ii) standard form 4 a) 123 000 000 iii) 52 4 b) 2 505 000 000 000 000 312 457591_13_CI_AS & A_Level_CS_304-327.indd 312 02/05/19 11:05 AM  Key terms Mantissa – the fractional part of a floating point number. numbers should be in the format 0.1 and negative numbers in the format 1.0. 13 Exponent – the power of 2 that the mantissa (fractional Overflow – the result of carrying out a calculation part) is raised to in a floating-point number. which produces a value too large for the computer’s Binary floating-point number – a binary number allocated word size. written in the form M × 2E (where M is the mantissa and Underflow – the result of carrying out a calculation E is the exponent). which produces a value too small for the computer’s 13.3 Floating-point numbers, representation and manipulation Normalisation (floating-point) – a method to improve allocated word size. the precision of binary floating-point numbers; positive 13.3.1 Floating-point number representation In Chapter 1, we learnt about how binary numbers can be stored in a fixed- point representation. The magnitude of the numbers stored depends on the number of bits used. For example, 8 bits allowed a range of −128 to +127 (using two’s complement representation) whereas 16 bits increased this range to −16 384 to +16 383. However, this type of representation limits the range of numbers and does not allow for fractional values. To increase the range, and to allow for fractions, we can look to the method used in the denary number system. For example, 312 110 000 000 000 000 000 000 can be written as 3.1211 × 1023 using scientific notation. If we adopt this system in binary, we get: M × 2E M is the mantissa and E is the exponent. This is known as binary floating-point representation. In our examples, we will assume a computer is using 8 bits to represent the mantissa and 8 bits to store the exponent (a binary point is assumed to exist between the first and second bits of the mantissa). Again, using denary as our example, a number such as 0.31211 × 1024 means: 1 1 1 1 1 10 100 1000 10 000 100 000 10 1 3 1 2 1 1 × 2 4 mantissa values exponent Figure 13.6 We thus get the binary floating-point equivalent (using 8 bits for the mantissa 1 and 8 bits for the exponent with the assumed binary point between –1 and in 2 the mantissa): 1 1 1 1 1 1 1 −1 2 4 16 −128 64 32 16 8 4 2 1 8 32 64 128 Figure 13.7 313 457591_13_CI_AS & A_Level_CS_304-327.indd 313 26/04/19 8:42 AM  Converting binary floating-point numbers into denary 13 Example 13.1 Convert this binary f loating-point number into denary. 1 1 1 1 1 1 1 −1 2 4 8 16 32 64 128 −128 64 32 16 8 4 2 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 13 DATA REPRESENTATION Solution Method 1 Add up the mantissa values where a 1 bit appears: 1 1 1 1 32 8 4 1 45 M= + + + ≡ + + + = 2 8 16 64 64 64 64 64 64 Add up the exponent values where a 1 bit appears: E=4 Use M × 2E: 45 45 4 45 45 ×× ×2 = == ×× 16 64 64 64 64 = 0.703125 × 16 = 11.25 (the denary value) Method 2 Write the mantissa as 0.1011010. The exponent is 4, so move the binary point four places to the right (to match the exponent value). This gives 01011.010. whole number part fraction part 1 1 1 −16 8 4 2 1 2 4 8 0 1 0 1 1 0 1 0 This gives 11.25 (the same result as method 1). Example 13.2 Convert this binary f loating-point number into denary. 1 1 1 1 1 1 1 −1 2 4 8 16 32 64 128 −128 64 32 16 8 4 2 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 314 457591_13_CI_AS & A_Level_CS_304-327.indd 314 02/05/19 11:06 AM  Solution Method 1 Add up the mantissa values where a 1 bit appears: 13 11 11 41 11 5 M === +++ ≡≡== +++ ≡== + 4 4 1616 16 16 164 1616 16 16 16 Add up the exponent values where a 1 bit appears: E=2+1=3 13.3 Floating-point numbers, representation and manipulation Use M × 2E: 55 55 ×× 2 3= = ×× 8 = 16 16 16 16 16 16 16 = 0.3125 × 8 = 2.5 (the denary value) Method 2 Write the mantissa as 0.0101000. The exponent is 3, so move the binary point three places to the right (to match the exponent value). This gives 0010.1000. whole number part fraction part 1 1 1 1 −8 4 2 1 2 4 8 16 0 0 1 0 1 0 0 0 This gives 2.5 (the same result as method 1). Now we shall consider negative values. Example 13.3 Convert this binary f loating-point number into denary. 1 1 1 1 1 1 1 −1 2 4 8 16 32 64 128 −128 64 32 16 8 4 2 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 Solution Method 1 Add up the mantissa values where a 1 bit appears: 1 1 1 16 2 1 19 32 19 13 M = −1 + + + ≡ −1 + + + ≡ −1 + ≡− + =− 2 16 32 32 32 32 32 32 32 32 Add up the exponent values where a 1 bit appears: E = 8 + 4 = 12 Use M × 2E: 13 13 − × 212 =− × 4096 32 32 = −0.40625 × 4096 = −1664 (the denary value) 315 457591_13_CI_AS & A_Level_CS_304-327.indd 315 02/05/19 11:07 AM  Method 2 13 Since the mantissa is negative, first convert the value using two’s complement. So, write the mantissa as 00110011 + 1 = 00110100. This gives −0.0110100. The exponent is 12, so move the binary point 12 places to the right (to match the exponent value). This gives −0011010000000.0. 13 DATA REPRESENTATION fraction whole number part part 1 −4096 2048 1024 512 256 128 64 32 6 8 4 2 1 2 0 0 1 1 0 1 0 0 0 0 0 0 0 0 This gives −(1024 + 512 + 128) = −1664 (the same result as method 1). Example 13.4 Convert this binary f loating-point number into denary. 1 1 1 1 1 1 1 −1 2 4 8 16 32 64 128 −128 64 32 16 8 4 2 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 Solution Method 1 Add up the mantissa values where a 1 bit appears: 1 1 1 16 2 1 19 32 19 13 M = −1 + + + ≡ −1 + + + ≡ −1 + ≡− + =− 2 16 32 32 32 32 32 32 32 32 Add up the exponent values where a 1 bit appears: E = −128 + 64 + 32 + 16 + 8 + 4 = −4 Use M × 2E: 13 13 − × 2−4 = − × 0.0625 32 32 = −0.40625 × 0.0625 = −0.025390625 (the denary value) Method 2 Since the mantissa is negative, first convert the value using two’s complement. So, write the mantissa as 00110011 + 1 = 00110100. This gives −0.0110100. The exponent is −4, so move the binary point four places to the left (to match the negative exponent value). This gives −0.00000110100. 316 457591_13_CI_AS & A_Level_CS_304-327.indd 316 02/05/19 11:08 AM  whole number part fraction part 13 1 1 1 1 1 1 1 1 1 1 1 −1 2 4 8 16 32 64 128 256 512 1024 2048 0 0 0 0 0 0 1 1 0 1 0 0 This gives − ( 1 + 1 + 1 )=− 13 13.3 Floating-point numbers, representation and manipulation 64 128 512 512 = −0.025390625 (the same result as method 1). ACTIVITY 13F Convert these binary floating-point numbers into denary numbers (the mantissa is 8 bits and the exponent is 8 bits in all cases). a) 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 1 b) 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 c) 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 d) 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 e) 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 f) 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 g) 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 h) 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 i) 1 0 1 1 0 0 0 0 1 1 1 1 1 1 0 1 j) 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 Converting denary numbers into binary floating-point numbers Example 13.5 Convert +4.5 into a binary f loating-point number. Solution Method 1 Turn the number into an improper fraction: 9 4.5 = 2 The fraction needs to be < 1, which means the numerator < denominator; we can do this by dividing successively by 2 until the denominator > numerator. 9 9 9 9 → → → The numerator (9) is now < denominator (16). 2 4 8 16 317 457591_13_CI_AS & A_Level_CS_304-327.indd 317 02/05/19 11:08 AM  9 9 So, 9 can be written as 13 ×8 ≡ × 23 and the original fraction is now written 2 16 16 in the correct format, M × 2E. 9 1 1 = + , which gives the mantissa as 0.1001. 16 2 16 And the exponent is 23, which is represented as 11 in our binary f loating point format. 13 DATA REPRESENTATION Filling in the gaps with 0s gives: 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 Method 2 4 = 0100 and.5 =.1 which gives: 0100.1 Now move the binary point as far as possible until 0.1 can be formed: 0100.1 becomes 0.1001 by moving the binary point three places left. So, the exponent must increase by three: 0.1001 × 11 Filling in the gaps with 0s gives: 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 This is the same result as method 1. Example 13.6 Convert +0.171875 into a binary f loating-point number. Solution Method 1 Remember, the fraction needs to be < 1, which means the numerator < denominator. 171875 11 0.171875 ≡ ≡ , so this fraction is already in the correct form. 1000 000 64 11 1 1 1 = + + , which gives the mantissa as 0.0010110 and exponent as 0. 64 8 32 64 Filling in the gaps with 0s gives: 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 Method 2 0 = 0 and.171875 =.001011 ( 1 + 8 32 1 + 1 64 ), which gives: 0.001011. Now move the binary point as far as possible until 0.1 can be formed: 0.001011 becomes 0.1011 by moving the binary point two places right. So, the exponent must increase by two (in other words, −2). The number 2, using eight bits is 00000010. 318 457591_13_CI_AS & A_Level_CS_304-327.indd 318 02/05/19 11:09 AM  Applying two’s complement gives us 11111101 + 1 = 11111110 Thus, we have: 0.1011 × 11111110 13 Filling in the gaps with 0s gives: 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 This is exactly the same result as method 1. 13.3 Floating-point numbers, representation and manipulation EXTENSION ACTIVITY 13C Show why: 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 is the same as: 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 Example 13.7 Convert −10.375 into a binary f loating-point number. Solution Method 1 Turn the number into an improper fraction: 3 83 0.375 ≡ , so − 10.375 = − 8 8 Now make the fraction < 1. 83 83 83 − ≡− × 16 ≡− × 24 8 128 128 83 45 − = −1 + , which gives the mantissa as 1.0101101 128 128 ( 45 128 = + 1 4 1 + 16 32 1 + 1 128 ). And the exponent is 24, which is represented as 100 in our binary f loating point format. Filling in the gaps with 0s gives: 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 Method 2 1 1 −10 = −01010 and + ≡.375 =.011, which gives: −01010.011. 4 8 Using two’s complement (on 01010011) we get: 10101100 + 1 = 10101101 (= 10101.101). Now move the binary point as far as possible until 1.0 can be formed: 319 457591_13_CI_AS & A_Level_CS_304-327.indd 319 02/05/19 11:11 AM  10101.101 becomes 1.0101101 by moving the binary point four places left. 13 So, the exponent must increase by four. 1.0101101 × 100 Filling in the gaps with 0s gives: 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 This is the same result as method 1. 13 DATA REPRESENTATION ACTIVITY 13G 1 Write these into binary floating-point format using an 8-bit mantissa and 8-bit exponent. 11 11 a) × 27 f) − × 24 32 64 19 9 b) × 23 g) − × 2−1 64 16 21 5 c) × 2−5 h) − × 25 128 16 15 1 d) × 2−3 i) − × 2−6 16 4 21 5 e) × 23 j) − × 2−2 8 8 2 Convert these denary numbers into binary floating-point numbers using an 8-bit mantissa and 8-bit exponent. 15 a) +3.5 f) − 32 b) 0.3125 g) −3.5 c) 15.375 h) −10.25 41 ⎛ 3⎞ d) i) −1.046875 ⎜≡ −1 ⎟ 64 ⎝ 64 ⎠ 11 e) 9.125 j) −3 32 Potential rounding errors and approximations All the problems up to this point have involved fractions which are linked 15 somehow to the number 2 (such as ). We will now consider numbers which 64 can only be represented as an approximate value (the accuracy of which will depend on the number of bits that make up the mantissa). The representation of the following example (denary number 5.88), using an 8-bit mantissa and 8-bit exponent, will lead to an inevitable rounding error since it is impossible to convert the denary number into an exact binary equivalent. This error could be reduced by increasing the size of the mantissa; for example, a 16-bit mantissa would allow the number 5.88 to be represented as 5.875, which is a better approximation. 320 457591_13_CI_AS & A_Level_CS_304-327.indd 320 26/04/19 8:42 AM  We will consider how to represent the denary number 5.88 using an 8-bit 13 mantissa and 8-bit exponent. To convert this into binary, we will use a method similar to that used in Chapter 1..88 × 2 = 1.76 so we will use the 1 value to give 0.1.76 × 2 = 1.52 so we will use the 1 value to give 0.11.52 × 2 = 1.04 so we will use the 1 value to give 0.111.04 × 2 = 0.08 so we will use the 0 value to give 0.1110 13.3 Floating-point numbers, representation and manipulation.08 × 2 = 0.16 so we will use the 0 value to give 0.11100.16 × 2 = 0.32 so we will use the 0 value to give 0.111000.32 × 2 = 0.64 so we will use the 0 value to give 0.1110000.64 × 2 = 1.28 so we will use the 1 value to give 0.11100001 We have to stop here since our system uses a maximum of 8 bits. Now the value of 5 (in binary) is 0101; this gives: 5.88 ≡ 0101.11100001 Moving the binary point as far to the left as possible gives: 0.1011100 × 23 (23 since the binary point was moved three places). Thus, we get 0.1011100 00000011 (mantissa) (exponent) 23 23 = × 23 = = 5.75 32 4 So, 5.88 is stored as 5.75 in our floating-point system. EXTENSION ACTIVITY 13D Using 8-bit mantissa and exponent, show how the following numbers would be approximated a) 1.63 b) 8.13 c) 12.32 d) 5.90 e) 7.40. Now consider this set of numbers. 1 0.1000000 00000010 ≡ × 22 =2 2 1 0.0100000 00000011 ≡ × 23 =2 4 1 0.0010000 00000100 ≡ × 24 =2 8 1 =2 0.0001000 00000101 ≡ × 25 16 Figure 13.8 321 457591_13_CI_AS & A_Level_CS_304-327.indd 321 26/04/19 8:42 AM  As shown, there are several ways of representing the number 2. Using this 13 sequence, if we kept shifting to the right, we would end up with: 0.0000000 00001001 =2 Figure 13.9 This could lead to problems. To overcome this, we use a method called normalisation. With this method, for a positive number, the mantissa must start with 13 DATA REPRESENTATION 0.1 (as in our first representation of 2 above). The bits in the mantissa are shifted to the left until we arrive at 0.1; for each shift left, the exponent is reduced by 1. Look at the examples above to see how this works (starting with 0.0001000 we shift the bits 3 places to the left to get to 0.100000 and we reduce the exponent by 3 to now give 00000010, so we end up with the first representation!). For a negative number the mantissa must start with 1.0. The bits in the mantissa are shifted until we arrive at 1.0; again, the exponent must be changed to reflect the number of shifts. Example 13.8 Normalise 0.0011100 00000101 ≡ ( 7 32 × 25 ) = 7. Solution Shift the bits left to get 0.1110000. Since the bits were shifted two places left, the exponent must reduce by two to give 00000011. This gives 0.1110000 00000011, which is now normalised. 7 Note: 0.1110000 00000011 ≡ × 2 3 = 7, so the normalised form still represents 8 the correct value. Example 13.9 Normalise 1.1101100 00001010 ≡ − ( 5 32 × 210 = −160 ) Solution Shift the bits left until to get 1.0110000. Since the bits were shifted two places left, the exponent must reduce by two to give 00001000. This gives 1.011000 00001000, which is now normalised. Note: 1.011000 00001000 ≡ − 5 × 28 = −5 × 32 = −160 , so the normalised form 8 still represents the same value. 322 457591_13_CI_AS & A_Level_CS_304-327.indd 322 02/05/19 11:12 AM  ACTIVITY 13H Normalise these binary floating-point numbers. 13 a) 0. 0 0 0 1 1 0 1 00000110 b) 0. 0 0 1 1 0 0 0 00001001 c) 0. 0 0 0 0 1 1 1 00000110 d) 0. 0 0 1 0 0 0 1 00000011 13.3 Floating-point numbers, representation and manipulation e) 0. 0 0 1 1 1 0 0 00001000 f) 1. 1 1 1 1 0 0 0 00001000 g) 1. 1 1 0 0 1 0 0 00001100 h) 1. 1 1 1 0 1 1 0 00000011 i) 0. 0 0 0 1 1 1 1 11111000 j) 1. 1 1 1 1 0 0 0 11110100 Precision versus range The following values relate to an 8-bit mantissa and an 8-bit exponent (using two’s complement): The maximum positive number which can be stored is: 127 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 ≡ × 2127 128 Figure 13.10 The smallest positive number which can be stored is: 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ≡ × 2−128 2 Figure 13.11 The smallest magnitude negative number which can be stored is: 65 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 ≡− × 2−128 128 Figure 13.12 The largest magnitude negative number which can be stored is: 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 ≡ −1 × 2127 Figure 13.13 » The accuracy of a number can be increased by increasing the number of bits used in the mantissa. » The range of numbers can be increased by increasing the number of bits used in the exponent. » Accuracy and range will always be a trade-off between mantissa and exponent size. 323 457591_13_CI_AS & A_Level_CS_304-327.indd 323 26/04/19 8:42 AM  Consider the following three cases. 13 1 0 1 Figure 13.14 1 1 1 1 1 1 1 1 1 1 0 1 1 1 The mantissa is 12 bits and the exponent is 4 bits. 2047 This gives a largest positive value of × 27 ; which gives high accuracy but 2048 small range. 13 DATA REPRESENTATION 2 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 Figure 13.15 The mantissa is 8 bits and the exponent is 8 bits. 127 This gives a largest positive value of × 2127, which gives reduced accuracy 128 but increased range. 3 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 Figure 13.16 The mantissa is 4 bits and the exponent is 12 bits. 7 This gives a largest possible value of × 22047, which gives poor accuracy but 8 extremely high range. Floating-point problems The storage of certain numbers is an approximation, due to limitations in the