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

Ответ 1

Отрицательные силы не являются проблемой, они просто обратные (1/x) положительной мощности.

Силы с плавающей запятой немного сложнее; как вы знаете, дробная мощность эквивалентна корню (например, x^(1/2) == sqrt(x)), и вы также знаете, что множители с той же базой эквивалентны, чтобы добавить их показатели.

Со всем вышесказанным вы можете:

• Разложить экспонента в целочисленной части и рациональную часть.
• Вычислить целочисленную мощность с помощью цикла (вы можете оптимизировать его разложение в коэффициентах и ​​повторное использование частичных вычислений).
• Вычислить корень с любым алгоритмом, который вам нравится (любое итеративное приближение, такое как bisection или метод Ньютона, может работать).
• Умножьте результат.
• Если показатель экспоненты отрицательный, примените инверсию.

Пример:

2^(-3.5) = (2^3 * 2^(1/2)))^-1 = 1 / (2*2*2 * sqrt(2))

Ответ 2

A ^B= Log ^-1 (Log (A) * B)

Изменить: да, это определение действительно обеспечивает что-то полезное. Например, на x86 он почти сразу преобразуется в FYL2X (Y * Log ₂ (X)) и F2XM1 (2 ^x -1):

fyl2x
fld st(0)
frndint
fsubr st(1),st
fxch st(1)
fchs
f2xmi
fld1
faddp st(1),st
fscale
fstp st(1) 

Код заканчивается немного дольше, чем вы могли ожидать, прежде всего потому, что F2XM1 работает только с числами в диапазоне -1.0..1.0. Часть fld st(0)/frndint/fsubr st(1),st вычитает целочисленную часть, поэтому мы остаемся только с долей. Мы применяем к нему F2XM1, добавляем 1 назад, затем используем FSCALE для обработки целой части экспоненциальности.

Ответ 3

Как правило, реализация функции pow(double, double) в математических библиотеках основана на идентификаторе:

pow(x,y) = pow(a, y * log_a(x))

Используя это тождество, вам нужно только знать, как поднять один номер a к произвольному экспоненте и как взять логарифмическую базу a. Вы эффективно превратили сложную функцию с несколькими переменными в две функции одной переменной и умножение, которое довольно легко реализовать. Наиболее часто выбираемыми значениями a являются e или 2 - e, потому что e^x и log_e(1+x) имеют некоторые очень хорошие математические свойства и 2, потому что у него есть некоторые хорошие свойства для реализации в арифметике с плавающей запятой.

Уловкой этого способа является то, что (если вы хотите получить полную точность) вам нужно вычислить термин log_a(x) (и его продукт с y) с большей точностью, чем представление с плавающей запятой x и y. Например, если x и y являются двойными, и вы хотите получить результат высокой точности, вам нужно будет каким-то образом сохранить промежуточные результаты (и сделать арифметику) в формате более высокой точности. Формат Intel x87 - это общий выбор, а также 64-битные целые числа (хотя, если вы действительно хотите реализовать высококачественную реализацию, вам нужно будет сделать несколько 96-битных целочисленных вычислений, которые немного болезненны в некоторых языки). С этим гораздо легче справиться, если вы реализуете powf(float,float), потому что тогда вы можете просто использовать double для промежуточных вычислений. Я бы рекомендовал начать с этого, если вы хотите использовать этот подход.

Алгоритм, который я изложил, не является единственным возможным способом вычисления pow. Это просто самое подходящее для доставки высокоскоростного результата, который удовлетворяет фиксированной априорной точности. Он менее подходит в некоторых других контекстах и, безусловно, намного сложнее реализовать, чем алгоритм повторного квадрата [root] -ing, предложенный некоторыми другими.

Если вы хотите попробовать алгоритм повторного квадрата [корень], начните с записи целочисленной функции с целым числом без знака, которая использует только повторное квадратирование. После того, как вы хорошо поймете алгоритм для этого уменьшенного случая, вы найдете довольно простой способ расширить его для обработки дробных показателей.

Ответ 4

Существует два разных случая: целые показатели и дробные показатели.

Для целых показателей вы можете использовать возведение в степень по квадрату.

