[python] 나눗셈 구현 (divide operator with bit-operations)

나눗셈을 구현하기:    몫과 나머지를 구하는 함수를 직접 구현해 본다.

 1) 느린 방법: for loop 이용하기 --> 아주 큰 숫자에 대해 너무 느린 문제가 있다.

 2) 빠른 방법: bit operation (shift) 이용하여 빠른 버전을 구현할 수 있다.

아래의 두 함수를 비교해 볼 수 있다.

divAndMod( y, x, debug=0) 으로 실행하면 디버그 메시지 없이 볼 수 있습니다.

divAndMod()를 더 최적화할 수 있는 방법을 제시해 주시면 대환영입니다 ^^.

	import sys
	# implement divide operation without using built-in divide operator
	def divAndMod_slow(y,x, debug=0):
	r = 0
	while y >= x:
	r += 1
	y -= x
	return r,y
	# implement divide operation without using built-in divide operator
	def divAndMod(y,x, debug=0):
	## find the highest position of positive bit of the ratio
	pos = -1
	while y >= x:
	pos += 1
	x <<= 1
	x >>= 1
	if debug: print "y=%d, x=%d, pos=%d" % (y,x,pos)
	if pos == -1:
	return 0, y
	r = 0
	while pos >= 0:
	if y >= x:
	r += (1 << pos)
	y -= x
	if debug: print "y=%d, x=%d, r=%d, pos=%d" % (y,x,r,pos)
	x >>= 1
	pos -= 1
	return r, y
	if __name__ =="__main__":
	if len(sys.argv) == 3:
	y = int(sys.argv[1])
	x = int(sys.argv[2])
	else:
	y = 313271356
	x = 7
	print "=== Slow Version ...."
	res = divAndMod_slow( y, x)
	print "%d = %d * %d + %d" % (y, x, res[0], res[1])
	print "=== Fast Version ...."
	res = divAndMod( y, x, debug=1)
	print "%d = %d * %d + %d" % (y, x, res[0], res[1])

view raw divide_with_bit_operation.py hosted with ❤ by GitHub