Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Help !!! (http://www.go4expert.com/forums/help-t8346/)

 ministerot 19Jan2008 18:55

Help !!!

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; }```

 Salem 19Jan2008 23:09

Re: Help !!!

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?

 ministerot 20Jan2008 04:55

Re: Help !!!

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.

 Salem 20Jan2008 21:36

Re: Help !!!

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

 oogabooga 20Jan2008 23:06

Re: Help !!!

Quote:
 Originally Posted by ministerot is there any way to speed up my program
A couple of questions: