머신러닝, AI & 알고리즘 HOT순차 프로그램에 대한 간단한 알고리즘과 재귀 알고리즘의 속도 테스트 - by 아크마

작성자 : 김대영(아크마)

작성일 : 2005년 11월

언어 :  어셈블리

설명 : 이 프로그램은  UCLA 대학에서 어셈블리 강의에 최종 테스트로 나와있는 퀴즈에 대한 프로그램입니다.

아직 그 홈피가 남아 있는지 모르겠지만 원하시는분은 검색해서 문제등을 찾아 보세요..

워낙 바쁘던 시기에 만든거라 정말 두서없이 X판으로 만들어졌습니다. (죄송합니다, 메뉴얼은 더  X판입니다.)

레포트등에 이용하시려면 꼬옥 참고만 하세요^^;

첨부파일에는 전체 소스와 어셈 라이브러리가 포함되어 있습니다..

 

(정말 개념없이 만들었으니 이해해주세요)

 

프로그램의 목적 : 

사용자로부터 생성할 랜덤값의 개수(N) 와 Seed값을 입력받아  N개의 랜덤한 숫자를 생성한 후에 Array 배열에 값을 저장한다. Array에서 구간별로 더한 값이 최대가 되는 값과 그에 대한 구간을 찾는다. 최대값과 구간을 구하는데 에는 두가지 알고리즘을 적용하는데 하나는 Simple이고 다른 하나는 Recursive이다. 랜던값의 개수N이 10이하이면 최대구간과 최대값을   출력하고 11이상이면 각 알고리즘을 수행한 후에 걸린 시간을 화면에 출력한다.

 

 

; MP3
; 김대영
; 2005년 11월

; This program compares the running times of the a simple algorithm and
; a recursive algorithm for the MAXimum Subsequence Sum Problem.

BITS    16

;====== SECTION 1: Define constants =======================================

CR      EQU     0Dh             ; Carriage return
LF      EQU     0Ah             ; Line feed
BS      EQU     08h             ; Backspace
SPACE   EQU     20h             ; Space
StrLen  EQU     60              ; MAXimum length of input string,
                                ; including '$'
MAXN    EQU     30000 
MAXVal  EQU     1000            ; MAXimum value to generate                    

; You may define additional constants here
 
       
;====== SECTION 2: Declare external procedures ============================
GLOBAL DoFew, Timing, Elapsed, Simple, Recursive, FixedEndSum, printList
GLOBAL GetStr, printIdxSum, GetRand
GLOBAL  N, Rnum, Array, Secs, Huns
GLOBAL  String, InvMsg
EXTERN  ascbin, binasc, kbdin, dspout, dspmsg, dosxit
;====== SECTION 3: Define stack segment ===================================

SEGMENT stkseg STACK                    ; *** STACK SEGMENT ***
        RESB      512*8
stacktop:
        RESB    0                       ; NASM bug workaround

;====== SECTION 4: Define code segment ====================================

SEGMENT code                            ; *** CODE SEGMENT ***

;====== SECTION 5: Declare variables for main procedure ===================

N       DW      1                       ; Number of words to handle
Rnum    DW      1                       ; Random number
Array   RESW    MAXN
Secs    RESB    1                       ; Initial time (seconds)
Huns    RESB    1                       ; Initial time (hundredths)

NMsg    DB      CR,LF,LF,'Number of words to handle: ','$'
SMsg    DB      CR,LF,'Random seed: ','$'
InvMsg  DB      CR,LF,'Invalid input','$'
String  RESB    StrLen                  ; Input string from user

; You may declare additional variables here
numRep DB CR,LF,'Number of repetitions: ','$'
repPos DB CR,LF,'Number of repetitions must be positive','$'
elapsedSimple   DB CR,LF,'Elapsed time for simple algorithm:      ','$'
elapsedRecursive DB CR,LF,'Elapsed time for recursive algorithm:   ','$'
idxSumSimple   DB 'With simple algorithm, indices and sum are   ','$'
idxSumRecursive  DB 'With recursive algorithm, indices and sum are','$'
secStr DB ' seconds','$'
invmsg  DB      CR,LF,'Invalid input','$'
crlfmsg DB   CR,LF, '$'

