有效地生成斯特恩的双原子序列

Question

斯特恩的双原子序列可以在这里详细阅读; 但是,为了我的目的,我现在将定义它.

---

斯特恩双原子序列的定义

我们n是一个数字,生成fusc出的功能.表示fusc(n).

如果n为0,则返回值为0.
如果n为1,则返回值为1.

如果n是,则返回值为fusc(n / 2).
如果n是奇数,则返回值为fusc((n - 1) / 2) + fusc((n + 1) / 2).

---

目前,我的Python代码暴力强制通过大部分代,除了除以两部分,因为它总是不会产生任何变化.

def fusc (n):
    if n <= 1:
        return n

    while n > 2 and n % 2 == 0:
        n /= 2

    return fusc((n - 1) / 2) + fusc((n + 1) / 2)

但是,我的代码必须能够处理数量级的数字 1000 数百万比特,并递归地运行该函数 数千 数百万次似乎没有效率或实用性.

有没有什么方法可以通过算法改进我的代码,以便可以传递大量数字而无需递归调用函数这么多次？

Answer 1

通过百万位的记忆,递归堆栈将非常大.我们可以先尝试查看一个足够大的数字,我们可以手工完成,fusc(71)在这种情况下:

fusc(71)= fusc(35)+ fusc(36)

fusc(35)= fusc(17)+ fusc(18)
fusc(36)= fusc(18)

fusc(71)= 1*fusc(17)+ 2*fusc(18)

fusc(17)= fusc(8)+ fusc(9)
fusc(18)= fusc(9)

fusc(71)= 1*fusc(8)+ 3*fusc(9)

fusc(8)= fusc(4)
fusc(9)= fusc(4)+ fusc(5)

fusc(71)= 4*fusc(4)+ 3*fusc(5)

fusc(4)= fusc(2)
fusc(3)= fusc(1)+ fusc(2)

fusc(71)= 7*fusc(2)+ 3*fusc(3)

fusc(2)= fusc(1)
fusc(3)= fusc(1)+ fusc(2)

fusc(71)= 11*fusc(1)+ 3*fusc(2)

fusc(2)= fusc(1)

fusc(71)= 14*fusc(1)= 14

我们意识到在这种情况下我们可以完全避免递归,因为我们总是可以fusc(n)在表单中表达a * fusc(m) + b * fusc(m+1)同时将m的值减小为0.从上面的示例中,您可以找到以下模式:

如果m是奇数:
a * fusc(m) + b * fusc(m+1)= a * fusc((m-1)/2) + (b+a) * fusc((m+1)/2)
如果m是偶数:
a * fusc(m) + b * fusc(m+1)=(a+b) * fusc(m/2) + b * fusc((m/2)+1)

因此,您可以使用简单的循环函数来解决O(lg(n))时间内的问题

def fusc(n):
  if n == 0: return 0
  a = 1
  b = 0
  while n > 0:
    if n%2:
      b = b + a
      n = (n-1)/2
    else:
      a = a + b
      n = n/2
  return b