Addultiplication: A Step-by-Step Guide to Implement Multiplication Using Only the Addition Operator

Introduction

The term "Addultiplication" is a blend of "Addition" and "Multiplication", reflecting its core principle: replacing the conventional multiplication operator (*) with a series of repeated addition operations. This method isn’t just a theoretical exercise—it has practical applications in low-level computing, algorithm optimization, and educational contexts where a deep understanding of fundamental arithmetic operations is desired.

Project Overview

The Addultiplication project demonstrates how to perform integer multiplication using only the addition operator (+). Rather than directly using the multiplication operator, the technique involves:

• Storing numbers in arrays where each element represents a single digit.
• Implementing helper functions to perform digit-wise arithmetic, including addition with proper carry management.
• Calculating large-scale arithmetic operations, such as 100! (100 factorial), by using repeated addition to simulate multiplication.

This approach allows us to work with numbers larger than what standard data types can hold, and it offers insight into the low-level mechanics of arithmetic operations.

Historical Context and Importance

Before the advent of modern high-performance computers and arbitrary-precision arithmetic libraries (like GMP), engineers and mathematicians had to implement methods for handling very large numbers manually. These early techniques, which often involved simulating arithmetic operations through basic, repeatable steps (such as addition in place of multiplication), were crucial for:

• Resource-constrained computing: Early computers had limited processing power and memory. Techniques that broke down complex operations into simpler, repeatable steps were easier to implement on the hardware available at the time.
• Educational purposes: Understanding how basic arithmetic operations can be decomposed into simpler steps (e.g., repeated addition for multiplication) offers valuable insight into how computers perform calculations at a fundamental level.
• Algorithmic efficiency improvements: Even though modern computers can multiply large numbers quickly, studying these methods helps in designing algorithms that are both efficient and optimized for specific tasks, especially in environments where hardware limitations still exist.

By exploring these historical techniques, developers and computer scientists can appreciate the evolution of numerical methods and the ingenuity required to work within the constraints of earlier computing systems.

Why It’s Useful to Know These Techniques

Understanding methods like Addultiplication is beneficial for several reasons:

• Foundational Knowledge: It deepens your understanding of arithmetic operations beyond the use of high-level operators. Knowing how multiplication can be simulated by addition provides insight into the underlying processes of computer arithmetic.
• Algorithmic Thinking: It trains you to think about problems in a modular, step-by-step manner, which is essential when developing efficient algorithms.
• Resource-Limited Environments: In systems where certain operations may be unavailable or costly (for example, in embedded systems or specialized hardware), having alternative methods can be invaluable.
• Historical Insight: Studying these methods gives you perspective on how early computer scientists overcame hardware limitations, which can inspire innovative solutions in modern applications.

Project Structure

The Addultiplication project is organized into several modular components:

main.c

This file is the entry point of the program. It:

• Initializes BigNumbers from input strings.
• Demonstrates arithmetic operations such as addition and multiplication.
• Computes and displays the factorial of 100 using repeated addition to simulate multiplication.

Below is an excerpt from main.c:

int main() {
  BigNumber num1 = createBigNumber("123");
  BigNumber num2 = createBigNumber("456");
  BigNumber sum = addBigNumbers(&num1, &num2);
  printf("Sum: ");
  printBigNumber(&sum);

  int multiplier = 3;
  BigNumber product = multiplyBigNumberByInt(&num1, multiplier);
  printf("Product: ");
  printBigNumber(&product);

  BigNumber factorial = createBigNumber("1");
  for (int i = 2; i <= 100; i++) {
    factorial = multiplyBigNumberByInt(&factorial, i);
  }
  printf("100! = ");
  printBigNumber(&factorial);
  
  return 0;
}

big_number.c & big_number.h

These files define the BigNumber type and functions for:

• Representing large numbers as arrays of digits.
• Initializing BigNumbers from strings.
• Printing BigNumbers.

Key features include:

• Reverse order storage: Digits are stored in reverse order (least significant digit first) to simplify arithmetic operations.
• Fixed size arrays: The macro MAX_DIGITS sets the maximum size for the number representation.

Example of the BigNumber structure:

/**
 * @brief Represents a large number using an array of digits.
 *
 * This structure stores a large integer as an array where each element holds a single digit.
 * The digits are stored in reverse order (i.e., the least significant digit is at index 0)
 * to simplify arithmetic operations such as addition and multiplication.
 *
 * The `length` field indicates how many digits are currently used in the array.
 *
 * @note The maximum number of digits that can be stored is defined by the macro `MAX_DIGITS`.
 */
typedef struct {
    int digits[MAX_DIGITS];
    int length;
} BigNumber;

operations.c & operations.h

These files encapsulate the core arithmetic operations:

• Addition: The addBigNumbers function performs digit-wise addition while managing carry-over.
• Multiplication: The multiplyBigNumberByInt function simulates multiplication by performing repeated addition.

A helper function, getDigitAndCarry, is used to calculate the resulting digit and carry from the sum of two digits. This function can conditionally use modulo/division operators or a subtraction-based approach, controlled via compile-time directives. Here is an excerpt:

/**
 * @brief Computes the least significant digit and carry from a given sum.
 *
 * If USE_MODULO_DIVISION is defined, the function uses modulo (%) and division (/) operators.
 * Otherwise, it subtracts 10 repeatedly to determine the digit and carry.
 *
 * @param sum   The sum of digits and carry.
 * @param digit Pointer to store the resulting least significant digit.
 * @param carry Pointer to store the resulting carry.
 */
static void getDigitAndCarry(int sum, int *digit, int *carry) {
    #ifdef USE_MODULO_DIVISION
        *digit = sum % 10;
        *carry = sum / 10;
    #else
        int temp = sum;
        int tempCarry = 0;
        while (temp >= 10) {
            temp -= 10;
            tempCarry++;
        }
        *digit = temp;
        *carry = tempCarry;
    #endif
}

Additional Implementation Details

To handle scenarios where the modulo and division operators might be restricted, the code leverages a compile-time directive (USE_MODULO_DIVISION). You can define this directive in your CMakeLists.txt using:

target_compile_definitions(addultiplication PUBLIC USE_MODULO_DIVISION)

or

add_definitions(-DUSE_MODULO_DIVISION)

If the directive is not defined, the code falls back on a more elementary subtraction-based approach to calculate the digit and carry.

Conclusion

The Addultiplication project not only demonstrates an alternative method to perform multiplication using repeated addition, but it also serves as a historical nod to early computational techniques. By understanding and implementing these methods, you gain:

• Deeper Insight: Into the low-level mechanics of arithmetic.
• Enhanced Problem-Solving Skills: That are applicable in resource-constrained or specialized environments.
• Historical Perspective: On how early computing challenges were met with innovative solutions.

Complete source code is hosted on Addultiplication Repository

Happy coding and exploring your insight on the basic operations possible with computers!