Как написать oop, который рассчитывает мощность? - PullRequest
Новая
       46

Как написать oop, который рассчитывает мощность?

0 голосов
/ 02 февраля 2020

Я пытаюсь написать al oop, который вычисляет мощность без использования функции pow (). Я застрял на том, как это сделать. Выполнение base *= base работает даже для способностей до 4, так что есть нечто совершенно странное, что я не могу понять. 

int Fast_Power(int base, int exp){
    int i = 2;
    int result;

    if(exp == 0){
        result = 1;
        }
    if(exp == 1){
        result = base;
        }
    else{
        for(i = 2; i < exp; i++){
            base *= base; 
            result = base;
        }
    }
    return result;
}

Ответы [ 4 ]

2 голосов
/ 02 февраля 2020 
base *= base;

Ваша проблема заключается в этом утверждении, вы не должны менять base вообще. Скорее, вы должны корректировать result на основе константного значения base.

Чтобы сделать полномочия, вам нужно повторить умножение, , но base *= base дает вам повторное квадрат от значения, и поэтому вы получите намного большее значение, чем нужно. Это на самом деле работает для степеней четырех, так как вы повторяете 4 - 2 раз, возводя в квадрат каждую итерацию, и x<sup>4</sup> == (x<sup>2</sup>)<sup>2</sup>.

Это будет не работать для более высоких степеней, как шесть, поскольку вы повторяете 6 - 2 раз и x<sup>6</sup> != (((x<sup>2</sup>)<sup>2</sup>)<sup>2</sup>)<sup>2</sup>. Это последнее значение на самом деле эквивалентно x<sup>16</sup>.

В качестве отступления (несмотря на ваше утверждение) на самом деле не гарантированно работает для двух степеней. Если вы будете следовать коду в этом случае, вы увидите, что result никогда не присваивается значение, поэтому возвращаемое значение будет произвольным. Если это работает для вас, это случайно и может в какой-то момент вас укусить.

Алгоритм, который вы можете использовать, должен выглядеть примерно так: 

float power(float base, int exponent):
    # 0^0 is undefined.

    if base == 0 and exponent == 0:
        throw bad_input

    # Handle negative exponents.

    if exponent < 0:
        return 1 / power(base, -exponent)

    # Repeated multiplication to get power.

    float result = 1
    while exponent > 0:
        # Use checks to detect overflow.

        float oldResult = result
        result *= base
        if result / base is not close to oldResult:
            throw overflow
        exponent -= 1

    return result

Этот алгоритм обрабатывает:

  • отрицательные целочисленные показатели (начиная с x<sup>-y</sup> = <sup>1</sup>/<sub>x<sup>y</sup></sub>);
  • неопределенный регистр 0<sup>0</sup>; и
  • переполнение, если у вас нет значений произвольной точности (в основном, если (x * y) / y != x, вы можете быть достаточно уверены, что произошло переполнение). Обратите внимание на использование «не близко к», неразумно проверять поплавки на точное равенство из-за вероятности ошибок из-за пределов точности - гораздо лучше реализовать проверку «достаточно близко к» некоторого описания.

Одна вещь, о которой следует помнить при переводе на C или C ++, реализация дополнения 2 вызовет проблемы при использовании наиболее отрицательного целого числа, так как его отрицание часто снова становится тем же значением из-за дисбаланса между положительные и отрицательные значения. Это может привести к бесконечной рекурсии.

Это можно исправить, просто обнаружив случай на раннем этапе (прежде всего), например: 

if INT_MIN == -INT_MAX - 1 and exp == INT_MIN:
    throw bad_input

Первая часть этого обнаруживает реализацию дополнения 2, а вторая обнаруживает (проблематично c) использование INT_MIN в качестве показателя степени.

1 голос
/ 02 февраля 2020

