Study Guide: Factorial Calculation in C

1. C Implementation of Factorial

Code:

// Calculate the factorial of n.
int factorial(int n)
{
  int result = n;

  while(--n > 0)
  {
    result = result * n;
  }

  return result;
}
  

Functionality:

- Takes an integer n as input.

- Calculates the factorial of n.

- Uses a while loop and a local variable result to compute the factorial.

- Returns the calculated factorial value.

Key Aspects:

- Uses a while loop to iterate.

- The --n operator decrements n before its value is compared to 0.

- More readable compared to assembly language.

- Portable and can be compiled for different processor types.

2. Exercise: Running the C Code

Goal: Understand the step-by-step execution of the C factorial function.

Method:

- Trace the code's execution with a specific input value (e.g., n = 4).

- Keep track of variable values (n and result) before and after each step.

Expected Outcome: Verify that the function returns the correct factorial (e.g., 24 for n = 4).

3. Compilation and Disassembly

Process:

- C code is compiled into machine code.

- Machine code can be disassembled into assembly language.

Implication: Compiled programs can be analyzed even without the original source code.

ARM Assembly Output:

Address     Assembly
0001051c    sub     r3, r0, #1
00010520    cmp     r3, #0
00010524    bxle    lr
00010528    mul     r0, r3, r0
0001052c    subs    r3, r3, #1
00010530    bne     00010528
00010534    bx      lr
  

Compiled C code outputs similar logic to the ARM assembly above.

Note: A compiler translates high-level language to machine code.

4. Cross-Platform Compilation

Advantage of High-Level Languages: Code portability.

Concept: The same C code can be compiled for different processors (e.g., ARM, x86) and operating systems (e.g., Linux, Windows), as long as it doesn’t depend on OS-specific features.

x86 Assembly Output (Windows):

Address     Assembly
00406c35    mov     ecx,dword ptr [esp+4]
00406c39    mov     eax,ecx
00406c3b    jmp     00406c40
00406c3d    imul    eax,ecx
00406c40    dec     ecx
00406c41    test    ecx,ecx
00406c43    jg      00406c3d
00406c45    ret
  

5. Key Takeaways

- High-level languages simplify development compared to assembly.

- Compilers handle the translation to machine code.

- High-level languages enable portability across processors and operating systems.

- Compiled code can be disassembled to study its underlying structure.

KembaraXtra-Computer Science - Functions

1. What are Functions?

Definition: A function is a reusable block of code that performs a specific task.

Purpose:

• Avoid code duplication.
• Promote code reusability.
• Improve code organization and readability.

Terminology: Functions may also be called subroutines, procedures, or methods (slight differences in meaning may exist depending on the language).

DRY Principle: Functions adhere to the "Don't Repeat Yourself" (DRY) principle by reducing duplicative code.

Encapsulation: Functions encapsulate internal details, providing an interface (inputs and outputs) for usage. Users don't need to know the inner workings.

2. Defining Functions

Definition: Creating a function and specifying its behavior.

Elements of a Function Definition:

• Name: A unique identifier for the function.
• Parameters (Inputs): Values passed to the function when it is called.
• Body: The code block containing the instructions the function executes.
• Return Value (Output): The value the function sends back to the caller (optional).

Example (C):

double areaOfCircle(double radius) {
    double area = 3.14 * radius * radius;
    return area;
}

• double: Return type (floating-point number).
• areaOfCircle: Function name.
• double radius: Input parameter (radius of the circle).
• { ... }: Function body.
• return area: Returns the calculated area.

Example (Python):

def area_of_circle(radius):
    area = 3.14 * radius * radius
    return area

• def: Keyword to define a function.
• Type declarations are not required in Python.

3. Calling Functions

Definition: Executing a defined function.

Process:

1. The calling code invokes the function.
2. Parameters are passed (if any).
3. Control is transferred to the function.
4. The function executes its code.
5. The function returns control (and a return value, if any) to the caller.

Example (C):

double area1 = areaOfCircle(2.0);
double area2 = areaOfCircle(38.6);

Example (Python):

area1 = area_of_circle(2.0)
area2 = area_of_circle(38.6)

The returned value can be stored in a variable or ignored (though ignoring the return value might not be useful, depending on the function).

4. Using Libraries

Definition: Leveraging pre-written functions provided by programming languages or third-party developers.

Standard Library: A set of functions included with a programming language.

Examples: Printing to the console, file operations, text processing.

