How do I square a number without using multiplication?

Squaring a Number Without Multiplication: Algorithms and Implementations

Explore various algorithms to calculate the square of a number without relying on the multiplication operator, focusing on addition-based methods and bitwise operations.

Calculating the square of a number, n * n, is a fundamental operation in mathematics and computer science. While the most straightforward approach involves using the multiplication operator, there are scenarios where this operator might be unavailable, disallowed, or inefficient for specific hardware architectures. This article delves into alternative methods to square a number, primarily focusing on techniques that leverage addition, bit shifts, and other mathematical properties.

Method 1: Repeated Addition (Sum of Odd Numbers)

One of the most intuitive ways to square a number without direct multiplication is by using repeated addition. A lesser-known mathematical property states that the square of any positive integer n is equal to the sum of the first n odd numbers. For example, 1² = 1, 2² = 1 + 3 = 4, 3² = 1 + 3 + 5 = 9, and so on. This method is simple to understand and implement, making it a good starting point for our exploration.

flowchart TD
    A[Start] --> B{"Input n"}
    B --> C["Initialize sum = 0, odd_num = 1"]
    C --> D{i from 1 to n}
    D -->|Yes| E["sum = sum + odd_num"]
    E --> F["odd_num = odd_num + 2"]
    F --> D
    D -->|No| G["Return sum"]
    G --> H[End]

Flowchart for squaring a number using the sum of odd numbers method.

def square_sum_of_odds(n)
  return 0 if n == 0
  sum = 0
  odd_num = 1
  n.times do
    sum += odd_num
    odd_num += 2
  end
  sum
end

puts square_sum_of_odds(5) # Expected: 25
puts square_sum_of_odds(0) # Expected: 0
puts square_sum_of_odds(7) # Expected: 49

Ruby implementation of squaring using the sum of odd numbers.

Method 2: Bitwise Operations (Binary Squaring)

For numbers represented in binary, squaring can be achieved using bitwise operations, specifically left shifts and additions. The core idea is based on the distributive property of multiplication: n² = n * n = n * (2^a + 2^b + ...) where 2^a + 2^b + ... is the binary representation of n. Each 2^k term corresponds to a set bit in n. Multiplying by 2^k is equivalent to a left shift by k positions (n << k).

Consider n = 5, which is 101 in binary. 5 * 5 can be thought of as 5 * (4 + 1) = 5 * 4 + 5 * 1. In bitwise terms, this is (5 << 2) + (5 << 0). This method is generally more efficient than repeated addition, especially for processors optimized for bitwise operations.

def square_bitwise(n)
  return 0 if n == 0
  result = 0
  temp_n = n.abs # Work with absolute value, square is always positive
  
  # Iterate through each bit of temp_n
  # If the k-th bit is set, add (n << k) to the result
  k = 0
  while temp_n > 0
    if (temp_n & 1) == 1 # Check if the least significant bit is 1
      result += (n << k)
    end
    temp_n >>= 1 # Shift temp_n right by 1 to check the next bit
    k += 1
  end
  result
end

puts square_bitwise(5)  # Expected: 25
puts square_bitwise(0)  # Expected: 0
puts square_bitwise(7)  # Expected: 49
puts square_bitwise(-3) # Expected: 9 (since (-3)*(-3) = 9)

Ruby implementation of squaring using bitwise operations.