대수는 내가 기본 <code>b</code>을 정수하는 정수 <code>n</code>의 대수의 상승 둥근 가치를 발견하고자하는 정수

Question

의 기본을 정수로. 코드에서 :

result = int(ceil(log(n, b))) 

문제는 때때로 값이 결과를 과대 평가, 부동 소수점 정확히 표현 될 수 없다는 것입니다. 예 :

log(125, 5) == int(ceil(3.0000000000000004)) == 4 

어떻게해야합니까? 작은 엡실론을 빼면 그것을 다른 곳에서 과소 평가합니다. base 2을 사용할 때처럼 부동 소수점 계산을 완전히 단계적으로 수행 할 수 있습니까?

로그를 찾기 위해 루프를 사용할 수는 있지만 일정 시간 내에이 작업을 수행 할 수 있는지 궁금합니다.

Answer 1

글쎄, 당신은 일정한 시간의 의미에주의해야합니다. 고정 너비 정수를 처리하는 경우 간단한 for 루프가 묶입니다 (밑 2의 64 비트 정수가 최악의 경우는 64 곱셈입니다). log을 호출하면 float로 변환하는 것보다 더 빠릅니다 함수로 끝나고 다시 정수로 자릅니다.

임의 정밀도 정수를 사용하는 경우 거의 모든 연산이 float 로의 캐스팅을 포함하여 O (log (n)) 이상이므로 기본적으로 상수 시간 알고리즘과 같은 것은 없습니다. (I 파이썬 같은 기능을 제공합니다 생각하지 않습니다하지만)

• 당신은 기본 2 인 로그를 찾기 위해 find first set 작업을 사용할 수 있습니다 말했다

  는

  , 당신이 시도 할 수있는 다른 몇 가지가있다 . x86에서는 이러한 목적으로 bsr 명령을 제공합니다. 이것은 또한 일정 시간이 될 수있는 임의의 정밀도 정수에 대한 몇 가지 연산 중 하나입니다 (구현, 메모리 저장 등에 따라 달라질 수 있음).

• 당신은 기본 2 인 로그가 있으면, 당신은 정수 나누기에 의한 전력의-2를 계산하는 데 사용할 수 있습니다.

• 만 동일한 기본 B를 사용하는 경우, 그리고 입력은 당신이 (O 될 것이다 이진 검색과 결합 B의 힘의 미리 계산 된 룩업 테이블 (로그를 사용할 수 B ^K에 의해 제한된다 k) * log (n))에 대한 검색을 수행합니다 (검색의 경우 log (k), 각 부등식 비교의 경우 log (n)).

• 이 경우가 아니더라도 몇 가지 종류의 이진 검색을 시도 할 수 있습니다. 너무 큰 경우에는 제곱하여 지수를 두 배로 유지 한 다음 이진 검색을 계속하십시오.

• 원래 아이디어는 오류 분석의 비트와 함께 결합, 빠르게 경우를 계산할 수있다, 당신은 부정확 한 것들에 후퇴 할 수 있습니다. 파이썬은 2 인자 인 log에 대한 에러 범위를 제공하지 않습니다. (예제는 정확해야하기 때문에 좋지 않습니다.) 요즘 가장 괜찮은 수학 라이브러리는 1 인수 인 log을 1 ulp (단위 마지막 자리에서), float로 캐스팅하고 1/2 ulp 이내로 나누면 3 ulps의 총 상대 오차가 발생합니다. (왜냐하면 이것들은 모두 multiplicitive이므로) 여러분의베이스가 float로 정확하게 표현 될 수 있다고 가정합니다 (즉, 1e30).

파이썬이 될 것이다 : 정수 후 정밀도 고정되면

import math, sys 
def clog(n,b): 
    a = math.log(n)/math.log(b) 
    r = round(a) 
    i = int(r) 
    if abs(a-r) <= a*3*sys.float_info.epsilon: 
     # slow 
     if n > b**i: 
      return i+1 
     else: 
      return i 
    else: 
     return int(math.ceil(a))