ci DB 0
outStr RESB 7
max   DW 1
reps DW 0
i DW 0
j DW 0
m DW 0
center DW 0
left DW 0
right DW 0
leftSum DW 0
rightSum DW 0
leftR DW 0
leftS DW 0
rightR DW 0
rightS DW 0
k DW 0
w DW 0
z DW 0

;====== SECTION 6: Program initialization =================================

..start:
        MOV     AX, CS                  ; Initialize Data Segment register
        MOV     DS, AX 
        MOV     AX, stkseg              ; Initialize Stack Segment register
        MOV     SS, AX
        MOV     SP, stacktop            ; Initialize Stack Pointer register

;====== SECTION 7: Main procedure =========================================

main:
.LoopN:
        MOV     DX, NMsg                ; Get number of words n
        CALL    dspmsg
        MOV     BX, String
        CALL    GetStr
        CALL    ascbin                  ; Convert to binary
        CMP     DL, 0                   ; Check for conversion error
        JNE     .BadN
        MOV     WORD [N], AX
        CMP     AX, 0                   ; Check in range
        JL      .BadN
        JE      .MP3Exit                ; On zero, exit program
        CMP     AX, MAXN
        JLE     .LoopS
.BadN:
        MOV     DX, InvMsg              ; Print Invalid message  
        CALL    dspmsg
        JMP     .LoopN

.LoopS:       
        MOV     DX, SMsg                ; Get random seed
        CALL    dspmsg 
        MOV     BX, String
        CALL    GetStr
        CALL    ascbin                  ; Convert to binary
        CMP     DL, 0                   ; Check for conversion error
        JE      .Continue
        MOV     DX, InvMsg              ; Print Invalid message
        CALL    dspmsg
        JMP     .LoopS       

.Continue:
        MOV     WORD [Rnum], AX         ; Initialize Rnum with seed
        CMP     WORD [N], 10            ; If n > 10 then
        JBE     .UpTo10
        CALL    Timing                  ;   CALL Timing
        JMP     .LoopN
.UpTo10:
        CALL    DoFew                   ;   else CALL DoFew
        JMP     .LoopN
       
.MP3Exit:
        CALL dosxit
       
;====== SECTION 8: Your subroutines =======================================
DoFew:
     ;CALL    libDoFew
     ;RET
 
    CALL GetRand
    
      CALL printList
     
      MOV DX, crlfmsg
   CALL dspmsg
  
   CALL Simple
   
   MOV DX, idxSumSimple
   CALL dspmsg
   CALL printIdxSum
  

   
   MOV SI, 0  ; p = 0
   MOV DI, WORD[N] ; v = n
   SUB DI, 1    ; v = n -1
   CALL Recursive
   
   MOV DX, idxSumRecursive
   CALL dspmsg
   
  
   CALL printIdxSum

      RET      

