중국인의 나머지 정리(Chinese Remainder Theorem, CRT) 계산 방법

Chinese Remainder Theorem (중국인의 나머지 정리)를 이용하여
x ≡ 1 ( mod 5 ) { x를 5로 나눈 나머지는 1 }
x ≡ 2 ( mod 6 ) { x를 6로 나눈 나머지는 2 }
x ≡ 3 ( mod 7 ) { x를 7로 나눈 나머지는 3 }
의 해를 구하는 과정.

• step 0: 주어진 mod 값 5, 6, 7 을 나란히 적는다.
• step 1: 주어진 나머지 값 1, 2, 3 을 나란히 적는다.
• step 2: 5와 각 mod에 대한 5의 잉여역원을 나머지의 앞,뒤로 곱해준다.(mod 가 5인 열 제외)
• step 3: 6과 각 mod에 대한 6의 잉여역원을 나머지의 앞,뒤로 곱해준다.(mod 가 6인 열 제외)
• step 4: 7과 각 mod에 대한 7의 잉여역원을 나머지의 앞,뒤로 곱해준다.(mod 가 7인 열 제외)
• (=>각 mod 에 대해 나머지 값을 유지하면서 다른 mod 에 대한 나머지는 0이 되도록 만드는 과정이다.)
• step 4-a: 현재 단계에서 각각의 곱을 계산하여 더해도 답을 구할 수 있다.
• step 5-a: 계산을 간단히 하기 위해 두개의 곱을 각 mod 에 대한 나머지값만 구한다.
• step 5-b: 위 과정을 반복하되, 각 mod 의 곱에 대해서는 나머지를 구하지 않고 유지한다.
• step 5-c: 각각의 곱을 계산하면 step 4-a 보다 작은 숫자가 나와 계산이 더 간단하다.
• (=>5-b에서 나머지를 구할 때 음수값을 잘 이용하면 숫자가 더 작아진다. ex) mod 7에서 6*5*5 -> 6*5*-2)
  

다른 예 step 5 의 과정을 통해 계산이 더 간단해졌다.
mod 11에서 11*7*4 를 11*7*-1로 계산하면 숫자가 더 작아진다.

[VB6] Excel의 NUMBERSTRING 함수 처럼 숫자를 한글로

'양의 정수형 식을 입력받아 한글로 변환하는 함수.
'Excel의 NUMBERSTRING 함수의 기능. 소숫점 이하는 무시.
'작성자: youtoometoo.blogspot.com
'
'vNum : 문자를 포함한 올바른 양의 정수형 숫자 형식
'sDelimiter : 만단위로 구분할 경우 구분자. 띄어쓰기 필요할 경우 사용 위해.
'blIsNormal : 수사앞의 "일"을 처리하는 방식.
' False - 기본값. 금전 거래시 사용하는 일천일백일십일 형식.(cf.위변조 방지위해 띄어쓰기도 안한다.)
' True - 실행활에서 주로 사용하는 천백십일 형식.
'에러 발생시 길이가 0인 문자열("") 반환.
Private Function Num2Han(vNum As Variant, Optional sDelimiter As String, Optional blIsNormal As Boolean) As String
Dim sDigit$(), sPlaceLo$(), sPlaceHi$()
Dim sNum As String, sPart As String
Dim lDigit As Long, i As Long

On Error GoTo Error_Handle

'일단 숫자형으로 변환해서 처리하는 방식. 후에 문자열만 처리할 경우는 숫자값만 추출해서 sNum에 저장한다.
sNum = CStr(Int(CDec(vNum)))

If sNum = "0" Then Num2Han = "영": Exit Function

sDigit = Split(",일,이,삼,사,오,육,칠,팔,구", ",")
sPlaceLo = Split(",십,백,천", ",")
sPlaceHi = Split(",만,억,조,경,해,자,양", ",") 'Decimal 형식 최대 자리수는 "양"까지.

'큰 수 이름 출처 : 네이버 캐스트 수학 산책. 글 허민 / 광운대학교 수학과 교수
'http://navercast.naver.com/contents.nhn?rid=22&contents_id=164
'일- 십- 백- 천- 만- 억- 조- 경- 해- 자- 양- 구- 간- 정- 재- 극-항하사- 아승기- 나유타- 불가사의- 무량수

For i = Len(sNum) - 1& To 0& Step -1&
lDigit = CLng(Mid$(sNum, Len(sNum) - i, 1&))

If lDigit Then
'일반 표기면 십,백,천 앞의 "일"은 미표시하도록 0으로 바꾼다. 10000은 예외로 "일만"표시.
If blIsNormal Then If lDigit = 1& Then If (i And &H3&) Then lDigit = 0&

'숫자 와 "",십,백,천 표시. 순환하는 특성 이용
sPart = sPart & (sDigit(lDigit) & sPlaceLo(i And &H3&))
End If


'4자리씩 끊어서 0000이 아닐 경우 만(萬) 단위로 수사(數詞)를 붙인다.
If ((i And &H3&) = 0&) Then
If LenB(sPart) Then
sPart = sPart & sPlaceHi(i \ 4&) & sDelimiter
Num2Han = Num2Han & sPart
sPart = vbNullString
End If
End If

Next i

'문자열 마지막의 구분자 제거
Num2Han = Left$(Num2Han, Len(Num2Han) - Len(sDelimiter))
Exit Function

Error_Handle:
Num2Han = ""
Debug.Print "Num2Han Error : 입력값 " & vNum & " (" & Err.Number & " - " & Err.Description & ")"
End Function


'테스트 : Text Box, Command Button
Private Sub Command1_Click()
Dim sNumber As String, cNum As Currency, sDm As String
Static blNormal As Boolean

sDm = " "
blNormal = Not blNormal
Text1 = ""


'문자형 테스트
sNumber = "+79,228,162,514,264,337,593,543,950,335" 'Decimal 형식 최대 수
Text1 = Text1 & sNumber & vbNewLine & Num2Han(sNumber, sDm, blNormal) & vbNewLine

sNumber = "+00000000000000000345,000,000,111,111,685"
Text1 = Text1 & sNumber & vbNewLine & Num2Han(sNumber, sDm, blNormal) & vbNewLine

sNumber = 1.21100000011111E+20 ' = 121100000011111000000
Text1 = Text1 & sNumber & vbNewLine & Num2Han(sNumber, sDm, blNormal) & vbNewLine

sNumber = "&h7fffffff"
Text1 = Text1 & sNumber & vbNewLine & Num2Han(sNumber, sDm, blNormal) & vbNewLine


'숫자형 테스트
cNum = Date
Text1 = Text1 & cNum & vbNewLine & Num2Han(cNum, sDm, blNormal) & vbNewLine

cNum = 10000
Text1 = Text1 & cNum & vbNewLine & Num2Han(cNum, sDm, blNormal) & vbNewLine

cNum = 232000000013#
Text1 = Text1 & cNum & vbNewLine & Num2Han(cNum, sDm, blNormal) & vbNewLine

cNum = 0.903
Text1 = Text1 & cNum & vbNewLine & Num2Han(cNum, sDm, blNormal) & vbNewLine

End Sub