1.11M Members

Calculating powers of 2

 
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

 
0
 

My time limit is 5.5 seconds.

 
0
 

My time limit is 5.5 seconds.

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

 
-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?

 
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.

 
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.

 
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 six months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: