How to multiply each digit in an amount effectively

Question

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

for example

515 would become 25(ie 5*1*5) 10 would become 0(ie 1*0) 111111 would become 1(ie 1*1*1*1*1*1) 

I used this code for this

 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; } 

The problem is that I want to estimate about billions of numbers like this

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

It takes about 146 seconds on my processor. I want to evaluate it for some seconds.

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

thanks

Answer 1

First find out how many numbers you can keep in memory. In this example, suppose you can store 999 numbers.

Your first step will be to pre-calculate the digit products for all numbers from 0 to 999 and store them in memory. So, you will have an array line by line:

  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, ...] 

Now you add your number to a bunch of three-digit numbers. For example, if your number is 1739203423 , you divide it into 1 , 739 , 203 and 423 . You will look at each of them in your multLookup array and multLookup results together like this:

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

With this approach, you will accelerate the calculations by 3 times (since we selected 999 elements for storage in memory). To speed it up by 5, store 99999 numbers in memory and follow the same steps. In your case, an acceleration of 5 means that you will come to your decision in 29.2 seconds .

Note: The gain is not exactly linear with respect to the number of numbers that you store in memory. See Jogojapan's reasoning in the comments on this question why this is so.

If you know more about the order in which your numbers are displayed, or about the range of your numbers (for example, your input is only in the range [0, 10000]), you can make this algorithm more intelligent.

In your example, you use a for loop to iterate from 0 to 1,000,000,000. In this case, this approach will be super-efficient, because the memory will not often occur due to a page error, and there will be less cache misses.

But wait! You can do it even faster (for your specific iteration example for a loop)! How, you ask? Caching! Suppose you have passed ten-digit numbers.

Let's say you start with 8934236000 . Based on 999 digits in the memory solution, you divide this into 8 , 934 , 236 and 000 . Then you will multiply:

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

Then you take 8934236001 , split it into 8 , 934 , 236 and 001 and multiply:

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

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

 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; } 

And just like that, we almost reduced the time by 4 times. So you take the 29.2 second decision you had and divide it by 4 to go through all the billions of numbers in ~ 7.3 seconds

Answer 2

If you can save the result of each operation for all your numbers, then you can use Memoization . Thus, you need to calculate only 1 digit.

 int prodOf(int num){ // can be optimized to store 1/10 of the numbers, since the last digit will always be processed static std::vector<int> memo(<max number of iterations>, -1); if(num == 0) return 0; if(memo[num] != -1 )return memo[num]; int prod = (num%10) * prodOf(num/10); memo[num] = prod; return prod; } 

Answer 3

Some test I did, With simple C / C ++ code on my PC (Xeon 3.2GHz)

last no = i = 999999999 ==> 387420489 nb sec 23

 #include "stdafx.h" #include <chrono> #include <iostream> #undef _TRACE_ inline int evaluate(int no) { #ifdef _TRACE_ std::cout << no; #endif if(no==0)return 0; int temp=1; do { temp=(no%10)*temp; no=no/10; }while(no>0); #ifdef _TRACE_ std::cout << " => " << temp << std::endl; #endif // _TRACE_ return temp; } int _tmain(int argc, _TCHAR* argv[]) { std::chrono::time_point<std::chrono::system_clock> start(std::chrono::system_clock::now()); int last = 0; int i = 0; for(/*int i = 0*/;i<1000000000;++i) { last = evaluate(i); } std::cout << "last no = i = " << (i-1) << " ==> " << last << std::endl; std::chrono::time_point<std::chrono::system_clock> end(std::chrono::system_clock::now()); std::cout << "nb sec " << std::chrono::duration_cast<std::chrono::seconds>(end - start).count() << std::endl; return 0; } 

I also tested a loop divided into several threads using openMP, and the result is 0 second, so I would say that it would be useful if you would consider the performance problem of using a real effective language.

 pragma omp parallel for for(int i = 0;i<1000000000;++i) { /*last[threadID][i] = */evaluate(i); }