Timing:
       ; CALL    libTiming
      ; RET
     
  PUSHA
  .getReps:
  ; printf("Number of Repetitions? ");
   MOV DX, numRep
   CALL dspmsg
  ; GetStr(BX);
   MOV BX, String
   CALL GetStr
  ; ascbin(BX);
   MOV BX, String
   CALL ascbin 
  
  ; if(AX > 0)
  ; {
   CMP DL, 0
   JNZ .bogus
   CMP AX, 0
   JG .startTiming
  .bogus:
   MOV DX, repPos
   CALL dspmsg
   JMP .getReps
 
  .startTiming:

  MOV WORD [reps], AX
  
  MOV DX, elapsedSimple
  CALL dspmsg
  
  MOV AH, 2Ch ; Get current time: (CH) = hrs, (CL) = mins,
  INT 21h   ;   (DH) = secs, (DL) = hundredths of secs
  MOV [Secs], DH
  MOV [Huns], DL
  
  CALL GetRand
  MOV CX, WORD [reps]
  .repSimple:
  
   CALL Simple
  LOOP .repSimple
  

  CALL Elapsed
  
  MOV DX, elapsedRecursive
  CALL dspmsg
  
  MOV AH, 2Ch ; Get current time: (CH) = hrs, (CL) = mins,
  INT 21h   ;   (DH) = secs, (DL) = hundredths of secs
  MOV [Secs], DH
  MOV [Huns], DL
  
  
  MOV CX, WORD [reps]
  .repRecursive:
   
   MOV SI, 0  ; p = 0
   MOV DI, WORD[N] ; v = n
   SUB DI, 1    ; v = n -1
   CALL Recursive
    
  LOOP .repRecursive
  
  CALL Elapsed
  
  
  POPA
  RET
      

Elapsed:
        ;CALL    libElapsed
        ;RET
 MOV AH, 2Ch ; Get current time: (CH) = hrs, (CL) = mins
  INT 21h     ;   (DH) = secs, (DL) = hundredths of secs
 
  SUB DH, byte[Secs]
  SUB DL, byte[Huns]

  CMP DL, 0   
  JGE .noChangeHun ; 0보다 같거나크면
  
  ;0보다 작으면 100을 더해주고 초에서 1초빼준다
  DEC DH
  ADD DL, 100
   
  .noChangeHun
    CMP DH, 0   
    JGE .noChangeSec ; 0보다 같거나 크면
   
    ;0보다 작으면 60초를 더한다. 컴퓨터가 충분히 빠르므로 1분이상 걸리지 않는 가정하에 분에서는 안빼준다.
    ADD DH, 60
   
  .noChangeSec

  PUSH DX
  
  MOVZX AX, DH
  MOV BX, outStr
  CALL binasc
  
  CMP CL, 1 ; x.yy , 00.00 포맷을 맞추기 위해  초에는 스페이스를, 밀리초에는 0을 입력, CL = Number of nonblank characters generated
  JG  .fixedFormSec  ; 1보다 크다면
  MOV DL, ' '
  CALL dspout
  
  .fixedFormSec
  MOV DX, BX
  CALL dspmsg
  
  MOV DL, '.'
  CALL dspout
  
  POP DX
  
  MOVZX AX, DL
  MOV BX, outStr
  CALL binasc

  CMP CL, 1 ; x.yy , 00.00 포맷을 맞추기 위해  초에는 스페이스를, 밀리초에는 0을 입력, CL = Number of nonblank characters generated
  JG  .fixedFormHun  ; 1보다 크다면
  MOV DL, '0'
  CALL dspout
    
  .fixedFormHun
  MOV DX, BX
  CALL dspmsg
  
  MOV DX, secStr
  CALL dspmsg
 
  MOV DX, crlfmsg
  CALL dspmsg

  RET       

Simple:
    ;CALL    libSimple
        ;RET
  
    PUSH CX
    PUSH DX
    PUSH BX

      MOV SI, 0    ; indices r
    MOV DI, 0    ; indices s
    MOV BX, WORD[Array]  ;m is  Value of maximum subsequence sum
    MOV WORD[m], BX
    
    MOV CX, 0  ; i
    MOV DX, 0  ; j
    
    ; BX를 J로 잡은것은 메모리 어드레스에서 +BX로 사용할수 있기 때문에
    
    .loopSimpleI
  
 
      ; WORD 단위로 증가하고 Array 오프셋 이동
      MOV AX, 2
      MUL CX
      
      MOV BX, Array
      ADD BX, AX

      MOV AX, 0  ; z = 0
      MOV DX, CX   ; j = i  
      .loopSimpleJ
       
        ADD AX, WORD[BX]  ;  z = z + Array[j]
        
        CMP WORD[m], AX   ; IF m < z THEN 
        JGE .noSet
        
        MOV SI, CX      ;r = i          (Replace current candidates for r, s)
               MOV DI, DX           ;s = j
               MOV WORD[m], AX       ;m = z          (m = Array[r] + ... + Array[s])
 
        .noSet
        ADD BX, 2
        INC DX
        CMP DX, WORD[N]  
      JL .loopSimpleJ
      
     INC CX
     CMP CX, WORD[N]
    JL .loopSimpleI
    
    MOV AX, WORD[m];

    POP BX
    POP DX
    POP CX
    RET
       
Recursive:
      ; CALL    libRecursive
      ; RET
      
      CMP SI, DI     
    JLE  .continueRecursive 
    MOV AX, 0
    RET
    
    .continueRecursive 
    ;If p = v, then Recursive exits with (SI)=(DI)=p and (AX) = Array[p].     
    CMP SI, DI
    JNE .nexistRecursive
    
    PUSH SI
    
    MOV AX, 2
    MUL SI
    MOV SI, Array
    ADD SI, AX
    
    MOV AX, WORD[SI]
    POP SI
    RET
     
    .nexistRecursive
   
    PUSH BX
       PUSH CX
      PUSH DX
      PUSH WORD[center]
    PUSH WORD[left]
    PUSH WORD[right]
    PUSH WORD[leftSum]
    PUSH WORD[rightSum]
    PUSH WORD[leftR]
    PUSH WORD[leftS]
    PUSH WORD[rightR]
    PUSH WORD[rightS]
   
      ;
      MOV DX, 0
    MOV AX, SI
    ADD AX, DI
    ADC DX, 0 ; 앞 연산의 캐리와 0을 더함
      MOV CX, 2 
    DIV CX
      
      
      MOV WORD[center], AX ; center
    MOV WORD[left], SI
    MOV WORD[right], DI;
    
    MOV SI, WORD[left]  ; p
    MOV DI, AX      ; t
     
    CALL Recursive
    MOV WORD[leftSum], AX
    MOV WORD[leftR], SI
    MOV WORD[leftS], DI
    
    MOV SI, WORD[center] ; t+1
    ADD SI, 1
    MOV DI, WORD[right]  ; v
    
    CALL Recursive
    MOV WORD[rightSum], AX
    MOV WORD[rightR], SI
    MOV WORD[rightS], DI
 
    ; left
    MOV CX,  WORD[center]
    MOV WORD[BX],  CX   ;  index f of the fixed end , CX is center t
    MOV CX, WORD[left]
    MOV WORD[BX+2], CX  ; index o of other end , left
    MOV WORD[BX+4], -1  ; direction d  is -1 to decrease)

    CALL FixedEndSum
    MOV SI, WORD[BX+6]
    MOV AX, WORD[BX+8]
    
    ; right
    MOV CX,  WORD[center]
    ADD CX, 1
    MOV WORD[BX],  CX   ;  index f of the fixed end , CX is center t
    MOV CX, WORD[right]
    MOV WORD[BX+2], CX  ; index o of other end , left
    MOV WORD[BX+4], 1  ; direction d  is -1 to decrease)
    
    CALL FixedEndSum
    MOV DI, WORD[BX+6]
    ADD AX, WORD[BX+8]
    
    MOV CX, WORD[leftSum]
    MOV DX, WORD[rightSum]
    
    ; find max value and set
    CMP CX, DX
    JG .max1
    
     CMP DX, AX
     JG .max4
     
     MOV AX, AX
     MOV SI, SI
     MOV DI, DI
     JMP .endMax
     
     .max4
     MOV AX, DX
     MOV SI, WORD[rightR]
     MOV DI, WORD[rightS]
     JMP .endMax
    
    .max1
    CMP CX, AX
    JG .max2
     
    MOV AX, AX
    MOV SI, SI
    MOV DI, DI
    JMP .endMax
    
    .max2
    MOV AX, CX
    MOV SI, WORD[leftR]
    MOV DI, WORD[leftS]
    
    
    .endMax
    
    POP WORD[rightS]
    POP WORD[rightR]
    POP WORD[leftS]
    POP WORD[leftR]
    POP WORD[rightSum]
    POP WORD[leftSum]
      POP WORD[right]
    POP WORD[left]
    POP WORD[center]
      POP DX
      POP CX
      POP BX
      RET  
      
