c - 递归计算数字总和为2 ^ n。 C(Recursive calculation of digits sum on 2^n. C)

Question

I am trying to make a program in C that calculates sum of digits on 2^n, where n < 10^7.

(我试图用C编写一个程序，计算2 ^ n上的数字总和，其中n <10 ^ 7。)

I did something that works, but it's very slowly (for n = 10^5 it takes 19 seconds).

(我做了一些有效的操作，但是速度非常慢（n = 10 ^ 5需要19秒）。)

The recursive function must return the sum in maximum 1 second.

(递归函数必须在最长1秒内返回总和。)

My algorithm calculates 2^n using arrays to store it's digits and it's not using a recursive function.

(我的算法使用数组计算2 ^ n来存储数字，并且不使用递归函数。)

Is there any way to compute this sum of digits without calculating 2^n?

(有什么方法可以不用计算2 ^ n就能计算出这个数字总和？)

Or a faster way to calculate 2^n an its digits sum?

(还是一种更快的方法来计算其数字总和的2 ^ n？)

Late edit: This is my code.

(后期编辑：这是我的代码。)

I don't know how could I implement a recursive function on this.

(我不知道如何在此上实现递归函数。)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main (void) {
    int n = 100000;
    int size = n*log10(2) + 1;
    short* digits = calloc(size, sizeof(short));
    digits[0] = 0;
    int high_order = 0;
    int i = 1;
    int sum = 0;

    digits[0] = 1;

    for (i = 1; i <= n; i++) {
        int j;
        int carry = 0;
        int product = 1;

        for (j = 0;  j <= high_order; j++) {
            product = (digits[j] << 1) + carry;
            digits[j] = product % 10;
            carry = product / 10;

            if ( ( carry != 0 ) && ( j == high_order ) )
                high_order++;
        }
    }

    for (i = 0; i <= high_order; i++)
        sum += digits[i];

    free(digits);
    printf("Sum is %d
", sum);
    return 1;
}

  ask by Popescu ?tefan translate from so

Answer 1

等待大神答复