This WAT program demonstrates loop unrolling for array summation. Instead of processing one element per iteration, the loop is unrolled by a factor of 4, meaning it processes four elements in each iteration. This reduces...

The `sum_array_unrolled` function calculates the sum of elements in an i32 array. It first determines how many full groups of 4 elements can be processed and how many remain. The main loop iterates `unrolled_len` times, but in each iteration, it loads and adds four elements at once. This reduces the number of loop control instructions (increments, comparisons, branches). After the unrolled loop, a separate loop handles the `remainder` elements. The time complexity remains O(N), but the constant factor is reduced due to fewer loop overheads, potentially leading to faster execution. Space complexity is O(1). Edge cases include empty arrays and arrays whose lengths are not multiples of the unrolling factor (4). The `create_test_array` helper is for demonstration.

function sum_array_unrolled(array, length): sum = 0 i = 0 unrolled_length = floor(length / 4) * 4 remainder = length - unrolled_length // Unrolled loop (process 4 elements at a time) while i < unrolled_length: sum = sum...

This WAT program implements a custom memory allocator that manages a pool of fixed-size memory chunks. It uses a free list, implemented as a linked list within the memory pool itself, to keep track of available chunks. T...

The custom allocator manages a contiguous block of memory divided into fixed-size chunks. A global variable, `$free_list_head`, points to the first available chunk. Each chunk, when not in use, contains a pointer (at a fixed offset, e.g., 4 bytes) to the next free chunk, forming a linked list. When `allocate_chunk` is called, it takes the chunk pointed to by `$free_list_head`, updates `$free_list_head` to point to the next chunk in the list, and returns the pointer to the allocated chunk. If `$free_list_head` is -1, the pool is full. `deallocate_chunk` takes a pointer, adds it to the front of the free list by updating its 'next' pointer and then setting `$free_list_head` to the deallocated chunk's pointer. It includes checks for invalid pointers and attempts to deallocate already freed chunks. The time complexity for allocation and deallocation is O(1) on average, assuming no need to check for already freed chunks. Space complexity is O(N) for the memory pool, where N is the number of chunks.

initialize memory pool with fixed-size chunks initialize free_list_head to point to the first chunk for each chunk (except the last): set its 'next' pointer to the address of the next chunk set the last chunk's 'next' po...

This WAT program implements an optimized matrix multiplication routine. It calculates the product of two matrices, C = A * B, where matrices are stored in row-major order. The implementation focuses on optimizing the inn...

The `matrix_multiply` function computes the product of two matrices A (m x n) and B (n x p) to produce matrix C (m x p). It iterates through each element C[i][j] of the result matrix. For each element, it computes the dot product of the i-th row of A and the j-th column of B. The inner loop (over k) accumulates the sum of products A[i][k] * B[k][j]. Indices are carefully calculated to access elements in row-major order. The time complexity is O(m * n * p), which is inherent to matrix multiplication. Space complexity is O(1) beyond the storage for the matrices themselves. Edge cases include checking for compatible dimensions (columns of A must equal rows of B) and ensuring the result matrix C is initialized to zeros before accumulation. The optimization lies in minimizing memory loads and maximizing arithmetic operations within the tight inner loop.

function matrix_multiply(A, B, C): rows_A = number of rows in A cols_A = number of columns in A rows_B = number of rows in B cols_B = number of columns in B if cols_A is not equal to rows_B: return error (incompatible di...

This WAT program implements a stack-based evaluator for postfix mathematical expressions. It parses a string representing a postfix expression, tokenizes it, and uses a stack to perform calculations. Numbers are pushed o...

The `evaluate_postfix` function processes a postfix expression string. It iterates through tokens, pushing numbers onto a simulated stack and applying operators to popped operands. The stack is implemented using linear memory, with `stack_ptr` and `stack_top` managing its state. Operator handling involves popping two operands, performing the operation (addition, subtraction, multiplication, division), and pushing the result. Division by zero is explicitly checked. The algorithm's time complexity is O(N), where N is the number of tokens, as each token is processed once. Space complexity is O(N) in the worst case for the stack, though typically much less for balanced expressions. Edge cases include empty expressions, single-number expressions, invalid tokens, stack underflow/overflow, and division by zero. The correctness relies on the property that in postfix notation, operands appear before their operators, allowing for direct stack manipulation.

function evaluate_postfix(expression_string): initialize stack set stack_top to -1 pointer = start of expression_string while pointer is not end of string: get next token and its length if token is empty, break loop if t...

This WAT program implements the binary search algorithm to efficiently find a target value within a sorted array. It repeatedly divides the search interval in half. If the value of the search key is less than the item in...

The `binary_search` function takes a pointer to a sorted array of i32s, its length, and the target value. It initializes `low` to 0 and `high` to `length - 1`. The core loop continues as long as `low <= high`. In each iteration, it calculates the middle index `mid`. It then compares the value at `array[mid]` with the `target`. If they match, `mid` is returned. If `array[mid]` is less than `target`, the search continues in the right half by setting `low = mid + 1`. If `array[mid]` is greater than `target`, the search continues in the left half by setting `high = mid - 1`. The loop invariant is that the target, if present, must lie within the inclusive range `[low, high]`. If the loop terminates without finding the target (i.e., `low > high`), -1 is returned. Time complexity is O(log N), and space complexity is O(1). Edge cases include empty arrays, target not present, and targets at the array's boundaries.

function binary_search(array, length, target): if length is 0: return -1 low = 0 high = length - 1 while low <= high: mid = low + (high - low) / 2 mid_value = array[mid] if mid_value == target: return mid else if mid_val...