计算floor（pow（2，n）/ 10）mod 10 - pow的数字之和（2，n） [英] Calculate floor(pow(2,n)/10) mod 10 - sum of digits of pow(2,n)

问题描述

这也是一个数学相关的问题，但我想在C ++中实现...所以，我有一个数字形式 2 ^ n 并且我必须计算其数字的总和（以10为底; P）。我的想法是用以下公式计算它：

This is also a math related question, but I'd like to implement it in C++...so, I have a number in the form 2^n, and I have to calculate the sum of its digits ( in base 10;P ). My idea is to calculate it with the following formula:

sum = (2^n mod 10) + (floor(2^n/10) mod 10) + (floor(2^n/100) mod 10) + ...

其所有数字： floor（n / floor（log2（10）））。

第一项很容易用模幂运算，但我和其他人有困难。
由于 n 是大的，我不想使用我的大整数库，我不能计算 pow（2， n）无模。第一个字词的程式码片段：

The first term is easy to calculate with modular exponentiation, but I'm in trouble with the others. Since n is big, and I don't want to use my big integer library, I can't calculate pow(2,n) without modulo. A code snippet for the first term:

while (n--){
    temp = (temp << 1) % 10;
};

但对于第二个我不知道。我也不能 floor 单独，因为它会给'0'（2/10）。是可能实现这一点吗？
（ http://www.mathblog.dk/project-euler-16/ 为更容易的解决方案。）当然，我会寻找其他方式，如果它不能用这个方法。 （例如以字节数组存储数字，如链接中的注释）。

but for the second I have no idea. I also cannot floor them individually, since it would give '0' (2/10). Is it possible to achieve this? (http://www.mathblog.dk/project-euler-16/ for the easier solution.) Of course I will look for other way if it cannot be done with this method. (for example storing digits in byte array, as in the comment in the link).

编辑：感谢现有答案，寻找一些方法来解数学。我只是想出了一个想法，可以实现没有bignum或数字向量，我要测试它是否工作。

Thanks for the existing answers, but I look for some way to solve it mathematically. I've just came up with one idea, which can be implemented without bignum or digit-vectors, I'm gonna test if it works.

所以，我有方程式。但 2 ^ n / 10 ^ k 可以写为 2 ^ n / 2 ^（log2 10 ^ k）这是 2 ^（nk * log2 10）。然后我把它的小数部分和它的整数部分，并对整数部分做模幂： 2 ^（nk * log2 10）= 2 ^（floor（nk * log2 10））* 2 ^ （fract（nk * log2 10））。在最后一次迭代之后，我还将它乘以分数模10.如果它不工作或如果我在上述想法的某个地方错了，我坚持向量解答并接受答案。

So, I have the equation above for the sum. But 2^n/10^k can be written as 2^n/2^(log2 10^k) which is 2^(n-k*log2 10). Then I take it's fractional part, and its integer part, and do modular exponentiation on the integer part: 2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10)). After the last iteration I also multiply it with the fractional modulo 10. If it won't work or if I'm wrong somewhere in the above idea, I stick to the vector solution and accept an answer.

编辑：好吧，看起来使用非整数取模的模幂运算是不可能的（？）关于它）。所以，我正在使用基于数字/向量的解决方案。

Ok, it seems doing modular exponentiation with non-integer modulo is not possible(?) (or I haven't found anything about it). So, I'm doing the digit/vector based solution.

它不会给出好的值：（1390而不是1366）：

It does not give the good value: (1390 instead of 1366):

typedef long double ldb;

ldb mod(ldb x, ldb y){             //accepts doubles
    ldb c(0);
    ldb tempx(x);
    while (tempx > y){
        tempx -= y;
        c++;
    };
    return (x - c*y);
};

int sumofdigs(unsigned short exp2){
    int s = 0;
    int nd = floor((exp2) * (log10(2.0))) + 1;
    int c = 0;
    while (true){
        ldb temp = 1.0;
        int expInt = floor(exp2 - c * log2((ldb)10.0));
        ldb expFrac = exp2 - c * log2((ldb)10.0) - expInt;
        while (expInt>0){
           temp = mod(temp * 2.0, 10.0 / pow(2.0, expFrac)); //modulo with non integer b:
                //floor(a*b) mod m = (floor(a mod (m/b)) * b) mod m, but can't code it
            expInt--;
        };
        ldb r = pow(2.0, expFrac);
        temp = (temp * r);
        temp = mod(temp,10.0);
        s += floor(temp);
        c++;
        if (c == nd) break;
    };
    return s;
};

推荐答案

如果你必须编写你自己的一切，那么你需要知道如何计算二进制除法和处理非常大的数字。如果你不必编程一切，获得一个大的整数数组的库，并应用链接中所示的算法：

If you have to program your own everything then you need to know how to calculate a binary division and handle very large numbers. If you don't have to program everything, get a library for large integer numbers and apply the algorithm shown in the link:

BigNumber big_number;
big_number = 1;
big_number <<= n;
int result = 0;
while(big_number != 0) {
    result += big_number % 10;
    big_number /= 10;
}
return result;

现在，实现BigNumber会很有趣。从算法我们看到，你需要分配，向左移动，不等于，模数和除法。一个BigNumber类可以是完全动态的，并分配一个整数缓冲区，使所述大数字拟合。它也可以用固定大小写（例如作为模板）。但如果你没有时间，也许这个人会这样做：

Now, implementing BigNumber would be fun. From the algorithm we see that you need assignment, shift to left, not equal, modulo and division. A BigNumber class can be fully dynamic and allocate a buffer of integers to make said big number fit. It can also be written with a fixed size (as a template for example). But if you don't have the time, maybe this one will do:

https://mattmccutchen.net/bigint/

这篇关于计算floor（pow（2，n）/ 10）mod 10 - pow的数字之和（2，n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！