Lab 05 | NPRG038

Part 1: Value Semantics and Immutability

In the assignment, you were tasked with designing a Fixed<TBase, TDot> type to represent fixed-point numbers. Just like the standard numeric types in C# (int, float, double), it makes sense for our fixed-point representation to have value semantics.

By defining this as a struct, we avoid heap allocation overhead and garbage collection pressure. This is especially critical in scenarios where fixed-point numbers are used heavily, such as in game engines, physics simulations, or on constrained hardware.

Furthermore, as we have seen in previous labs, enabling a struct to be mutable can lead to many unexpected behaviors when values are boxed or passed to functions (for example in situation where struct implements an interface). The problem is that mutability, by definition, lets the user modify the original object. This is problematic in cases where the “original” object is actually a copy (like during boxing or when passing a struct by value to another function). Therefore, it is much better to define the struct as immutable—that is, do not let its state be modified after creation.

In C#, we can enforce this for the entirety of the struct using the readonly keyword. The definition of our fixed-point type then looks like this:

public readonly struct Fixed<TBase, TDot>
    where TBase : IBinaryInteger<TBase>, IConvertible
    where TDot : IFractionalPartDefinition
{
    public TBase Value { get; init; }
    // ...
}

Question 1

If Fixed<TBase, TDot> relies on TDot to know how many bits are used for the fractional part (e.g., 3 bits for Dot3), why don’t we just store this as a field inside the struct?

private readonly int _fractionalBits;

What is the fundamental problem with this approach? Solution

Part 2: Static Abstract Interface Members

Since we do not store the fractional bit count in the struct instance, we need to extract it from the type parameter TDot itself. We achieve this by enforcing that TDot implements an interface with a static abstract member:

public interface IFractionalPartDefinition {
    public static abstract int Bits { get; }
}

This requires any implementing class (like Dot3 or Dot8) to define a static getter for the bit count.

Question 2

Why is using the expression body public static int Bits => 3; (below) better than writing public static int Bits { get; } = 3;? Solution

public sealed class Dot3 : IFractionalPartDefinition {
    public static int Bits => 3;
}

Part 3: Constraining Marker Classes

The classes Dot3, Dot8, etc., exist purely to satisfy generic constraints and provide constants. We want to strictly limit what a developer can do with these classes to prevent misuse.

Question 3.1

We don’t want developers to instantiate new Dot3(), create variables of type Dot3, or inherit from Dot3. What keywords should we use to forbid this? Solution

Question 3.2

Which of the class modifiers would you rather use for the Dot classes and why? (sealed or abstract) Solution

Question 3.3

Having chosen the sealed class, is it possible to constrain the Dot types a bit further to prevent instantiation? Solution

Part 4: Arithmetic Precision and Casting

When adding or subtracting fixed-point numbers, you simply add or subtract the underlying integers. However, multiplication and division are significantly more complex because they affect the position of the “virtual” decimal point.

When you multiply two fixed-point numbers that each have X fractional bits, the intermediate result inherently has 2 * X fractional bits.

Question 4.1

Look at the multiplication implementation from the reference solution:

public static Fixed<TBase, TDot> operator *(Fixed<TBase, TDot> left, Fixed<TBase, TDot> right) {
     // Step 1: Cast up to 64-bit to perform the math
     var resultUncorrected = left.Value.ToInt64(null) * right.Value.ToInt64(null);

     // Step 2: Shift back and truncate to original base type
     var rawResult = TBase.CreateTruncating(resultUncorrected >> TDot.Bits);

     // Step 3: Create the result wrapper
     return CreateFromRaw(rawResult);
}

Why do we cast the values to Int64 (long) before performing the multiplication, rather than multiplying the TBase values directly? Solution

Question 4.2

Why do we use TBase.CreateTruncating(...)? Solution

Question 4.3 (Bonus)

Is it possible to avoid losing precision during multiplication while using only the base type (e.g., without casting to a 64-bit type)? This would allow us to perform reliable multiplication even for long types. Solution

Part 5: Casting from Double

When converting a double to a Fixed point number, we must be careful with the order of operations.

public Fixed(double value) {
    double normalized = value * (1L << TDot.Bits);
    Value = TBase.CreateTruncating((long)normalized);
}

Scale First: We multiply the floating-point value by 2 to the power of Bits first. This shifts the fractional part of the double into the integer range.
Intermediate Cast: We cast to long to discard any remaining infinitesimal precision from the double.
Final Truncation: We use CreateTruncating to fit the scaled integer into our TBase.

Part 6: Generic List Summation and Additive Identity

In another part of the assignment, you were tasked with implementing a generic SumAll extension method. The goal is to create a method that can sum up the elements of a list, regardless of the specific numeric type used.

A naive first attempt at this implementation might look like the following:

public static class ListExtensions {
    public static T SumAll<T>(this List<T> list)
    {
        // Start by taking the first element
        T sum = list[0];

        for(int i = 1; i < list.Count; i++)
        {
            sum += list[i];
        }
        return sum;
    }
}

Question 5.1

What is the primary runtime flaw in the naive approach above, and how would you attempt to fix it? Solution

Complete solution can be found here.

