Page 8 of 13
Posted: Fri Jul 07, 2006 6:27 pm
by 898989
Salamo Aleko
It is an advice: Implement your factorial function far from your big integer class. I do this problem * and my code about 20 line, and i can generate up to 1250! in time less than 1 second
This come from working in result in the same time. No more calls(one function).
As for my code [Asume multiplying 12560 * 9]
First will number in an array but reversed
int arr[MAX]
09521 //assume 0 in arr[0], 9 in arr[1], .....1 in arr[4]
9
//I will start to multiple direct on them
so 0 81 45 18 9 //0 in arr[0], 81 in arr[1], 45 in arr[2]......
Now if arr
>=10 -->arr[i+1]=arr/10, arr %= 10;
So we get
013311 reverse it to get 113310 [Use this idea in factorial multipicatio]
In any case this is set of input & ouput
Code: Select all
Input
0
10
100
20
50
22
133
500
999
Code: Select all
output
0!
1
10!
3628800
100!
93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000
20!
2432902008176640000
50!
30414093201713378043612608166064768844377641568960512000000000000
22!
1124000727777607680000
133!
14872707060906857289084508911813048098675809251055070300508818286592035566485075
75438808212467157184170279331708196003716652524636892470053753828294811730174131
7436012998958826217903503076596121600000000000000000000000000000000
500!
12201368259911100687012387854230469262535743428031928421924135883858453731538819
97605496447502203281863013616477148203584163378722078177200480785205159329285477
90757193933060377296085908627042917454788242491272634430567017327076946106280231
04526442188787894657547771498634943677810376442740338273653974713864778784954384
89595537537990423241061271326984327745715546309977202781014561081188373709531016
35632443298702956389662891165897476957208792692887128178007026517450776841071962
43903943225364226052349458501299185715012487069615681416253590566934238130088562
49246891564126775654481886506593847951775360894005745238940335798476363944905313
06232374906644504882466507594673586207463792518420045936969298102226397195259719
09452178233317569345815085523328207628200234026269078983424517120062077146409794
56116127629145951237229913340169552363850942885592018727433795173014586357570828
35578015873543276888868012039988238470215146760544540766353598417443048012893831
38968816394874696588175045069263653381750554781286400000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000
999!
40238726007709377354370243392300398571937486421071463254379991042993851239862902
05920442084869694048004799886101971960586316668729948085589013238296699445909974
24504087073759918823627727188732519779505950995276120874975462497043601418278094
64649629105639388743788648733711918104582578364784997701247663288983595573543251
31853239584630755574091142624174743493475534286465766116677973966688202912073791
43853719588249808126867838374559731746136085379534524221586593201928090878297308
43139284440328123155861103697680135730421616874760967587134831202547858932076716
91324484262361314125087802080002616831510273418279777047846358681701643650241536
91398281264810213092761244896359928705114964975419909342221566832572080821333186
11681155361583654698404670897560290095053761647584772842188967964624494516076535
34081989013854424879849599533191017233555566021394503997362807501378376153071277
61926849034352625200015888535147331611702103968175921510907788019393178114194545
25722386554146106289218796022383897147608850627686296714667469756291123408243920
81601537808898939645182632436716167621791689097799119037540312746222899880051954
44414282012187361745992642956581746628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422614397428693306169089796848259012
54583271682264580665267699586526822728070757813918581788896522081643483448259932
66043367660176999612831860788386150279465955131156552036093988180612138558600301
43569452722420634463179746059468257310379008402443243846565724501440282188525247
09351906209290231364932734975655139587205596542287497740114133469627154228458623
77387538230483865688976461927383814900140767310446640259899490222221765904339901
88601856652648506179970235619389701786004081188972991831102117122984590164192106
88843871218556461249607987229085192968193723886426148396573822911231250241866493
53143970137428531926649875337218940694281434118520158014123344828015051399694290
15348307764456909907315243327828826986460278986432113908350621709500259738986355
42771967428222487575867657523442202075736305694988250879689281627538488633969099
59826280956121450994871701244516461260379029309120889086942028510640182154399457
15680594187274899809425474217358240106367740459574178516082923013535808184009699
63725242305608559037006242712434169090041536901059339838357779394109700277534720
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000
Posted: Fri Jul 07, 2006 10:44 pm
by Darko
There is no reason why you couldn't keep an array of groups of digits, it is a bit faster. I did it using 4 digits, so their product still fits in 32-bits, but for this purpose you can deal with 8-digit blocks and just replace "/10" and "%10" with "/10^8" and "%10^8".
thanks alot
Posted: Sat Jul 08, 2006 3:36 pm
by bidol
898989,
your idea looks, very impresive... ^^... i'll try it~
Have you checked...
Posted: Mon Aug 14, 2006 8:09 pm
by milacao
Hi Thomas,
I don't have time to look at your code in depth, but, have you checked if it works with 0? It happened to me and when I changed it, I got AC
Regards.
how can i calculate 500!
Posted: Mon Aug 28, 2006 11:20 am
by newton
Thank you
Re: how can i calculate 500!
Posted: Wed Aug 30, 2006 12:17 am
by Martin Macko
What problem is your question about? If you're not asking a question about a problem from
this problemset and have a question about some algorithms, use the
Algorithms forum.
Posted: Wed Aug 30, 2006 7:19 am
by Tanu
all programmer have to spend some time with big integer...
it is the earlier step of them...
actually the problem is not upto 500!
the limit is 1000!
consider the number as string back to the child age and
use the way we learn to multyply....
use array for storing answers...
hope it helps...
Posted: Thu Aug 31, 2006 6:06 am
by newton
thanks for your encouragement.
i am trying.........
623- Compile Error
Posted: Fri Sep 01, 2006 4:16 pm
by phoenix7
why I got compile error?
Code: Select all
import java.io.*;
import java.util.*;
import java.math.BigInteger;
class Main
{
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point
}
void Begin()
{
String input;
//int a, b, min, max, num, n, cycle, cyclemax;
while ((input = Five.ReadLn (255)) != null) {
int n = Integer.parseInt(input);
BigInteger f = BigInteger.ONE;
for(int i = 1; i <= n; i ++)
f = f.multiply(new BigInteger(String.valueOf(i)));
System.out.println(n + "!");
System.out.println(f);
}
}
}
[/code]
Posted: Fri Sep 01, 2006 6:01 pm
by Vexorian
If you provided your email address when registering you should have gotten an email message telling you the exact position of the compile error and explanation.
You probably should read the java submitting documentation on restricted / missing classes and the such.
OJ uses GCJ to compile, GCJ is a free implementation of JAVA that has some missing classes in its library. You should try to get it and test your OJ programs there instead of JDK to avoid getting surprise compile errors when submitting.
Some friends of mine that use JAVA told me that some extra blank lines are required after the last } , but I cannot confirm that.
Posted: Fri Sep 01, 2006 7:20 pm
by phoenix7
it said the error is here |
\/
Posted: Fri Sep 01, 2006 7:40 pm
by Vexorian
well then the BigInteger class is missing there, so you have to code your own bigint class.
Posted: Wed Oct 11, 2006 9:27 pm
by dev_sust
hi,
I wrote a code to find factorial of max 1000. I pre calculate 1000! for avoiding TLE.
i used a large structure to store ans of 1!-1000!.
prob 1:
It works when the structure is less or
equal than 143 in my pc. (i m using borland 5). but if sz2>=144 then the EXE
terminates automically.
/* Even "Thread stoped.... fault: access violation", such kind of msg is not showed!*/
whats the problem? MLE?
prob 2:
i used a function to copy bignum. it does nt work. If i use it the prog terminates automically.
even if the sz2<=143. but another function of bignum such add, multiply, minus work properly.
whats the problem of the function "bigcopy"?
here is my code:
Code: Select all
#include <stdio.h>
//#include <conio.h>
//#include <time.h>
//#include <mem.h> // for multiply
#include <string.h>
#define sz 3000 //works when 142
#define sz2 1001
typedef struct
{
long int len;
char digit[sz];
long int sign;
}bignum;
bignum fl[sz2];
bignum bigin(int *p);
void bigout( bignum a);
bignum rev( bignum a);
bignum fact( void);
bignum multilong(bignum a, long int n);
bignum bigcopy(bignum a);
int main()
{
//freopen("a.txt","w", stdout);
//printf("hisss");
int tx=1;
int *tagx=&tx;
bignum ans;
long int n;
//printf("hi");
//getch();
// clock_t start, end;
//start = clock();
ans=fact();
// end = clock();
// printf("The time was: %f\n", (end - start) / CLK_TCK);
//getch(); getch(); getch(); getch(); printf("hi2"); getch(); getch();getch();getch(); printf("hiY");
while(scanf("\n%ld", &n)==1)
{
// printf("hiX=");
printf("%ld!\n", n);
bigout(fl[n]);
printf("\n");
}
// printf("hiZ"); getch(); getch();
return 0;
}
bignum fact( void)
{
long int n=sz2;
bignum result;
long int i, j;
result.digit[0]=1;
result.len=1;
result.sign=1;
// printf("hi3 %ld ", i=0);
for (i=1; i<=n; i++)
{
result=multilong( result, i);
// fl[i]=bigcopy(result);
fl[i].len=result.len;
fl[i].sign=result.sign;
for(j=0; j<result.len; j++)
fl[i].digit[j]=result.digit[j];
}
// bigout();
// printf("hi3 %ld ", i); getch();
return (result);
}
bignum bigcopy(bignum a)
{
bignum res;
long int i;
res.len=a.len;
res.sign=a.sign;
for(i=0; i<a.len; i++)
res.digit[i]=a.digit[i];
//printf(" hi4 ");
return ( res);
//return ( a);
}
bignum bigin(int *p)
{
bignum a;
char str[sz];
long int ln, i; //printf(" hi5 ");
if(scanf("%s", str)==1)
{
ln=strlen(str);
a.len=ln;
a.sign=1; // agnored (-)
for(i=0; i<ln; i++)
a.digit[i]=str[i]-'0';
*p=1;
return a;
}
else
{
*p=0;
return a;
}
}
void bigout(bignum a)
{
long int i; //printf(" hi6 ");
if(a.sign==-1)
printf("-");
for(i=0; i<a.len; i++)
printf("%c", a.digit[i]+'0');
}
bignum rev( bignum a)
{
long int ln, lim, i, temp;
//printf(" hi7 ");
ln=a.len;
lim=ln/2;
for(i=0; i< lim; i++)
{
temp=a.digit[i];
a.digit[i]=a.digit[ln-1-i];
a.digit[ln-1-i]=temp;
}
return (a);
}
bignum multilong(bignum a, long int n)
{
bignum res;
long int carry, i, k;
for(i=a.len-1, carry=0, k=0; i>=0; i--)
{
res.digit[k++]=(a.digit[i]*n+carry)%10;
carry=(a.digit[i]*n+carry)/10;
}
while(carry>0)
{
res.digit[k++]=carry%10;
carry=carry/10;
}
//printf("hi9");
res.len=k;
if(a.sign*n>=0) // should be modified for '-'
res.sign=1;
else
res.sign=-1;
res=rev(res);
return(res);
}
Posted: Fri Dec 01, 2006 6:10 pm
by marif
Just use a string array for storing your pre-calculated factorials value. In this way u'r array size will smaller.
Posted: Fri Dec 08, 2006 7:01 am
by sakhassan
Can anyone give me the correct output for factorial 800! & 987!
Thanks in advance!!