전체 : 4,150,784 명
어제 : 0 명
오늘 : 0 명

두 자리 수 이상의 곱셈에 대한 알고리즘

진혼이중주 | 2008.05.16 09:32 | 조회 7276

우리는 이미 초등학교때 곱셈에 대해서 배웠을 것이다.

그럼 다음을 계산 하여 봐라.

45 X 37

거의 100%의 확률로 다음과 같이 계산 할것이다.

45

X 37

--------

315

135

---------

1665

이것으 이미 초등학교때 배우는 곱셈 방식이다.

하지만 이것말고도 곱셈의 방식은 또 있다. 이른바 a la russe알고리즘이다.

일단 두개의 정수를 첫번째 위치 두번째 위치에 써둔다. 그리고 첫번째 위치는 계속 2로 나누고 두번째 위치에 있는 것은 계속 2로 곱한다.

첫번째 위치에 있는 것이 나눗셈할때 1이 남는경우 1은 신경쓰지않고 버린다.(2로 나누기에 나머지는 1과 0만 있을 뿐이다.)

첫번째 위치에 있는 것이 홀수일경우고 2번찌 위치에 있는것을 복사해서 따로 적어둔다. 그리고 첫번째 있는 수가 결국 1이 될때까지 계속 나눗셈을 해간다.

그리고 복사해서 적어둔것을 다 더하면 곰셈이 끝난다.

/2 X2

45 37 37

22 74 .

11 148 148

5 296 296

2 592 .

1 1184 1184

-------------------------------

+ 1665

확실히 초등학교때 배운 곱셈보다 복잡하다. 하지만

컴퓨터는 2진수 시스템이기때문에 이게 더 편하다고 한다.

하지만 프로그래밍할때 무조건 저 알고리즘을 써라 하는건 아니다.

상황에 맞게 쓰는 게 중요한것이다.

twitter facebook me2day 요즘
처음 보는 방법이네요.
처음 보는 방법이네요.
07.23 03:34 | 다니에르님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
I want to download
I want to download
08.18 04:13 | testt2님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
........윽 ㅜㅜ 어렵다
........윽 ㅜㅜ 어렵다
01.19 23:05 | 안전제일님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
연산량이 줄어든다는건가요?
연산량이 줄어든다는건가요?
02.15 03:49 | 히이로님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
독특한 방법이네요..

독특한 방법이네요..

02.20 13:37 | 피닉스님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
댓글쓰기 - 로그인한 후 댓글작성권한이 있을 경우 이용하실 수 있습니다.

비밀번호 확인

댓글 등록시에 입력했던 비밀번호를 입력해 주세요.
87개(1/5페이지)
rss
C
번호 제목 작성자 작성일 조회
87 배열설정 쉽게하기 부보 2012.12.22 2147
86 [고급]연습문제[11] 권율 2010.01.10 9660
85 [고급]C언어에서 포인터 이용한 간단한 암호 ~[8] 쫭구 2009.11.11 9478
84 [중급]BOF의 개념과 BOF를 이용한 해킹 방법[10] Ezbeat 2010.03.19 10252
83 [중급]ReadProcessMemory & WriteProcessMemory사진[8] COOLSOFT 2009.06.04 10033
82 [기초]C언어의 탄생 배경[20] COOLSOFT 2007.11.03 10136
81 [기초]비주얼 C++ 설치하기사진첨부파일[15] COOLSOFT 2007.10.27 7296
80 [기초]Microsoft Visual C++ Windows Applications by Example첨부파일[4] COOLSOFT 2009.04.03 7399
79 [기초][TIP]swap함수 매크로 한줄로 끝내기[9] secretofsh 2009.03.05 10739
78 [기초]c# 화면캡쳐프로그램 -소스포함 |첨부파일[12] 야옹이 2008.12.25 13036
77 [기초]주민번호를 만들어내는 규칙에 대해서 설명과 소스[26] COOLSOFT 2008.07.12 10297
76 [기초]윈도우 기본 창 생성 소스 -주석 포함-[7] 진혼이중주 2008.05.31 10893
75 [기초]WIN 32 API 시작하기전에 간단히 알아두기[10] 진혼이중주 2008.05.31 9485
74 [기초]c++ 강좌 #3 변수와 상수 (1)[15] 진혼이중주 2008.05.28 8985
73 [기초]C++ 강좌 #2 C++언어의 기본적인 구조[6] 진혼이중주 2008.05.28 6069
72 [기초]C++ 강좌 #1[12] 진혼이중주 2008.05.28 6849
71 [기초]리스트 자료구조의 기본적인 개념[3] 진혼이중주 2008.05.16 8037
>> [기초]두 자리 수 이상의 곱셈에 대한 알고리즘[5] 진혼이중주 2008.05.16 7277
69 [기초]Turbo 2.0 설치 및 사용법첨부파일[2] 진혼이중주 2008.05.16 8913
68 [기초]삼성 프로그래머들의 C/C++ 코딩 스타일의 지침서첨부파일[41] 진혼이중주 2008.05.05 15626
처음페이지이전 10 페이지12345다음 10 페이지마지막페이지