(a/b)^n을 근사하는 효과적인 방법이 있습니까? a, b 및 n은 부호없는 정수입니까?

Question

Exponentiation by squaring은 ⁿ을 신속하게 계산하는 알고리즘입니다. 여기서 a 및 n은 부호있는 정수입니다. (O (log n) 곱셈에서 그렇게한다).

유사한 알고리즘이 있는가

, 그 대신에 연산은 (a/b) a, b 및 n 모든 부호없는 정수는 N ? 분명한 접근법 (즉, ⁿ/b ⁿ)의 문제점은 중간 값의 정수 오버플로로 인해 잘못된 결과를 반환한다는 것입니다.

호스트 언어에 부동 소수점이없고 정수 만 사용할 수 있습니다.

나는 대략적인 대답으로 괜찮습니다.

Answer 1

a, b 및 n이 부호없는 정수인 경우 (a/b)^n의 값에 대해 우수한 정확도를 원하고 부동 소수점 산술을 사용할 수없는 경우 - 확장 정밀도 정수 계산을 사용하여 a^n과 b^n을 구한 다음, 둘을 나눕니다.

파이썬과 같은 일부 언어에는 확장 정수 연산이 내장되어 있습니다. 언어에 해당하지 않는 언어를 구현하는 패키지를 찾으십시오. 그렇게 할 수 없다면, 직접 패키지를 만드십시오. 그것은 어렵지 않습니다. 그런 패키지는 제 2 학기 컴퓨터 과학 수업에서 배정되었습니다. 곱셈과 곱셈은 매우 간단합니다. 몫과 나머지를 원한다고해도 가장 어려운 부분은 부분입니다. 그러나 "가장 어렵다"는 의미는 "매우 어렵다"는 뜻은 아닙니다. 두 번째는 확장 된 정수를 십진수 형식으로 인쇄하는 어려운 루틴입니다.

기본 개념은 각 정수를 정규 부호없는 정수 배열 또는 목록에 저장하는 것입니다. 여기서 정수는 큰 기본이있는 산술에서 "숫자"입니다. 두 자릿수의 제품을 처리 할 수 ​​있기를 원합니다. 따라서 시스템에 32 비트 정수가 있고 64 비트 정수를 처리 할 방법이없는 경우 각각 16 비트의 "자릿수"를 저장하십시오. "숫자"가 클수록 계산이 빨라집니다. 계산량이 적고 10 진수로 인쇄하는 것이 자주 발생하면 각 "숫자"에 대해 10000과 같은 10의 지수를 사용하십시오.

자세한 내용이 필요하면 질문하십시오.

Answer 2

사람이 상수 공간 솔루션을 찾고있는 경우를 대비하여 이항 확장을 사용하여 문제를 해결했습니다. 이는 근사적인 근사치입니다. 단순히 r 작은 양의 실수이다 (1 + r)^N의 이항 확장의 p 첫 번째 조건을 계산

// Computes `k * (1+1/q)^N`, with precision `p`. The higher 
// the precision, the higher the gas cost. It should be 
// something around the log of `n`. When `p == n`, the 
// precision is absolute (sans possible integer overflows). 
// Much smaller values are sufficient to get a great approximation. 
function fracExp(uint k, uint q, uint n, uint p) returns (uint) { 
    uint s = 0; 
    uint N = 1; 
    uint B = 1; 
    for (uint i = 0; i < p; ++i){ 
    s += k * N/B/(q**i); 
    N = N * (n-i); 
    B = B * (i+1); 
    } 
    return s; 
} 

: 나는 다음과 같은 코드를 사용하고 있습니다. 나는 Ethereum Stack Exchange에 더 사려 깊은 설명을 올렸다.

Answer 3

다음은 Feynman의 로그 알고리즘을 기반으로 고정 소수점으로 구현 된 pow입니다. 그것은 빠르고 더러운 것입니다. C 라이브러리는 다항식 근사법을 사용하는 경향이 있지만 그 접근법은 더 복잡하며 고정 점으로 변환하는 것이 얼마나 좋은지 잘 모르겠습니다.

