Member Avatar for swissknife007

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

  • 3 Contributors
  • 6 Replies
  • 247 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by histrungalot

Dani AI

Generated

The original approach works but wastes a lot of time by (a) using a single decimal digit per array cell, (b) scanning/zeroing the whole 16604-array on every multiply, and (c) recomputing from 1 for every test case. already spotted the out‑of‑bounds index and the digit-count optimization; those are correct and should be applied. The next step is to reduce the inner-loop work by storing many decimal digits per limb and by reusing work across test cases.

Use a large base (for example BASE = 1000000000) with little‑endian limbs in a vector<uint32_t>. Doubling becomes cheap: iterate only the currently used limbs, do a 64‑bit multiply/add, and set carry with a compare/subtract instead of slow division/modulo. Example sketch (C++):

const uint32_t BASE = 1000000000;
vector<uint32_t> a(1,1);             // little-endian limbs, a[0] = 1
for (int step = 0; step < n; ++step) {
  uint64_t carry = 0;
  for (size_t i = 0; i < a.size(); ++i) {
    uint64_t x = (uint64_t)a[i] * 2 + carry;
    if (x >= BASE) { a[i] = (uint32_t)(x - BASE); carry = 1; }
    else { a[i] = (uint32_t)x; carry = 0; }
  }
  if (carry) a.push_back((uint32_t)carry);
}

Practical extras that matter under a 5.5s limit:

  • Read all test cases, sort them by exponent ascending (keep original indices), then compute powers incrementally up to each requested n and emit results — avoids repeating work.
  • Reserve vector capacity once using an estimate: limbs ≈ ceil((n*log10(2))/9)+1.
  • Print limbs with printf("%u", a.back()) for the most significant limb and printf("%09u", a[i]) for the others to avoid slow per-digit printing.
  • Use fast I/O (ios::sync_with_stdio(false) / cin.tie(nullptr) or fread/fwrite) to cut I/O overhead.

If only a few huge exponents must be computed, consider a big‑integer library (boost::multiprecision or GMP) or asymptotically faster multiplication (Karatsuba/FFT) via exponentiation by squaring — but for typical contest inputs the base‑1e9 + reuse strategy will be the simplest, fastest fix.

Recommended Answers

All 6 Replies

Member Avatar for swissknife007

My time limit is 5.5 seconds.

Member Avatar for swissknife007

My time limit is 5.5 seconds.

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

Member Avatar for -[xxxxxxx]-

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 for swissknife007

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 for histrungalot

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 for histrungalot

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;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.