Data Representation (A Level)

This chapter extends chapter 1 and chapter 10 for Paper 3. You will define your own data types, choose a file organisation for a problem, and work with real numbers stored in floating-point form. The floating-point calculations are a regular source of marks, so it is worth practising them until the method is automatic.

13.1 User-defined data types

Why user-defined types are necessary

The built-in types (INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE) are not always a good fit for the data of a problem. A user-defined data type is one the programmer defines to match the data exactly. It makes the program more readable (the values have meaningful names), safer (the translator stops values that are not allowed), and lets related data be grouped.

User-defined types are non-composite (built on a single value) or composite (made of several values).

Non-composite types

Enumerated type. The programmer lists every value the type may take, in order. The values are given as names, not as strings.

TYPE TDay = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday)
DECLARE Today : TDay
Today ← Wednesday
IF Today = Saturday OR Today = Sunday THEN
    OUTPUT "Weekend"
ENDIF

Behind the scenes the values are stored as integers (Monday = 0, Tuesday = 1, ...), so they can be compared and put in order. The benefit: Today ← "Wedensday" or Today ← 9 is not allowed, so wrong data is rejected by the language. Enumerated types are used for days, months, colours, suits and states.

Pointer type. A pointer is a variable that holds the memory address of another variable, not the value. A pointer type is defined to point at one specific type.

TYPE TIntPointer = ^INTEGER
DECLARE MyPointer : TIntPointer
DECLARE Number : INTEGER

Number ← 42
MyPointer ← ^Number          // MyPointer now holds the address of Number
OUTPUT MyPointer^            // the caret after the name gives the value stored there: 42

^Number means "the address of Number", and MyPointer^ means "the value at the address held in MyPointer" (dereferencing). Pointers are used to build dynamic data structures such as linked lists, stacks and trees, and to pass big structures without copying.

Composite types

A composite data type is built from several values.

Record type: a set of fields of different data types under one name (chapter 10).

TYPE TBook
    DECLARE Title : STRING
    DECLARE Pages : INTEGER
    DECLARE Price : REAL
ENDTYPE

Set type: a collection of distinct values of the same type with no order and no duplicates. Operations are those of mathematical sets: union, intersection and difference, and a test for membership.

TYPE TIntSet = SET OF INTEGER
DEFINE Evens (2, 4, 6, 8) : TIntSet
DEFINE Primes (2, 3, 5, 7) : TIntSet

The union of Evens and Primes is {2, 3, 4, 5, 6, 7, 8}; the intersection is {2}; Evens minus Primes is {4, 6, 8}. A set is useful for a task such as "which students take both Physics and Chemistry".

Class or object type: a class is also a user-defined composite type. It holds data (attributes) together with the methods that work on it, and each variable of the class is an object (chapter 20).

Designing a type for a problem

Look at the data and decide: a value from a fixed list → enumerated; the address of other data → pointer; related fields of different types → record; a group of unique values with no order → set; a list of the same type → array. Then write the definition and give each field the most suitable data type.

13.2 File organisation and access

File organisation

File organisation is how the records of a file are arranged in storage.

• Serial organisation: records are stored one after another in the order they were added, with no sort order. New records are added at the end. Used for temporary files, such as a transaction file collecting data before it is processed, or logs and backups.
• Sequential organisation: records are stored in order of a key field (for example sorted by customer ID). Used for processing every record in order, such as printing payslips or a master file updated in batch. Adding a record means creating a new file or inserting in place, since the order must be kept.
• Direct (random) organisation: records are stored at a calculated address, found by applying a hashing algorithm to the key field. Any record can be found directly without searching.

File access

• Serial access: start at the beginning and read records in turn until the one wanted is found. Used with serial files (and by sequential files when all records are processed).
• Sequential access: read in key order from the start; for a sorted file it can stop once the key passes the one sought.
• Direct access: go straight to the record using its address (calculated from the key), so it is much faster for finding one record in a big file. Used by databases and booking systems.

Which access suits which file. A serial file can only be read in order from the start, because its records are in no order. A sequential file is normally read with sequential access, but it can also use direct access: go straight to a record using an index or a binary search on the key field. A random file uses direct access, with the address found by hashing the key.

Hashing algorithms

