컴퓨터에서 곱셈이 나눗셈보다 빠른 이유 (feat. Reciprocal Approximation)

 
 

 

목차

• 정수 및 부동 소수점 곱셈 방법
• 정수 및 부동 소수점 나눗셈 방법
• 나눗셈이 더 느린 이유
• $0.1$과$\frac{1}{10}$은 같지만 다른 이유 (?)
• 코드로 실제 연산 속도 비교
• 요약

 

결론부터 말하면

곱셈(*)과 나눗셈(/)의 연산 속도 차이는 나눗셈이 역수를 근사적으로 계산하는 과정과 하드웨어적인 차이에서 비롯됩니다.
 
곱셈은 덧셈과 비트 시프트를 병렬적으로 수행할 수 있어 하드웨어적으로 병렬 연산이 가능하지만, 나눗셈은 이전 단계의 결과를 확인한 후 다음 연산을 수행(병렬 연산 X)해야 하기 때문에 속도 차이가 발생합니다.
 
이 글에서는 "나눗셈이 역수를 근사적으로 계산하는 과정"에 대해 다룹니다.
현재 아래 내용을 다루고 있지 않습니다. (따로 작성 할 예정)

곱셈 알고리즘: Booth's Algorithm, Wallace Tree Multiplication)
나눗셈 알고리즘: Restoring Division, Non-Restoring Division, SRT Division(Intel이 주로 사용)

---

 
 

곱셈

컴퓨터에서 곱셈은 기본적으로 비트 시프트(Shift)와 덧셈(Addition)으로 변환되어 처리된다.
즉, 비트 이동(Shift)만으로 빠르게 계산할 수 있기 때문에 실행 속도가 빠르다.
예를 들어 $5 \times 3$을 수행한다고 생각해 보자.

정수 곱셈 예시  $5 \times 3$

1. 5를 2진수로 표현하면

5 = 101(2)
3 = 011(2)

 
2.  $5 \times 3$을 곱셈 연산 없이 비트 연산으로 처리

$5 \times 3$ = $5 \times (2^1 + 2^0)$ = (5 << 1) + (5 << 0)

5 << 1 → 101(2) << 1 → 1010(2) = 10(10진수)
5 << 0 → 101(2) << 0 → 101(2) = 5(10진수)
10 + 5 = 15

즉, 비트 이동(Shift) 연산과 덧셈만으로 빠르게 곱셈을 수행할 수 있다.

