Help !!!

ministerot's Avatar, Join Date: Jan 2008
Newbie Member
Hi

is there any way to speed up my program
it needs to find:
The first smallest number who's factorial is bigger or equal to the inputed number
first we input the number of test cases
ex.
input
3
1
101
2008
output
1
70
811

should i use some other data structure(tree or something) than dynamic array??

Code:
#include <math.h>
#include <stdio.h>
#include <stdlib.h> 

int main()
{  
int i=0,br,t=0,br_cif;          
int *a= (int*)malloc(sizeof(int)*205019);
scanf("%d",&t);

float dig=0.0;           //for log10
for (i = 1; i <=205019; i++)    
{
         dig +=log10(i);
         a[i]=(int)floor(dig)+1;      //aproximation
}

while(t--){
scanf("%d", &br);
i=1;
          //we search for the first number
while(1){                
             if(a[i]>=br) {printf("%d\n",i);break;}
            i++ ;
            }


}  
return 0;
}
0
Salem's Avatar, Join Date: Nov 2007
Ambitious contributor
Well the number of factorials you can store in a 32-bit int is pretty small. Perhaps a lookup table and a search would be better?
0
ministerot's Avatar, Join Date: Jan 2008
Newbie Member
Quote:
Originally Posted by Salem
Well the number of factorials you can store in a 32-bit int is pretty small. Perhaps a lookup table and a search would be better?
YES but I dont store the numbers of a factorials,
but the number of the digits of the factorial.

I don't know how to search the array any faster beacuse i need THE SMALLESET INTEGER WOES FACTORIAL IS GREATHER THAN OR EQUAL TO THE INPUTET NUMBER.
0
Salem's Avatar, Join Date: Nov 2007
Ambitious contributor
Since your array is sorted, I guess you could use the bsearch() function in stdlib.h to search the array a lot quicker than a linear search would do.

> for (i = 1; i <=205019; i++)
Arrays start at 0, not 1
They also end at 1 step before the array length, so use <, not <=

> int *a= (int*)malloc(sizeof(int)*205019);
If this really is a C program, then the cast is unnecessary.
http://faq.cprogramming.com/cgi-bin/...&id=1043284351
If you remove the cast, and get something about casting void*, then you're compiling your C program with a C++ compiler. Adjust your tools to do the right thing, not maul the code to make it fit.

There's no need to shout.
http://www.catb.org/~esr/faqs/smart-...html#writewell
0
oogabooga's Avatar
Ambitious contributor
Quote:
Originally Posted by ministerot
is there any way to speed up my program
A couple of questions:
  1. Does your program run?
  2. How long does it take to run?
  3. Does it get the correct results?
  4. Why are you storing the "number of digits" of factorials?
  5. Where does the number 205019 come from?