C and Python both have standard libraries. Python's is known to be extensive.

Additional Libraries: Libraries created by developers and shared for others to use.

Package Managers: Tools for managing and distributing libraries (packages).

• Python: pip (widely used).
• C: Multiple package managers exist, but none are universally adopted.

Program Flow: Controlling What Your Code Does

Core Idea: Program flow (or control flow) lets your program make decisions and repeat actions based on conditions.

1. If Statements: Doing Something Based on a Condition

Purpose: Executes a block of code only if a specified condition is true. Optionally includes else to execute a different block if the condition is false.

Basic Structure:

Python:

if condition:
    # Code to execute if condition is true
else:
    # Code to execute if condition is false

C:

if (condition) {
    // Code to execute if condition is true
} else {
    // Code to execute if condition is false
}

Key Differences (Python vs. C):

• Code Blocks:
• Python: Uses indentation to define code blocks (lines with the same indentation level belong to the same block).
• C: Uses curly braces {} to define code blocks. Braces can be omitted for single-line blocks.
• elif (Python) / else if (C): Used to check multiple conditions in sequence. The elif/else if condition is only evaluated if the preceding if or elif/else if condition was false.

Python:

if condition1:
    # Code for condition1
elif condition2:
    # Code for condition2
else:
    # Code if neither condition1 nor condition2 is true

C:

if (condition1) {
    // Code for condition1
} else if (condition2) {
    // Code for condition2
} else {
    // Code if neither condition1 nor condition2 is true
}

2. Looping: Repeating Actions

Purpose: Executes a block of code repeatedly.

Types:

• while loop: Repeats as long as a condition is true.

Python:

while condition:
    # Code to repeat

C:

while (condition) {
    // Code to repeat
}

Important: Make sure the condition eventually becomes false to avoid an infinite loop!

• for loop: Iterates over a sequence of values (numbers, items in a list, etc.).

C Style (for with numeric range):

for (initialization; condition; increment/decrement) {
    // Code to execute in each iteration
}

• initialization: Executed once at the beginning of the loop (e.g., int x = 1;).
• condition: Checked before each iteration. The loop continues as long as the condition is true (e.g., x <= 10;).
• increment/decrement: Executed after each iteration (e.g., x++;).

Python Style (for with collection):

for item in collection:
    # Code to execute for each item in the collection

• collection: A list, tuple, string, or other iterable object.
• item: A variable that takes on the value of each item in the collection during each loop iteration.

Study Guide: Logic in Programming

I. Introduction

• Processors excel at logical operations, which are fundamental to digital circuits.

• Programming languages provide operators for handling logic.

• Two main types of logical operators:

• Bitwise Operators: Operate on individual bits of integers.
• Boolean Operators: Operate on Boolean (true/false) values.

• Terminology varies across languages (e.g., C uses "logical" instead of "Boolean"). This guide will use "bitwise" and "Boolean."

II. Bitwise Operators

• Act on individual bits of integers.

• Result: an integer value.

• Perform logical operations (AND, OR, XOR, NOT) on the bits of integers in parallel.

• Operators (common in C and Python):

• AND: &
• OR: |
• XOR: ^
• NOT (complement): ~

Example (Python):

x = 5  # Binary: 0101
y = 3  # Binary: 0011
a = x & y  # Bitwise AND
b = x | y  # Bitwise OR

# a is 1 (0001 in binary)
# b is 7 (0111 in binary)

Explanation of Example

• AND: The result is 1 only when both corresponding bits are 1.

• 5 & 3:

0101
0011
----
0001 (1 in decimal)

• OR: The result is 1 if either corresponding bit (or both) is 1.

• 5 | 3:

0101
0011
----
0111 (7 in decimal)

III. Boolean Operators

• Work on Boolean values (true or false).

• Result: a Boolean value.

• Boolean values: represented differently in different languages (e.g., True or False in Python).

• Boolean variable: a named memory address holding a true or false value.

• Expressions can evaluate to true or false (e.g., item_cost > 5).

Boolean Operators:

• Perform logical operations (AND, OR, NOT) on Boolean values.

• Example: item_on_sale and item_cost > 5 (checks if both conditions are true).

Comparison Operators:

• Compare two values and evaluate to true or false.

Important:

• == (double equals) is for equality comparison (returns true/false).
• = (single equals) is for assignment (sets a variable's value).
• Example: x == 5 (is x equal to 5?) vs. x = 5 (set x to 5).