1부터 100까지의 합(또는 특정구간)을 구하기 위한 최적화

대문 / 프로그래밍 / 1부터 100까지의 합(또는 특정구간)을 구하기 위한 최적화

1부터 100까지의 합(또는 특정구간)을 구하기 위한 최적화

작성자
조재혁(minzkn@minzkn.com)
고친과정
2007년 5월 5일 : 처음씀

1. 1부터 100까지의 합(또는 특정구간)을 구하기 위한 최적화

1.1. 개요
1.2. 순차적으로 합을 구하는 방법 (최적화 없는 단순 논리 구현)
1.3. 수열정리를 이용한 방법

1.1. 개요

1부터 100까지의 합을 구하기 위한 C 언어 및 어셈블리 구현 예제 입니다.
여기서는 2가지를 선보입니다.
한가지는 그냥 상식선에서 1부터 차례차례 더하는 것이고
또 다른 한가지는 수열을 정리해서 반복문을 제거한 방법을 구현한 것입니다.

1.2. 순차적으로 합을 구하는 방법 (최적화 없는 단순 논리 구현)

어셈블리 예제 (MASM16 소스)

DEF_STACKSIZE = 1024

           ASSUME CS:CODE_SUM, DS:NOTHING, ES:NOTHING, SS:NOTHING
CODE_SUM   SEGMENT PARA PUBLIC USE16 'CODE'
           ORG 100H
L_START:
           ; Setup stack
           CLI
           MOV AX, CS
           MOV SS, AX
           MOV SP, OFFSET L_STACK_ENTRY
           STI

           XOR AX, AX
           XOR BX, BX
L_SUM_LOOP:
           INC BX
           ADD AX, BX
           CMP BX, 100
           JNE L_SUM_LOOP

           MOV BX, 10
           XOR CX, CX
L_PRINT_DIGIT_0:
           XOR DX, DX
           DIV BX
           ADD DX, '0'
           PUSH DX
           INC CX
           OR AX, AX
           JNZ L_PRINT_DIGIT_0
L_PRINT_DIGIT_1:
           POP DX
           MOV AH, 02H
           INT 21H
           LOOP L_PRINT_DIGIT_1

           MOV AX, 04C00H
           INT 21H


           DB DEF_STACKSIZE DUP (?)
L_STACK_ENTRY:
CODE_SUM   ENDS

           END L_START

# End of source

C 언어 예제

#include <stdio.h>
int main(void)
{
        unsigned long start = 1ul, end = 100ul, sum = 0ul, count;
        for(count = start;count <= end;count++) { sum += count; }
        (void)printf("sum(%lu ~ %lu) is %lu\n", start, end, sum);
}

python 예제

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

if __name__ == u"__main__":
    start = 1
    end = 100
    sum = 0
    for count in range(start,end + 1):
        sum += count
    print("sum(%u ~ %u) is %u\n"%(start, end, sum))

1.3. 수열정리를 이용한 방법

일단 누적합의 경우는 루프가 많다는 점이 가장 최적화 해야 할 부분이라고 생각했습니다. 그래서 먼저 수열을 정리하면서 풀어해쳤더니 복잡한 중간과정은 생략하고
항상 y = (end + start) * ((end - start + 1) / 2) 이라는 공식이 먼저 산출되었습니다.
하지만 이것은 실수계산인 경우이겠죠.

우리의 컴퓨터는 야속하게도 정수계산을 더욱 좋아하기 때문에 이를 정수계산만으로 해결하는 방법을 위해 다시 계산 공식을 수정해야 합니다.
그래서 한번 얼핏 상상해봤습니다. 그랬더니 start 부터 end 까지의 숫자갯수가 짝수인 경우는 그냥 위의 공식이 그대로 될법 했습니다.
하지만 홀수는 0.5씩 값이 정수계산시에 loss 납니다.
결국 어째저째 하여 정수계산시 발생하는 loss 는 start + ((end - start + 1) / 2) 라는 결론이 났습니다.

