일반 더하기 곱셈 vs 고대 이집트 곱셈법

곱셈을 덧셈으로

만약 곱셈을 할 줄 모르는 상태에서 a * 8을 구해야 한다고 해보자.

곱셈을 모르기 때문에 a + a + a + a + a + a + a + a 이렇게 계산하면 원하는 결과를 얻을 수 있다.

다만 이렇게 하면 덧셈을 7번이나 해야 한다.

 

그런데, a + a를 일단 계산하면 2a를 알 수 있으므로

결국 2a + 2a + 2a + 2a를 계산하면 된다.

 

이를 확장해 보면

8a = a + a + a + a + a + a + a + a

     = 2a + 2a + 2a + 2a

     = 4a + 4a

     = 8a

 

이 방법을 8a를 계산하면 다음과 같이 3회의 덧셈으로 계산이 끝난다.

 

a + a

2a + 2a

4a + 4a

 

곱하는 수 8이 2의 거듭제곱의 형태이므로 2³ = log₂8 = 3회의 덧셈으로 끝난 것이다.

 

로그(log)란 무엇인가?

이진법으로 생각하면

이 계산은 이진법으로 따지면 간단한 비트 쉬프트이다.

2를 곱하는 것은 오른쪽에 0을 하나 추가하는 것으로 간단하게 계산할 수 있다.

static void Main(string[] args)
{
    var a = 13;

    Console.WriteLine($" a = {a:b}");
    Console.WriteLine($"2a = {a * 2:b}");
    Console.WriteLine($"4a = {a * 4:b}");
    Console.WriteLine($"8a = {a * 8:b}");
    Console.WriteLine($"{a * 8:b} == {a * 8}");
}

 

 

홀짝을 구분해서 계산하기

모든 자연수는 홀수 또는 짝수이기 때문에 다음과 같이 표현할 수 있다.

 

그러므로 a * b를 계산할 때 다음의 방법을 따르면 된다.

• a가 1 이면 답은 b이다.
• a가 홀수이면 결과에 b를 한 번 더한다.
• a를 반으로 나누고(내림), b를 2배 한 다음, 새로운 a와 새로운 b의 곱을 결과에 더한다.
  • a는 반으로 줄어서 언젠가 1이 될 것이다.

 

이제 이 규칙을 통해서 함수를 작성해 보자.

 

매번 재귀 호출 때마다 값이 절반으로 줄어들기 때문에 총 log n번만큼 호출하게 된다. 그리고 result + a에 해당하는 덧셈도 가끔 계산해야 한다. 따라서 총 덧셈 횟수는 다음과 같은 식으로 구할 수 있다. 

 

#+(n) = [log n] + (v(n) - 1)

 

여기에서 v(n)은 n을 이진법으로 썼을 때 1의 개수를 뜻한다.

 

#+(15) = 3 + (4 - 1) = 6

 

O(n)의 복잡도를 가진 알고리즘을 O(log n)의 복잡도를 가진 알고리즘으로 고친 셈이다.

 

홀짝 구분과 반으로 나누기

C# 비트 연산자를 이용한 홀수짝수 판별, 절반으로 나누기 함수 구현

 

일반 더하기로 곱셈법 vs 고대 이집트 곱셈법

using System;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        var num1 = Int32.Parse(input[0]);
        var num2 = Int32.Parse(input[1]);

        var watch = new Stopwatch();
        watch.Start();

        Console.WriteLine(Multipy(num1, num2));

        watch.Stop();
        Console.WriteLine($"단순 더해서 곱하기 : 실행시간 {watch.ElapsedMilliseconds} 밀리초");

        var watch2 = new Stopwatch();
        watch2.Start();

        Console.WriteLine(EgyptionMultipy(num1, num2));

        watch2.Stop();
        Console.WriteLine($"이집트 곱하기 : 실행시간 {watch2.ElapsedMilliseconds} 밀리초");
    }

    static int Multipy(int a, int b)
    {
        var temp = Enumerable.Repeat(a, b).ToArray();
        return temp.Aggregate((x, y) => x + y);
    }

    static bool IsOdd(int n)
    {
        return (n & 1) == 1;
    }

    static int Half(int n)
    {
        return n >> 1;
    }

    static int EgyptionMultipy(int a, int b)
    {
        if (a == 1)
        {
            return b;
        }

        if (IsOdd(a))
        {
            return b + EgyptionMultipy(Half(a), b + b);
        }

        return EgyptionMultipy(Half(a), b + b);
    }
}

 

알고리즘 개선 곱셈 누적 함수

이제 그냥 곱하기만 하는 게 아니고 곱한 값을 더하는 곱셈 누적(multipy-accumulate) 연산을 할 것이다. 이 원칙은 프로그래밍뿐 아니라 하드웨어 설계나 수학에도 적용되곤 하는데 특정 결과만 보이는 것보다 일반적인 결과를 통째로 증명하는 게 더 쉬운 경우에 적용할 수 있다.

 

