この対数の不等式を効率的にどのように解いていますか？

Question

不等式は次のとおりです。nlogn < = a（nは自然数、ログは10を基準にしています）。質問：nの最大値はどのくらいですか？

私の解決策は、nlogn> aのポイントに達するまで、n = 1から無限に（ステップ1）スキャンすることです。返される結果はn-1

ですが、aが非常に大きいときに効率的ではないことがわかりました。誰もそれを解決する良いアイデアを持っていますか？

Answer 1

暴風雨対策のための代数を正しく行い、実装しました。私のマシンでは、ニュートンの方法は4分の1のバイナリサーチに勝っています。newton()をすべての非負の32ビット整数でテストしました。

#include <assert.h> 
#include <limits.h> 
#include <math.h> 
#include <stdio.h> 
#include <time.h> 

static int newton(double a) { 
    if (a < 2.0 * log10(2.0)) { 
     return 1; 
    } else if (a < 3.0 * log10(3.0)) { 
     return 2; 
    } 
    double a_log_10 = a * log(10); 
    double x = a/log10(a); 
    x = (x + a_log_10)/(1.0 + log(x)); 
    x = (x + a_log_10)/(1.0 + log(x)); 
    double n = floor(x); 
    if (n * log10(n) > a) { 
     n--; 
    } else if ((n + 1.0) * log10(n + 1.0) <= a) { 
     n++; 
    } 
    return n; 
} 

static int binarysearch(double a) { 
    double l = floor(a/log10(a)); 
    double u = floor(a) + 1.0; 
    while (1) { 
     double m = floor((l + u)/2.0); 
     if (m == l) break; 
     if (m * log10(m) > a) { 
      u = m; 
     } else { 
      l = m; 
     } 
    } 
    return l; 
} 

static void benchmark(const char *name, int (*solve)(double)) { 
    clock_t start = clock(); 
    for (int a = 1 << 22; a >= 10; a--) { 
     int n = solve(a); 
     assert(n * log10(n) <= a); 
     assert((n + 1) * log10(n + 1) > a); 
    } 
    printf("%s: %.2f\n", name, (clock() - start)/(double)CLOCKS_PER_SEC); 
} 

int main(int argc, char *argv[]) { 
    benchmark("newton", newton); 
    benchmark("binarysearch", binarysearch); 
} 

Answer 2

バイナリ検索で行います。開始間隔は、（1、a）または（sqrt（a）、a）です。

Answer 3

nlogn = aという方程式を解くと、比較を行うたびにその計算を行うことを避けることができます。等式はTranscendental equationなので、一定の時間反復で結果が得られますが、これはかなり良い近似値です。その後、データ上でBinary Searchを実行します。

procedure solve_transcendental 
    n = 50 
    for i = 1 .. 20 
     n = a/log(n) 
    end 
end 

Answer 4

バイナリ検索は信頼できる回答です。このような方程式を解くもう1つの方法は、x = f（x）として書き直し、f（x）、f（f（x））、f（f（f）））などを解くことです。結果が収束することを願っています。 | f '（x）| < 1. n log n = aをn = a/log nとして書き換えることは、実際には驚くほどうまくいくように見えます。