factorial

big number factorial

Page 1 of 1

11 Replies - 5748 Views - Last Post: 24 March 2007 - 05:59 PM

#1 vennik  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 07

factorial

Posted 17 March 2007 - 04:26 AM

Hello,
I search efective algorithm for calculating factorial of big number (f.e. 1000 or even more). It is not easy task, because the result is very huge. I have written some program in C# that calculate it (you can see it here: http://www.geocities...olov/b_n_f.htm), but I think that there is more efficiently decision of the problem (especially regading time consuming). Thank you in advance.

Is This A Good Question/Topic? 0
  • +

Replies To: factorial

#2 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 204
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: factorial

Posted 17 March 2007 - 05:15 AM

in practice large factorials are not calculated becasue they must traverse each element. There are method to estimate large factorials accurately, as well as using prime factorization to calculate precisely, but these are large algorithms and very complicated.

why do you need 1000 factorial?
Was This Post Helpful? 0
  • +
  • -

#3 vennik  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 07

Re: factorial

Posted 17 March 2007 - 06:59 AM

View PostWilliam_Wilson, on 17 Mar, 2007 - 05:15 AM, said:

in practice large factorials are not calculated becasue they must traverse each element. There are method to estimate large factorials accurately, as well as using prime factorization to calculate precisely, but these are large algorithms and very complicated.

why do you need 1000 factorial?


I need to calculate factorial in my job, there is real situation to reach value near to 1000. Do you know where I could find more information for the methods you are talking about?
Was This Post Helpful? 0
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2246
  • View blog
  • Posts: 9,236
  • Joined: 18-February 07

Re: factorial

Posted 17 March 2007 - 10:25 PM

well lets see mathematica does 1000! is well less then 1 second on my 2Ghz pc (my machine is very slow and old).

You are right that there are faster algorithems then just the standard recursive ones.

Now these numbers don't fit into a double: 1000! ruffly = 4.0238726x10^2567

so you need to think about the format you want the number in as that has a lot to do with how you will construct the algorithm.

I know of two aproches. One is to view the thing as a polynomial and use the polynomial algorithm. The other does a ruff and dirty factorization and uses the pow() function to cut down on the multiplications.
Was This Post Helpful? 0
  • +
  • -

#5 vennik  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 07

Re: factorial

Posted 18 March 2007 - 03:25 AM

I use polymonial wrote multiplier and the product is in kind shown below:
Z=X.Y=X.(y(n-1).10^(n-1)+y(n-2).10^(n-2)+...+y(1).10^1+y(0).10^(0))=X.y(n-2).10^(n-2)+X.y(n-3).10^(n-3)+...+X.y(1).10^(1)+X.y(0).2^(0)
y(i) is consequtive digit of multiplier in n digits decimal area(i=0 is junior, i=n-1 is senior digit). The count of addends is equals to digits of the multiplier. The scheme I use is:

-------> ------>
---------------------- -----------------------------
| | | | |
---------------------- -----------------------------
transitory sum multiplier |-> y(i)
+
----------------------
| |
----------------------
multiplicant

in every step is forming product ((multiplicant).y(i)) and add the result to the current transitory sum (in the beggining transitory sum is 0), after that I shift transitory sum and multiplier one digit rigth-hand side and the operation repeate. After consideration of all multiplier digits, the transitory sum is final result.
In that way I forming multiplication to calculate factorial, but transitory sum grow bigger ang bigger and I use string for its representation. When I need to process it I work in portions that could be represent in C# long int type, and after that every portion is again transfrom in string that is put into string represented transitory sum. Moreover multiplier and multiplicant grow up too in the process of factorial calculation, so I need to represent them like a strings too. Frequently transform from string to long int data type and back into the string is slow. But in truth also maybe I could consider some other algorithm to calculate factorial. But I need it to be accurate (not round).



View PostNickDMax, on 17 Mar, 2007 - 10:25 PM, said:

well lets see mathematica does 1000! is well less then 1 second on my 2Ghz pc (my machine is very slow and old).

You are right that there are faster algorithems then just the standard recursive ones.

Now these numbers don't fit into a double: 1000! ruffly = 4.0238726x10^2567

so you need to think about the format you want the number in as that has a lot to do with how you will construct the algorithm.

I know of two aproches. One is to view the thing as a polynomial and use the polynomial algorithm. The other does a ruff and dirty factorization and uses the pow() function to cut down on the multiplications.

Was This Post Helpful? 0
  • +
  • -

#6 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2246
  • View blog
  • Posts: 9,236
  • Joined: 18-February 07

Re: factorial

Posted 18 March 2007 - 10:08 AM

