# Question B: uf8 encode and decode ##
## Overview

This program tests the UF8 compression scheme by encoding and decoding a series of integer values.

It prints: Original → Encoded (hex) → Decoded.

Validates:

Exact match for small values (<16).

Allows up to 6.25% relative error for larger values (>=16).

Reports [PASS] or [FAIL] for each test and prints a summary at the end.

The program uses RISC-V system calls:

a7=4: print string

a7=1: print integer

a7=11: print character

a7=10: exit program
#### Data Section (.data)

Strings: headers, arrows, messages (PASS/FAIL, summary, newline) for console output.

Test values: array test_values (13 integers in this version) and test_count.

Counters: total, pass_count, fail_count.
#### Main program
##### Initialization
set stack pointer

lui sp, 0x10010
addi sp, sp, -32

##### Test Loop
Load original value

slli t0,s2,2       # index*4
add t0,s0,t0
lw s3,0(t0)        # s3 = original value

##### UF8 decode

mv a0,s3
jal ra,uf8_encode
mv s4,a0            # s4 = encoded byte

##### UF8 encode

mv a0,s4
jal ra,uf8_decode
mv s5,a0            # s5 = decoded integer

##### Validation
If <16: decoded must exactly match original (beq s5,s3,test_pass).

Else: allow |decoded - original| * 16 <= original (6.25% tolerance).

Uses

sub t0,s5,s3
bgez t0,diff_positive
neg t0,t0
slli t0,t0,4
ble t0,s3,test_pass

#### Print_hex function
First, prints one byte as two hex characters.

Second, high nibble: srli a0,s0,4 → if <10 → '0'..'9', else 'a'..'f'.

Third, low nibble: andi a0,s0,0x0F → same conversion.

Fourth, prints characters with syscall a7=11.

Lastly, restores s0 on stack to preserve value.

#### UF8 Decode
Input: encoded byte [exp:4][mant:4].

Output: decoded integer.

Algorithm:

First, extract mantissa (t0 = a0 & 0x0F) and exponent (t1 = a0 >> 4).

Second, compute offset = (2^exp - 1) << 4.

Third, shift mantissa: mantissa << exp.

Fourth, sum: value = (mantissa << exp) + offset.

Lastly, return in a0.

#### UF8 Encode
Input: integer a0. Output: 1-byte UF8 [exp:4][mant:4].

Each step:

First, if a0 < 16 → no compression needed (exp=0, mant=a0).

Else, find exponent exp. Next is computing base_offset = sum of previous blocks.

Loop:

candidate = base_offset + block_size
if candidate > value → done
else base_offset = candidate, block_size <<=1, exp++

Compute mantissa

remainder = value - base_offset
mantissa = remainder >> exp
mantissa &= 0x0F

Combine: encoded = (exp << 4) | mantissa and return a0.

#### Validation rules
smaller than 16: exact match.

Else relative error ≤ 6.25%:

|decoded - original| / original <= 1/16

## Output Observations

### Small value (<16)
Test 1–3: 0, 7, 15 → encoded = original (0x00, 0x07, 0x0f)

Decoded values exactly match the original → [PASS].

### Great value (>=16)
Test 4–13: 16, 18, 46, 48, 100, 144, 240, 275, 976, 1000

UF8 compression uses exponent/mantissa:

* Example: 100 → 0x2d
* High nibble: exponent = 2 (0x2 = 2)
* Low nibble: mantissa = 13 (0xd = 13)
* Decoded: (13 << 2) + ((2^2 - 1) << 4) = 52 + 48 = 100
* Slight rounding differences

* Test 11–13: 275 → 0x42 → 272, 976 → 0x5f → 976, 1000 → 0x5f → 976
* The decoded value is slightly different from original if the exact integer can’t be represented in 1 byte and the relative error is ≤ 6.25% → [PASS].

# Leetcode question #
## 2571. Minimum Operations to Reduce an Integer to 0

Hint:
You are given a positive integer n, you can do the following operation any number of times:

Add or subtract a power of 2 from n.
Return the minimum number of operations to make n equal to 0.

A number x is power of 2 if x == 2i where i >= 0.

* Example 1:

Input: n = 39
Output: 3

Explanation: We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

* Example 2:

Input: n = 54
Output: 3

Explanation: We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.

## Implementation

1. Initialiazation

* Load n = 39 into t0.
* Set operation counter t1 = 0.
2. Perform Operations
* t0 = t0 + 1 (Add 1 → n = 40)
* t0 = t0 - 8 (Subtract 8 → n = 32)
* t0 = t0 - 32 (Subtract 32 → n = 0)
* Each step increments the counter t1.
3. Store and print results
* Save t1 (which equals 3) into memory label result.
* Load result into a0 and print using syscall a7 = 1.
* Program exits with syscall a7 = 10.

## 1338. Reduce Array Size to The Half
You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

### Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7]

Output: 2

Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.
Example 2:

Input: arr = [7,7,7,7,7,7]

Output: 1

Explanation: The only possible set you can choose is {7}. This will make the new array empty.

## Implementation

### Data layout

.data
freq:   .word 0,0,2,4,0,3,0,1,0,0,0,0,0,0,0,0
result: .word 0

* freq is a contiguous array of 16 words (each word = 4 bytes). The array corresponds to frequencies of integer values 0 through 15.

* Interpretation: freq[0] = 0, freq[1] = 0, freq[2] = 2, freq[3] = 4, freq[4] = 0, freq[5] = 3, freq[6] = 0, freq[7] = 1, etc.

* result allocates one word reserved for storing the final answer (the set_size).

### Initialization

