[C] Booth's Algorithm 구현

소개글

프로그램 소스 코드 및 보고서 첨부했습니다.
A+ 받은 과제입니다.

컴파일 실행환경

보고서에 첨부/
gcc 사용

본문내용

Booth’s algorithm을 simulation하는 프로그램을 구현한다. Booth’s algorithm은 곱셈을 수행할 때 add 연산의 회수를 줄이는 algorithm으로 쉽게 생각할 수 있는 곱셈 방법을 개선한 algorithm이다. 32bit 곱셈에서 쉽게 생각할 수 있는 방법은 32회의 iteration을 수행하며 각 iteration에서 해당 번째의 multiplier의 bit를 확인하여 1이면, multiplicand를 해당 bit 만큼 shift left해 준 값을 product에 더해주는 방법을 사용한다. 따라서, shift는 32회 발생하고, add 연산은 multiplier의 bit 중 1의 개수만큼 발생한다.
Booth’s algorithm에서는 이를 개선하여, 특정 숫자 k를 2^n – 2^m으로 바꾸어 연산하는 방법을 사용한다. 따라서, 같은 숫자를 갖는 bit가 연이어 나올 경우 add 연산을 상당히 줄일 수 있다. Booth’s algorithm은 이를 이용하여, 여러 번 발생하는 add 연산을 몇 회의 add, sub 연산으로 바꾸어 연산한다. Booth’s simulator에서는 이를 구현하며, 각 iteration에서의 결과 중 argument에서 지정한 iteration의 결과를 출력하고, 최종 결과를 출력한다.

압축파일 내 파일목록

report.doc
sim-booth.c

참고 자료

없음