current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

This question is similar to Project Euler #48 but constraints are different:

$$N < 2000000$$

Just in case the link is unavailable, here is the problem statement:

We've to print

$$\left( \sum_{i=1}^N i^i \right) \mod 10^{10}$$

I've tried the following, but I need something faster than that, because the execution time limit is 2s, and this program can only compute values until \$ N=30000\$ (approx) in the given time limit.

#include <iostream>
using namespace std;

#define Mod 10000000000

int main() 
{
    int N;
    cin>>N;
    long long Temp,Sum=0;
    for( int ii=1 ; ii<=N ; ii++ )
    {
        if(ii%10==0)
        {
            continue;
        }        
        Temp=1;
        for( int jj=1 ; jj<=ii ; jj++ )
        {   
            Temp*=ii;
            Temp=Temp%Mod;
        }
        Sum+=Temp;
        Sum=Sum%Mod;
    }
    cout<<Sum;
    return 0;
}

I've added 

if(N%10==0)
{
    continue;
}

because numbers of form $$ (k*10)^{k*10}=k^{k*10}*10^{k*10}=k^{k*10}*10^{k}*10^{10} $$ are not at all going to contribute to the answer.

Note: code is compiled using g++ 4.8.2, C++11 mode

share|improve this question
1  
I don't think I can give you a full answer, because I don't know C++ and I haven't solved this question myself, but you might want to look up the Square and Multiply Algorithm for Modular Exponentiation. I'm pretty sure that's where you're spending all your time. If you want to take this question to its extreme, then also look up the Sliding Window approach to this algorithm. I think Montgomery Arithmetic could also save you some time here, but if memory serves that only really works for a fixed base. –  ymbirtt Oct 3 '14 at 7:51
    
Perhaps this answer will bring you some idea. –  outoftime Oct 3 '14 at 8:06
    
You really don't need any of those modulo operators. They are expensive, and the speed of multiplication and addition is unaffected by how many bits are set in your result. Use unsigned values, and leave the modulo to the end. Also for omitting power of 10s, just have a counter that goes up to 10 then reset it –  Tom Tanner Oct 3 '14 at 13:10
    
There may be some ideas from here: oeis.org/A001923 –  d'alar'cop Oct 3 '14 at 14:01
    
@TomTanner, though this would be a great idea ordinarily, think of the numbers involved. $$2,000,000^{2,000,000} = 2^{2,000,000} \cdot (10^3)^{4,000,000} \approxeq 2^{2,000,000} \cdot 2^{40,000,000} = 2^{42,000,000}$$. Handling a 42,000,000 bit integer is a bad idea. –  ymbirtt Oct 3 '14 at 20:22

2 Answers 2

up vote 5 down vote

Time complexity

Let's have a look at the time complexity of your algorithm.

The bound is: \$N<2\cdot 10^6\$ and we want to compute: \$\left(\sum_{i=1}^N i^i\right)\mod(10^{10})\$.

Naively computing \$i^i\$ like you are doing will require \$\mathcal{O}(i)\$ operations. Computing the sum \$\sum_{i=1}^N i^i\$ will cost you \$\sum_{i=1}^N \mathcal{O}(i) = \mathcal{O}(N^2)\$ operations. Or in other words you're looking at the order of \$N^2 = 10^{12}\$ iterations of your inner loop. Or if every iteration of your inner loop take 10 ns (i.e. about 10 clock cycles on a 1GHz CPU), you're looking at \$10\cdot 10^{-9}\cdot 10^{12}=10^4\$ (\$10\$ cycles, \$10^{-9}\$ seconds per cycle) seconds which is about 3 hours.

However by using Exponentiation by Squaring you can reduce the time to calculate \$i^i\$ from \$\mathcal{O}(i)\$ to roughly \$\mathcal{O}(\log_2(i))\$ meaning that your expected complexity to calculate the sum: \$\sum_{i=1}^N i^i\$ is \$\mathcal{O}(N\log_2(N))\$. For \$N=10^6\$ you're looking at about \$2\cdot 10^7\$ iterations (\$\log_2(10^6)\approx 20\$) which should take our hypothetical computer about \$2\cdot 10^7\cdot 10\cdot 10^{-9}=0.2\$ seconds to compute.