// powFraction approximates (a/b)**n. 
func powFraction(a uint64, b uint64, n uint64) uint64 { 
    if a == 0 || b == 0 || a < b { 
     panic("powFraction") 
    } 
    return expFixed((logFixed(a) - logFixed(b)) * n) 
} 

// logFixed approximates 2**58 * log2(x). [Feynman] 
func logFixed(x uint64) uint64 { 
    if x == 0 { 
     panic("logFixed") 
    } 
    // Normalize x into [2**63, 2**64). 
    n := numberOfLeadingZeros(x) 
    x <<= n 
    p := uint64(1 << 63) 
    y := uint64(0) 
    for k := uint(1); k <= 63; k++ { 
     // Warning: if q > x-p, then p + q may overflow. 
     if q := p >> k; q <= x-p { 
      p += q 
      y += table[k-1] 
     } 
    } 
    return uint64(63-n)<<58 + y>>6 
} 

// expFixed approximately inverts logFixed. 
func expFixed(y uint64) uint64 { 
    n := 63 - uint(y>>58) 
    y <<= 6 
    p := uint64(1 << 63) 
    for k := uint(1); k <= 63; k++ { 
     if z := table[k-1]; z <= y { 
      p += p >> k 
      y -= z 
     } 
    } 
    return p >> n 
} 

// numberOfLeadingZeros returns the number of leading zeros in the word x. 
// [Hacker's Delight] 
func numberOfLeadingZeros(x uint64) uint { 
    n := uint(64) 
    if y := x >> 32; y != 0 { 
     x = y 
     n = 32 
    } 
    if y := x >> 16; y != 0 { 
     x = y 
     n -= 16 
    } 
    if y := x >> 8; y != 0 { 
     x = y 
     n -= 8 
    } 
    if y := x >> 4; y != 0 { 
     x = y 
     n -= 4 
    } 
    if y := x >> 2; y != 0 { 
     x = y 
     n -= 2 
    } 
    if x>>1 != 0 { 
     return n - 2 
    } 
    return n - uint(x) 
} 

// table[k-1] approximates 2**64 * log2(1 + 2**-k). [MPFR] 
var table = [...]uint64{ 
    10790653543520307104, // 1 
    5938525176524057593, // 2 
    3134563013331062591, // 3 
    1613404648504497789, // 4 
    818926958183105433, // 5 
    412613322424486499, // 6 
    207106307442936368, // 7 
    103754619509458805, // 8 
    51927872466823974, // 9 
    25976601570169168, // 10 
    12991470209511302, // 11 
    6496527847636937,  // 12 
    3248462157916594,  // 13 
    1624280643531991,  // 14 
    812152713665686,  // 15 
    406079454902306,  // 16 
    203040501980337,  // 17 
    101520444623942,  // 18 
    50760270720599,  // 19 
    25380147462480,  // 20 
    12690076756788,  // 21 
    6345039134781,  // 22 
    3172519756487,  // 23 
    1586259925518,  // 24 
    793129974578,   // 25 
    396564990243,   // 26 
    198282495860,   // 27 
    99141248115,   // 28 
    49570624104,   // 29 
    24785312063,   // 30 
    12392656035,   // 31 
    6196328018,   // 32 
    3098164009,   // 33 
    1549082005,   // 34 
    774541002,   // 35 
    387270501,   // 36 
    193635251,   // 37 
    96817625,    // 38 
    48408813,    // 39 
    24204406,    // 40 
    12102203,    // 41 
    6051102,    // 42 
    3025551,    // 43 
    1512775,    // 44 
    756388,    // 45 
    378194,    // 46 
    189097,    // 47 
    94548,    // 48 
    47274,    // 49 
    23637,    // 50 
    11819,    // 51 
    5909,     // 52 
    2955,     // 53 
    1477,     // 54 
    739,     // 55 
    369,     // 56 
    185,     // 57 
    92,     // 58 
    46,     // 59 
    23,     // 60 
    12,     // 61 
    6,     // 62 
    3,     // 63 
}