c++ - べき乗の最初の n 桁

Question

べき乗 (a ^b ) の最初の n 桁を特定する方法を教えてください。

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

Answer 1

次の反復によって^{a b}を計算します。

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

あなたはa _i+1 = a _i ×aを持っています。各a _iを正確に計算するわけではありません。問題は、 a ^bの相対誤差が a の相対誤差のn倍未満であるということです。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

この場合 - マジック ナンバー 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));

出力 = "1069"

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

整数値 = 1069

編集: これは、結果がオーバーフローしない任意の組み合わせで機能するはずdoubleです。

Answer 5

プログラムでこれを行う最も簡単な方法は、stringstream を使用して指数の結果を文字列に変換し、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;
}

しかし、それは最もエレガントなコードとは言えません。きっと改善できると思います。