28

私のコンプで3000を達成するには約1分かかりますが、シリーズの100万番目の数字を知る必要があります。定義は再帰的であるため、百万番目の数より前のすべてを計算する以外のショートカットは表示されません。シリーズの百万番目の数をすばやく計算するにはどうすればよいですか？

シリーズ定義

n_{i+1} = \floor{ 3/2 * n_{i} }およびn_{0}=2。

興味深いことに、グーグルによると、1つのサイトだけがシリーズをリストしています：これは。

遅すぎるBashコード

#!/bin/bash

function series 
{
        n=$( echo "3/2*$n" | bc -l | tr '\n' ' ' | sed -e 's@\\@@g' -e 's@ @@g' );
                                        # bc gives \ at very large numbers, sed-tr for it
        n=$( echo $n/1 | bc )           #DUMMY FLOOR func
}

n=2
nth=1

while [ true ]; #$nth -lt 500 ];
do
        series $n                        # n gets new value in the function through global value
        echo $nth $n
        nth=$( echo $nth + 1 | bc )     #n++
done
4

12 に答える 12

20

これは、問題を 2 進数で考えると簡単に解決できます。Floor(3/2*i) は基本的に右にシフトし、切り捨てて加算します。擬似コード:

0b_n[0]   = 10              // the start is 2
0b_n[1]   = 10 + 1(0) = 11  // shift right, chop one bit off and add 
0b_n[i+1] = 0b_n[i] + Truncate(ShiftRight(0b_n[i]))

これは、どのような形でも実装するのに非常に高速です。

Mathematica でこれを実装したところですが、BitShiftRight 操作もユニット位置を過ぎたビットを切り取っているように見えるので、自動的に処理されます。これがワンライナーです：

