정수 기반 전원 함수 pow(int, int)를 구현하는 가장 효율적인 방법
정수를 C에 있는 다른 정수의 거듭제곱으로 증가시키는 가장 효율적인 방법은 무엇입니까?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
제곱에 의한 지수화.
int ipow(int base, int exp)
{
int result = 1;
for (;;)
{
if (exp & 1)
result *= base;
exp >>= 1;
if (!exp)
break;
base *= base;
}
return result;
}
이것은 비대칭 암호학에서 방대한 수의 모듈러 인수를 수행하기 위한 표준 방법입니다.
제곱에 의한 지수화는 최적의 방법이 아닙니다.모든 지수 값에 대해 사용할 수 있는 일반적인 방법으로는 이것이 가장 좋지만 특정 지수 값에 대해 곱셈이 더 적게 필요한 더 나은 시퀀스가 있을 수 있습니다.
예를 들어, x^15를 계산하려면 제곱에 의한 지수법을 사용하면 다음과 같은 결과를 얻을 수 있습니다.
x^15 = (x^7)*(x^7)*x
x^7 = (x^3)*(x^3)*x
x^3 = x*x*x
이것은 총 6의 곱셈입니다.
이는 추가 체인 지수를 통해 "단순한" 5승법을 사용하여 수행할 수 있는 것으로 나타났습니다.
n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15
이 최적의 곱셈 시퀀스를 찾는 효율적인 알고리즘은 없습니다.Wikipedia에서:
최단 덧셈 체인을 찾는 문제는 최적의 하부 구조의 가정을 만족시키지 못하기 때문에 동적 프로그래밍으로 해결할 수 없습니다.즉, 더 작은 전력에 대한 추가 체인은 (연산을 공유하기 위해) 관련될 수 있기 때문에 전력을 더 작은 전력으로 분해하는 것은 충분하지 않다.예를 들어, 위의 a1에 대한 최단 덧셈 체인에서 a1의 하위 문제는 a2가 재사용되기 때문에 (a2 = a²(a²)²로 계산해야 하며, 이는 3배의 곱셈이 필요합니다.)
2의 거듭제곱을 해야 한다면.이를 위한 가장 빠른 방법은 전력에 의한 비트 시프트입니다.
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
power()정수에만 사용할 함수
int power(int base, unsigned int exp){
if (exp == 0)
return 1;
int temp = power(base, exp/2);
if (exp%2 == 0)
return temp*temp;
else
return base*temp*temp;
}
복잡도 = O(log(exp)
power()음의 exp 및 float base에 대해 기능합니다.
float power(float base, int exp) {
if( exp == 0)
return 1;
float temp = power(base, exp/2);
if (exp%2 == 0)
return temp*temp;
else {
if(exp > 0)
return base*temp*temp;
else
return (temp*temp)/base; //negative exponent computation
}
}
복잡도 = O(log(exp)
매우 특수한 경우는 2^(-x의 y제곱)이라고 할 때, 여기서 x는 물론 음수이고 y는 너무 커서 int에서 시프트를 할 수 없습니다.플로트로 나사를 조이면 2^x를 일정한 시간에 할 수 있습니다.
struct IeeeFloat
{
unsigned int base : 23;
unsigned int exponent : 8;
unsigned int signBit : 1;
};
union IeeeFloatUnion
{
IeeeFloat brokenOut;
float f;
};
inline float twoToThe(char exponent)
{
// notice how the range checking is already done on the exponent var
static IeeeFloatUnion u;
u.f = 2.0;
// Change the exponent part of the float
u.brokenOut.exponent += (exponent - 1);
return (u.f);
}
기본형으로 더블을 사용하면 2의 거듭제곱을 더 얻을 수 있습니다.(이 투고를 정정할 수 있도록 도와주신 코멘트 분들께 감사드립니다).
또한 IEEE에 대해 더 많은 것을 알게 되면 다른 특별한 지수화 사례가 나타날 수도 있습니다.
int pow(int const x, unsigned const e) noexcept
{
return !e ? 1 : 1 == e ? x : (e % 2 ? x : 1) * pow(x * x, e / 2);
//return !e ? 1 : 1 == e ? x : (((x ^ 1) & -(e % 2)) ^ 1) * pow(x * x, e / 2);
}
네, 재귀적이지만 컴파일러를 잘 최적화하면 재귀가 최적화됩니다.
int pow( int base, int exponent)
{ // Does not work for negative exponents. (But that would be leaving the range of int)
if (exponent == 0) return 1; // base case;
int temp = pow(base, exponent/2);
if (exponent % 2 == 0)
return temp * temp;
else
return (base * temp * temp);
}
Swift의 O(log N) 솔루션...
// Time complexity is O(log N)
func power(_ base: Int, _ exp: Int) -> Int {
// 1. If the exponent is 1 then return the number (e.g a^1 == a)
//Time complexity O(1)
if exp == 1 {
return base
}
// 2. Calculate the value of the number raised to half of the exponent. This will be used to calculate the final answer by squaring the result (e.g a^2n == (a^n)^2 == a^n * a^n). The idea is that we can do half the amount of work by obtaining a^n and multiplying the result by itself to get a^2n
//Time complexity O(log N)
let tempVal = power(base, exp/2)
// 3. If the exponent was odd then decompose the result in such a way that it allows you to divide the exponent in two (e.g. a^(2n+1) == a^1 * a^2n == a^1 * a^n * a^n). If the eponent is even then the result must be the base raised to half the exponent squared (e.g. a^2n == a^n * a^n = (a^n)^2).
//Time complexity O(1)
return (exp % 2 == 1 ? base : 1) * tempVal * tempVal
}
파티에 늦다:
이하에, 이하와 같은 대처 방법을 나타냅니다.y < 0선선해해해해해해
- 문장은 의과결 of of of of of of of 의 결과를 합니다.
intmax_t최대 범위입니다..intmax_t powjii(0, 0) --> 1이 사건에서 흔히 볼 수 있는 결과입니다.pow(0,negative)또 「미정의되지 않은 결과가 반환됩니다.INTMAX_MAXintmax_t powjii(int x, int y) { if (y < 0) { switch (x) { case 0: return INTMAX_MAX; case 1: return 1; case -1: return y % 2 ? -1 : 1; } return 0; } intmax_t z = 1; intmax_t base = x; for (;;) { if (y % 2) { z *= base; } y /= 2; if (y == 0) { break; } base *= base; } return z; }
루프가 됩니다.for(;;)를 base *= base하다1) 하고 2) 곱셈은 2)가 될 수 .int*int(UB(UB))
2에 대한 정수 값을 무언가의 거듭제곱으로 올리려면 항상 shift 옵션을 사용하는 것이 좋습니다.
pow(2,5)할 수 1<<5
이것이 훨씬 더 효율적입니다.
또 하나의 구현(Java).가장 효율적인 솔루션은 아니지만 반복 횟수는 지수 솔루션과 동일합니다.
public static long pow(long base, long exp){
if(exp ==0){
return 1;
}
if(exp ==1){
return base;
}
if(exp % 2 == 0){
long half = pow(base, exp/2);
return half * half;
}else{
long half = pow(base, (exp -1)/2);
return base * half * half;
}
}
나는 모든 계산 파워를 기억한 후 필요할 때 사용하는 알고리즘을 구현했다.예를 들어 x^13은 (x^2)^2^2 * x^2^2 * x 와 같습니다. 여기서 x^2^2는 다시 계산하지 않고 표에서 가져옵니다.이것은 기본적으로 @Pramod answer의 구현입니다(단, C#).필요한 곱셈 수는 Ceil(Log n)입니다.
public static int Power(int base, int exp)
{
int tab[] = new int[exp + 1];
tab[0] = 1;
tab[1] = base;
return Power(base, exp, tab);
}
public static int Power(int base, int exp, int tab[])
{
if(exp == 0) return 1;
if(exp == 1) return base;
int i = 1;
while(i < exp/2)
{
if(tab[2 * i] <= 0)
tab[2 * i] = tab[i] * tab[i];
i = i << 1;
}
if(exp <= i)
return tab[i];
else return tab[i] * Power(base, exp - i, tab);
}
내 경우는 조금 달라서 파워로 마스크를 만들려고 하는데 어쨌든 내가 찾은 해결책을 공유하려고 했어.
2의 거듭제곱에 대해서만 효과가 있습니다.
Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
컴파일 시 지수(및 정수)를 알고 있는 경우 템플릿을 사용하여 루프를 전개할 수 있습니다.이것은 보다 효율적으로 할 수 있지만, 저는 여기서 기본적인 원칙을 보여주고 싶었습니다.
#include <iostream>
template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
return base * exp_unroll<N-1>(base);
}
템플릿 특화를 사용하여 재귀를 종료합니다.
template<>
unsigned long inline exp_unroll<1>(unsigned base) {
return base;
}
실행 시 지수를 알아야 합니다.
int main(int argc, char * argv[]) {
std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}
Java에서의 메서드는 다음과 같습니다.
private int ipow(int base, int exp)
{
int result = 1;
while (exp != 0)
{
if ((exp & 1) == 1)
result *= base;
exp >>= 1;
base *= base;
}
return result;
}
제곱에 의한 지수의 효율성에 대한 코멘트에 대한 후속 조치입니다.
이 접근법의 장점은 로그(n) 시간 내에 실행된다는 것입니다.예를 들어 x^1048575(2^20 - 1)와 같이 큰 것을 계산하는 경우, 순진한 접근방식을 사용하여 100만 이상이 아니라 루프를 20회만 통과하면 됩니다.
또한, 코드 복잡성의 측면에서, 이것은 프라모드의 제안인 최적의 곱셈 시퀀스를 찾는 것보다 단순하다.
편집:
누군가 나에게 넘칠 수 있는 가능성에 대해 꼬리표를 붙이기 전에 분명히 해야 할 것 같아요.이 접근법에서는 일종의 거대한 라이브러리가 있다고 가정합니다.
마이너스 지수넷을 고려한 보다 일반적인 솔루션
private static int pow(int base, int exponent) {
int result = 1;
if (exponent == 0)
return result; // base case;
if (exponent < 0)
return 1 / pow(base, -exponent);
int temp = pow(base, exponent / 2);
if (exponent % 2 == 0)
return temp * temp;
else
return (base * temp * temp);
}
exp가 짝수이면 5^10 = 25^5를 재귀로 사용합니다.
int pow(float base,float exp){
if (exp==0)return 1;
else if(exp>0&&exp%2==0){
return pow(base*base,exp/2);
}else if (exp>0&&exp%2!=0){
return base*pow(base,exp-1);
}
}
Elias의 답변과 더불어 부호 있는 정수로 구현될 경우 정의되지 않은 동작을 유발하고 부호 없는 정수로 구현될 경우 높은 입력에 잘못된 값을 발생시킵니다.
다음은 부호 있는 정수 유형에서도 작동하며 잘못된 값을 제공하지 않는 스쿼링에 의한 지수화의 수정된 버전입니다.
#include <stdint.h>
#define SQRT_INT64_MAX (INT64_C(0xB504F333))
int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
int_fast64_t base_;
int_fast64_t result;
base_ = base;
if (base_ == 1)
return 1;
if (!exp)
return 1;
if (!base_)
return 0;
result = 1;
if (exp & 1)
result *= base_;
exp >>= 1;
while (exp) {
if (base_ > SQRT_INT64_MAX)
return 0;
base_ *= base_;
if (exp & 1)
result *= base_;
exp >>= 1;
}
return result;
}
이 기능에 관한 고려사항:
(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0
오버플로나 래핑이 발생할 경우return 0;
나는 사용했다int64_t단, 임의의 폭(부호 포함 또는 부호 없음)은 거의 변경하지 않고 사용할 수 있습니다.단, 비고정폭 정수형을 사용해야 하는 경우,SQRT_INT64_MAX타고(int)sqrt(INT_MAX)(사용하는 경우)int또는 이와 유사한 것으로 최적화해야 하지만 C 상수식이 아니라 더 추합니다.또한 결과물을 캐스팅하는 중sqrt()에 대해서int완벽한 사각형의 경우 부동 소수점 프리퍼런스로 인해 매우 좋지 않습니다. 그러나 나는 어떤 구현도 알지 못하기 때문에INT_MAX- 또는 어떤 유형의 최대값도 완벽한 정사각형입니다. - 당신은 그것을 감수할 수 있습니다.
언급URL : https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int
'programing' 카테고리의 다른 글
| 하위 구성 요소에서 Vuex가 작동하지 않음 (0) | 2022.08.18 |
|---|---|
| Vue-repo "모듈 빌드 실패:오류: ESLint 구성을 찾을 수 없습니다." (0) | 2022.08.18 |
| Vue.JS 및 Rails-UJS/Jquery-UJS 경합 - Vuex 돌연변이가 작동하지 않음 (0) | 2022.08.11 |
| 포인터가 NULL 포인터인지 확인하려면 어떻게 해야 하나요? (0) | 2022.08.11 |
| 여러 조건의 if 실행 순서 (0) | 2022.08.11 |