특히, 곱셈을 최적화하는 알고리즘(Booth's Algorithm, Wallace Tree 등)을 활용하면, 부분 곱(Partial Products) 계산을 병렬적으로 수행하여 속도를 더욱 향상시킬 수 있다.
 

부동소수점 곱셈

부동소수점(float, double) 곱셈도 IEEE 754 표준을 따르며,
지수(Exponent)와 가수(Mantissa)를 비트 연산으로 계산할 수 있기 때문에 빠르다.
연산은 2배 정밀도(double) 부동소수점을 이용한다고 가정하겠다.
 

$5.0 \times 3.0$을 부동소수점 연산으로 이해해 보자

부동소수점은 다음과 같은 형식으로 저장된다.

$(-1)^S \times 1.M \times 2^E$

• S: 부호 비트 (양수면 0, 음수면 1)
• E: 지수 비트 (2의 몇 승인지 나타냄)
• M: 가수 비트 (유효 숫자 부분)

 

(1) 5.0과 3.0을 IEEE 754 부동소수점으로 변환

• $5.0(10) = 1.01 × 2^2$
  S = 0
  E = 1023 + 2 = 1025 (2진수: 10000000001)
  M = 01000000000000000000000
• $3.0(10) = 1.1 × 2^1$
  S = 0
  E = 1023 + 1 = 1024 (2진수: 10000000000)
  M = 10000000000000000000000

   

(2) 부동소수점 곱셈 과정

1. 지수 부분을 더한다
   $E_{result} = E_{5.0} + E_{3.0} - Bias$
   =1025 + 1024 - 1023
   = 1026
2. 가수 부분을 곱한다
   (1.01) × (1.1) = 1.1110
3. 결과 즉, 비트 연산을 통해 곱셈을 매우 빠르게 수행할 수 있다.
   S = 0
   E = 1026
   M = 11100000000000000000000

즉, 비트 연산을 통해 곱셈을 매우 빠르게 수행할 수 있다.
 

---

 

나눗셈

나눗셈(/)은 곱셈처럼 간단한 비트 연산(Shift & Add)으로 계산할 수 없다.
나눗셈은 기본적으로 역수를 구한 후 곱셈으로 변환하는 과정을 포함하며, 이 과정에서 반복적인 근사 연산이 필요하다.
나눗셈이 어떻게 동작하는지 정수 나눗셈, 부동소수점 나눗셈, 역함수 개념과 함께 알아보자.
 

정수 나눗셈

컴퓨터가 정수 나눗셈을 수행할 때 가장 단순한 방법은 뺄셈을 반복해서 수행하는 것이다.
즉, 37 / 5를 계산한다고 하면,

37 - 5 = 32
32 - 5 = 27
27 - 5 = 22
22 - 5 = 17
17 - 5 = 12
12 - 5 = 7
7 - 5 = 2   (더 이상 못 빼면 몫은 7, 나머지는 2)

즉, 5를 몇 번 빼는지(count) 세어서 몫(quotient)을 구하는 방식이다.
이 방식은 O(n)의 시간 복잡도를 가지므로 매우 비효율적이다.
 
 

더 빠른 정수 나눗셈: 비트 연산 활용 (Binary Long Division)

우리는 초등학생 때 나눗셈을 배울 때 아래와 같이, 한 자리씩 나누는 방식을 배운다.

   7
  -----
5 | 37
   - 35   (5 × 7 = 35)
   -----
      2  (나머지)

 
컴퓨터도 정수 나눗셈을 수행할 때 비트 시프트(Shift)와 뺄셈을 조합하여 속도를 높인다.
이를 이진 나눗셈(Binary Long Division)이라고 한다.
이진수 나눗셈도 10진수 나눗셈처럼 왼쪽부터 한 자리씩 내려오면서 계산하는 방식으로, 한 자리씩 확인하면서 나눌 수가 몇 번 들어가는지 확인하는 과정을 진행한다. 직접 진행하면서 이해해 보자.
 
 

예제: $37(10) ÷ 5(10)$ → 100101(2) ÷ 101(2)

1. 왼쪽부터 한 자리씩 내려오면서 나눌 수 있는지를 확인
2. 가능한 경우 뺄셈 수행
3. 결과적으로 나눗셈은 순차적으로 진행되며, 각 단계가 이전 단계의 결과를 기반으로 하기 때문에 병렬화가 어렵습니다.

 

왼쪽에서부터 비트를 하나씩 추가하면서 나눌 수 있는지를 확인한다.
 
Step 1: 100(2)와 비교

• 100은 101보다 작음 → 몫에 0 추가

   0
  -----
101 | 100101

 

Step 2: 1001(2)와 비교

• 1001(2) = 9(10)
• 9 >= 5, 즉 나눌 수 있음
• 뺄셈 수행 (1001 - 101 = 100)
  
• 몫에 1 추가

   01
  -----
101 | 100101
              -  101
              ------
               10001  <-- 뒤에 남은 비트까지 유지해야 함!

 

Step 3: 10001(2)와 비교

• 10001(2) = 17(10)
• 17 >= 5, 즉 나눌 수 있음
• 뺄셈 수행 (10001 - 101 = 1100)
  
• 몫에 1 추가

   011
  -----
101 | 100101
              - 101
              ------
               10001
              -  101
              ------
                1100

 

Step 4: 1100(2)와 비교

• 1100(2) = 12(10)
• 12 >= 5, 즉 나눌 수 있음
• 뺄셈 수행 (1100 - 101 = 0010)
• 몫에 1 추가

   0111
  -----
101 | 100101
              - 101
              ------
               10001
              - 101
              ------
                1100
              - 101
              ------
                0010

 

결과

• 몫: 0111(2) = 7(10)
• 나머지: 0010(2) = 2(10)

---

 

부동소수점 나눗셈은 더 느리다

정수 나눗셈에서 뺄셈을 반복하는 것처럼, 부동소수점 나눗셈(5.0 / 3.0)도 반복적인 연산을 필요로 한다.
컴퓨터는 부동소수점 나눗셈을 단순히 계산하지 않고, 1/3(역수)을 반복적인 계산을 통해 근삿값으로 구한 후, 곱셈을 수행하는 방식을 사용한다.
 

나눗셈이 더 느린 이유

1. 무한소수 문제

• 예: $1 ÷ 3 = 0.3333...$ (무한히 반복)
• 컴퓨터는 이 값을 완벽하게 저장할 수 없고, 근삿값으로 저장해야 함.
• 추가적인 보정 연산이 필요하여 속도가 느려짐.

2. 반복적인 근사 연산 필요

• 뉴턴-랩슨(Newton-Raphson) 방법을 사용하여 역수를 반복적으로 보정해야 함.
• 예:
  • 초기 근삿값: $y_0 = 0.3$
  • $y_1 = y_0 \times (2 - 3 \times y_0) = 0.3 \times 1.1 = 0.33$
  • $y_2 = y_1 \times (2 - 3 \times y_1) = 0.33 \times 1.01 = 0.3333$
• 원하는 정밀도까지 반복 연산 수행.

이처럼 부동소수점 나눗셈은 "근삿값을 구하는 반복 연산"이 포함되어 있어 느리다.
 
뉴턴-랩슨 방법 참고 링크

---

 

컴퓨터에서 0.1과 1/10은 다르다

많은 사람들이 $0.1$과 $\frac{1}{10}$이 같은 값이라고 생각하지만, 컴퓨터의 입장에서 보면 다릅니다.

$0.1$은 이미 고정된 이진수 값

• $0.1(10) = 0.00011001100110011...(2)$ (무한 반복)
• 컴퓨터는 특정한 비트 수까지만 저장하여 근삿값을 사용함.

$\frac{1}{10}$은 나눗셈을 수행해야 하는 값

• $1/10$은 바로 계산할 수 있는 값이 아니며, 반복적인 근사 연산이 필요함.
• 추가적인 연산이 들어가기 때문에 0.1보다 더 느림.

---

코드

곱셈과 나눗셈을 각각 iterations번 하는 코드다. (현재 iterations = 1,000,000,000)

public class MultiplicationVsDivision {
    public static void main(String[] args) {
        final int iterations = 1_000_000_000;

        // 곱셈 연산 시간 측정
        double value = 123.456;
        long startTime = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            value *= 1.0001;  // 곱셈
        }
        long endTime = System.nanoTime();
        System.out.println("Multiplication Time: " + (endTime - startTime) / 1e6 + " ms");

        // 나눗셈 연산 시간 측정
        value = 123.456;
        startTime = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            value /= 1.0001;  // 나눗셈
        }
        endTime = System.nanoTime();
        System.out.println("Division Time: " + (endTime - startTime) / 1e6 + " ms");
    }
}

• 1,000번 연산한 경우

Multiplication Time: 0.00475 ms
          Division Time: 0.005709 ms

 

• 1,000,000번 연산한 경우

Multiplication Time: 1.961125 ms
          Division Time: 3.424333 ms

 

• 1,000,000,000번 연산한 경우

Multiplication Time: 1024.849 ms
          Division Time: 2501.061792 ms

 
1,000번 연산한 경우 약 1.2배 속도차이
1,000,000,000번 연산한 경우 약 2.5배 속도차이
사실을 볼 수 있다.
 
참고: 결과는 SW, HW에 따라 다르다.

---

요약

• 곱셈은 병렬화가 가능해 빠름 (Booth's Algorithm, Wallace Tree 등)
• 나눗셈은 순차적인 연산이 필요하여 느림
• 부동소수점 나눗셈은 무한소수와 반복 연산 문제로 더욱 느림
• $0.1$은 이미 고정된 값이지만, $\frac{1}{10}$은 역수를 구해야 하므로 추가 연산이 필요함
• $x / 10$ 보다 $x * 0.1$ 같은 곱셈연산이 더 빠르다.