Data Representation

📁 16.02 File organisation

Every day we meet many kinds of file: graphics, word-processing documents, spreadsheets and so on. Whatever the type, the content is stored in a binary code that lets the file be used as intended.

For data that a program reads as input, or writes as output, there are only two file types: a text file or a binary file.

A binary file is organised into records. Each record contains fields, and each field holds a value.

🗂️ Serial, sequential and direct-access files

Serial files

The records are in no defined order. A bank's transaction file is a typical use: every deposit or withdrawal is simply appended, so the only order is the time each record was entered.

Sequential files

The records are ordered by a key field whose values are unique and sequential, though not necessarily consecutive. In the bank example, a sequential file could be the master file of customer accounts. At regular intervals the transaction file is read and every affected account in the master file is updated.

To add a record you could append it and sort the file later. More likely, the file is read in order and each record copied to a new file until the right position is reached. The new record is written there, then the rest of the old file is copied across.

Direct-access files

Sometimes called "random-access" files, but, as with random-access memory, the only random thing is that you can go to any record without reading the file in order. There are two ways to get direct access:

• Keep a sequential file plus a separate index file. Each index record has two fields: the key field value, and the position of that record in the main file.
• Use a hashing algorithm when each record is written to the file.

#️⃣ Hashing

One simple hashing algorithm works when every record has a numeric key field. Divide the key by a suitable number. The remainder is the address in the file for that record. The divisor works best if it is a prime number of about the same size as the expected size of the file.

For simplicity, take 4-digit keys and divide by 1000:

0045 / 1000 gives remainder 45  → address 45
2005 / 1000 gives remainder 5   → address 5
3005 / 1000 gives remainder 5   → address 5

Two facts follow:

1. The addresses have no order related to the key values.
2. Different keys can give the same address.

If the records have no suitable numeric field, choose a field with letters, look up the ASCII code of each character, add the codes together, and use the remainder of dividing that sum in the same way.

When different keys give the same address it is called a collision (the keys are sometimes called synonyms). The best hashing algorithm spreads the addresses as evenly as possible and keeps collisions to a minimum. Collisions can't be avoided altogether, so there must be a defined way to deal with them. Options include:

• a sequential search for the next vacant address after the calculated one
• keeping some overflow addresses at the end of the file
• a linked list that can be reached from each address

🔎 File access

Once the file organisation is chosen and the data entered, you need to decide how the data will be accessed.

• Serial file: normally the whole file is read record by record. To find a particular value, the only option is to read from the start until the target record is found.
• Sequential file: searching may have to be done the same way. But if you know the key field value of the record you want, it is faster, because only the key fields need to be read.
• Direct-access file: the key is put through the hashing algorithm again. It gives the same address as when the record was written, so there is no need to read from the start. Because of collisions, some serial searching may still be needed after the first jump.

Deleting or editing

• Sequential file: the same method as adding: copy records from the old file to a new one until the record to delete or edit is reached, deal with it, then copy all the rest.
• Direct-access file: no new file is needed. A record can be found and edited directly without disturbing anything else. To delete a record, a flag is set in it so later reads skip over it.

Choice of file organisation

A key field in a file is not the same as a primary key in a database table. Primary key values must all be unique; key field values in a file do not have to be. Unique key values can be sensible for some applications, but they are not mandatory.

🔢 16.03 Real numbers

A real number has a fractional part. In denary we can write it simply, or in exponential (scientific) notation. For example, 25.3 can be written as

.253 × 10² or 2.53 × 10¹ or 25.3 × 10⁰ or 253 × 10⁻¹

For 25.3 the simple form is best, but for very large or very small numbers exponential notation is the only sensible choice.

Floating-point and fixed-point representations

A computer must store a real number as a binary code. One option is fixed point: a set number of bits for the whole-number part and the rest for the fractional part. The alternative is floating point, which has the general form

± M × R^E

Some bits hold the significand or mantissa, ±M. The rest hold the exponent or exrad, E. The radix R is not stored: it is always 2.

📏 Eight bits, two ways

To compare the two, suppose a real number must fit in eight bits.

Fixed point (sign and magnitude)

Use the most significant bit as a sign bit, the next five bits for the whole-number part, and the last two bits for the fraction. The gap shows where the binary point is implied.

Table 16.01 Example fixed-point representations (using sign and magnitude)

Floating point (4-bit mantissa, 4-bit exponent)

Now use four bits for the mantissa and four for the exponent, both in two's complement. The exponent is a signed integer. The mantissa is a fixed-point real value, so the question is where to put its binary point. Tables (a) and (b) show two choices; table (c) shows the exponent values.

Table 16.02 Coding a floating-point real value in eight bits (four for the mantissa and four for the exponent)

Putting the implied binary point straight after the sign bit gives a smaller spacing between the values that can be stored. That is the preferred option. With it, the most important non-zero values are:

Table 16.03 Example floating-point representations

Comparing Tables 16.01 and 16.03 shows the much greater range of positive and negative values that floating point gives from the same eight bits.

🎛️ Lab: build a floating-point number

⚖️ Precision and normalisation

A floating-point format needs two decisions: the total number of bits, and how they are split between mantissa and exponent. In practice the total is offered as an option when the program is written (single or double precision, for example), but the split is fixed by the floating-point processor. If you did have a choice:

• More mantissa bits → better precision
• fewer exponent bits → smaller range of possible values

To get the best precision you normalise the number (nothing to do with normalising a database). Precision depends on how many mantissa bits are used, so it is best when the mantissa holds the largest possible magnitude.