Part 7: Enumerables and Collections

Lastly we discuss how to return collections from methods. This is where we distinguish between Lazy and Eager evaluation.

`IEnumerable<T>` (Lazy)

When a method returns IEnumerable<T> (often using yield return), it is Lazy. The values are not calculated until you actually iterate over them. This is memory efficient because you don’t need to store the whole list at once.

Use Case: Reading lines from a massive file or generating a mathematical sequence.
Key Tools: Enumerable.Range(start, count) or Enumerable.Empty<T>().

`List<T>` or `IReadOnlyList<T>` (Eager)

If a method returns a List, it is Eager. All items are calculated and stored in memory immediately.

Use Case: When you need to access items by index (list[5]) or need to know the Count multiple times without re-calculating the whole sequence.

Note that returning immutable (readonly) type allows you to cache the values without having to recompute them (you can’t cache reference to mutable list because user is allowed to modify the list; you gave the reference as modifiable type).

Rule of Thumb for designing function API

For input parameters use the most general type possible (usually IEnumerable<T>) so your method can accept arrays, lists, or even lazy sequences. This limits you, as an developer, but allows users to specify broader selection of types.

On the other hand, for return types when returning collection eagerly, consider more specific type. This again limits you (you will be more restricted to future changes), but once again gives users more functionality to use.

In an ideal world, we would use a static class. However, in C#, static classes cannot implement interfaces. Since Dot3 must implement IFractionalPartDefinition, we must use other modifiers.

Modifier	Inheritable?	Instantiable?	Variables Allowed?	Interface Support?
`static`	No	No	No	No
`abstract`	Yes	No	Yes	Yes
`sealed`	No	Yes	Yes	Yes

Yes, by adding a private constructor.

public sealed class Dot3 : IFractionalPartDefinition {
    public static int Bits => 3;
    private Dot3() {}
}

By making the constructor private, we prevent any code outside the class from using the new keyword. Combining sealed with a private constructor gets us as close to a static class as possible while still allowing interface implementation.

Yes, by using “Long Multiplication” in parts.

The idea is to treat our numbers as polynomials. If we have two large numbers of 2 * N bits, A and B, we can split them into “High” (H) and “Low” (L) parts of N bits each:

A = (AH * (1 << N) + AL)
B = (BH * (1 << N) + BL)

When we multiply them, we expand the expression:

(AH * (1 << N) + AL) * (BH * (1 << N) + BL) = AH * BH * (1 << 2 * N) + (AH * BL + AL * BH) * (1 << N) + AL * BL

By calculating these individual products (which are smaller and won’t overflow the base type) and then shifting and adding them carefully, we can reconstruct the full result.

But the whole point of introducing the fixed point type in the first place was (likely) to provide efficiency. This approach multiplies two numbers using four multiplications, two shifts and three additions, which will hardly be efficient.

The code relies on the assumption that the list is not empty. If a user passes an empty list, list[0] will throw an ArgumentOutOfRangeException at runtime. To make this robust, we need a way to initialize the sum variable to a neutral “zero” value before we even enter the loop.

Here are two common but suboptimal attempts to fix this using generic constraints:

Attempt A: The new() constraint

public static class ListExtensions {
    public static T SumAll<T>(this List<T> list)
        where T : new() // Requires a parameterless constructor
    {
        T sum = new();
        foreach (var item in list) {
            sum += item;
        }
        return sum;
    }
}

Attempt B: The struct constraint

public static class ListExtensions {
    public static T SumAll<T>(this List<T> list)
        where T : struct // Limits T to value types
    {
        T sum = default; // Initializes to zero-bit pattern
        foreach (var item in list) {
            sum += item;
        }
        return sum;
    }
}

Why these “fixes” are problematic:

Artificial Constraints: These constraints are often too restrictive. where T : struct prevents us from using the method with any reference types (classes) that might logically support addition. where T : new() excludes many useful types that don’t happen to have a public, parameterless constructor.
Lack of Mathematical Meaning: Just because a type can be initialized with new() or default doesn’t mean that the resulting value is interpretable as “zero”. For more complex type, the default state of a memory block (all zeros) might not be the actual additive identity.

The Mathematical Solution: `IAdditiveIdentity`

In mathematics, an identity element is a value that, when used in an operation, leaves the other value unchanged. For addition, the identity is a value id such that, for any x, id + x = x + id = x

For integers, this is 0. For string concatenation, this is an empty string "".

The generic math of C# provides an interface IAdditiveIdentity<T, T> which all base types implement that serves this purpose. Instead of guessing what zero looks like, we can explicitly require the type T to define its own identity:

public static class ListExtensions {
    public static T SumAll<T>(this List<T> list)
        where T : IAdditionOperators<T, T, T>, IAdditiveIdentity<T, T>
    {
        // We fetch the mathematically correct "zero" for type T
        T sum = T.AdditiveIdentity;

        foreach (var item in list) {
            sum += item;
        }
        return sum;
    }
}

By using T.AdditiveIdentity, we ensure that our SumAll method works correctly even for an empty list (returning the logical zero) and remains compatible with any type that correctly implements the standard math interfaces—including our custom Fixed<TBase, TDot> struct.