Author |
Topic: First and Last k digit of n power n (Read 5316 times) |
|
johny_cage
Full Member
Gender: 
Posts: 155
|
 |
First and Last k digit of n power n
« on: Mar 3rd, 2009, 8:45am » |
 Quote  Modify
|
Find first and last k digits of nn, where 1 <= k <= 9 and n <= 109
|
| « Last Edit: Mar 3rd, 2009, 9:04am by johny_cage » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: First and Last k digit of n power n
« Reply #1 on: Mar 3rd, 2009, 8:50am » |
Quote Modify
|
The last k digits are easily gotten by using modular arithmetic and powerdoubling.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: First and Last k digit of n power n
« Reply #2 on: Mar 3rd, 2009, 9:04am » |
Quote Modify
|
And what about first k digits ?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: First and Last k digit of n power n
« Reply #3 on: Mar 3rd, 2009, 10:24am » |
Quote Modify
|
The first k digits can be calculated by taking a sufficiently precise logarithm of n, multiplying by n, and taking the exponential of the result, but I'd have to look up what "sufficiently precise" is. Didn't we have a thread on that a while back?
Edit: I was thinking of this thread over in Putnam.
Edit 2: If I'm understanding what I'm reading, double-precision floating point should be good enough (although maybe not quite for both large n and large k), so
(unsigned long)floor(pow(10.0, modf(n*log10((double)n), &dummy) + k - 1))
should get you the first k digits of nn unless both n and k are near the given limits.
--SMQ
|
| « Last Edit: Mar 3rd, 2009, 10:37am by SMQ » |
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: First and Last k digit of n power n
« Reply #4 on: Mar 4th, 2009, 2:11am » |
Quote Modify
|
If n ~ 109, and you need the fractional part of n log n to 9 digits, then you need log n to 18 digits. Maybe long double is enough.
Or compute nn as if you were using big ints, but only keep track of the first so many digits. Something like this:
Code:
#define S 4
#define MOD 1000000000
int X[S], Y[S], T[2*S];
void mult(int* X, int* Y) {
int i,j;
long long t;
memset(T,0,sizeof(T));
for(i=0;i<S;i++) {
for(t=j=0;j<S;j++) {
t+=T[i+j]+((long long)X[i])*Y[j];
T[i+j]=t%MOD;
t/=MOD;
}
T[i+j]=t;
}
for(i=2*S-1; i && !T[i]; i--);
if(i<S) for(j=0;j<S;j++) X[j]=T[j];
else for(j=0;j<S;j++) X[j]=T[j+i-S+1];
}
void pw(int* X, int n, int* Y) {
int i,j,k;
Y[0]=1; for(i=1;i<S;i++) Y[i]=0;
while(n) {
if(n&1) mult(Y,X);
mult(X,X);
n>>=1;
}
}
int main() {
int i,n;
double t;
while(scanf("%d",&n)==1) {
memset(X,0,sizeof(X));
X[0]=n;
pw(X,n,Y);
for(i=S-1;i && !Y[i];i--);
printf("%d",Y[i]);
while(i--) printf("%09d",Y[i]);
printf("\n");
}
}
|
|
S=3 should be enough for 9 correct digits, but I'd make it 4 to be on the safe side.
|
| « Last Edit: Mar 4th, 2009, 2:20am by Eigenray » |
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: First and Last k digit of n power n
« Reply #5 on: Mar 4th, 2009, 8:53am » |
Quote Modify
|
Eigenray
Nice code buddy 
Can you provide the same logic for finding the last k digits of the number nn.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: First and Last k digit of n power n
« Reply #6 on: Mar 4th, 2009, 9:26am » |
Quote Modify
|
on Mar 4th, 2009, 8:53am, johny_cage wrote:| Can you provide the same logic for finding the last k digits of the number nn. |
|
Code:int foo(int n, int k)
{
int m=1;
for(; k > 0; k--) m*=10;
int r=1, t=n % m;
while(n)
{
if (n % 2)
r = r * t % m;
t = t * t % m;
n >>= 1;
}
return r;
} |
|
|
| « Last Edit: Mar 4th, 2009, 9:27am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: First and Last k digit of n power n
« Reply #7 on: Mar 4th, 2009, 8:52pm » |
Quote Modify
|
@towr
int foo(int n, int k)
Quote:
What is the MAX value of n and k , it can give the valid result ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: First and Last k digit of n power n
« Reply #8 on: Mar 5th, 2009, 12:45am » |
Quote Modify
|
on Mar 4th, 2009, 8:52pm, nks wrote:| What is the MAX value of n and k , it can give the valid result ? |
|
Depends on the size of the ints. n  MAX_INT, k 1/2 10log MAX_INT
|
| « Last Edit: Mar 5th, 2009, 12:46am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: First and Last k digit of n power n
« Reply #9 on: Nov 26th, 2009, 3:52am » |
Quote Modify
|
Can somebody explain Eigenray's solution please
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
serenity
Newbie
Posts: 25
|
|
Re: First and Last k digit of n power n
« Reply #10 on: Apr 23rd, 2010, 2:17am » |
Quote Modify
|
can someone explain eigenray solution please 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7528
|
|
Re: First and Last k digit of n power n
« Reply #11 on: May 3rd, 2010, 1:43am » |
Quote Modify
|
Eigenray used large-number but limited-precision arithmetic.
A number is stored in an array of int's, with 9 digits per int. The arrays are of a fixed size S. So, an (int*) in his code represents an integer of up to 9*S = 36 digits.
mult(X,Y) multiplies X by Y, result in X.
It is impemented pretty much as you would multiply a decimal number by hand. Every X[i] is multiplied by every Y[j] and added to T[i+j]. The variable t is used to carry over the overflow to the next higher column, i.e. T[i+j+1].
If the result does not fit in S integers, he keeps only the first S integers. Normally, you would track the exponent, i.e. how many times the number was shifted, but for this problem, it is not necessary.
The power is computed by combining squaring and multiplying. Any power of y can be computed by combining x=x2 and x=x·y.
For example, to compute x10 you do:
x = 1 (=y0)
x = x·y (=y1)
x = x2 (=y2)
x = x2 (=y4)
x = x·y (=y5)
x = x2 (=y10)
What is missing from Eigenray's solution is an evaluation of the error in the final result. In the worst case, his multiplication has a relative error of 1e-(9(S-1)). (or 1e-27 for S=4). Every multiplication adds that much to the possible error, and every squaring doubles the relative error.
(X(1+e))2 ~ X2(1+2e)
In short, the relative error is
n * 1e-(9(S-1))
Before betting your life on the result, (for instance if it makes the difference between marrying the sultan's daughter or getting executed), multiply the result by n * 109(S-1), add that to the result and trust only the part that doesn't change.
Roughly, for S=4 and n=1000000, trust only the first 27-4 = 21 digits.
|
| « Last Edit: May 3rd, 2010, 1:44am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print