def pow(base, exponent):
    if exponent == 0:
        return 1
    elif exponent < 0:
        return 1 / pow(base, -exponent)
    elif exponent % 2 == 0:
        half_pow = pow(base, exponent // 2)
        return half_pow * half_pow
    else:
        return base * pow(base, exponent - 1)

Второй "elif" - это то, что отличает это от наивной функции pow. Это позволяет функции делать O (log n) рекурсивные вызовы вместо O (n).

Для дробных показателей вы можете использовать тождество a ^ b = C ^ (b * log_C (a)). Удобно брать C = 2, поэтому a ^ b = 2 ^ (b * log2 (a)). Это сводит задачу к написанию функций для 2 ^ x и log2 (x).

Причина, по которой удобно принимать C = 2, состоит в том, что числа с плавающей запятой хранятся в плавающей запятой base-2. log2 (a * 2 ^ b) = log2 (a) + b. Это упрощает запись вашей функции log2: вам не нужно быть точным для каждого положительного числа, только на интервале [1, 2]. Аналогично, для вычисления 2 ^ х можно умножить 2 ^ (целая часть х) * 2 ^ (дробная часть х). Первая часть тривиальна для хранения в числе с плавающей запятой, для второй части вам просто нужна функция 2 ^ x по интервалу [0, 1).

Трудная часть находит хорошее приближение 2 ^ x и log2 (x). Простым подходом является использование серии Тейлора.

Ответ 5

По определению:

a ^ b = exp (b ln (a))

где exp(x) = 1 + x + x^2/2 + x^3/3! + x^4/4! + x^5/5! + ...

где n! = 1 * 2 * ... * n.

На практике вы можете сохранить массив из первых 10 значений 1/n!, а затем приблизиться к

exp(x) = 1 + x + x^2/2 + x^3/3! + ... + x^10/10!

потому что 10! это огромное количество, так что 1/10! очень мала (2.7557319224⋅10 ^ -7).

Ответ 6

Функции Wolfram дает широкий спектр формул для вычисления мощности. Некоторые из них были бы очень простыми для реализации.

Ответ 7

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

Ответ 8

Используя три реализованные пользователем функции iPow(x, n), Ln(x) и Exp(x), я могу вычислить fPow(x, a), x и a удваивает. Ни одна из функций ниже не использует библиотечные функции, а просто итерацию.

Некоторое объяснение о реализованных функциях:

(1) iPow(x, n): x is double, n - int. Это простая итерация, так как n - целое число.

(2) Ln(x): Эта функция использует итерацию серии Тейлора. Ряд, используемый в итерации, равен Σ (from int i = 0 to n) {(1 / (2 * i + 1)) * ((x - 1) / (x + 1)) ^ (2 * n + 1)}. Символ ^ обозначает силовую функцию Pow(x, n), реализованную в первой функции, которая использует простую итерацию.

(3) Exp(x): Эта функция снова использует итерацию серии Тейлора. Ряд, используемый в итерации, равен Σ (from int i = 0 to n) {x^i / i!}. Здесь ^ обозначает силовую функцию, но она не вычисляется путем вызова функции 1 Pow(x, n); вместо этого он реализуется в рамках третьей функции, одновременно с факториалом, используя d *= x / i. Я чувствовал, что мне пришлось использовать этот трюк, потому что в этой функции итерация занимает несколько шагов по сравнению с другими функциями, а факториал (i!) переполняется большую часть времени. Чтобы убедиться, что итерация не переполнена, функция мощности в этой части повторяется одновременно с факториалом. Таким образом, я преодолел переполнение.

(4) fPow(x, a): x и a оба удваиваются. Эта функция ничего не делает, а просто вызывает другие три функции, реализованные выше. Основная идея этой функции зависит от некоторого исчисления: fPow(x, a) = Exp(a * Ln(x)). И теперь у меня есть все функции iPow, Ln и Exp с уже итерацией.

n.b. Я использовал constant MAX_DELTA_DOUBLE, чтобы решить, на каком этапе остановить итерацию. Я установил его в 1.0E-15, что кажется разумным для парных. Итак, итерация останавливается, если (delta < MAX_DELTA_DOUBLE) Если вам нужна более высокая точность, вы можете использовать long double и уменьшить значение константы для MAX_DELTA_DOUBLE, 1.0E-18 например (1.0E-18 будет минимальным).

Вот код, который работает для меня.

#define MAX_DELTA_DOUBLE 1.0E-15
#define EULERS_NUMBER 2.718281828459045

double MathAbs_Double (double x) {
    return ((x >= 0) ? x : -x);
}

int MathAbs_Int (int x) {
    return ((x >= 0) ? x : -x);
}

double MathPow_Double_Int(double x, int n) {
    double ret;
    if ((x == 1.0) || (n == 1)) {
        ret = x;
    } else if (n < 0) {
        ret = 1.0 / MathPow_Double_Int(x, -n);
    } else {
        ret = 1.0;
        while (n--) {
            ret *= x;
        }
    }
    return (ret);
}

double MathLn_Double(double x) {
    double ret = 0.0, d;
    if (x > 0) {
        int n = 0;
        do {
            int a = 2 * n + 1;
            d = (1.0 / a) * MathPow_Double_Int((x - 1) / (x + 1), a);
            ret += d;
            n++;
        } while (MathAbs_Double(d) > MAX_DELTA_DOUBLE);
    } else {
        printf("\nerror: x < 0 in ln(x)\n");
        exit(-1);
    }
    return (ret * 2);
}

double MathExp_Double(double x) {
    double ret;
    if (x == 1.0) {
        ret = EULERS_NUMBER;
    } else if (x < 0) {
        ret = 1.0 / MathExp_Double(-x);
    } else {
        int n = 2;
        double d;
        ret = 1.0 + x;
        do {
            d = x;
            for (int i = 2; i <= n; i++) {
                d *= x / i;
            }
            ret += d;
            n++;
        } while (d > MAX_DELTA_DOUBLE);
    }
    return (ret);
}

double MathPow_Double_Double(double x, double a) {
    double ret;
    if ((x == 1.0) || (a == 1.0)) {
        ret = x;
    } else if (a < 0) {
        ret = 1.0 / MathPow_Double_Double(x, -a);
    } else {
        ret = MathExp_Double(a * MathLn_Double(x));
    }
    return (ret);
}

Ответ 9

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

• Используйте цикл.
• Используйте рекурсию (не лучше, но интереснее, тем не менее)
• Оптимизируйте свою рекурсию, используя разделение и завоевание Методы
• Использовать логарифмы

Ответ 10

Лучший алгоритм для эффективного вычисления положительных целых степеней многократно квадратично основывает, отслеживая дополнительные многократные множители. Вот пример решения на Python, которое должно быть относительно легко понятным и переведенным на ваш предпочтительный язык:

def power(base, exponent):
  remaining_multiplicand = 1
  result = base

  while exponent > 1:
    remainder = exponent % 2
    if remainder > 0:
      remaining_multiplicand = remaining_multiplicand * result
    exponent = (exponent - remainder) / 2
    result = result * result

  return result * remaining_multiplicand

Чтобы обработать отрицательные показатели, все, что вам нужно сделать, это вычислить положительную версию и делить 1 на результат, так что это должна быть простая модификация вышеуказанного кода. Дробные показатели значительно сложнее, так как это означает по существу вычисление n-го корня базы, где n = 1/abs(exponent % 1) и умножение результата на результат вычисления мощности целочисленной части:

power(base, exponent - (exponent % 1))

Вы можете рассчитать корни до желаемого уровня точности, используя метод Ньютона. Проверьте статью в википедии об алгоритме.

Ответ 11

Вы можете найти функцию pow следующим образом:

static double pows (double p_nombre, double p_puissance)
{
    double nombre   = p_nombre;
    double i=0;
    for(i=0; i < (p_puissance-1);i++){
          nombre = nombre * p_nombre;
       }
    return (nombre);
}

Вы можете найти функцию floor следующим образом:

static double floors(double p_nomber)
{
    double x =  p_nomber;
    long partent = (long) x; 

    if (x<0)
    {
        return (partent-1);
    }
    else
    {
        return (partent);
    }
}

С наилучшими пожеланиями

Ответ 12

Я использую фиксированную точку длинной арифметики, а моя 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). надеюсь, это поможет прояснить ситуацию...

Ответ 13

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

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

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

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

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

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

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