li t0, 0              # t0 = set_size
    li t1, 0              # t1 = total_removed
    li t2, 5              # t2 = half

* t0 — set_size: counter of how many distinct values we selected (initially 0).
* t1 — total_removed: running total of elements removed (initially 0).

* t2 — half: the target number to reach or exceed (here hardcoded 5, because original array length is 10 and half = 10/2).

### Pick the first (largest) frequency (hardcoded as freq[3] = 4)

    lw t3, freq+12        # freq[3] = 4
    add t1, t1, t3        # total_removed += 4
    addi t0, t0, 1        # set_size++

* lw t3, freq+12: load the 32-bit value at memory address freq + 12. 12 = 3 * 4, so this reads freq[3]. After this instruction t3 = 4.

* add t1, t1, t3: add t3 into t1. So total_removed = 0 + 4 = 4.

* addi t0, t0, 1: increment set_size to reflect that we selected one distinct value. So t0 = 1.
### Check whether we reached the target (half)

 blt t1, t2, pick_second
j done                # already >= half

* blt t1, t2, pick_second — branch to label pick_second if t1 < t2 (signed <). Here 4 < 5 so the branch is taken.

* If the branch were not taken (i.e., t1 >= t2), the unconditional j done would execute and the program would skip selecting more values. (In the current run we do take the branch.)

### Pick the second frequency (hardcoded as freq[5] = 3)

pick_second:
    lw t3, freq+20        # freq[5] = 3
    add t1, t1, t3        # total_removed += 3
    addi t0, t0, 1        # set_size++

* lw t3, freq+20: load freq[5] because 20 = 5 * 4. After this t3 = 3.

* add t1, t1, t3: accumulate total_removed = 4 + 3 = 7.

* addi t0, t0, 1: increment set_size to 2.

### Store the result into memory

done:
    la t4, result
    sw t0, 0(t4)

* la t4, result — load the address of the result label into register t4. This is needed because memory store uses base+offset addressing (sw value, offset(base)).

* sw t0, 0(t4) — store the word in t0 (which holds set_size = 2) to memory address t4 + 0. After this instruction, result contains the integer 2.

### Output
* The program simulates removing items in order of their frequency until at least half of the total items are removed.

* First removal: 4 items (still less than half)

* Second removal: +3 items (total 7 ≥ 5)

* It took 2 frequency values to reach half the total,
* so the minimum set size = 2. Output is 2.

# Question C : BF16
BF16 Format Overview

The BFloat16 (BF16) format is a 16-bit floating-point representation used by Google Brain to reduce memory usage while preserving float32’s dynamic range.

## Arithmetic Opeations
### Add implementation

srli s2, s0, 15        # extract sign_a
srli s3, s0, 7
andi s3, s3, 0xFF      # extract exp_a
andi s4, s0, 0x7F      # extract mant_a
...
bnez s3, add_imp_a     # add implicit 1 to mantissa if normalized

* Sign, exponent, mantissa are extracted using shifts and masks.

* Normalized numbers get implicit 1 added to mantissa (0x80).

* Exponents are aligned for addition/subtraction.

beq s2, s5, same_sign_add
sub t4, s4, t1         # different signs -> subtraction
...
same_sign_add:
add t4, s4, t1         # same sign -> addition

* Addition or subtraction depends on signs.

* Handles overflow (shift mantissa right, increment exponent).

andi t4, t4, 0x7F
slli t3, t3, 7
slli t5, t5, 15
or a2, t3, t4
or a2, a2, t5           # pack result into BF16

* Pack sign, exponent, mantissa into 16-bit BF16 result.

### MUL / DIV
* Similar structure:

* Extract sign, exponent, mantissa

* Add implicit 1 if normalized

* Compute result sign: sign_a XOR sign_b

* Multiply/divide mantissas using integer arithmetic

* Adjust exponent according to BF16 rules (exp_a + exp_b - 127 for MUL, exp_a - exp_b + 127 for DIV)

* Normalize mantissa if overflow/underflow occurs

* Pack into BF16

### SQRT
#### Input and Bit Extraction

mv s0, a0          # Load BF16 input
srli s2, s0, 15     # Extract sign bit
srli s3, s0, 7      # Extract exponent (8-bit)
andi s3, s3, 0xFF
andi s4, s0, 0x7F   # Extract mantissa (7-bit)

s2 = sign (0 = positive, 1 = negative)

s3 = exponent (8 bits)

s4 = mantissa (7 bits)

This is equivalent to extracting the sign, exponent, and mantissa from a BF16 number.

#### Special Case Handling

beqz s3, sqrt_zero      # exponent=0 ⇒ sqrt(0)=0
bgez s2, sqrt_pos       # sign≥0 ⇒ continue
sqrt_nan:
li a2, 0x7FC0           # Return NaN if x < 0
j ret_sqrt
sqrt_zero:
li a2, 0                # Return 0 for input zero
j ret_sqrt

If the number is 0, return 0.

If the number is negative, return NaN (0x7FC0).

Otherwise, continue to calculate sqrt.

#### Approximate Square Root Calculation

slli t0, s3, 7
or t0, t0, s4
srli t0, t0, 1
ori t0, t0, 0x40
mv a2, t0

slli t0, s3, 7 → shift exponent into mantissa position, forming a temporary 16-bit value.

or t0, t0, s4 → combine exponent and mantissa.

srli t0, t0, 1 → divide by 2 (approximation a/2).

ori t0, t0, 0x40 → add a constant 0.5 to improve the approximation (a/2 + 0.5).

mv a2, t0 → store the approximate sqrt result into a2