FixedEndSum:

       PUSH AX
      PUSH CX
      PUSH DX
      PUSH SI
      PUSH DI
      
     
      MOV CX, WORD[BX] ; k
      MOV WORD[k], CX
     
      MOV AX, 2
      MUL CX
      MOV DI, Array
      ADD DI, AX
      
      MOV CX, WORD[DI] ; w
      MOV WORD[w], CX
      
      MOV WORD[z], CX  ; z
      
      MOV CX, WORD[k] ; i
     
       
      .loopFixedEndSum
       CMP CX, WORD[BX+2]
       JE .endFixedEndSum
       
       ADD CX, WORD[BX+4] ; i = i+4
       
       MOV AX, 2
       MUL CX
       MOV DI, Array
       ADD DI, AX
       MOV AX, WORD[DI]
      
       ADD WORD[z], AX  ; z = z + Array[i]
       
       MOV AX, WORD[w]
       CMP WORD[z], AX
        JLE .loopFixedEndSum
        MOV WORD[k], CX
        MOV AX, WORD[z]
        MOV WORD[w], AX
       
       JMP .loopFixedEndSum
     
      .endFixedEndSum
      
      
      MOV AX, WORD[k];
      MOV WORD[BX+6], AX
      
      MOV AX, WORD[w];
      MOV WORD[BX+8], AX
      
      POP DI
      POP SI
      POP DX
      POP CX
      POP AX
       RET 
    
    
    
   
