[gmusk]

I have been trying to implement factorial for large numbers upto 10,000. I need help on this.

[mattman059]

I would recommend using a language like python it's so much faster. dont get me wrong, i love C++ ...but for things like this, Python (a scripted language) far surpasses C++ (a compiled language)

[KYA]

Alternatively, embed Lua in a C++ program, then use Lua to do the large number calculation.

[gmusk]

mattman059, on 31 Aug, 2009 - 05:31 AM, said:

I would recommend using a language like python it's so much faster. dont get me wrong, i love C++ ...but for things like this, Python (a scripted language) far surpasses C++ (a compiled language)

Ok. Thanks. But im a beginner of programming.. I tried it in java using big integer class.. Its not efficient.. In general how to deal with large numbers?
Thanks in advance..

[gmusk]

KYA, on 31 Aug, 2009 - 05:37 AM, said:

Alternatively, embed Lua in a C++ program, then use Lua to do the large number calculation.

thanks a lot and im sorry! Im just a beginner of programming.. It would b more helpful for me if i can get more details on Lua..
thanks in advance

[KYA]

Yes! I have someone interested in Lua! Check this out:

#define _CRT_SECURE_NO_DEPRECATE

#include <stdio.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif
#include <lua.h>
#include <lauxlib.h>
#include <lualib.h>
#ifdef __cplusplus
}
#endif

int main()
{
	char buff[256];
	int error;
		lua_State *L = luaL_newstate();			/*open a new lua state*/
	luaL_openlibs(L);						/*open standard libraries*/

	printf("Currently in C\n\n");
	luaL_dofile(L, "Factorial.lua"); /*This function will do all the actual work*/
	printf("\n\nBack in C\n\n");
	lua_close(L); /*clean up*/

	return 0;
}

Contents of the factorial.lua file:

function factorial(n)
  if n == 0 then
	return 1
  else
	return n * factorial(n - 1)
  end
end

--example usage
--Without any additional help, lua can calculate past 12!
--where most other language snippets would have an overflowed
--integer value
print("[In Lua] Enter a number to find it's factorial: ")
num = io.read()
print("\n"..factorial(num).."\n")

This post has been edited by KYA: 31 August 2009 - 07:15 AM

[baavgai]

KYA, on 31 Aug, 2009 - 08:15 AM, said:

Yes! I have someone interested in Lua!

Lua failed!

I was curious about this and was going to say something about how much easier it would be in python.

So:

[email protected]:~$ python
Python 2.5.2 (r252:60911, Jul 22 2009, 15:33:10) 
[GCC 4.2.4 (Ubuntu 4.2.4-1ubuntu3)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> def fact(n):
...   if n==0: return 1
...   else: return n * fact(n - 1)
... 
>>> 
>>> print fact(5)
120
>>> print fact(1000)
Lots of these: File "<stdin>", line 3, in fact
RuntimeError: maximum recursion depth exceeded

Oops, 1000 seems to be a python recursion break point.

Can lua do better?

[email protected]:~$ lua50
Lua 5.0.3  Copyright (C) 1994-2006 Tecgraf, PUC-Rio
> function factorial(n)
>>   if n == 0 then
>>	 return 1
>>   else
>>	 return n * factorial(n - 1)
>>   end
>> end
> 
> print(factorial(5))
120
> print(factorial(1000))
inf

Ok, guess not. Well non recursion it is. This worked fine in python:

def fact(n):
   f = 1
   while n>0:
	  f = f * n
	  n = n - 1
   return f

To be fair, I tested in lua:

> function factorial(n)
>>   local f = 1
>>   while n>0 do
>>	  f = f * n
>>	  n = n - 1
>>   end
>>   return f
>> end
>
> print(factorial(1000))
inf

Hmm, more in lua:

> print(factorial(100))
9.3326215443944e+157

Same in python:

>>> print fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Pity. Maybe time to write an Lua big number handler?

[KYA]

Dang it. Lua failed

[Nizbel99]

You could also use scheme which supports unbounded integers.... computing the factorial of 1000 took less than
one second...

(define (factorial n)
  (local [(define (helper n acc)
			(cond
			  [(zero? n) acc]
			  [else (helper (sub1 n) (* acc n))]))]
	(helper n 1)))

So, for example:

> (factorial 5)
120

> (factorial 6)
720

> (factorial 1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

And like I said, took less than one second - You should take a look at Dr Scheme. It's a nice scheme interpreter.

EDIT:
I've calculated the factorial of 10000 with this function, and it only took 2 or 3 seconds. But the number is
pretty large to copy.

-Zach

This post has been edited by Nizbel99: 31 August 2009 - 09:36 AM

[baavgai]

Nizbel99, on 31 Aug, 2009 - 10:33 AM, said:

You could also use scheme

Yeah, but then you'd be using scheme.

If you're going to pull out a functional language hammer, is should at least be more elegant than something trivial in python.

Here, have some Haskell.

let fac = product . enumFromTo 1

[tobix10]

Quote

Oops, 1000 seems to be a python recursion break point.

Heh. I've just started with python and I know that in module sys are functions getrecursionlimit and setrecursionlimit.

Quote

sys.setrecursionlimit(2000)
>>> fact(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L

[mattman059]

tobix10, on 31 Aug, 2009 - 01:45 PM, said:

Quote

Oops, 1000 seems to be a python recursion break point.

Heh. I've just started with python and I know that in module sys are functions getrecursionlimit and setrecursionlimit.

Quote

sys.setrecursionlimit(2000)
>>> fact(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L

I like that...didnt know that existed