#keywords sum,100,add,loop,5050,optimize,합,구간합,정수합,어셈블리,C
#title 1부터 100까지의 합(또는 특정구간)을 구하기 위한 최적화
[wiki:Home 대문] / [wiki:CategoryProgramming 프로그래밍] / [wiki:Sum1to100 1부터 100까지의 합(또는 특정구간)을 구하기 위한 최적화]
----
== [wiki:Sum1to100 1부터 100까지의 합(또는 특정구간)을 구하기 위한 최적화] ==
 * 작성자
  조재혁([mailto:minzkn@minzkn.com])

 * 고친과정
  2007년 5월 5일 : 처음씀

[[TableOfContents]]
=== 개요 ===
 1부터 100까지의 합을 구하기 위한 C 언어 및 어셈블리 구현 예제 입니다.[[br]]
 여기서는 2가지를 선보입니다.[[br]]
 한가지는 그냥 상식선에서 1부터 차례차례 더하는 것이고[[br]]
 또 다른 한가지는 수열을 정리해서 반복문을 제거한 방법을 구현한 것입니다.
=== 순차적으로 합을 구하는 방법 (최적화 없는 단순 논리 구현) ===
 * 어셈블리 예제 (MASM16 소스)
 {{{#!enscript asm
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 언어 예제
 {{{#!enscript 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 예제
 {{{#!enscript 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))
}}}
=== 수열정리를 이용한 방법 ===
 일단 누적합의 경우는 루프가 많다는 점이 가장 최적화 해야 할 부분이라고 생각했습니다. 그래서 먼저 수열을 정리하면서 풀어해쳤더니 복잡한 중간과정은 생략하고[[br]]
 항상 y = (end + start) * ((end - start + 1) / 2) 이라는 공식이 먼저 산출되었습니다.[[br]]
 하지만 이것은 실수계산인 경우이겠죠. 

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

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

 이제 코드로 만들어 내면 되는데 다음과 같이 우선 C로 해봤습니다.
 {{{#!enscript 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;
}}}
 잘됩니다. 드디어 루프없이 특정범위의 합을 계산할수 있는것이 가능하다는 증명이 되었습니다. ㅎㅎㅎ

 이제 아래처럼 어셈블리로 코딩하였습니다. 역시 빠릅니다. 루프는 이제 누적합에서 사용하지 않아도 된다는 결론입니다.
 {{{#!enscript asm
.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 언어로 정리 
 {{{#!enscript 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 으로 정리
 {{{#!enscript 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))
}}}