A hashing algorithm takes the key of a record and calculates the address where the record is stored. A simple one is the modulo (remainder) method: Address ← Key MOD TableSize. For a file with 100 locations, the record with key 3457 goes to address $3457 \text{ MOD } 100 = 57$. To find the record, apply the same calculation, and go straight to address 57.

A good hash function spreads the keys evenly over the addresses, is quick to calculate, and always gives the same address for the same key.

Tap to enlarge

Four keys 23, 45, 13 and 34 stored using the hash function key MOD 10: 23 and 45 go to addresses 3 and 5, 13 collides at 3 and is moved on to 4, and 34 collides at 4 and 5 and is moved on to 6, shown in a file of ten addresses

Close

A collision occurs when two different keys give the same address. Ways to deal with it:

• Open addressing / linear probing: put the record in the next free location after the calculated address (wrapping around at the end). When looking up, start at the calculated address and check each next location until the key is found or an empty location is reached.
• Chaining (an overflow area): a record that collides is put in a separate overflow area, and a pointer links it to the record at the calculated address.

13.3 Floating-point numbers, representation and manipulation

Format

A floating-point number is stored in scientific-notation form, in binary, as two parts:

$\text{value} = \text{mantissa} \times 2^{\text{exponent}}$

• The mantissa holds the significant digits (the precision) as a two's complement fraction with the binary point after the sign bit.
• The exponent is a two's complement integer that says how far the binary point moves (the range).

A question tells you how many bits there are for each part, for example "10 bits for the mantissa and 6 bits for the exponent".

Tap to enlarge

A floating-point number as an 8-bit mantissa with the binary point after the sign bit and a 4-bit exponent, converted to denary 4.75, and an example of normalising a mantissa by shifting left until the first two bits differ while reducing the exponent

Close

Converting floating-point to denary

Example: mantissa 0100 1100 and exponent 0011 (8-bit mantissa, 4-bit exponent).

1. The exponent 0011 is +3.
2. The mantissa is 0.1001100: the binary point is after the first (sign) bit, which is 0, so the number is positive.
3. Move the point 3 places right (positive exponent): 0.1001100 becomes 0100.1100.
4. Convert: $4 + 0.5 + 0.25 = 4.75$.

If the exponent is negative, move the point to the left. If the mantissa is negative (it starts with 1), use the two's complement place value: the first bit is worth $-1$, then ½, ¼, and so on, before shifting the point.

Place values of the mantissa (binary point after the first bit): $-1,\ \tfrac12,\ \tfrac14,\ \tfrac18,\ \tfrac1{16}, \dots$

Converting denary to floating-point

Example: store 2.75 with an 8-bit mantissa and a 4-bit exponent.

1. Convert to binary: $2.75 = 10.11_2$.
2. Write it as a mantissa with the point after the sign bit: $0.1011 \times 2^2$ (the point moved 2 places to the left). Mantissa 0.1011000, so 01011000.
3. The exponent is +2, so 0010.

For a negative number, work out the positive value first and then take the two's complement of the mantissa: −2.75 is 10101000, exponent 0010.

Normalisation

A floating-point number is normalised if the first two bits of the mantissa are different: 01... for a positive number, 10... for a negative number. Normalising

• gives the maximum precision for the number of bits (no bits wasted on leading zeros or ones), and
• gives each number one unique representation, which makes comparing and calculating easier.

To normalise: shift the mantissa left until the first two bits differ, and subtract 1 from the exponent for each shift, so the value is unchanged. Fill the right-hand end with zeros. Example: 00010100 with exponent 0100 (+4) is not normalised. Shift 2 places left to get 01010000, and the exponent becomes $4 - 2 = 2$ (0010).

Approximations and rounding errors

Many decimal fractions cannot be written exactly in binary. For example 0.1 in binary is a never-ending pattern 0.0001100110011.... With a limited number of bits in the mantissa, the stored number is only an approximation of the real value, and the difference is a rounding error. These errors can build up in repeated calculations.

Consequences:

• Two numbers that should be equal may differ by a tiny amount, so a test such as IF X = 0.3 may be FALSE. Programmers compare with a small tolerance instead.
• Money values should not be held as binary fractions; use whole numbers of cents, or BCD, to avoid rounding errors.
• Very large and very small numbers cannot be stored exactly; a number too large for the exponent causes overflow, and one too close to zero causes underflow.

To reduce rounding errors, use more bits for the mantissa (greater precision).