Как написать цикл, вычисляющий мощность?

base *= base;

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

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

Это не сработает для более высоких степеней, таких как шесть, поскольку вы выполняете итерацию 6 - 2 раз и x6 != (((x2)2)2)2. Последнее значение фактически эквивалентно x16.

Кстати (несмотря на ваше утверждение), на самом деле это не гарантированно работает при степени двойки. Если вы следуете коду в этом случае, вы увидите, что 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-y = 1/xy);
• неопределенный случай 00; и
• переполнение, если у вас нет значений произвольной точности (в основном, если (x * y) / y != x, вы можете быть достаточно уверены в том, что произошло переполнение). Обратите внимание на использование «не близко к», неразумно проверять точное равенство с плавающей запятой из-за возможности ошибок из-за ограничений точности - гораздо лучше реализовать проверку «достаточно близко к» некоторого описания.

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

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

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

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

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

Вместо этого вы хотите, чтобы база оставалась прежней, и умножьте конечный результат на исходную базовую «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;
}

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

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 может очень легко переполниться. Вам необходимо выполнить базовую проверку, чтобы предотвратить целочисленное переполнение и неопределенное поведение.

Минимальная проверка (см .: Поймать и вычислить переполнение во время умножения двух больших целых чисел), можно объединить следующим образом. Здесь вы должны использовать более широкий тип для временного расчета, а затем сравнить результаты с 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 в комментарии, ноль в степени нуля может быть неопределенным, поскольку есть нет согласованной стоимости. Вы можете добавить тест и в этом случае выдать предупреждение / ошибку, если хотите.

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

• 3^1 = 3
• 3^2 = 3*3 = 9
• 3^4 = 3^2 * 3^2 = 81
• 3^8 = 3^4 * 3^4 = 6,561

Затем вы можете использовать эти результаты для вычисления 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 не указывал, что должно происходить при переполнении или отрицательных показателях, этот код не пытается обработать ни один из этих случаев. Разумные методы решения этих проблем можно найти в других ответах.