well rather than try to write out an example myself here is link to several algorithems: Fast Factorial Functions I think you will find much more there than I would be able to type out.
Was This Post Helpful? 0
  • +
  • -

#7 vennik  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 07

Re: factorial

Posted 19 March 2007 - 11:10 AM

Yes, there is useful information. Thank you very much.


View PostNickDMax, on 18 Mar, 2007 - 10:08 AM, said:

well rather than try to write out an example myself here is link to several algorithems: Fast Factorial Functions I think you will find much more there than I would be able to type out.

Was This Post Helpful? 0
  • +
  • -

#8 alpha02  Icon User is offline

  • Sexy DIC God
  • member icon

Reputation: 46
  • View blog
  • Posts: 803
  • Joined: 20-May 06

Re: factorial

Posted 23 March 2007 - 07:38 AM

View Postvennik, on 19 Mar, 2007 - 02:10 PM, said:

Yes, there is useful information. Thank you very much.


View PostNickDMax, on 18 Mar, 2007 - 10:08 AM, said:

well rather than try to write out an example myself here is link to several algorithems: Fast Factorial Functions I think you will find much more there than I would be able to type out.


To keep this simple, use this Java code:

public class test1{
	public static void main (String[] args){
		int fact = 1000; //Number to factorize
		for (int i=1; i<=fact; i++){
			if (fact%i == 0){ //It works
				System.out.print (i + " "); //Print this number
			}
		}
	}
}


This code prints all factors of this number. In this example, the output is:
1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000

This post has been edited by alpha02: 23 March 2007 - 07:41 AM

Was This Post Helpful? 0
  • +
  • -

#9 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 204
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: factorial

Posted 23 March 2007 - 07:43 AM

View Postalpha02, on 23 Mar, 2007 - 12:38 PM, said:

View Postvennik, on 19 Mar, 2007 - 02:10 PM, said:

Yes, there is useful information. Thank you very much.


View PostNickDMax, on 18 Mar, 2007 - 10:08 AM, said:

well rather than try to write out an example myself here is link to several algorithems: Fast Factorial Functions I think you will find much more there than I would be able to type out.


To keep this simple, use this Java code:

public class test1{
	public static void main (String[] args){
		int fact = 1000; //Number to factorize
		for (int i=1; i<=fact; i++){
			if (fact%i == 0){ //It works
				System.out.print (i + " "); //Print this number
			}
		}
	}
}


This code prints all factors of this number. In this example, the output is:
1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000

he was looking for a factorial, not a factor, these are completely different:
a factorial is of the form:
5! = 5*4*3*2*1
Was This Post Helpful? 0
  • +
  • -

#10 alpha02  Icon User is offline

  • Sexy DIC God
  • member icon

Reputation: 46
  • View blog
  • Posts: 803
  • Joined: 20-May 06

Re: factorial

Posted 23 March 2007 - 09:38 AM

View PostWilliam_Wilson, on 23 Mar, 2007 - 10:43 AM, said:

View Postalpha02, on 23 Mar, 2007 - 12:38 PM, said:

View Postvennik, on 19 Mar, 2007 - 02:10 PM, said:

Yes, there is useful information. Thank you very much.


View PostNickDMax, on 18 Mar, 2007 - 10:08 AM, said:

well rather than try to write out an example myself here is link to several algorithems: Fast Factorial Functions I think you will find much more there than I would be able to type out.


To keep this simple, use this Java code:

public class test1{
	public static void main (String[] args){
		int fact = 1000; //Number to factorize
		for (int i=1; i<=fact; i++){
			if (fact%i == 0){ //It works
				System.out.print (i + " "); //Print this number
			}
		}
	}
}


This code prints all factors of this number. In this example, the output is:
1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000

he was looking for a factorial, not a factor, these are completely different:
a factorial is of the form:
5! = 5*4*3*2*1


ah ok. well someone can find my code useul, and for a factorial I thought about:

public class test1{
	public static void main (String[] args){
		int fact = 1000; //Number to factorize
				int total = 1;
		for (int i=fact; i>0; i--){
			total = total*i;
		}
				System.out.println(total);
	}
}


It outputs the number. However I'm afraid this will not work if the number is too high because of Java's data types limitations, but it is worth the try.

This post has been edited by alpha02: 23 March 2007 - 09:39 AM

Was This Post Helpful? 0
  • +
  • -

#11 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 251
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: factorial

Posted 23 March 2007 - 10:36 AM

Java's BigInteger class will buy you a little more breathing room, but with some factorial algorithms, it's a losing battle. :)
Was This Post Helpful? 0
  • +
  • -

#12 vennik  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 17-March 07

Re: factorial

Posted 24 March 2007 - 05:59 PM

There is algorithms solve problem without using of BigInteger class. Just must some ingenuity.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1