c # — алгоритм Grokkable для понимания возведения в степень, где показатель степени является плавающей точкой
Чтобы уточнить сначала:
- 2 ^ 3 = 8. Это эквивалентно 2 * 2 * 2. Легко.
- 2 ^ 4 = 16. Это эквивалентно 2 * 2 * 2 * 2. Тоже легко.
- 2 ^ 3.5 = 11.313708 … Э-э, это не так просто.
Хочу, я хочу, это простой алгоритм, который наиболее четко показывает, как 2 ^ 3,5 = 11,313708. Желательно не использовать какие-либо функции, кроме базовых операторов сложения, вычитания, умножения или деления.
Код, конечно, не обязательно должен быть быстрым и не обязательно должен быть коротким (хотя это поможет). Не беспокойся Можно быть приблизительными с заданной пользователем точностью (которая также должна быть частью алгоритма). Я надеюсь, что будет происходить бинарный поиск / поиск типа, так как это довольно просто уловить.
Пока я нашел этот, но главный ответ далеко не прост для понимания на концептуальном уровне.
Чем больше ответов, тем лучше, поэтому я могу попытаться понять различные способы решения проблемы.
Моим языковым предпочтением для ответа будет C # / C / C ++ / Java или псевдокод для меня.
Решение
Хорошо, давайте реализуем pow (x, y), используя только двоичный поиск, сложение и умножение.
Вождение y ниже 1
Во-первых, уберите это из пути:
pow(x, y) == pow(x*x, y/2)
pow(x, y) == 1/pow(x, -y)
Это важно для обработки отрицательных показателей и y ниже 1, где вещи начинают становиться интересными. Это сводит проблему к поиску pow(x, y) где 0<y<1,
В этом ответе я предполагаю, что вы знаете, как выполнить sqrt, я знаю sqrt(x) = x^(1/2), но это легко реализовать, просто используя бинарный поиск, чтобы найти y = sqrt(x) с помощью y*y=x функция поиска, например:
#define EPS 1e-8
double sqrt2(double x) {
double a = 0, b = x>1 ? x : 1;
while(abs(a-b) > EPS) {
double y = (a+b)/2;
if (y*y > x) b = y; else a = y;
}
return a;
}
Обоснование состоит в том, что каждое число ниже 1 может быть аппроксимировано как сумма долей 1/2^x:
0.875 = 1/2 + 1/4 + 1/8
0.333333... = 1/4 + 1/16 + 1/64 + 1/256 + ...
Если вы найдете эти дроби, вы действительно обнаружите, что:
x^0.875 = x^(1/2+1/4+1/8) = x^(1/2) * x^(1/4) * x^(1/8)
Это в конечном итоге приводит к
sqrt(x) * sqrt(sqrt(x)) * sqrt(sqrt(sqrt(x)))
#define EPS 1e-8
double pow2(double x, double y){
if (x < 0 and abs(round(y)-y) < EPS) {
return pow2(-x, y) * ((int)round(y)%2==1 ? -1 : 1);
} else if (y < 0) {
return 1/pow2(x, -y);
} else if(y > 1) {
return pow2(x * x, y / 2);
} else {
double fraction = 1;
double result = 1;
while(y > EPS) {
if (y >= fraction) {
y -= fraction;
result *= x;
}
fraction /= 2;
x = sqrt2(x);
}
return result;
}
}
Другие решения
Вы можете проверить что 2 ^ 3.5 = 11.313708 очень легко: проверьте, что 11.313708 ^ 2 = (2 ^ 3.5) ^ 2 = 2 ^ 7 = 128
Я думаю, что самый простой способ понять вычисления, которые вы на самом деле сделали бы для этого, это освежить ваше понимание логарифмов — одна отправная точка будет http://en.wikipedia.org/wiki/Logarithm#Exponentiation.
Если вы действительно хотите вычислить нецелочисленные степени с минимальной технологией, то один из способов сделать это — выразить их в виде дроби со знаменателем в степени два, а затем взять много квадратных корней. Например. х ^ 3,75 = х ^ 3 * х ^ (1/2) * х ^ (1/4), а затем х ^ (1/2) = sqrt (x), х ^ (1/4) = sqrt (sqrt (x) )) и так далее.
Вот еще один подход, основанный на идее проверки догадки. Учитывая y, вы хотите найти x такой, что x ^ (a / b) = y, где a и b — целые числа. Из этого уравнения следует, что x ^ a = y ^ b. Вы можете рассчитать y ^ b, так как вы знаете оба числа. Вы знаете a, так что вы можете — как вы изначально подозревали — использовать двоичную отбивку или, возможно, какой-то численно более эффективный алгоритм, чтобы найти x ^ a = y ^ b для x, просто угадав x, вычислив x ^ a для этого предположения, сравнив его с у ^ б, а затем итеративно улучшая предположение.
Пример: предположим, что мы хотим найти 2 ^ 0,878 этим методом. Затем установите a = 439, b = 500, поэтому мы хотим найти 2 ^ (439/500). Если мы установим x = 2 ^ (439/500), то получим x ^ 500 = 2 ^ 439, поэтому вычислим 2 ^ 439 и (с помощью бинарной отбивки или иным образом) найдем x таким, что x ^ 500 = 2 ^ 439.
Как указано в комментариях, неясно, хотите ли вы получить математическое описание работы дробных степеней или алгоритм для вычисления дробных степеней.
Я возьму на себя последнее.
Почти для всех функций (например, y = 2 ^ x) есть способ аппроксимации функции с использованием вещи под названием ряд Тейлора http://en.wikipedia.org/wiki/Taylor_series. Это аппроксимирует любую функцию с разумным поведением как полином, и полиномы могут быть вычислены с использованием только умножения, деления, сложения и вычитания (все это может делать ЦП напрямую). Если вы вычислите ряд Тейлора для y = 2 ^ x и включите x = 3.5, вы получите 11,313 …
Это почти наверняка не то, как возведение в степень фактически сделано на вашем компьютере. Есть много алгоритмов, которые работают быстрее для разных входов. Например, если вы вычислите 2 ^ 3.5, используя ряд Тейлора, то вам придется взглянуть на множество терминов, чтобы вычислить его с любой точностью. Однако ряд Тейлора будет сходиться гораздо быстрее при x = 0,5, чем при x = 3,5. Таким образом, одно очевидное улучшение состоит в том, чтобы вычислить 2 ^ 3.5 как 2 ^ 3 * 2 ^ 0.5, так как 2 ^ 3 легко вычислить напрямую. Современные алгоритмы возведения в степень будут использовать много-много хитростей для ускорения обработки, но принцип все тот же, аппроксимирует функцию возведения в степень как некоторую бесконечную сумму и вычисляет столько терминов, сколько необходимо для получения требуемой точности.
Большая часть этого сводится к возможности инвертировать силовые операции.
Другими словами, основная идея состоит в том, что (например) N2 должно быть в основном «противоположностью» N1/2 так что если вы делаете что-то вроде:
М = Н2
L = M1/2
Тогда результат, который вы получите в L, должен быть таким же, как исходное значение в N (игнорируя любое округление и тому подобное).
Математически это означает, что N1/2 такой же как sqrt(N), N1/3 кубический корень из N, и так далее.
Следующим шагом после этого будет что-то вроде N3/2. Это почти та же идея: знаменатель — это корень, а числитель — это степень, поэтому N3/2 квадратный корень куба N (или куб квадратного корня N — получается то же самое).
С десятичными числами мы просто выражаем дробь в немного другой форме, так что-то вроде N3,14 можно рассматривать как N314/100—сотый корень N возведен в степень 314.
Что касается того, как вы их вычисляете: есть довольно много разных способов, в значительной степени зависящих от компромисса, который вы предпочитаете между сложностью (область чипа, если вы реализуете ее аппаратно) и скоростью. Очевидный способ — использовать логарифм: В = Журнал-1(Вход (А) * В).
Для более ограниченного набора входных данных, таких как просто нахождение квадратного корня из N, вы часто можете добиться большего успеха, чем этот чрезвычайно общий метод. Например, двоичный метод сокращения довольно быстро — реализован в программном обеспечении, он все еще примерно такой же скорости, как инструкция Intel FSQRT.
Получив идеи из других отличных постов, я придумал собственную реализацию. Ответ основан на идее, что base^(exponent*accuracy) = answer^accuracy, Учитывая, что мы знаем base, exponent а также accuracy переменные заранее, мы можем выполнить поиск (бинарное измельчение или что-то еще), чтобы уравнение можно было сбалансировать, найдя answer, Мы хотим, чтобы показатель степени в обеих сторонах уравнения был целым числом (иначе мы вернемся к квадрату), поэтому мы можем сделать accuracy любой размер, который нам нравится, а затем округлите его до ближайшего целого числа.
Я дал два способа сделать это. Первый очень медленный и часто дает очень большие числа, которые не будут работать с большинством языков. С другой стороны, он не использует журнал, и концептуально проще.
public double powSimple(double a, double b)
{
int accuracy = 10;
bool negExponent = b < 0;
b = Math.Abs(b);
bool ansMoreThanA = (a>1 && b>1) || (a<1 && b<1); // Example 0.5^2=0.25 so answer is lower than A.
double accuracy2 = 1.0 + 1.0 / accuracy;
double total = a;
for (int i = 1; i < accuracy* b; i++) total = total*a;
double t = a;
while (true) {
double t2 = t;
for(int i = 1; i < accuracy; i++) t2 = t2 * t; // Not even a binary search. We just hunt forwards by a certain increment
if((ansMoreThanA && t2 > total) || (!ansMoreThanA && t2 < total)) break;
if (ansMoreThanA) t *= accuracy2; else t /= accuracy2;
}
if (negExponent) t = 1 / t;
return t;
}
Этот ниже немного более сложный, поскольку он использует log (). Но это намного быстрее и не страдает от проблем со сверхвысоким числом, как указано выше.
public double powSimple2(double a, double b)
{
int accuracy = 1000000;
bool negExponent= b<0;
b = Math.Abs(b);
double accuracy2 = 1.0 + 1.0 / accuracy;
bool ansMoreThanA = (a>1 && b>1) || (a<1 && b<1); // Example 0.5^2=0.25 so answer is lower than A.
double total = Math.Log(a) * accuracy * b;
double t = a;
while (true) {
double t2 = Math.Log(t) * accuracy;
if ((ansMoreThanA && t2 > total) || (!ansMoreThanA && t2 < total)) break;
if (ansMoreThanA) t *= accuracy2; else t /= accuracy2;
}
if (negExponent) t = 1 / t;
return t;
}