In[1] := Timing[num = Nest[(BitShiftRight[#] + #) &, 2, 999999];]
Out[2] = {16.6022, Null}

16 秒、数値は問題なく出力されますが、かなり長いです。

In[2] := IntegerLength[num]
Out[2] = 176092

In[3] := num
Out[3] = 1963756...123087

完全な結果はこちら.

于 2010-05-15T19:24:25.577 に答える
13

あなたはほとんどそれを見つけました。次回は、整数級数のオンライン百科事典をチェックしてください。

エントリは次のとおりです: http://oeis.org/A061418

     FORMULA    

a(n) = ceiling[K*(3/2)^n] where K=1.08151366859...

The constant K is 2/3*K(3) (see A083286). - Ralf Stephan, May 29, 2003

それは言った：

>>> def f(n):
...     K = 1.08151366859
...     return int(ceil(K*(1.5)**n))

健全性テスト:

>>> for x in range(1, 10):
...     print f(x)
...     
2
3
4
6
9
13
19
28
42

素晴らしい！では、1000000 はどうでしょうか。

>>> f(1000000)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 3, in f
OverflowError: (34, 'Result too large')

さて、私は試しました。:]しかし、あなたはその考えを理解します。

もう一度編集:解決策が見つかりました! TimoまたはLasse V. Karlsenの回答を参照してください。

編集：ティモのビットシフトのアイデアを使用：

import gmpy
n=gmpy.mpz(2)
for _ in xrange(10**6-1):
    n+=n>>1
print(n)

収量

1963756763...226123087 (176092 桁)

% time test.py > test.out

real    0m21.735s
user    0m21.709s
sys 0m0.024s
于 2010-05-15T15:24:02.697 に答える
11

スクリプトが非常に遅い理由は、ループで1 回と1bc回、3 回生成されるためです。trsed

全体を に書き直して、最後にbcを実行しsedます。私のテストでは、bc-only バージョンが 600 倍以上高速であることが示されています。古い遅いシステムでは、バージョンが 100,000 番目の値を見つけるのに 16 分弱かかりましたbc(最後の値のみを表示します)。

また、「フロア」関数は実際には「int」であることに注意してください。

#!/usr/bin/bc -lq
define int(n) {
    auto oscale
    oscale = scale
    scale = 0
    n = n/1
    scale = oscale
    return n
}

define series(n) {
    return int(3/2*n)
}

n = 2
end = 1000
for (count = 1; count < end; count++ ) {
    n = series(n)
}
print count, "\t", n, "\n"
quit

printは拡張機能であり、一部のバージョンには含まれていない可能性があることに注意してくださいbc。その場合は、変数を単独で参照するだけで、その値が出力されます。

chmod +x series.bcこれで、次のようにして呼び出すことができます。

./series.bc | tr -d '\n' | sed 's.\\..g'
于 2010-05-15T18:06:13.050 に答える
6

次の Java プログラムを使用しました。

import java.math.*;

public class Series {
    public static void main(String[] args) {
        BigInteger num = BigInteger.valueOf(2);
        final int N = 1000000;

        long t = System.currentTimeMillis();
        for (int i = 1; i < N; i++) {
            num = num.shiftLeft(1).add(num).shiftRight(1);
        }
        System.out.println(System.currentTimeMillis() - t);
        System.out.println(num);
    }
}

トリミングされた出力：（ペーストビンの完全な出力）

516380 (milliseconds)
196375676351034182442....29226123087

したがって、私の控えめなマシンで約 8.5 分かかりました。を使用-Xmx128Mしましたが、それが本当に必要かどうかはわかりません。

おそらくもっと良いアルゴリズムがあるでしょうが、単純な実装の作成とプログラムの実行を含めて、合計 10 分かかりました。

サンプルラン

于 2010-05-15T15:51:26.500 に答える
5

これは、私の 10 年前のラップトップで実行に約 220 秒かかる Python バージョンです。

import math;
import timeit;

def code():
  n = 2
  nth = 1

  while nth < 1000000:
    n = (n * 3) >> 1
    nth = nth + 1

  print(n);

t = timeit.Timer(setup="from __main__ import code", stmt="code()");
print(t.timeit(1));

この回答がペーストビンにあるのと同じ結果が生成されます（つまり、すべてではなく、開始と終了を確認しました。）

于 2010-05-15T19:17:04.223 に答える
3

Hmm, bash is not what I'd be using for high speed numerical processing. Get yourself a copy of GMP and put together a C program to do it.

There may well be a mathematical formula to give it to you quickly but, in the time it takes you to figure it out, GMP could probably throw you the result :-)

于 2010-05-15T15:19:17.570 に答える
2

パリで行うのはとても簡単です：

n=2;for(k=1,10^6,n+=n>>1)

これは私のマシンでは14秒かかります。もちろん、もっと速い方法があります-GMPが思い浮かびます-しかし、なぜわざわざするのですか？ランタイムを10秒以上短縮することはできず、開発時間は数分程度になります。:)

マイナーポイント：元の定式化では、百万番目の項n 999999が必要か、n 1000000、インデックスが100万の数かはあいまいです。前者はすでに上で計算されているので、後者を示します。

于 2010-05-20T04:57:54.870 に答える
2

たとえば、Scheme などのより適切な言語を使用することで、おそらくもう少し近づくことができます。

(define (series n) (if (= n 0) 2
                       (quotient (* 3 (series (- n 1))) 2)))

(series 100000)これにより、私のマシンでは約 8 秒で17610 桁が計算されます。残念なことに、(series 1000000)非常に新しい/高速なマシンでさえ、1 分で完了することを期待するには、まだ時間がかかりすぎます。

big-integer ライブラリ (この場合は NTL) を使用して C++ に切り替える:

#include <NTL/zz.h>
#include <fstream>
#include <time.h>
#include <iostream>

int main(int argc, char **argv) {
    NTL::ZZ sum;

    clock_t start = clock();
    for (int i=0; i<1000000; i++) 
        sum = (sum*3)/2;
    clock_t finish = clock();
    std::cout << "computation took: " << double(finish-start)/CLOCKS_PER_SEC << " seconds.\n";

    std::ofstream out("series_out.txt");
    out << sum;

    return 0;
}

これは、私のマシンで 4 分 35 秒で 1000000 の系列を計算します。これは、非常に高速な新しいマシンが少なくとも 1 分で終了に近づく可能性があるとほぼ信じられるほどの速さです(はい、乗算/除算の代わりにシフトを使用したときに何が起こるかを確認しましたが、それは遅くなりました)。

残念ながら、他の人が提案した閉形式の計算はほとんど役に立たないようです。これを使用するには、定数 K を十分な精度で計算する必要があります。K の閉じた形式の計算は見られないので、これは実際には反復を K の計算に移すだけであり、十分な精度で K を計算することは、元の級数を計算するよりも少し (もしあれば) 高速であるように見えます。

于 2010-05-15T19:07:20.037 に答える
2

A061418これは、サイト内のシーケンスとして識別されsequencesます (別名「整数シーケンスのオンライン百科事典」)。関連ページごとに、

FORMULA a(n) =A061419(n)+1 = ceiling[K*(3/2)^n]where K=1.08151366859... 定数 K は 2/3*K(3)(A083286 を参照)。

適切な高精度ライブラリ (既に提案されている GMP、または MPIR、そしておそらく Python 用の my baby gmpyのようなラッパー) を使用すると、閉じた形式の式を使用して、「シリーズ」など。

多くの場合、再帰的に指定された繰り返しを閉じた数式に入れることができます。このテーマの広範な初心者向け入門書としては、Concrete Mathematics (Graham、Knuth、および Patashnik 著) に勝るものはありません。

于 2010-05-15T15:28:42.437 に答える
1

これは、物事を台無しにする床を除いて、ほとんど一次再帰関係です。床が欲しくない場合は、

http://en.wikipedia.org/wiki/Recurrence_relation

また、bash は使用しないでください。

于 2010-05-15T15:24:34.107 に答える
0

私はTimoのアイデアをelispに変換しました。100で失敗し、負の数になります。失敗してください、BigNumsは表示されません！

(progn
  (let ((a 2)
        (dummy 0))
    (while (< dummy 100)
      (setq a (+ a (lsh a -1)))
      (setq dummy (1+ dummy)))
    (message "%d" a)))
-211190189 #WRONG evalution
于 2010-05-16T17:41:41.060 に答える
0

再帰的な定式化は、マシン スタックを維持する必要があるため、ほとんどの状況下で非常に長い時間がかかります。代わりに動的計画法を使用しないのはなぜですか?

すなわち（疑似コード）

bignum x = 2
for (int i = 1; i < 1000000; i++) {
    x = floor(3.0/2*x)
}

もちろん、意味のある結果を得るには、高精度の数値ライブラリが必要です。

于 2010-05-15T15:52:36.040 に答える