如何有效地将数字中的每个数字相乘 [英] How to multiply each digit in a number efficiently

问题描述

我想将数字中的每个数字彼此相乘.

I want to multiply every digit in a number to each other.

例如

515 would become 25(i.e 5*1*5)
10 would become 0(i.e 1*0)
111111 would become 1(i.e 1*1*1*1*1*1)

我用这段代码来做

public static int evalulate(int no)
{
    if(no==0)return 0;
    int temp=1;

    do
    {
        temp=(no%10)*temp;
        no=no/10;
    }while(no>0);

    return temp;
}

问题是我想评估大约十亿个数字

problem is I want to evaluate for about a billion numbers like this

for(int i=0;i<1000000000;i++)evaluate(i);

这在我的处理器上大约需要 146 秒.我想在 some 秒内对其进行评估.

This takes about 146 seconds on my processor.I want to evaluate it within some seconds.

因此，是否可以使用某些shift，and，or运算符来优化此代码，这样我就可以减少评估的时间，而无需使用多个线程或对其进行并行化

So,is it possible to optimize this code using some shift,and,or operators so that I can reduce the time to evaluate without using multiple threads or parallelizing it

谢谢

推荐答案

首先，确定可以在内存中存储多少个数字.对于此示例，假设您可以存储999个数字.

First, figure out how many numbers you can store in memory. For this example, let's say you can store 999 numbers.

您的第一步将是为0-999中的所有数字预先计算数字乘积，并将其存储在内存中.因此，您将拥有一个类似于以下内容的数组:

Your first step will be to pre-calculate the products of digits for all numbers from 0-999, and store that in memory. So, you'd have an array along the lines of:

  multLookup = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                0, 2, 4, 6, 8, 10, 12, 14, 16, 18,
                0, 3, 6, 9, 12, 15, 18, 21, 24, 27,
                0, 4, 8, 12, 16, 20, 24, 28, 32, 36,
                ...]

现在，您可以将数字分解为3位数字.例如，如果您的电话号码是1739203423，则可以将其分解为1，739，203和423.您可以在multLookup数组中查找每一个，然后将结果相乘，如下所示:

Now, you'd break your number up into a bunch of 3 digit numbers. For example, if your number is 1739203423, you'd break it up into 1, 739, 203, and 423. You'd look each of these up in your multLookup array, and multiply the results together, like so:

  solution = multLookup[1] * multLookup[739] * multLookup[203] * multLookup[423];

使用这种方法，您将把计算速度提高了3倍(因为我们选择了999个要存储在内存中的项目).要使其速度提高5，请将99999数字存储在内存中，然后执行相同的步骤.就您而言，将其加速5意味着您将在 29.2秒内找到解决方案.

With this approach, you will have sped up your calculations by a factor of 3 (since we picked 999 items to store in memory). To speed it up by 5, store 99999 numbers in memory and follow the same steps. In your case, speeding it up by 5 means you'll arrive at your solution in 29.2 seconds.

注意:相对于您存储在内存中的数字而言，增益并不是完全线性的.请参阅此答案下方注释中的jogojapan推理，以了解原因.

Note: the gain isn't exactly linear with respect to how many numbers you store in memory. See jogojapan's reasoning in the comments under this answer for why that is.

如果您进一步了解数字显示的顺序或数字范围(例如，输入仅在[0，10000]范围内)，则可以使该算法更智能.

If you know more about the order in which your numbers show up, or the range of your numbers (say your input is only in the range of [0, 10000]), you can make this algorithm smarter.

在您的示例中，您使用的是for循环从0迭代到1000000000.在这种情况下，这种方法将非常有效，因为内存不会非常频繁地进行页面错误操作，并且缓存丢失的情况会更少.

In your example, you're using a for loop to iterate from 0 to 1000000000. In this case, this approach will be super efficient because the memory won't page-fault very frequently and there will be fewer cache-misses.

但是请等一下！ ！您可以使其更快(针对您的特定for循环迭代示例)！你怎么问?正在缓存！假设您要输入10位数字.

But wait! You can make this even faster (for your specific for-loop iteration example)!! How, you ask? Caching! Lets say you're going through 10 digit numbers.

假设您从8934236000开始.根据内存解决方案中的999位数字，您可以将其分解为8，934，236和000.然后您将乘以:

Let's say you start off at 8934236000. Based on the 999 digits in memory solution, you'd break this down into 8, 934, 236, and 000. Then you'd multiply:

solution = multLookup[8] * multLookup[934] * multLookup[236] * multLookup[0];

接下来，您将使用8934236001，将其分解为8，934，236和001，然后相乘:

Next, you'd take 8934236001, break it down to 8, 934, 236, and 001, and multiply:

solution = multLookup[8] * multLookup[934] * multLookup[236] * multLookup[1];

依此类推...但是，我们注意到在接下来的997次迭代中，前三个查询是相同的！因此，我们将其缓存.

And so on... But we notice that the first three lookups are the same for the next 997 iterations! So, we cache that.

cache = multLookup[8] * multLookup[934] * multLookup[236];

然后我们像这样使用缓存:

And then we use the cache as such:

for (int i = 0; i < 1000; i++) {
    solution = cache * i;
}

就像这样，我们几乎将时间减少了4倍.因此，您采用的是〜29.2秒的解决方案，然后将其除以4，以在〜7.3秒内遍历所有十亿个数字

And just like that, we've almost reduced the time by a factor of 4. So you take the ~29.2 second solution you had, and divide that by 4 to go through all billion numbers in ~7.3 seconds

这篇关于如何有效地将数字中的每个数字相乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！