Bignum

[khengol khan]

I want to solve problem 48 of projecteuler.net to find the last ten digits of the series 1^1 + 2^2 + ... + 1000^1000

so i wrote this code!! there is one mistake because my answer after runnig this code is 9259769260 but the correct answer is 9110846700!! I really mixed up!

#include <iostream>
using namespace std;
int main(){
	int a[1000][12],i,j,count,m,n,sum[12]={0,0,0,0,0,0,0,0,0,0,0,0};
	for(i=0;i<=999;i++){
		a[i][11]=1;
		for(j=0;j<=10;j++) a[i][j]=0;
	}
for(i=1;i<=1000;i++){
	for(count=1;count<=i;count++){
		for(j=0;j<=11;j++){
			a[i-1][j]*=i;
			for(m=0;m<=999;m++){
				for(n=11;n>=0;n--){
					while(a[m][n]>=10){
						a[m][n-1]++;
						a[m][n]-=10;
					}
				}
			}
		}
	}
}
for(j=11;j>=2;j--){
   for(i=0;i<=999;i++){
	sum[j]+=a[i][j];
	}
}
for(j=11;j>=0;j--){
	while(sum[j]>=10){
		sum[j-1]++;
		sum[j]-=10;
	}
}
for(i=2;i<=11;i++)  cout<<sum[i]<<" ";
cout<<endl<<sum[0]<< "  "<<sum[1];
}

Help please!!

[AbstractionAnon]

So what is your question?
Are you asking us to debug your code for you?

[khengol khan]

Yes :S wasnt it clear?!?

[Chervil]

I briefly looked at this code, but it seems immensely complicated relative to the task which is to be achieved. And quite inefficient, on my machine it took over three minutes to execute, (and of course gives an incorrect result). One of the innermost loops executes over 1.7 billion times.

Rather than trying to debug this, I'd suggest having a re-think. The result requires ten digits, which is too big for a 32-bit integer, but will fit within a type double or a long long. If you use the latter, then a simple loop can be used to calculate n^n and use the mod operator % to limit the number of digits to no more than 10. You should be able to get a solution which takes less than 1 second to execute. Type double also would work, if you use the fmod() function in place of the % operator.
http://www.cplusplus.com/reference/cmath/fmod/

[khengol khan]

Rather than trying to debug this, I'd suggest having a re-think. The result requires ten digits, which is too big for a 32-bit integer, but will fit within a type double or a long long. If you use the latter, then a simple loop can be used to calculate n^n and use the mod operator % to limit the number of digits to no more than 10.

It seems to be helpful But Can you help me with debugging this?!? I dont know where my mistake is?!?

[Chervil]

Can you help me with debugging this?

Without comments or meaningful variable names, the code is very hard to understand. That's why I didn't debug it - the algorithm or method in use isn't clear to me.

[khengol khan]

Really Really Really Helpful!! Tnx ;)

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	unsigned long long sum=0;
	int i,count;
for(i=1;i<=1000;i++){
	unsigned long long n=1;
	for(count=1;count<=i;count++){
		n*=i;
		n=fmod(n,10000000000);
	}
	sum+=n;
}
cout<<sum%10000000000;
}

9110846700

[khengol khan]

about the previous code :

#include <iostream>
using namespace std;
int main(){
	int a[1000][12],i,j,count,m,n,sum[12]={0,0,0,0,0,0,0,0,0,0,0,0}; // an array for each integer
	for(i=0;i<=999;i++){
		a[i][11]=1;                    // all of the array for each integer is filled
		for(j=0;j<=10;j++) a[i][j]=0;  // with 0 , except last one filled with 1
	}
for(i=1;i<=1000;i++){
	for(count=1;count<=i;count++){ // each of the integer x multiplied x time     
		for(j=0;j<=11;j++){
			a[i-1][j]*=i;
			for(m=0;m<=999;m++){        // in this for structure 
				for(n=11;n>=0;n--){     // while an integer in the arrat is greater than 10  
					while(a[m][n]>=10){ // reduce while it becomes less than 10
						a[m][n-1]++;
						a[m][n]-=10;
					}
				}
			}
		}
	}
}
for(j=11;j>=2;j--){    // adding all of the 1000 array ;
   for(i=0;i<=999;i++){
	sum[j]+=a[i][j];
	}
}
for(j=11;j>=0;j--){   // reducing each integer in array while it becomes less than 10
	while(sum[j]>=10){
		sum[j-1]++;
		sum[j]-=10;
	}
}
for(i=2;i<=11;i++)  cout<<sum[i]<<" ";
cout<<endl<<sum[0]<< "  "<<sum[1];
}

[JLBorges]

> find the last ten digits
> the correct answer is 9110846700

Use modular arithmetic on unsigned long long with 10000000000 as the divisor.

(a*b) % c = ( (a%c) * (b%c) ) % c
(a+b) % c = ( (a%c) + (b%c) ) % c

Brute force:

#include <iostream>

int main()
{
    constexpr unsigned long long DIVISOR_10_DIGITS = 10000000000 ;
    unsigned long long result = 0;

    for( unsigned int n = 1 ; n < 1001 ; ++n )
    {
        unsigned long long n_pow_n = n ;
        for( unsigned int i = 1 ; i<n ; ++i )
        {
            n_pow_n *= n ;
            n_pow_n %= DIVISOR_10_DIGITS ;
        }

        result += n_pow_n ;
        result %= DIVISOR_10_DIGITS ;
    }

    std::cout << "last 10 digits: " << result << '\n' ;
}

http://coliru.stacked-crooked.com/a/0216222930770da4

[Chervil]

The original code was accessing an array element out of bounds.

                for(n=11;n>=0;n--){     // while an integer in the arrat is greater than 10  
                    while(a[m][n]>=10){ // reduce while it becomes less than 10
                        a[m][n-1]++;
                        a[m][n]-=10;
                    }
                }

Look at line 14, n will take each value from 11 to 0 inclusive.
Now see line 16, a[m][n-1]++;, when n is zero, this is accessing
a[m][-1]++; The negative subscript will update some adjacent element of the array, corrupting its value.

Solution, change n>=0 to n>0

                for(n=11;n>0;n--){     // while an integer in the arrat is greater than 10  
                    while(a[m][n]>=10){ // reduce while it becomes less than 10
                        a[m][n-1]++;
                        a[m][n]-=10;
                    }
                }

[khengol khan]

Done! ;) Tnx

i was so depressed for thiis! :D