일단 공식을 좀더 정리해볼수 있을법 하지만 일단 이 이상은 머리아파서 그만 정리하겠습니다.

이제 코드로 만들어 내면 되는데 다음과 같이 우선 C로 해봤습니다.

int s_result, s_quota, s_range;

s_range = s_end - s_start + 1;
s_quota = s_range >> 1;
s_result = (s_end + s_start) * s_quota;
if(s_range & 1)s_result += s_quota + s_start;

잘됩니다. 드디어 루프없이 특정범위의 합을 계산할수 있는것이 가능하다는 증명이 되었습니다. ㅎㅎㅎ

이제 아래처럼 어셈블리로 코딩하였습니다. 역시 빠릅니다. 루프는 이제 누적합에서 사용하지 않아도 된다는 결론입니다.

.MODEL SMALL
.RADIX 0AH

; 테스트는 여러가지로 아래의 값을 변경하면서 해보세요.
DEF_BEGIN_VALUE = 1                 ; 시작값
DEF_END_VALUE   = 100               ; 끝값

        ASSUME CS:SEG_CODE,DS:SEG_CODE,ES:NOTHING,SS:SEG_STACK
SEG_CODE SEGMENT PARA PUBLIC USE16 'CLASS_CODE'
L_ENTRY:
        CLI
        MOV AX, SEG_STACK
        MOV SS, AX
        MOV SP, OFFSET SEG_STACK:L_STACK_EOP
        STI
        MOV AX, SEG_CODE
        MOV DS, AX
        MOV ES, AX

        ; "DEF_BEGIN_VALUE"부터 "DEF_END_VALUE"까지 더하는 테스트
        XOR CX, CX
        MOV AX, DEF_END_VALUE
        MOV BX, DEF_BEGIN_VALUE
        ADD BX, AX
        SUB AX, DEF_BEGIN_VALUE
        INC AX
        SHR AX, 1
        JNC L_EVEN ; 짝수일때 L_EVEN으로 분기
        ADD CX, AX
        ADD CX, DEF_BEGIN_VALUE
L_EVEN:
        MUL BX
        ADD AX, CX
L_END_TEST:

        ; 결과값 AX의 확인을 위해 화면에 출력
        MOV BX, 10
        XOR CX, CX
L_PRINT_0:
        XOR DX, DX
        DIV BX
        ADD DX, '0'
        PUSH DX
        INC CX
        OR AX, AX
        JNZ L_PRINT_0
L_PRINT_1:
        POP DX
        MOV AH, 02H
        INT 21H
        LOOP L_PRINT_1

        ; 프로그램 종료
        MOV AX, 4C00H
        INT 21H
        JMP $
SEG_CODE ENDS

        ASSUME CS:SEG_CODE,DS:SEG_CODE,ES:NOTHING,SS:SEG_STACK
SEG_STACK SEGMENT PARA STACK USE16 'CLASS_STACK'
        DB 1024 DUP (?) ; 스택 공간 확보
        L_STACK_EOP:
SEG_STACK ENDS
        END L_ENTRY ; 시작점

; End of source

C 언어로 정리

#include <stdio.h>

int mysum(int s_start, int s_end)
{
    int s_result, s_quota, s_range;

    s_range = s_end - s_start + 1;
    s_quota = s_range >> 1;
    s_result = (s_end + s_start) * s_quota;
    if(s_range & 1)s_result += s_quota + s_start;

    return(s_result);
}

int main(void)
{
    (void)fprintf(stdout, "1 부터 1000 까지 합 구하기 : %d\n", mysum(1, 1000));

    return(0);
}

python 으로 정리

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

if __name__ == u"__main__":
    start = 1
    end = 100
    irange = end - start + 1
    quota = irange >> 1
    isum = (end + start) * quota
    if irange & 1: isum += quota + start
    print("sum(%u ~ %u) is %u\n"%(start, end, isum))