Using the 8-bit format of Table 16.03, here are three ways to store denary 2:

Table 16.04 (left) Alternative representations of denary 2 · Table 16.05 (right) Alternative representations of denary −4, using four bits each for mantissa and exponent

When the mantissa has its highest magnitude, the two most significant bits are different. That is how you recognise a normalised number: it starts 01 if positive or 10 if negative.

• Positive: shift the mantissa bits left until they start 0 then 1. For each shift left, subtract 1 from the exponent.
• Negative: shift left in the same way until they start 1 then 0. Ignore bits falling off the most significant end.

🔁 Conversion of representations

Chapter 1 (section 1.01) only converted integers. Now we convert real numbers.

Fixed point first

4.75 looks easy: 4 is 100 and .75 is .11, so 4.75 is 100.11. But a positive number must start with 0, so add a sign bit: 0100.11.

For −4.75, use two's complement on the representation of 4.75:

0100.11  converts to  1011.00  in one's complement
         then to      1011.01  in two's complement

Check with Method 2 of Worked Example 1.01 (Chapter 1): 1011 is −8 + 3, and .01 is .25, so −8 + 3 + .25 = −4.75 ✓

Most fractions can't be stored exactly

Binary fraction places are worth a half, a quarter, an eighth, a sixteenth and so on. Unless a denary fraction is a sum of these, it cannot be converted exactly. Of .1 to .9, only .5 converts exactly. (This was mentioned in Chapter 1, section 1.03, about storing currency values.)

Method for a positive value

1. Convert the whole-number part (Chapter 1, section 1.01).
2. Add the 0 sign bit.
3. Convert the fractional part using a method from Worked Example 16.01.
4. Put the whole-number and fractional parts together into the most significant bits of the mantissa.
5. Fill the remaining mantissa bits, and the exponent bits, with zeros.
6. Move the binary point by changing the exponent until the number is normalised.

For a negative value, treat it as positive for the first five steps. Then convert the mantissa to two's complement before doing step 6.

.63 × 2 = 1.26   so 1 is stored, giving the fraction .1
.26 × 2 = .52    so 0 is stored, giving the fraction .10
.52 × 2 = 1.04   so 1 is stored, giving the fraction .101
.04 × 2 = .08    so 0 is stored, giving the fraction .1010

7.75             = 111.11
add sign bit     = 0111.11
two's complement : invert → 1000.00, add 1 at the last place → 1000.01
                   (check: −8 + .25 = −7.75 ✓)
move the point 3 places left so it follows the sign bit:
                   1.00001 × 2^3
mantissa (10 bits) = 1000010000
exponent (4 bits)  = 0011
check: 1.000010000 = −1 + 1/32 = −0.96875;  −0.96875 × 2^3 = −7.75 ✓

⚠️ Problems with using floating-point numbers

Converting a denary real value to binary almost guarantees some approximation, and the mantissa has only so many bits.

Floating-point numbers are used in long mathematical procedures with repeated calculations, such as weather forecasting with a model of the atmosphere, or economic forecasting. Each result is recorded with a slight approximation. These rounding errors can become significant if a calculation is repeated enough times. The only way to stop them becoming a serious problem is more precision, that is, more mantissa bits. That is why languages offer double precision or quadruple precision.

The other problem is range. In the 8-bit format of Table 16.03 the largest value is 112. A calculation can easily produce more than that: an overflow error (Chapter 1, section 1.02). Floating point can also fail the other way. Divide a very small number by a number greater than 1 and the result may be smaller than the smallest value that can be stored: an underflow error. Depending on the situation, a program might carry on by treating the tiny number as zero, but that is risky.

📌 Summary

• Examples of non-composite user-defined data types include enumerated and pointer types.
• Record, set and class are examples of composite user-defined data types.
• File organisation allows for serial, sequential or direct access.
• Floating-point representation of a real number allows a wider range of values to be represented.
• A normalised floating-point representation gives the best precision for the value stored.
• Stored floating-point values rarely give an accurate representation of the denary equivalent.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.

TYPE TAnimal
    DECLARE AnimalName : STRING
    DECLARE AnimalAge : INTEGER
    DECLARE NumberInZoo : INTEGER
    DECLARE Location : STRING
ENDTYPE

12           = 1100
.43 × 2 = 0.86 → 0
.86 × 2 = 1.72 → 1
.72 × 2 = 1.44 → 1
.44 × 2 = 0.88 → 0 …
12.43 ≈ 1100.0110…
with sign bit   0 1100.011…
normalise       0.1100011 × 2^4   (only 7 bits fit after the sign bit)
mantissa  = 01100011
exponent  = 00000100

TYPE ThisDate
    DECLARE ThisDay   : (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
                         14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
                         24, 25, 26, 27, 28, 29, 30, 31)
    DECLARE ThisMonth : (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug,
                         Sep, Oct, Nov, Dec)
    DECLARE ThisYear  : INTEGER
ENDTYPE

DECLARE DateOfBirth : ThisDate

TYPE LocationRainfall
    DECLARE LocationName : STRING
    DECLARE Height       : INTEGER
    DECLARE Rainfall     : ARRAY[1:12] OF REAL
ENDTYPE

(a)  3.5 = 11.1 = 0.111 × 2^2
     mantissa 0.1110000 → 01110000
     exponent 2         → 00000010

(b)  start from +3.5:   01110000
     invert             10001111
     add 1              10010000
     exponent unchanged 00000010
     check: 1.0010000 = −1 + 0.125 = −0.875;  −0.875 × 2^2 = −3.5 ✓