1,105,556 Community Members

Calculating powers of 2

Member Avatar
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 3 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I am making a program to store all the powers of 2(1,2,4,8...) till 2 ^50000.
Although I am getting the answer,I am not getting my answer in the required time limit.
Any suggestions?
How should I store the numbers?
Here is my stupid code as of now

#include<stdio.h>
#include<math.h>
#include<string.h>
int bin[16604];
 
int main()
{
    int n;
int t,i,j;
scanf("%d",&t);
while(t--){
    scanf("%d",&n);
    for(i=0;i<16604;i++)
{
    bin[i]=0;
}
bin[16603]=1;
//bin[4]=3;
int temp=0,x=0;
for( j=1;j<=n;j++)
{
    for(i=16604;i>=0;i--)
{
    temp=bin[i]*2+x;
   bin[i]=temp%10;
   x=temp/10;
//   printf("temp %d x %d bin[i] %d\n",temp,x,bin[i]);
}
temp=0;x=0;
}
int j;
for( j=0;j<16604;j++)
if(bin[j])
break;
 
for( i=j;i<16604;i++)
{
    printf("%d",bin[i]);
 
 
} //printf("%d",sum[n]);
 
 
 
 
   putchar('\n');
}
  return 0;
}

Here t is my number of test cases....
Here n is the number whose 2^n I am displaying.
Eg
2
10
1024
5
32

Member Avatar
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 3 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

My time limit is 5.5 seconds.

Member Avatar
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 3 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

My time limit is 5.5 seconds.

Please any suggestion is highly welcomed...It means the world to me.

Member Avatar
-[xxxxxxx]-
Newbie Poster
8 posts since Mar 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 1 [?]
Skill Endorsements: 0 [?]
 
-1
 

You know that your program can't reach that far because of the integer overflowing problem. Actually this program can be done within one for-loop.
Also, i think you can take away the second scanf() out of that while-loop, can you?

Member Avatar
swissknife007
Junior Poster in Training
74 posts since Oct 2008
Reputation Points: 3 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

You know that your program can't reach that far because of the integer overflowing problem. Actually this program can be done within one for-loop.
Also, i think you can take away the second scanf() out of that while-loop, can you?

Where am i using integers to have an integer overflow,obviously u didn't understand the code it seems.
My code is displaying 2^50000 correctly.
The problem is with the efficiency part of it.

Member Avatar
histrungalot
Posting Whiz in Training
280 posts since May 2008
Reputation Points: 32 [?]
Q&As Helped to Solve: 36 [?]
Skill Endorsements: 3 [?]
 
1
 

Line 22 should be for(i=16603;i>=0;i--) because bin has 16604 elements. 
As for the speed up, you don't have to loop over all 16604 (in that same for loop) elements because the number of digits in the number 2^n is n*log10(2). Only go to the ceil(n*log10(2)) in the for loop. That should help.

Member Avatar
histrungalot
Posting Whiz in Training
280 posts since May 2008
Reputation Points: 32 [?]
Q&As Helped to Solve: 36 [?]
Skill Endorsements: 3 [?]
 
0
 

Its not perfect but here is the difference without optimization

$ ./yourCode
1
50000
Time: 9.03527 sec <---------- Your time
$ ./myChanges
1
50000
Time: 3.43095 sec  <---------- Changes time

With -O3

$ ./yourCodeWith-O3
1
50000
Time: 3.48640 sec  <---------- Your time
$ ./myChangesWith-O3
1
50000
Time: 1.52436 sec  <---------- Changes time
#include<stdio.h>
#include<math.h>
#include<string.h>
#include <sys/time.h>

int bin[16604];
 
int main()
{
    int n,t,i,j,lower;
    struct timeval a,b;
    scanf("%d",&t);
    while(t--){
       scanf("%d",&n);
       memset(bin,0,sizeof(bin));
       bin[0]=1;
       int temp=0,x=0;
gettimeofday(&b,NULL);
       for( j=1;j<=n;j++){
         lower=(int)(ceil(j*log10(2)));
         for(i=0;i<lower;i++) {
           temp=(bin[i]<<1)|x;
           bin[i]=temp%10;
           x=temp>9;
         }
         x=0;
       }
gettimeofday(&a,NULL);
       for( i=(lower-1);i>=0;i--) {
          printf("%d",bin[i]);
       } 
       putchar('\n');
printf("Time: %.5f sec\n",(float)((a.tv_sec*1e6+a.tv_usec)-(b.tv_sec*1e6+b.tv_usec))/1e6);
   }
  return 0;
}
You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: