对于Collatz问题，可以通过缓存“尾部”来显著提高性能。这是一个时间和内存的权衡。看:记忆 (https://en.wikipedia.org/wiki/Memoization)。您还可以考虑其他时间/内存权衡的动态编程解决方案。

python实现示例:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))

评论:

但是，这段代码从未停止(因为整数溢出)!?!伊夫Daoust

对于许多数字，它不会溢出。

如果它会溢出——对于那些不幸的初始种子之一，溢出的数字很可能会收敛到1而不会再次溢出。

这仍然提出了一个有趣的问题，是否存在一些溢出循环的种子数?

任何简单的最终收敛级数都以2的幂值开始(够明显了吗?)

2^64会溢出到零，根据算法，这是一个未定义的无限循环(仅以1结束)，但由于shr rax产生ZF=1, answer中的最优解将结束。

能得到2^64吗?如果起始数是0x5555555555555555，它是奇数，那么下一个数是3n+1，它是0xFFFFFFFFFFFFFFFF +1 = 0。理论上算法处于未定义状态，但johnfound的优化答案在ZF=1时退出即可恢复。cmp rax, Peter Cordes的1将在无限循环中结束(QED变体1，“cheapo”通过未定义的0数)。

How about some more complex number, which will create cycle without 0? Frankly, I'm not sure, my Math theory is too hazy to get any serious idea, how to deal with it in serious way. But intuitively I would say the series will converge to 1 for every number : 0 < number, as the 3n+1 formula will slowly turn every non-2 prime factor of original number (or intermediate) into some power of 2, sooner or later. So we don't need to worry about infinite loop for original series, only overflow can hamper us.

我只是把一些数字写在表格里，然后看了看8位截断的数字。

有三个值溢出到0:227、170和85(85直接到0，其他两个递增到85)。

但是创建循环溢出种子没有任何价值。

有趣的是，我做了一个检查，这是第一个遭受8位截断的数字，已经有27个受到影响!在正确的非截断序列中，它确实达到了值9232(第一个截断值在第12步中是322)，在非截断的方式中，2-255输入数字中的任何一个达到的最大值是13120(对于255本身)，收敛到1的最大步数大约是128(+-2，不确定“1”是否算数，等等……)

有趣的是(对我来说)数字9232是许多其他源数字的最大值，它有什么特别之处?:-O 9232 = 0x2410…嗯. .不知道。

不幸的是，我无法深入了解这个系列，为什么它会收敛，截断它们到k位的含义是什么，但随着cmp数，1终止条件，当然可以将算法放入无限循环，特定的输入值在截断后以0结束。

但是对于8位的情况，值27溢出有点警告，这看起来像如果你计算到达值1的步数，你会得到错误的结果，对于整个k位整数集的大多数数字。对于8位整数，256个数字中的146个数字通过截断影响了序列(其中一些可能仍然意外地命中了正确的步数，我太懒了，没有检查)。

声称c++编译器可以产生比合格的汇编语言程序员更优的代码是一个非常严重的错误。尤其是在这种情况下。人类总是能比编译器编写出更好的代码，这种特殊情况很好地说明了这一点。

您看到的时间差异是因为问题中的汇编代码在内部循环中远远不是最优的。

(下面的代码是32位的，但可以很容易地转换为64位)

例如，序列函数可以优化到只有5条指令:

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

整个代码看起来像这样:

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

为了编译这段代码，需要使用FreshLib。

在我的测试中，(1 GHz AMD A4-1200处理器)，上面的代码大约比问题中的c++代码快四倍(当用-O0编译时:430毫秒vs. 1900毫秒)，当用-O3编译时，快两倍多(430毫秒vs. 830毫秒)。

两个程序的输出是相同的:在i = 837799上，max sequence = 525。

在一个相当不相关的注意:更多的性能hack !

[the first «conjecture» has been finally debunked by @ShreevatsaR; removed] When traversing the sequence, we can only get 3 possible cases in the 2-neighborhood of the current element N (shown first): [even] [odd] [odd] [even] [even] [even] To leap past these 2 elements means to compute (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1 and N >> 2, respectively. Let`s prove that for both cases (1) and (2) it is possible to use the first formula, (N >> 1) + N + 1. Case (1) is obvious. Case (2) implies (N & 1) == 1, so if we assume (without loss of generality) that N is 2-bit long and its bits are ba from most- to least-significant, then a = 1, and the following holds: (N << 1) + N + 1: (N >> 1) + N + 1: b10 b1 b1 b + 1 + 1 ---- --- bBb0 bBb where B = !b. Right-shifting the first result gives us exactly what we want. Q.E.D.: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1. As proven, we can traverse the sequence 2 elements at a time, using a single ternary operation. Another 2× time reduction.

得到的算法如下所示:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

这里我们比较n > 2，因为如果序列的总长度是奇数，则过程可能停止在2而不是1。

(编辑:)

让我们把它翻译成汇编!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

使用以下命令编译:

nasm -f elf64 file.asm
ld -o file file.o

请看C和由Peter Cordes在Godbolt上编写的asm的改进/bug修复版本。(编者注:抱歉把我的东西放在你的答案中，但我的答案达到了Godbolt链接+文本的30k字符限制!)

答案很简单:

做一个MOV RBX, 3和MUL RBX是昂贵的;只要加上RBX, RBX两次 add1在这里可能比INC更快 MOV 2和DIV非常昂贵;向右平移 64位代码通常明显比32位代码慢，对齐问题更复杂;对于这样的小程序，你必须打包它们，这样你才能进行并行计算，从而有可能比32位代码更快

如果为c++程序生成程序集列表，可以看到它与程序集的区别。

对于Collatz问题，可以通过缓存“尾部”来显著提高性能。这是一个时间和内存的权衡。看:记忆 (https://en.wikipedia.org/wiki/Memoization)。您还可以考虑其他时间/内存权衡的动态编程解决方案。

python实现示例:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))