первые n цифр возведения в степень

Question

Как определить первые n цифр возведения в степень (a ^b ).

eg: for a = 12, b = 13 & n = 4, the first 4 digits are 1069.

Answer 1

Рассчитайте ^b с помощью следующих итераций:

a ₁ = a ¹ ,
a ₂ = a ² ,
...
a _i = a ⁱ ,
...
a _b = a ^b

У вас есть a _{i + 1} = a _i × a .Вычислять каждый a _i не совсем точно.Дело в том, что относительная ошибка a ^b меньше, чем n раз, относительная ошибка a .
Вы хотитеполучить окончательную относительную ошибку менее чем 10 ^-n .Таким образом, относительная ошибка на каждом шаге может составлять .Удалите последние цифры на каждом шаге.

Например, a = 2 , b = 16 , n = 1 .Конечная относительная погрешность составляет 10 ^-n = 0,1 .Относительная ошибка на каждом шаге составляет 0,1 / 16> 0,001 .Таким образом, 3 цифры важны на каждом шаге.Если n = 2, вы должны сохранить 4 цифры.Общее правило: сохранять [ n + log ₁₀ b ] цифр на каждом шаге.

2 (1), 4 (2), 8 (3), 16(4), 32 (5), 64 (6), 128 (7), 256 (8), 512 (9), 1024 (10) → 102,
204 (11), 408 (12), 816(13), 1632 (14) → 163, 326 (15), 652 (16).

Ответ: 6.

Этот алгоритм имеет округлость O (b).Но это легко изменить, чтобы получить O (log b)

Answer 2

Другое решение, использующее log10:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char **argv) {
       int a = 12;
       int b = 13;
       int n = 4;
       double x, y;

       x = b * log10(a);
       y = floor(pow(10, x - floor(x) + n - 1));
       printf("Result: %d\n", (int)y);

       return EXIT_SUCCESS;
}

Answer 3

n = 9 k = 3 n ^ n = 387420489, и ответ должен быть 387

. Это то же самое, что @RC, что сделано в его коде.Спасибо @RC, я только что показал математическое представление вашего кода.

Answer 4

Самый простой способ сделать это программно - использовать поток строк для преобразования результата возведения в строку и затем взять n самых значимых (то есть левых) символов.

если вы хотите путь без строк, то это будет работать:

#include <iostream>
#include <sstream>
#include <math.h>

using namespace std;

double nDigExp( double a, double b, int n )
{
    stringstream ss;
    ss.setf( ios::fixed, ios::floatfield );
    ss << pow(a,b);
    double ret;
    for ( int i = 0; i < n; ++i) ret = (10 * ret) + (ss.get() - '0'); // Yeuch!!
    return ret;
}

int main( )
{
    double result = nDigExp( 12, 13, 4 );

    cout << result << endl;

    return 0;
}

Но это едва ли не самый элегантный код. Я уверен, что вы можете улучшить его.

Answer 5

Для этого случая - с магическими числами на месте 12,13,4:

#include <sstream>
#include <iomanip>
#include <cmath>

double a = 12;
int b = 13;
double result = std::pow(a,b);

std::stringstream strVal;
strVal.setf( ios::fixed, ios::floatfield );
strVal << result;
std::string output(strVal.str().substr(0,4));

output = "1069"

std::stringstream intStr(output);
int intVal;
intStr >> intVal;

intVal = 1069

РЕДАКТИРОВАТЬ: Это должно работать для любой комбинации, где результат не переполняется double.