c - 查找具有一定步数/计数的最小起始值的数字
问题描述
我正在研究一个 Collatz 猜想程序。我有一个遵循简单规则的序列:
如果当前任期是偶数:下一个任期是当前任期的一半。
如果当前项是奇数:下一项是当前项的 3 倍,加 1。
我们继续这样做,直到我们达到一个并计算使用的每个术语。
例如:对于数字 17,我们有:
17 52 26 13 40 20 10 5 16 8 4 2 1
因此,计数为 13。
我特别需要帮助的是我需要找到计数超过 1234 的最小起始值(数字)。
IE:
1 有计数 1
2 有计数 2
3 有数 8
4 有数 3
5 有数 6
6 有数 9
……
- 18 有数 21
……
97 有计数 119
ETC
这是我认为有效但需要很长时间才能处理的代码。我该如何优化它,以便它可以更快地找到计数?有人建议我进行二分搜索,但计数不是线性的,所以这不起作用..
#include <stdio.h>
int main (void) {
unsigned long long int num1 = 1;
while (num1 <= 99999999999999999) {
unsigned long long int num = num1;
int count = 1;
while (num != 1) {
if (num % 2 == 0) {
num = (num/2);
count++;
}
else {
num = ((num*3) + 1);
count++;
}
}
if (count > 1234) {
printf("%llu\n", num1);
break;
}
num1++;
}
return 0;
}
解决方案
产生超过 1234 步的 Collatz 序列的最小根是 133561134663。它达到最大值 319497287463520,这是一个 49 位的值。因此,可以使用许多 C 库uint64_t
提供的<stdint.h>
(通常是通过)来评估这个序列。<inttypes.h>
不幸的是,有许多序列开始较低,需要最多 71 位整数才能正确解析,例如从 110243094271 开始的 573 步序列。
最烦人的是,如果您使用 64 位无符号整数实现 Collatz 序列,而不检查溢出,您将计算这些序列的错误长度;但是因为它们恰好有无趣的长度,所以这个错误被掩盖了,你仍然可以找到上述解决方案!
从本质上讲,如果这是一个 C 练习,那么它是有问题的:即使是一个可怕的错误和有限的实现也可以找到正确的答案。
我碰巧在 64 位 Linux 上使用 GCC-5.4.0(在笔记本电脑上的 Core i5-7200U CPU 上运行),所以我可以将unsigned __int128
128 位无符号整数类型用于 Collatz 序列。我还有 16 GiB 的 RAM,其中我使用了大约 12 GiB,用于存储长达 130 亿 (13×10 9 ) 的序列长度,用于奇数索引。
每当您找到从某个奇数i开始的序列长度时,从 2 i开始的序列长度就会长一步(但其他方面相同)。事实上,有一个从 2 k i开始的序列正好长k步。如果您只是为某个最小长度的序列寻找最小的起始值,您可以忽略所有偶数起始点,直到k足够小(基本上包含您需要查看的起始值范围)。
仅考虑起始值会显着提高速度(20% 或更多),但我在这里画了我的“线”,而是检查每个起始值。
为了加快计算速度,我使用了 __builtin_ctz() GCC 内置(__builtin_ctzll()
用于 64-bit unsigned long long
)来查找连续最低有效零位的数量。这样我可以一次处理所有连续的“偶数”步骤,但正确计算步骤数。
我还将序列步进器分成两个并行的,一个处理状态适合 64 位变量的情况,另一个处理需要完整 128 位的情况。
在仅 64 位部分中,如果当前状态的序列长度是可缓存的,我会查找它。如果它不为零,我将它添加到我们已经完成的步骤数中,我得到了结果。否则,我将该缓存条目索引和从根开始的步骤数添加到一个小的更新缓存中。这样,当我得到结果时,我不需要重复这个序列,并且可以简单地在一个紧密的循环中应用更新。在乘以三和加一之前,我确实检查了该值是否溢出(6148914691236517205 溢出,到 2 64);如果是这样,我切换到 128 位部分,并在那里进行乘加。
在 128 位部分,我假设我们没有那么多内存(在艾字节范围内),所以我根本不需要担心缓存部分。在乘以三并加一之前(我使用curr128 += curr128 + curr128 + 1
),我确实检查了状态是否溢出,以确保。
在配备 Intel Core i5-7200U 的笔记本电脑上,使用单核,计算从 1 到 133561134663 的所有 Collatz 序列的长度大约需要 4253 秒的 CPU 时间(约一小时十分钟)。
下一个更长的序列从 158294678119 开始,长 1243 步;为了做到这一点,我的笔记本电脑消耗了一个半小时的 CPU 时间。
然而,为了达到这一点,代码已经变得不像 OP,而且非常可怕。特别是,为了混合 64 位/128 位循环,我不得不求助于goto
; 并且整个实现都充斥着 GCC 内置函数。我认为它几乎是只写代码;也就是说,如果我怀疑它的任何部分,我会从头开始重写它。当优化优先于可维护性和稳健性时,这是典型的最终结果。
无论如何,为了让其他人在 x86-64 上的 Linux 上使用 GCC 来验证上述内容,这里是可怕的代码collatz.c:
#define _POSIX_C_SOURCE 200809L
#define _GNU_SOURCE
#include <stdlib.h>
#include <unistd.h>
#include <inttypes.h>
#include <string.h>
#include <stdarg.h>
#include <stdio.h>
#include <errno.h>
#include <time.h>
#define MAX_SEQ_LEN 2000
#define OVER64 UINT64_C(6148914691236517205)
typedef unsigned __int128 u128;
typedef uint64_t u64;
static inline u64 u128_lo(const u128 u) { return (u64)u; }
static inline u64 u128_hi(const u128 u) { return (u64)(u >> 64); }
static inline u64 highest_bit_set_64(const u64 u)
{
if (sizeof u == sizeof (unsigned int))
return 63 - __builtin_clz(u);
else
if (sizeof u == sizeof (unsigned long))
return 63 - __builtin_clzl(u);
else
if (sizeof u == sizeof (unsigned long long))
return 63 - __builtin_clzll(u);
else
exit(EXIT_FAILURE);
}
static unsigned int highest_bit_set_128(u128 u)
{
u64 hi = u128_hi(u);
if (hi)
return 64 + highest_bit_set_64(hi);
else
return highest_bit_set_64(u128_lo(u));
}
static inline unsigned int ctz64(const u64 u)
{
if (sizeof u <= sizeof (unsigned int))
return __builtin_ctz(u);
else
if (sizeof u <= sizeof (unsigned long))
return __builtin_ctzl(u);
else
if (sizeof u <= sizeof (unsigned long long))
return __builtin_ctzll(u);
else
exit(EXIT_FAILURE);
}
static inline unsigned int ctz128(const u128 u)
{
if (sizeof u == sizeof (unsigned long long))
return __builtin_ctzll(u);
else {
const u64 lo = u128_lo(u);
if (lo)
return ctz64(u);
else
return 64 + ctz64(u128_hi(u));
}
}
static const char *s128(u128 u)
{
static char buffer[40];
char *p = buffer + sizeof buffer;
*(--p) = '\0';
do {
*(--p) = '0' + (u % 10);
u /= 10;
} while (u);
return p;
}
static struct timespec wall_started, wall_now;
static inline void wall_start(void)
{
clock_gettime(CLOCK_MONOTONIC, &wall_started);
}
static inline double wall_seconds(void)
{
clock_gettime(CLOCK_MONOTONIC, &wall_now);
return (double)(wall_now.tv_sec - wall_started.tv_sec)
+ (double)(wall_now.tv_nsec - wall_started.tv_nsec) / 1000000000.0;
}
static struct timespec cpu_elapsed;
static inline double cpu_seconds(void)
{
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &cpu_elapsed);
return (double)cpu_elapsed.tv_sec + (double)cpu_elapsed.tv_nsec / 1000000000.0;
}
static int out_and_err = 0;
static void print(const char *fmt, ...)
{
va_list args;
va_start(args, fmt);
vdprintf(STDOUT_FILENO, fmt, args);
va_end(args);
if (out_and_err) {
va_start(args, fmt);
vdprintf(STDERR_FILENO, fmt, args);
va_end(args);
}
}
static size_t cache_index[MAX_SEQ_LEN];
static unsigned int cache_depth[MAX_SEQ_LEN];
static u64 seq_max = 0; /* 2*seq_num */
static size_t seq_num = 0;
static uint16_t *seq_len = NULL;
static unsigned int tip_bits = 0;
static u128 tip_max = 0;
static inline unsigned int collatz_length(const u64 root, u128 *maxto)
{
u128 curr128, max128;
u64 curr64, max64, lo;
size_t cached = 0, i;
unsigned int steps = 1, n;
curr128 = max128 = root;
curr64 = max64 = root;
any64bit:
if (!(curr64 & 1)) {
n = ctz64(curr64);
curr64 >>= n;
steps += n;
}
if (curr64 >= OVER64) {
curr128 = curr64;
goto odd128bit;
}
odd64bit:
if (curr64 <= 1)
goto done;
if (curr64 < seq_max) {
i = curr64 >> 1;
if (seq_len[i]) {
steps += seq_len[i];
goto done;
}
cache_index[cached] = i;
cache_depth[cached] = steps;
cached++;
}
curr64 += curr64 + curr64 + 1;
steps++;
if (max64 < curr64)
max64 = curr64;
goto any64bit;
any128bit:
if (!(curr128 & 1)) {
n = ctz128(curr128);
curr128 >>= n;
steps += n;
if (!u128_hi(curr128)) {
lo = u128_lo(curr128);
if (lo <= 1)
goto done;
if (lo < OVER64) {
curr64 = lo;
goto odd64bit;
}
}
}
odd128bit:
if (u128_hi(curr128) >= OVER64) {
print("Overflow at root %" PRIu64 ".\n", root);
exit(EXIT_FAILURE);
}
curr128 += curr128 + curr128 + 1;
steps++;
if (max128 < curr128)
max128 = curr128;
goto any128bit;
done:
if (cached >= MAX_SEQ_LEN) {
print("Update cache overrun.\n");
exit(EXIT_FAILURE);
}
while (cached-->0)
seq_len[ cache_index[cached] ] = steps - cache_depth[cached];
if (max128 < (u128)max64)
max128 = max64;
if (maxto)
*maxto = max128;
if (tip_max <= max128) {
const unsigned int maxbits = highest_bit_set_128(max128) + 1;
tip_max = max128;
if (tip_bits <= maxbits) {
tip_bits = maxbits;
print("%" PRIu64 " length %u (reaches %s - %u bits).\n", root, steps, s128(max128), maxbits);
}
}
return steps;
}
int main(void)
{
unsigned int n, nmax = 0;
u128 m;
uint64_t i = 1;
wall_start();
/* If standard output is redirected to a file, print everything to standard error also. */
out_and_err = (isatty(STDERR_FILENO) && !isatty(STDOUT_FILENO));
/* Try allocating up to 16 GiB of cache. */
seq_num = (size_t)1024 * 1024 * 1024 * 16 / sizeof seq_len[0];
while (1) {
seq_len = malloc(seq_num * sizeof seq_len[0]);
if (seq_len)
break;
seq_num = ( seq_num * 7 ) / 8;
}
seq_max = 2 * (uint64_t)seq_num;
memset(seq_len,~0, seq_num * sizeof seq_len[0]);
memset(seq_len, 0, seq_num * sizeof seq_len[0]);
print("Allocated %zu entries (%.3f GiB)\n", seq_num, (double)(seq_num * sizeof seq_len[0]) / 1073741824.0);
do {
n = collatz_length(i, &m);
if (n >= nmax) {
const double cs = cpu_seconds();
const double ws = wall_seconds();
const char *s = s128(m);
nmax = n;
print("%" PRIu64 " length %u (reaches %s) [%.3f seconds elapsed, %.3f seconds CPU time]\n", i, n, s, ws, cs);
}
i++;
} while (nmax < MAX_SEQ_LEN);
return EXIT_SUCCESS;
}
我使用gcc -Wall -O2 collatz.c -lrt -o collatz && ./collatz > results.txt
. (优化确保例如sizeof
if 子句在编译时被解析,并生成最少数量的缓慢条件跳转,使用条件移动代替。因此,上述程序被设计-O2
为至少使用编译。)它确实包含额外的代码,例如显示使用的实时时间和 CPU 时间。由于它们与手头的问题无关,它们确实可以帮助助教轻松检测是否有人尝试将此代码作为自己的作业提交。
当它工作时,我可以grep -gk 3 results.txt
在另一个终端中使用来查看迄今为止获得的结果,并按增加的序列长度排序;或grep -gk 5 results.txt
查看根据序列中的峰值(序列中的最大值)排序的结果。
推荐阅读
- swift - 如何在 Swift 中使 UITabBar 模糊
- kotlin - IntelliJ 错误:Kotlin:模块已编译
- mobaxterm - 录制 MobaXterm 宏时如何使用“等待模式”?
- c# - .NET Core 2.2 的 MassTransit
- vb.net - 如何将批处理文件嵌入到 vb.net 中的表单中
- javascript - 如何在 JavaScript/React 上向现有对象添加属性
- json - Flutter/Dart:JSON 解析
- ruby-on-rails - Rails 帮助 - 事件的未知属性“creator_id”
- visual-studio-code - 如何在 VS Code 中获取上一个终端?
- python - Tidyverse 在 Pandas 中的嵌套数据框工作流程