곱셉 누적 함수는 다음과 같이 구현할 수 있다.

int mult_acc0(int r, int n, int a)
{
    if (n == 1) return r + a;
    if (odd(n))
    {
        return mult_acc0(r + a, half(n), a + a);
    }
    else
    {
        return mult_acc0(r, half(n), a + a);
    }
}

 

이 함수에서는 r + na = r0 + n0a0라는 불변식을 따른다.(r0, n0, a0는 각각 r, n, a의 초깃값).

 

재귀 호출을 더 단순화시킬 수도 있다. 함수 안에 있는 두 재귀 호출은 첫째 인자만 빼면 똑같다. 짝수와 홀수 각각의 경우에 대해 재귀 호출을 하는 대신 다음과 같이 재귀 호출을 하기 전에 r을 바꿀 수도 있다.

 

int mult_acc1(int r, int n, int a)
{
    if (n == 1) return r + a;
    if (odd(n)) r = r + a;
    
    return mult_acc1(r, half(n), a + a);
}

 

이제 이 함수는 꼬리 재귀 호출(tail-recursive) 함수, 즉 마지막 리턴 단계에서만 재귀 호출을 하는 함수가 되었다.

이 곱셈을 곰곰이 생각해 보면 다음과 같은 사실을 알 수 있다.

 

• n이 1인 경우는 거의 없다.
• n이 짝수라면 n이 1인지 확인할 필요도 없다.

따라서 홀수 여부를 먼저 확인하는 것만으로도 n을 1과 비교하는 횟수를 절반으로 줄일 수 있다.

int mult_acc2(int r, int n, int a)
{
    if (odd(n)) 
    {
        r = r + a;
        if (n == 1) return r;
    } 
    
    return mult_acc2(r, half(n), a + a);
}

 

이 정도만 해도 꽤 괜찮아 보인다. 하지만 재귀 호출을 완전히 없애서 함수 호출에 따르는 오버헤드를 피해보자.

 

모든 형식 매개변수를 각각에 상응하는 인자로 사용하는 꼬리 재귀 호출을 순 꼬리 재귀 호출(strictly tail-recursive)이라고 한다.

 

재귀 호출을 하기 전에 변수의 값을 미리 설정해 주면 순 꼬리 재귀 호출로 고칠 수 있다.

 

int mult_acc3(int r, int n, int a)
{
    if (odd(n)) 
    {
        r = r + a;
        if (n == 1) return r;
    }
    
    n = half(n);
    a = a + a;
    
    return mult_acc3(r, n, a);
}

 

이제 꼬리 재귀 호출을 while(true) 구문으로 바꾸기만 하면 손쉽게 반복문 형태로의 프로그램으로 고칠 수 있다.

 

int mult_acc4(int r, int n, int a)
{
    while(true)
    {
        if (odd(n)) 
        {
            r = r + a;
            if (n == 1) return r;
        }
        
        n = half(n);
        a = a + a;
    }
}

 

이렇게 최적화한 곱셈 누적 함수를 이용하여 새 버전의 곱셈 함수를 만들 수 있다. 다음과 같이 보조용으로 만든 곱셈 누적 함수를 호출하면 된다.

 

int multiply2(int n, int a)
{
    if (n == 1) return a;
    return mult_acc4(a, n - 1, a);
}

 

여기에서는 mult_acc4를 처음 호출할 때부터 r 값에 a로, n을 1 줄여서 n - 1로 넘겨줌으로써 계산 횟수를 한 번 더 줄였다.

 

이것도 괜찮긴 하지만, n이 2의 거듭제곱이면 조금 문제가 된다. 처음에 n에서 1을 뺀 상태로 시작하는데 이러면 2진수로 썼을 때 모든 자리 숫자가 1이 되어 이 알고리즘에서는 최악의 경우로 시작하는 셈이다. 이런 문제를 해결하기 위해 n이 짝수이면 n이 홀수가 될 때까지 n을 절반으로 나누고 a를 두 배로 키우는 작업을 추가해 보자.

 

int multiply3(int n, int a)
{
    while(!odd(n))
    {
        a = a + a;
        n = half(n);
    }
    
    return mult_acc4(a, n - 1, a);
}

 

이렇게 고쳐놓고 다시 보면 mult_acc4를 처음 호출할 때는 n이 항상 짝수이므로 n이 홀수인지 확인할 필요도 없음을 알 수 있다. 따라서 아예 mult_acc4를 호출할 때부터 n - 1은 반으로 나누고 a는 두 배로 하여 다음과 같은 식으로 고칠 수 있다.

 

int multiply3(int n, int a)
{
    while(!odd(n))
    {
        a = a + a;
        n = half(n);
    }
    
    if (n == 1) return a;
    
    return mult_acc4(a, half(n - 1), a + a);
}

 

출처

알고리즘 산책 - 예스24

참고 사이트

고대 이집트 곱셈법