我正在编写一个程序，用于计算数字范围（1 - 100,000,000）之间的Collatz猜想的最多循环，我需要它在 4 分钟内在 Linux 系统上运行
command gcc -O0 -m32 -Wall -Wextra -Werror -pedantic -o collatz collatz.c.
关于如何改进算法的任何想法，因为在 10,000,000 次之后，程序需要很长时间才能完成，请记住，我不能使用多线程，也不能使用预先计算的数据。
欢迎所有答案，谢谢您的宝贵时间。😀
// Lets find the longest collatz
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
// This function finds how many times it took for a number to reach 1
unsigned long int collatz(uint32_t First_num){
// steps measures how many times a number needs to reach 1
uint32_t steps = 1;
// This is the loop that applies the rules of the collatz conjecture
while (First_num != 1) {
(First_num % 2 == 0) ? (First_numm>>=1) : (First_num = (3*First_num+1)/2);
steps++;
}
return steps;
}
// This is the function that calculates the maximum loops a number needs to reach 1
int max(uint32_t First_num,uint32_t Second_num){
// This "if" determines if the number is correct
if (First_num <= 0 || Second_num <= 0){
printf("0\n");
}
uint32_t max = 0;
uint32_t max_num = 0;
uint32_t i = First_num;
// This loop is used to find the maximum times the collatz function needs to be used
for (i;i<=Second_num;i++){
printf("The num %u took the most %ld!!!\n",i,collatz(i));
// This block finds the number with the most loops
if ((collatz(i)) >= max){
max = collatz(i);
max_num = i;
}
}
printf("The num %u took the most %u !!!\n",max_num,max);
return 0;
}
// This is the main function in which the "max" function is used and the user gives his input and gets his output
int main(int argc, char **argv){
if (argc != 3){
printf("Program needs to be called as './prog num1 num2'\n");
return 1;
}
//Users input
uint32_t num1 = atoi(argv[1]);
uint32_t num2 = atoi(argv[2]);
// Users input
max(num1,num2);
return 0;
}
//End of the program
删除调试输出
for (i;i<=Second_num;i++){
// printf("The num %u took the most %ld!!!\n",i,collatz(i))
保存之前的工作
#define PRIOR_N (100u*1000*1000)
static uint32_t prior[PRIOR_N];
// This function finds how many times it took for a number to reach 1
unsigned long int collatz(uint32_t First_num) {
if (First_num < PRIOR_N && prior[First_num] && First_num > 1) {
return prior[First_num];
}
// steps measures how many times a number needs to reach 1
uint32_t steps = 1;
// This is the loop that applies the rules of the collatz conjecture
while (First_num != 1) {
(First_num % 2 == 0) ?
(First_num >>= 1) : (First_num = (3 * First_num + 1) / 2);
steps++;
}
if (First_num < PRIOR_N) {
prior[First_num] = steps;
}
return steps;
}
// About 1 minute
The num 83706505 took the most 473 !!!