我正在尝试在C中创建一个递归函数，该函数计算2ⁿ中的位数之和，其中n <10⁷。我做了一些有用的东西，但是速度很慢（n =10⁵需要19秒）。该函数必须在最长1秒内返回总和。我的算法使用数组计算2ⁿ来存储其数字，而不使用递归函数。
是否有任何方法可以计算出这个数字的总和而不计算2ⁿ？还是一种更快的方法来计算2ⁿ及其数字总和？
P.S .：递归函数必须仅获取n参数，即int f(int n);
后期编辑：我编写了递归解决方案，它速度更快，但不适用于n>10⁵。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int sumOfDigits(int* num, int n) {
if (n == 0) {
int sum = 0;
for (int i = 1; i <= num[0]; ++i) {
while (num[i] > 0) {
sum += num[i] % 10;
num[i] /= 10;
}
}
return sum;
}
int carry = 0;
for (int i = 1; i <= num[0]; ++i) {
num[i] = num[i] * 2 + carry;
carry = num[i] / 1000000000;
num[i] %= 1000000000;
if (carry != 0 && i == num[0]) {
++num[0];
}
}
return sumOfDigits(num, n - 1);
}
int main (void) {
int n = 100000;
int size = (n*log10(2) + 1) / 9 + 2;
int* num = calloc(size, sizeof(int));
num[0] = 1;
num[1] = 1;
printf("\n%d", sumOfDigits(num, n));
free(num);
return 0;
}
2 ^ 8 =（2 * 2 * 2 * 2 * 2 * 2 * 2 * 2）=（2 * 2 * 2 * 2）*（2 * 2 * 2 * 2）=（2 * 2 * 2 * 2）^ 2 =（（2 * 2）*（2 * 2））^ 2 =（（2 * 2）^ 2）^ 2 =（（2 ^ 2）^ 2）^ 2
因此，首先需要计算log（2，n），以了解如何有效地进行计算。如果log（2，n）是整数，则只需很少的运算就可以简单地计算平方...的平方。如果log（2，n）不是整数，则计算2 ^（（int）log（2，n）），因此您将非常有效地进行部分计算，然后对其余部分进行相同的计算，直到不再存在余数。
将您的部分结果统一为一个数字（可能由数组表示），然后计算数字的总和。计算位数之和很简单。 2 ^ n的实际计算是最耗时的。
如果您没有达到数字格式的极限，那么您可以考虑向左移动，但是对于您使用的域，这实际上不是一个选择。
似乎发布的代码正在使用“隐式”任意精度类型（“数字”在[0，999999999]范围内）以2递归计算所有乘法，这意味着例如n = 100，是膨胀计算的100倍。
根据指数是偶数还是奇数，每次将数字乘以itself或2，应该更高效（用O（log（n））而不是O（n））。 。例如。 2 7 = 2 *（2 3 * 2 3）。
另一种方法是明确地实现Bing Int类型，但是具有二进制基础类型（例如uint32_t）。计算2 n将是微不足道的，它只是零的数组，最终幂为2（再次是一个非零位）。
现在，要获得（基数为10的）数字的总和，您需要将基数转换为100000000（如OP所做的那样），并且要做到这一点，必须在两个Big Ints和用1亿除以一个长除法，剩余的也将得到。使用该余数来计算数字的部分和并进行迭代。
下面是一个最小的实现，可以测试here。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#define D_BASE 1000000
#define MSB_MASK 1 << 31
typedef struct
{
uint32_t size;
uint32_t capacity;
uint32_t *digits;
} BigInt;
void divide_bigint(BigInt *n, uint32_t x, uint32_t *remainder);
BigInt *make_bigint_of_two_raised_to(uint32_t n)
{
BigInt *p = malloc(sizeof *p);
if (!p)
{
perror("Fatal error");
exit(1);
}
uint32_t pos = n / 32;
uint32_t remainder = n % 32;
uint32_t capacity = (remainder == 31) ? pos + 2 : pos + 1;
uint32_t *pp = calloc(capacity, sizeof *pp);
if (!pp)
{
perror("Error initializing a Big Int as a power of two");
free(p);
exit(1);
}
p->capacity = capacity;
p->size = capacity;
pp[pos] = 1u << remainder;
p->digits = pp;
return p;
}
void free_bigint(BigInt **p);
uint64_t sum_of_digits_of_two_raised_to_the_power(uint32_t n)
{
BigInt *power_of_two = make_bigint_of_two_raised_to(n);
uint32_t remainder;
uint64_t sum = 0;
while (!(power_of_two->size == 1 && power_of_two->digits[0] == 0))
{
divide_bigint(power_of_two, 1000000000, &remainder);
while (remainder)
{
sum += remainder % 10;
remainder /= 10;
}
}
free_bigint(&power_of_two);
return sum;
}
void test(uint32_t n)
{
uint64_t sum = sum_of_digits_of_two_raised_to_the_power(n);
printf("Sum of digits of 2^%d: %" PRIu64 "\n", n, sum);
}
int main(void)
{
test(5);
test(10);
test(1000);
test(10000);
test(100000);
test(1000000);
return 0;
}
void shrink_size(BigInt *n)
{
while ( n->size > 1 )
{
if ( n->digits[n->size - 1] == 0 && !(n->digits[n->size - 2] & MSB_MASK) )
--n->size;
else
break;
}
}
void divide_bigint(BigInt *n, uint32_t x, uint32_t *remainder)
{
uint64_t carry = 0;
uint32_t i = n->size;
while ( i-- > 0 )
{
carry <<= 32;
carry += n->digits[i];
if ( carry < x )
{
n->digits[i] = 0;
continue;
}
uint64_t multiplier = (carry / x);
carry -= multiplier * x;
n->digits[i] = (uint32_t)multiplier;
}
shrink_size(n);
*remainder = carry;
}
void free_bigint(BigInt **p)
{
if (p && *p)
{
free((*p)->digits);
free(*p);
*p = NULL;
}
}
[Lajos Arpad的方法相对于建议的蛮力而言更为优雅，并且收敛迅速地做出回答，唯一的不确定性是每次剩下的期望值。
[如果看一下OP的意图，那就是要计算多项式函数（在x == [a = 2]时）：f（x）= 2 ^ n，0 <= n <10 ^ 7，将其渲染为a幂（10）序列并对其系数求和。现在f：= 2 ^ n足够解析，派生函数f'== f（1）'：= 2 ^ n.ln（2），并且寻求序列（N）（在更改对数底数（2 ^ n = 10 ^ x => 2 = x.ln（10 / ln（2））是e-pow（x）上的无限泰勒级数，其余数可以用不同的方式估算，并且可能适合此上下文可以是Lagrange的形式Rem（N，x，a）= f（N + 1）'（c）=（xa）^（N + 1）/（N + 1）!,其中 当然是f（N）'：= 2 ^ n.ln（2）.ln（2）... Ntimes ... ln（2） 这可以在少于几次迭代中提供收敛。 我希望这比混淆更有用