So to fix your performance you need to use a better exponential computation, there are plenty of examples on the web.

Your code

Now to look at your loop:

    if(ii%10==0)
    {
        continue;
    }        
    Temp=1;
    for( int jj=1 ; jj<=ii ; jj++ )
    {   
        Temp*=ii;
        Temp=Temp%Mod;
    }
    Sum+=Temp;
    Sum=Sum%Mod;

The ii%10 == 0 optimization gives you maybe 10% speed gain which isn't much. And I say maybe, it depends on if your CPU correctly predicts the branch so it's probably a bit less than 10%. These kind of problems very rarely depend on how you optimize your code, but rather that you have the correct time complexity, see the above.

share|improve this answer
    
nice trick with runtime overloading. –  outoftime Oct 4 '14 at 16:44
    
@Emily I'm afraid you're wrong, unsigned long long A=0; A=A-2; cout<<A<<endl; A=A*2; cout<<A; In environment I mentioned This piece of code is not doing what you said it would –  The Mean Square Oct 5 '14 at 4:32
    
Ah yeah dunno why I thought that, it would have worked if the mod day power of 2. I'll just remove it from the answer. The problem is the same, you still need a better exponential calculation. See if you can adapt exponentiaton by squaring or use Montgomery arithmetic. –  Emily L. Oct 5 '14 at 8:43
    
@EmilyL. Yes I agree, I need some variation of exponentiation by squaring algorithm. Any tip about how to avoid overflow? –  The Mean Square Oct 5 '14 at 9:02
1  
You just have to study the algorithm and deduce where and when it can overflow. Then add appropriate modulo operations. As this is a challenge type question I'm not inclined to give you the whole solution as that would reduce the learning opportunity in my opinion. But I can point you in the right direction. –  Emily L. Oct 5 '14 at 9:34
up vote 2 down vote

At least you can use binary power function instead of linear power loop. And add some binary operations for perfomance improvements.

typedef unsigned long long int ULL;
typedef unsigned int UI;

const ULL module = 1e11;
const UI N = 2e6;

ULL binary_power(ULL a, UI power) {
    ULL result = 1;
    while (power) {
        if (power & 1) {
            result = (result * a) % module;
            --power;
        } else {
            a = (a * a) % module;
            power >>= 1;
        }
    }
    return result;
}

Binary power improvements

Well, you can improve module operation, full description can be found there http://www.hackersdelight.org/MontgomeryMultiplication.pdf

share|improve this answer
1  
We don't really need the helper program; we just solve $$2^n>10^{10} \implies n>10 \log_2 10 \implies n>33.2...$$ This gives the same result without extra code. Your solution, however, appears to give the wrong answer. Suppose we were interested only in the last digit; you'd choose n=4, so we'd be using the bitmask 0xf to perform a reduction modulo 16. Suppose our sum gave us the number 20 at some point. $$ 20 \cong 0 \mod 10$$ But $$20 \cong 4 \mod 16$$ If I reduce modulo 16 first, I get the wrong answer. –  ymbirtt Oct 4 '14 at 6:28
    
The idea behind your bitmasking is, however, sensible. If you're interested in the correct way to do this, look up Montgomery Reductions; en.wikipedia.org/wiki/Montgomery_reduction. –  ymbirtt Oct 4 '14 at 6:33
    
@ymbirtt, couldn't figure out what are talking about, but now I see that \$2^{34} \mod{10000000} \neq 0 \$ –  outoftime Oct 4 '14 at 7:59
    
@ymbirtt I'm reading this article hackersdelight.org/MontgomeryMultiplication.pdf –  outoftime Oct 4 '14 at 8:19
    
Ah, I've just realised that this technique will only be worthwhile when our modulus is odd. Apologies; I learnt it in cryptographic situations where, if the modulus is even, something is very very wrong somewhere. Whilst I was learning about it, I found that there weren't really any good explanations of how it works and how to implement it on the internet, and there still doesn't seem to be one on the Cryptography Stackexchange, which would be an appropriate place for it. If you're interested in the technique, drop a question in crypto.stackexchange.com/questions, and link it at me. –  ymbirtt Oct 4 '14 at 18:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.