Прежде всего, я согласен, что, вероятно, было ошибкой использовать base *= base. Тем не менее, это не обязательно ошибка. Моим первым впечатлением было то, что ОП пытался вычислить силы так, как это мог бы сделать человек вручную. Например, если вы хотите вычислить 3 ^ 13, разумный способ начать - это вычислить показатели, которые имеют степени 2.

  • 3 ^ 1 = 3
  • 3 ^ 2 = 3 * 3 = 9
  • 3 ^ 4 = 3 ^ 2 * 3 ^ 2 = 81
  • 3 ^ 8 = 3 ^ 4 * 3 ^ 4 = 6561

Затем вы можете использовать эти результаты для вычисления 3 ^ 13 как

  • 3 ^ 13 = 3 ^ 1 * 3 ^ 4 * 3 ^ 8 = 1,594,323

Один раз Вы понимаете шаги, которые вы могли бы написать это. Сложнее всего, вероятно, определить, когда прекратить возводить в квадрат базу и какие квадраты следует включить в окончательный расчет. Возможно, на удивление (без знака) двоичное представление показателя говорит нам об этом! Это потому, что цифры в двоичном коде представляют степени двух, которые суммируются вместе, чтобы сформировать число. Имея это в виду, мы можем написать следующее: 

int Fast_Power(int base, int exp) {
    int result = 1;
    unsigned int expu = exp;
    unsigned int power_of_two = 1;
    while (expu > 0) {
        if (power_of_two & expu) {
            result *= base;
            expu ^= power_of_two;
        }
        power_of_two <<= 1;
        base *= base;
    }
    return result;
}

Этот код не имеет защиты от переполнения, хотя это было бы хорошей идеей. Придерживаясь исходного прототипа, он все еще принимает отрицательные показатели и возвращает целые числа, что является противоречием. Поскольку OP не указывает, что должно происходить при переполнении или отрицательных показателях, этот код не пытается обработать ни один из этих случаев. Разумные методы решения этих проблем даются в других ответах.

1 голос
/ 02 февраля 2020

Базовый c но наивный алгоритм, который вы ищете, который ужасно подвержен целочисленному переполнению: 

int Fast_Power (int base, int exp)
{
    int result = base;

    if (exp == 0)
        return result ? 1 : 0;

    for (int i = 1; i < exp; i++) {
        result *= base;
    }

    return result;
}

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

минимальная проверка (см .: Перехват и вычисление переполнения при умножении двух больших целых чисел ) можно включить следующим образом. Здесь вы должны использовать более широкий тип для временного расчета, а затем сравнить результаты с INT_MIN и INT_MAX (в заголовке limits.h), чтобы определить, произошло ли переполнение: 

#include <limits.h>
...
int Fast_Power (int base, int exp)
{
    int result = base;

    if (exp == 0)
        return result ? 1 : 0;

    for (int i = 1; i < exp; i++) {
        long long int tmp = (long long) result * base;  /* tmp of wider type */
        if (tmp < INT_MIN || INT_MAX < tmp) {           /* check for overflow */
            fputs ("error: overflow occurred.\n", stderr);
            return 0;
        }
        result = tmp;
    }

    return result;
}

Сейчас если вы попытаетесь, например, Fast_Power (2, 31);, будет сгенерирована ошибка и возвращено ноль.

Кроме того, как @paxdiablo отмечает в комментарии Ноль в степени нуля может быть неопределенным, так как нет согласованного по значению. Вы можете добавить тест и выдать предупреждение / ошибку в этом случае, если хотите.

1 голос
/ 02 февраля 2020

То, что вы делали неправильно, это base *= base каждый раз через l oop, который меняет саму базу, каждую итерацию.

Вместо этого вы хотите, чтобы база оставалась неизменной, и умножьте финальный результат. результат к этому оригинальному разу "exp". 

int Fast_Power(int base, int exp){
    int result=1;

    if(exp == 0){
        result = 1;
    }
    if(exp == 1){
        result = base;
    }
    else{
        for(int i = 0; i < exp; i++){
            result *= base;
        }
    }
    return result;
}
...