Saturating arithmetic instructions in ARM Architecture - Time & Space Complexity

Time Complexity: Saturating arithmetic instructions

O(N)

Understanding Time Complexity

We want to understand how the time it takes to run saturating arithmetic instructions changes as the amount of data grows.

Specifically, we ask: how does execution time scale when using these instructions repeatedly?

Scenario Under Consideration

Analyze the time complexity of the following ARM saturating addition code.

    MOV R0, #0          ; Initialize counter
LOOP:
      QADD R1, R2, R3   ; Saturating add R2 and R3, store in R1
      ADD R0, R0, #1    ; Increment counter
      CMP R0, #N        ; Compare counter with N
      BLT LOOP          ; Repeat if counter < N
    

This code performs a saturating addition N times in a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The saturating addition instruction QADD inside the loop.
• How many times: It runs exactly N times, controlled by the loop counter.

How Execution Grows With Input

Each time we increase N, the number of saturating additions grows directly with it.

Input Size (N)	Approx. Operations
10	10 saturating adds
100	100 saturating adds
1000	1000 saturating adds

Pattern observation: The total work grows in a straight line as N increases.

Final Time Complexity

Time Complexity: O(N)

This means the time to complete the instructions grows directly in proportion to the number of times we run the saturating addition.

Common Mistake

[X] Wrong: "Saturating instructions take longer time per operation, so the total time grows faster than the number of operations."

[OK] Correct: Each saturating instruction runs in a fixed time similar to normal arithmetic; the total time depends mainly on how many times it runs, not on the instruction type.

Interview Connect

Understanding how loops with special instructions scale helps you explain performance clearly and shows you grasp how processors handle different operations.

Self-Check

"What if we replaced the saturating addition with a normal addition inside the loop? How would the time complexity change?"

Practice

1. What is the main purpose of saturating arithmetic instructions like QADD and QSUB in ARM architecture?

easy

A. To convert numbers between different bases

B. To perform floating-point calculations

C. To speed up multiplication operations

D. To keep numbers within fixed limits and avoid overflow or underflow

Solution

1. Step 1: Understand saturating arithmetic concept

   Saturating arithmetic limits the result to a maximum or minimum value instead of wrapping around.

2. Step 2: Identify the role of QADD and QSUB

   QADD and QSUB perform addition and subtraction with saturation to prevent overflow or underflow errors.

3. Final Answer:

   To keep numbers within fixed limits and avoid overflow or underflow -> Option D

4. Quick Check:

   Saturating arithmetic = Keep numbers within limits [OK]

Hint: Saturating means stopping at limits, not wrapping around [OK]

Common Mistakes:

• Confusing saturating with normal addition
• Thinking it speeds up multiplication
• Assuming it changes number bases

2. Which of the following is the correct syntax for the ARM instruction that adds two registers with saturation?

easy

A. ADDQ Rd, Rn, Rm

B. QADD Rd, Rn, Rm

C. QSUB Rd, Rn, Rm

D. ADDS Rd, Rn, Rm

Solution

1. Step 1: Recall ARM saturating addition syntax

   The correct instruction for saturating addition is QADD followed by destination and source registers.

2. Step 2: Compare options

   QADD Rd, Rn, Rm matches the correct syntax: QADD Rd, Rn, Rm. Others are either incorrect or different instructions.

3. Final Answer:

   QADD Rd, Rn, Rm -> Option B

4. Quick Check:

   QADD syntax = QADD Rd, Rn, Rm [OK]

Hint: QADD means saturating add; syntax is QADD Rd, Rn, Rm [OK]

Common Mistakes:

• Mixing QADD with ADDQ
• Confusing QSUB with QADD
• Using ADDS which is not saturating

3. Consider the following ARM assembly code snippet:

  MOV R0, #2147483647  ; Max positive 32-bit int
  MOV R1, #1
  QADD R2, R0, R1

What will be the value in register R2 after execution?

medium

A. 2147483648

B. -2147483648

C. 2147483647

D. 0

Solution

1. Step 1: Understand the initial values

   R0 holds the maximum 32-bit signed integer (2147483647), R1 holds 1.

2. Step 2: Apply QADD saturating addition

   Adding 2147483647 + 1 would overflow normal int, but QADD saturates at max value 2147483647.

3. Final Answer:

   2147483647 -> Option C

4. Quick Check:

   QADD saturates at max int = 2147483647 [OK]

Hint: QADD stops at max int, no overflow wrap-around [OK]

Common Mistakes:

• Assuming normal addition overflow
• Thinking result wraps to negative
• Confusing QADD with normal ADD

4. Identify the error in this ARM assembly code using saturating subtraction:

  MOV R0, #-2147483648  ; Min signed 32-bit int
  MOV R1, #1
  QSUB R2, R0, R1

What is the problem?

medium

A. No error; QSUB saturates and sets R2 to minimum value

B. QSUB will cause underflow and crash the processor

C. QSUB does not exist in ARM instruction set

D. MOV instructions are invalid for immediate values

Solution

1. Step 1: Check instruction validity

   QSUB is a valid ARM instruction for saturating subtraction.

2. Step 2: Understand saturating subtraction behavior

   Subtracting 1 from -2147483648 would underflow in normal arithmetic, but QSUB saturates at minimum signed int (-2147483648).

3. Final Answer:

   No error; QSUB saturates and sets R2 to minimum value -> Option A

4. Quick Check:

   QSUB saturates at min int, no crash [OK]

Hint: QSUB saturates at min int, no crash or error [OK]

Common Mistakes:

• Thinking QSUB causes processor crash
• Believing QSUB is invalid instruction
• Assuming MOV can't load immediate values

5. You want to safely add two signed 16-bit numbers in ARM assembly without overflow. Which approach correctly uses saturating arithmetic to achieve this?

hard

A. Use QADD16 instruction to add two 16-bit values with saturation

B. Use QADD instruction after sign-extending 16-bit numbers to 32-bit

C. Use normal ADD instruction and check overflow flag manually

D. Use QSUB instruction to add the numbers

Solution

1. Step 1: Understand 16-bit addition with saturation

   QADD16 performs two parallel 16-bit saturating additions on the low and high halves of the registers.

2. Step 2: Identify correct saturating addition for two 16-bit numbers

   Place the numbers in the low halves of source registers and use QADD16 Rd, Rn, Rm for saturation to 16-bit range.

3. Step 3: Evaluate other options

   Sign-extending to 32-bit then QADD saturates to 32-bit limits (e.g., 32767+32767=65534, not 32767). Normal ADD does not saturate; QSUB is subtraction.

4. Final Answer:

   Use QADD16 instruction to add two 16-bit values with saturation -> Option A

5. Quick Check:

   QADD16 = 16-bit lane saturating add [OK]

Hint: QADD16 for 16-bit saturating adds [OK]

Common Mistakes:

• Using QADD on sign-extended values (saturates to 32-bit range)
• Using normal ADD with manual overflow check
• Using QSUB for addition