There is probably a joke in the comment that I am missing
but this post is going to give the design approaches to solving
the problem posed by FirstPerson in his signature:
find the last ten digits of
x^x (x raised to the power of x)
for all the positive 0dd numbers below 1000
1^1 + 3^3 + 5^5 ..... +997^997 + 999^999
The first thing to realise is that this is a
computationally small problem and the complete
answer can be found it just requires a ~million digits :)
If you only want the bottom 10 digits and only adding and multiplying
^x is like multiplying x times
you only care about the last 10 digits of any number you are using
temporary or otherwise
Some of you may not know why due to multiplication being taught
wrongly at school. It is easy enough for anyone
to do a 99-digit by 99-digit multiplication only writing down the
answer ;)
This is done the way that a computer can be used to find the exact answer
consider
12345678
x30978793
the answer can be found a digit at a time:
if you reverse one of the numbers
30978793 -> 39787903
then the last digit of the answer is:
12345678
|
39787903
is the last digit of 8 * 3 = 24
so a 4 then we have a 2 that we need to carry:
shift the numbers along by one to find next digit
carry - 2
12345678
||
39787903
and the next digit is the last of
2 + 7*3 + 8*9 = 95
5 and then there is a carry 9
shift the numbers along by one
carry - 9
12345678
|||
39787903
9 + 6*3 + 7*9 + 8*7 = 146
6 carry 14
keep going until the final digit
12345678
|
39787903
and you get the answer:
382454203206654
and as you can see the last 3 digits are as we thought
654
this shows that for multiplication it is only the last 10
digits that can affect the the last ten digits
Now back to the problem there are 3 approaches to consider:
1 - simple
2 - standard maths +
3 - bat out of hell
Using the above maths I am going to give a simple solution
We need a special class to keep track of the last 10 digits
and the minimal representation of it is as follows:
main shows the problem
#include "ten_digits.h"
#include <iostream>
int main()
{
ten_digits sum(0, 0);
for(int i(1); i < 1000; ++i)
{
if(i%2 == 1)
{
ten_digits self_power(0, i);
self_power.raise_to_power(i - 1);//already had one power
sum += self_power;
}
}
std::cout << sum.get_display_string() << std::endl;
return 0;
}now in practice you would test ten_digits first
here is the .h
/*int cannot guarantee ten digits
this is a partial class
chopping top 5 & bottom 5
*/
#pragma once
#include <string>
class ten_digits
{
public:
ten_digits(int upper = 0, int lower = 0);
ten_digits & operator+=(const ten_digits &td);
void times_by(int small_int);
bool raise_to_power(int pow);
std::string get_display_string() const;
int get_ones() const {return ones;}
int get_hundred_thousands() const {return hundred_thousands;}
private:
int hundred_thousands, ones;
const int i_100000;
};this is needed as a 32 bit int is to small for 10 digits and a long
won't work directly for a*b%10000000000 without a potential overflow