User-Defined Types and Floating-Point CHP13

Overview

• Topics: user-defined data types, file organization and access, floating-point representation and manipulation.
• Focus: definitions, examples, conversion methods, normalization, and common errors.
• Purpose: concise study notes for CAIE A2 Computer Science data representation.

User-Defined Data Types

• Definition: Data types constructed by the programmer from primitive types.
• Importance: improves code organization and reusability.
• Common examples: record, set, class, object, pointer, enumerated type.

Composite User-Defined Types

• Characteristic: reference at least one other type.

• Record

  • Collection of related items, possibly different types.
  • Example syntax:
    • TYPE TBook: DECLARE Name: STRING; DECLARE Isbn: INTEGER; ENDTYPE
    • DECLARE Book1: TBook; Book1.Name = "To Kill a Mockingbird"

• Set

  • Stores finite unique items in no particular order.
  • Supports set-theory operations.
  • Example syntax:
    • TYPE Numbers = SET OF INTEGERS
    • DEFINE EvenNumbers (2,4,6,8,10) : Numbers

• Class (OOP)

  • Template for objects with properties and methods; supports inheritance.
  • Example syntax:
    • CLASS Bird PRIVATE Name: STRING PUBLIC PROCEDURE NEW(pName: STRING) Name pName ENDPROCEDURE ENDCLASS
    • CLASS FlyingBird IMPLEMENTS Bird
    • Creating: MyPet NEW Bird("Kiwi")

Non-Composite User-Defined Types

• Characteristic: do not reference another type.

• Examples: integers, booleans, strings, characters.

• Enumerated Type

  • Ordered list of possible values.
  • Example:
    • TYPE Days: (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday)
    • DECLARE Today: Days; Today = Sunday; Today = Days + 1

• Pointer Type

  • References a memory location.
  • Example syntax:
    • TYPE PIntPointer: ^INTEGER
    • DECLARE MyPointer: PIntPointer
    • MyPointer^ = 3 (sets value at pointed address)
    • MyPointer = @variable (points to variable's address)

File Organization

• Serial

  • Records stored chronologically, appended to end.
  • Benefits: no sorting required, easy appends.

• Sequential

  • Records stored ordered by key field; insertion requires updating file (new version).
  • Benefits: suitable for batch processing, maintains sorted order.

• Random

  • Records stored with no set order; direct modification possible.
  • Uses hashing of unique key to home location; handles collisions with overflow or linear probing.
  • Benefits: supports fast real-time processing.

File Access

• Sequential Access

  • Read records in storage order until target found or key exceeded.
  • Used with serial and sequential file organizations.

• Direct / Random Access

  • Access specific records directly.
  • Used with sequential (via index of key fields) and random (via hash) organizations.

Floating-Point Representation

• Structure: Mantissa (M) × 2^Exponent (E).
  • Mantissa: determines precision (more bits = more accuracy).
  • Exponent: determines range (more bits = larger range).

Converting Binary to Positive Float (example steps)

• Given mantissa and exponent bits:

  • Place the binary point in mantissa.
  • Multiply the mantissa by 2^exponent (move decimal point right).
  • Convert resulting binary to decimal.

• Example (mantissa 01101000, exponent 0011 -> 3):

  • Binary placed and shifted to give value 0110.1 -> decimal 6.5

Converting Float to Binary (example steps)

• Express float as fraction (e.g., 6.5 = 13/2).
• Multiply denominator by 2 repeatedly until denominator > numerator to find exponent.
• Decompose fraction into binary fractions (1/2, 1/4, 1/8, ...).
• Assemble mantissa bits from fractional decomposition.
• Example result: mantissa 01101000, exponent 0011.

Converting Binary to Negative Float

• Obtain negative float by taking two's complement of the positive binary float representation.
• Do not take two's complement of the exponent.
• Example: +3.5 representation becomes -3.5 after two's complement applied to mantissa/sign.

Normalization

• Goal: unique representation and maximal precision.
• For positive numbers: ensure first two bits differ (remove leading zeros before first 1).
• For negative numbers: first bit must be 1; shift mantissa until 1.0 reached and adjust exponent by subtracting shifts.
• Benefits:
  • Prevents multiple representations of same number.
  • Maximizes precision for given bit width.
  • Optimizes range storage.

Important Floating-Point Values

| Description | Binary Example | | Largest positive number | 0111 1111 0111 | | Smallest positive number | 0000 0001 1000 | | Smallest normalized positive number | 0100 0000 1000 | | Largest magnitude negative number | 1000 0000 0111 |

Errors In Floating-Point Computations

• Rounding Error

  • Occurs when values cannot be exactly represented in binary.
  • Small approximation errors accumulate in operations (e.g., 0.1 + 0.2 ≠ 0.3 exactly).

• Underflow

  • Occurs when a number is too close to zero to represent; precision lost.

• Overflow

  • Occurs when magnitude exceeds representable range for given bits.

Key Terms and Definitions

• Mantissa: part of float that stores significant digits; affects precision.
• Exponent: part of float that scales the mantissa; affects range.
• Normalization: adjusting mantissa and exponent to a standard form.
• Two's Complement: method to represent negative numbers in binary.
• Hashing: mapping keys to storage locations for random file organization.
• Collision: when two keys map to same hash location; resolved via overflow/linear search.

Action Items / Next Steps (if studying)

• Practice conversions both directions with other examples.
• Work through normalization with positive and negative examples.
• Compare file organization and access methods with real-world use cases.
• Solve exercises on pointer usage, record definitions, and enumerated types.