; Subroutine Rand
; Generates random number
;       Inputs  (CX) -- range of random number
;               R -- current stored random number
;       Ouput   (AX) -- random number in range 1 .. (CX)-1
C2053   DW      2053
C13849  DW      13849
C216M1  DW      0FFFFh                  ; 2^16 - 1
RandOut RESW    1

Rand:
         PUSHA
         MOV     AX, WORD [Rnum]            ; Current random number
         MUL     WORD [C2053]
         ADD     AX, WORD [C13849]
         ADC     DX, 0                   ; Propagate carry to DX
         DIV     WORD [C216M1]           ; Remainder is in DX
         MOV     WORD [Rnum], DX            ; New random number
         MOV     AX, DX
         MOV     DX, 0                   ; Prepare for division
         DIV     CX
         MOV     [RandOut], DX           ; In range 0, ..., (CX) - 1
         POPA
         MOV     AX, [RandOut]
         SUB    AX, 1000
         RET

GetRand:
  PUSHA
  
  MOV AX, 2
  MUL WORD [N]
  ADD AX, Array
  SUB AX, 2
  MOV WORD [max], AX
  MOV BX, Array
  
  MOV CX, 2001
  .loopGetRand
  
  CALL Rand
  
  MOV WORD[BX], AX
  ADD BX, 2
  CMP BX, WORD[max]
  JLE .loopGetRand
  
  POPA
  RET
  

       
;GetRan 함수로 생성된 값들을 출력  
printList:

   RET
   PUSHA
   MOV AX, 2
   MUL WORD [N]
   ADD AX, Array
   SUB AX, 2
   MOV WORD [max], AX
   MOV BX, Array
   
   MOV BYTE[ci], 48 ; 0 ascii 48
   
   .loopPrintList
   CMP BX, WORD [max]
   JA .endPrintList
   
   MOV AX, WORD [BX]
   PUSH BX
   
   MOV DX, WORD[ci]
   CALL dspout
   
   MOV BX, outStr
   CALL binasc
   MOV DX, outStr
   CALL dspmsg
   MOV DX, crlfmsg
   CALL dspmsg
   INC BYTE[ci]
   POP BX
   ADD BX, 2
   
   CMP BX, WORD [max]
   JLE .loopPrintList
  
  .endPrintList
   POPA
   RET

 

; 사용자로부터 키 입력을 받는다.
GetStr:
  
  PUSHA
  
  
  MOV AX,0
  MOV CX, BX;  //첫번째 위치값을 저장함
  
  .beginGetStr 
  CALL  kbdin   ; Wait for a key to be pressed
  CMP   AL, 13   ; if key is return
  JE   .endGetStr
  
  CMP   AL, 8   ; if key is bakspace
  JNE  .noBackspace
  
  CMP  CX, BX ; 백스페이스로 지울때 처음 위치까지만 지우도록
  JE  .beginGetStr
  
  DEC  BX  ; 백스페이스 누르면 입력스트링의 가르키는 오프셋을 감소
  
  MOV  DX, 8 
  CALL  dspout
  
  MOV  DX, ''
  CALL  dspout
  
  MOV  DX, 8 
  CALL  dspout
  
  JMP  .beginGetStr
  
  .noBackspace 
  MOV  BYTE[BX], AL  ; patter[i] = AL
  
  MOV  DX, AX
  CALL  dspout
  INC  BX
  JMP .beginGetStr
  
  .endGetStr 
  MOV byte[BX], '$'
  
  MOV DX, crlfmsg
  CALL dspmsg
  
  POPA
  RET
  
  
printIdxSum:

 PUSHA
 
  PUSH AX
  
  MOV AX, SI
  MOV BX, outStr
  CALL binasc
  MOV DX, outStr
  CALL dspmsg
 
  MOV AX, DI
  MOV BX, outStr
  CALL binasc
  MOV DX, outStr
  CALL dspmsg  
  
  POP AX
  MOV BX, outStr
  CALL binasc
  MOV DX, outStr
  CALL dspmsg 
   
  MOV DX, crlfmsg
  CALL dspmsg
   
 POPA

 RET