28

在我的比赛中达到 3000 大约需要一分钟，但我需要知道系列中的第 100 万个数字。该定义是递归的，因此除了计算第 100 万个数字之前的所有内容外，我看不到任何快捷方式。您如何快速计算系列中的第 10 万个数字？

系列定义

n_{i+1} = \floor{ 3/2 * n_{i} }和n_{0}=2。

有趣的是，只有一个网站根据谷歌列出了该系列：this one。

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

您可以通过以二进制形式考虑问题来轻松解决此问题。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的答案。

编辑：使用 Timo 的移位想法：

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

您的脚本如此缓慢的原因是它产生bc了三次，tr一次sed又一次循环。

重写整个事情bc并sed在最后做。我的测试表明bc-only 版本快了 600 倍以上。在旧的慢速系统上，该bc版本花了不到 16 分钟的时间找到第 100,000 个值（仅打印最后一个）。

另外，请注意您的“floor”函数实际上是“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);
    }
}

裁剪后的输出：（pastebin 上的完整输出）

516380 (milliseconds)
196375676351034182442....29226123087

所以在我的普通机器上花了大约 8.5 分钟。我用过-Xmx128M，但不确定是否真的有必要。

那里可能有更好的算法，但这总共花了 10 分钟，包括编写幼稚的实现和运行程序。

样品运行

于 2010-05-15T15:51:26.500 回答
5

这是一个 Python 版本，在我使用了 10 年的笔记本电脑上运行大约需要 220 秒：

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));

它产生的结果与此答案在 pastebin 上的结果相同（也就是说，我验证了它的开始和结束，而不是所有内容。）

于 2010-05-15T19:17:04.223 回答
3

嗯，bash这不是我用于高速数值处理的东西。给自己一份GMP的副本，然后编写一个 C 程序来完成它。

很可能有一个数学公式可以快速提供给您，但是在您弄清楚它的时间里，GMP 可能会为您提供结果:-)

于 2010-05-15T15:19:17.570 回答
2

这被识别为站点A061418中的序列sequences（AKA“整数序列在线百科全书”）；根据相关页面，

FORMULA a(n) =A061419(n)+1 = ceiling[K*(3/2)^n]where K=1.08151366859... 常数 K 是 2/3*K(3)（见 A083286）。

并且使用合适的高精度库（如前所述的 GMP，或 MPIR，也许还有一个像我的宝贝gmpy用于 Python 的包装器），您可以使用封闭式公式来更快地计算“第 100 万个项目”系列”之类的。

通常可以将递归指定的递归放入封闭的公式中。对于广泛的初学者对该主题的介绍，具体数学（格雷厄姆，克努斯和帕塔什尼克）真的很难被击败。

于 2010-05-15T15:28:42.437 回答
2

通过使用更合适的语言，您可能会更接近一点，例如，Scheme：

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

(series 100000)这会在我的机器上大约 8 秒内计算出 17610 个数字。不幸的是，(series 1000000)即使是更新/更快的机器也需要很长时间才能在一分钟内完成。

使用大整数库（在本例中为 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 的系列。这足够快，我几乎可以相信一台非常快的新机器至少可以在一分钟内完成（是的，我检查了当我使用轮班而不是乘法/除法时发生了什么——它更慢）。

不幸的是，其他人建议的封闭式计算似乎没有什么帮助。要使用它，您需要将常数 K 计算到足够的精度。我没有看到 K 的封闭式计算，所以这实际上只是将迭代转移到计算 K，而且看起来将 K 计算到足够的精度比计算原始系列快一点（如果有的话）。

于 2010-05-15T19:07:20.037 回答
2

在Pari很容易做到：

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

这在我的机器上需要 14 秒。当然，还有更快的方法——我想到了 GMP——但为什么要麻烦呢？您将无法将运行时间缩短超过 10 秒，并且开发时间大约为minutes。:)

次要点：原始公式中是否需要第百万项 n 999999或 n 1000000，索引为一百万的数字是模棱两可的；我给后者，因为我看到前者已经在上面计算过了。

于 2010-05-20T04:57:54.870 回答
1

这几乎是一阶递归关系，除了地板，它把事情搞砸了。如果你不想要地板，

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

另外，不要使用 bash。

于 2010-05-15T15:24:34.107 回答
0

在大多数情况下，递归公式将花费相当长的时间，因为它必须维护机器堆栈。为什么不使用动态规划呢？

即（伪代码）

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

当然，为了获得有意义的结果，您需要一个高精度数字库。

于 2010-05-15T15:52:36.040 回答
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 回答