// * 연산자를 사용하지 않고 divide를 수행하는 가장 빠른 방법

Question

Skiena의 알고리즘 서적을 따르고 있습니다. 1 장에서는/또는 * 연산자를 사용하지 않고 실수를 나눌 수있는 문제가 있습니다.

def main(dividend, divisor): 
    print "dividend : ",dividend 
    print "divisor : ", divisor 
    if dividend<divisor: 
     print "dividend has to be greater than divisor" 
     return; 
    quotient=0 
    sum=0 
    while sum<dividend: 
     sum = sum+divisor 
     print "sum : ",sum 
     quotient = quotient+1 
     if sum>dividend: 
      remainder = dividend-(sum-divisor) 
      quotient=quotient-1 
      print "remainder : ", remainder 
    print "quotient :", quotient 





    if __name__ == "__main__": 
     # pass any two real number as dividend and divisor 
     main(29, 3) 

이 문제는 또한, "그것을 할 수있는 가장 빠른 방법을 찾아"해야한다고 주장 : 이 같은 파이썬에서 것을 구현했습니다. 문제를 더 빨리 해결할 수있는 다른 방법이 있습니까?

Answer 1

코드를 작성하지는 않겠지 만 빠른 방법은 2의 제곱과 덧셈과 뺄셈 연산자 만 사용합니다. 973/47의 예를 생각해 봅시다. 먼저 제수의 2 배의 거듭 제곱의 테이블을 작성하십시오. 당신은 간단한 추가와 함께이 작업을 수행 할 수 있습니다 (2) 자체에 추가의

이

1: 47 
2: 94 
4: 188 
8: 376 
16: 752 
32: 1504 

2의 각 전원 단지 이전의 힘이다. 2의 배율이 배당금을 초과하면 중지하십시오. 이제 남은 배당 미만인 경우 (2)의 전력을 빼서, 후진 동작 :

16: 973 - 752 = 221 
4: 221 - 188 = 33 

따라서 지수는 16 + 4 = 20이고, 나머지 33

이 알고리즘은 비슷하다 내가 곱셈을위한 농민 알고리즘을 말하며, 이것에 대해서는 my blog에서 논의한다.