我可以更有效地计算 2ⁿ 的数字和吗？

Question

我正在尝试在 C 中创建一个递归函数来计算 2ⁿ 中的数字之和，其中 n < 10⁷。我做了一些有用的东西，但速度很慢（对于 n = 10⁵ 需要 19 秒）。该函数必须 return 最多 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;
}

Answer 1

似乎发布的代码使用 "implicit" 任意精度类型（"digits" 在 [0, 999999999] 范围内）递归计算所有乘以 2，这意味着，例如n = 100，执行100次膨胀计算。

每次将数字乘以本身或乘以2应该更有效（O（log（n））而不是O（n）），基于指数是偶数还是奇数。例如。 2⁷ = 2 * (2³ * 2³).

另一种方法是显式实现 Bing Int 类型，但使用二进制基础类型（比如 uint32_t）。计算 2ⁿ 是微不足道的，它只是一个最终幂为 2 的零数组（同样，只有一个非零位）。

现在，要获得（以 10 为基数）数字的总和，您需要将该数字转换为基数，比如 100000000（就像 OP 所做的那样），为此，您必须在两个数之间执行一个长减法Big Ints 和长除以 100000000，这也会给你余数。使用该余数计算数字的部分和并进行迭代。

以下是一个最小的实现，可测试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;
    }
}

Answer 2

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的实际计算是最耗时的。

如果您没有达到数字格式的限制，那么您可以考虑向左移动，但是对于您使用的域，这并不是一个真正的选择。

我可以更有效地计算 2ⁿ 的数字和吗？

Can I compute digital sum of 2ⁿ more efficiently?

c

algorithm

recursion

sum-of-digits