Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forumdisplay.php?f=20)
-   -   Help !!! (http://www.go4expert.com/showthread.php?t=8346)

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


All times are GMT +5.5. The time now is 19:34.