Как я могу написать степенную функцию сам?

Question

Мне всегда было интересно, как я могу сделать функцию, которая сама рассчитывает мощность (например, 2 ³ ). На большинстве языков они включены в стандартную библиотеку, в основном как pow(double x, double y), но как я могу написать это сам?

Я думал о for loops, но он думал, что мой мозг оказался в цикле (когда я хотел сделать мощность с нецелым показателем, например, 5 ^4.5 или отрицательные значения 2 ^-21 ) и я сошел с ума;)

Итак, как мне написать функцию, которая вычисляет мощность действительного числа? Спасибо

---

О, может быть, важно отметить: я не могу использовать функции, которые используют полномочия (например, exp), которые сделали бы это в конечном счете бесполезным.

Answer 1

Это интересное упражнение. Вот несколько предложений, которые вы должны попробовать в следующем порядке:

1. Используйте цикл.
2. Используйте рекурсию (не лучше, но, тем не менее, интересно)
3. Значительно оптимизируйте рекурсию, используя метод «разделяй и властвуй» методы
4. Использовать логарифмы

Answer 2

Множество подходов дано в других ответах. Вот кое-что, что я подумал, может быть полезно в случае целочисленных степеней.

В случае целочисленной степени x, равной n ^x , простой подход потребовал бы умножения x-1. Чтобы оптимизировать это, мы можем использовать динамическое программирование и повторно использовать более ранний результат умножения, чтобы избежать всех умножений x. Например, в 5 ⁹ мы можем, скажем, сделать пакетов по 3 , то есть вычислить 5 ³ один раз, получить 125, а затем куб 125, используя тот же логика, принимая только 4 умножения в процессе, вместо 8 умножений с простым способом.

Вопрос в том, каков идеальный размер партии b, чтобы число умножений было минимальным. Итак, давайте напишем уравнение для этого. Если f (x, b) является функцией, представляющей количество умножений, использованных при вычислении n ^x с использованием вышеуказанного метода, тогда

f (x, b) = (x / b - 1) + (b-1) ">

Объяснение: Произведение из серии чисел p будет умножаться на p-1. Если мы разделим x умножений на b пакетов, в каждом пакете потребуется (x / b) -1 умножений, а для всех b пакетов потребуется умножение b-1.

Теперь мы можем вычислить первую производную этой функции по b и приравнять ее к 0, чтобы получить b для наименьшего числа умножений.

2 + 1 = 0">

Теперь верните это значение b в функцию f (x, b), чтобы получить наименьшее количество умножений:

Для всех положительных x это значение меньше, чем умножения прямым способом.

Answer 3

Я использую арифметику с фиксированной запятой, и мой pow основан на log2 / exp2. Числа состоят из:

• int sig = { -1; +1 } signum
• DWORD a[A+B] число
• A - это число DWORD с для целой части числа
• B - это число DWORD с для дробной части

Мое упрощенное решение таково:

//---------------------------------------------------------------------------
longnum exp2 (const longnum &x)
{
    int i,j;
    longnum c,d;
    c.one();
    if (x.iszero()) return c;
    i=x.bits()-1;
    for(d=2,j=_longnum_bits_b;j<=i;j++,d*=d)
    if (x.bitget(j))
    c*=d;
    for(i=0,j=_longnum_bits_b-1;i<_longnum_bits_b;j--,i++)
    if (x.bitget(j))
    c*=_longnum_log2[i];
    if (x.sig<0) {d.one(); c=d/c;}
    return c;
}
//---------------------------------------------------------------------------
longnum log2 (const longnum &x)
{
    int i,j;
    longnum c,d,dd,e,xx;
    c.zero(); d.one(); e.zero(); xx=x;
    if (xx.iszero()) return c; //**** error: log2(0) = infinity
    if (xx.sig<0) return c; //**** error: log2(negative x) ... no result possible
    if (d.geq(x,d)==0) {xx=d/xx; xx.sig=-1;}
    i=xx.bits()-1;
    e.bitset(i); i-=_longnum_bits_b;
    for (;i>0;i--,e>>=1) // integer part
    {
        dd=d*e;
        j=dd.geq(dd,xx);
        if (j==1) continue; // dd> xx
        c+=i; d=dd;
        if (j==2) break; // dd==xx
    }
    for (i=0;i<_longnum_bits_b;i++) // fractional part
    {
        dd=d*_longnum_log2[i];
        j=dd.geq(dd,xx);
        if (j==1) continue; // dd> xx
        c.bitset(_longnum_bits_b-i-1); d=dd;
        if (j==2) break; // dd==xx
    }
    c.sig=xx.sig;
    c.iszero();
    return c;
}
//---------------------------------------------------------------------------
longnum pow (const longnum &x,const longnum &y)
{
    //x^y = exp2(y*log2(x))
    int ssig=+1; longnum c; c=x;
    if (y.iszero()) {c.one(); return c;} // ?^0=1
    if (c.iszero()) return c; // 0^?=0
    if (c.sig<0)
    {
        c.overflow(); c.sig=+1;
        if (y.isreal()) {c.zero(); return c;} //**** error: negative x ^ noninteger y
        if (y.bitget(_longnum_bits_b)) ssig=-1;
    }
    c=exp2(log2(c)*y); c.sig=ssig; c.iszero();
    return c;
}
//---------------------------------------------------------------------------

где:

_longnum_bits_a = A*32
_longnum_bits_b = B*32
_longnum_log2[i] = 2 ^ (1/(2^i))  ... precomputed sqrt table 
_longnum_log2[0]=sqrt(2)  
_longnum_log2[1]=sqrt[tab[0]) 
_longnum_log2[i]=sqrt(tab[i-1])
longnum::zero() sets *this=0
longnum::one() sets *this=+1
bool longnum::iszero() returns (*this==0)
bool longnum::isnonzero() returns (*this!=0)
bool longnum::isreal() returns (true if fractional part !=0)
bool longnum::isinteger() returns (true if fractional part ==0)
int longnum::bits() return num of used bits in number counted from LSB
longnum::bitget()/bitset()/bitres()/bitxor() are bit access
longnum.overflow() rounds number if there was a overflow X.FFFFFFFFFF...FFFFFFFFF??h  -> (X+1).0000000000000...000000000h
int longnum::geq(x,y)  is comparition |x|,|y| returns 0,1,2 for (<,>,==)

Все, что вам нужно для понимания этого кода, - это то, что числа в двоичной форме состоят из суммы степеней 2, когда вам нужно вычислить 2 ^ num, тогда это можно переписать так:

• 2^(b(-n)*2^(-n) + ... + b(+m)*2^(+m))

, где n - дробные биты, а m - целочисленные биты. умножение / деление на 2 в двоичной форме - это просто сдвиг битов, поэтому, если вы сложите все вместе, вы получите код для exp2, аналогичный моему. log2 основан на бинарном поиске ... изменение битов результата с MSB на LSB до совпадения с искомым значением (очень похожий алгоритм для быстрого вычисления sqrt). надеюсь, это поможет прояснить ситуацию ...