🔒 Locked

Next factorial

Started by Thomas_CR Jun 24, 2004 at 4:47 AM 37 replies 5.5k views

Original Post

Thomas_CR

Jun 24, 2004 at 4:47 AM

How one computes the nearest superior factorial? ie : 6 -> 6 25 -> 120 700 -> 720

haro

Jun 24, 2004 at 5:05 AM

This sounds distinctly like homework. Try to solve the problem. Its not very difficult. As a hint you will use some sort of a loop.

DigitalDelusion

Jun 24, 2004 at 5:25 AM

Im guessing you'll start spewing code again but anyhow here's two simple way todo it for 32bit unsigned ints.

Naïve runtime approach:

unsigned SupFact_Naive(unsigned n){	if(n > 479001600) return 1932053504;	if(n > 39916800) return 479001600;	if(n > 3628800) return 39916800;	if(n > 362880) return 3628800;	if(n > 40320) return 362880;	if(n > 5040) return 40320;	if(n > 720) return 5040;	if(n > 120) return 720;	if(n > 24) return 120;	if(n > 6) return 24;	if(n > 2) return 6;	if(n > 1) return 2;	return 1;}

compile time approach:

template <unsigned N, unsigned I = 1, unsigned J = 1, bool B = false>struct SupFact{	enum {val = SupFact<N, I*J, J + 1, N <= I*J>::val};};template <unsigned N, unsigned I, unsigned J>struct SupFact<N, I, J, true>{	enum {val = I};};

usage:

	printf("%u %u\n", SupFact_Naive( 6), SupFact<6>::val);	printf("%u %u\n", SupFact_Naive( 25), SupFact<25>::val);	printf("%u %u\n", SupFact_Naive( 700), SupFact<700>::val);

output:

6 6120 120720 720

If the requirements are that calculations must be carried out at runtime and it's performance sensative then other approaches should be explored.

DigitalDelusion

Jun 24, 2004 at 5:27 AM

Quote:
Original post by haro
This sounds distinctly like homework. Try to solve the problem. Its not very difficult. As a hint you will use some sort of a loop.

Actually it sounds like trying to revive a locked topic using a calculation better suited to give favorable results using his beloved tool that got a quite severe beating in another thread.

But hopefully things will stay civil enough for us all to learn something intresting this time around.

Thomas_CR

Jun 24, 2004 at 5:31 AM

Every aspect should be explored. Simple programs and not so simple programs - in the sense of the Kolmogorov's complexity.

With a lot of precalculation done and without.

The fastest algorithms and the simpliest.

DigitalDelusion

Jun 24, 2004 at 5:50 AM

@Thomas_CR: honestly why would we bother wasting time on this unless you at least can be honest enough to post the code you already have, we all know that as soon as we actually put some effort into this you'll post a huge codeblock wanting someone else to benchmark it and when someone eventually does you'll claim the benchmark to be flawed without having any substantial arguments then you'll claim that the results are impossible on some vauge "C++ ops/sec" argument.

Really if you want a serious discussion you'll have to start actuing mature and honest yourself, you'll have to start reading what people post and you'll have to be open to the possibility that your solution isn't the best and man enough to realize that there's other people on theese boards that actually know what they're doing. I won't invest more than the few minutes it took me to hack togheter the previous code samples until I see some sign of you starting to listen to reason and at least playing a fair game.

haro

Jun 24, 2004 at 6:01 AM

Quote:
Original post by Thomas_CR
Every aspect should be explored. Simple programs and not so simple programs

With a lot of precalculation done and without.

This is an absolutely silly "problem" to try to "optimize". Factorial values grow so quickly that the problem would not be creating an optimal solution to the factorial problem, but creating an optimal BigNumber implementation.

DrPizza

Jun 24, 2004 at 6:12 AM

Even for factorials that fit into a double you're still only looking at a lookup table of 200 elements.

wolverine

Jun 24, 2004 at 6:21 AM

well, just for fun:
1000! =
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[wow]

Qw3r7yU10p!

Jun 24, 2004 at 6:58 AM

Make a std::set of the factorials.
Use std::set::upper_bound to find the result.

Tada.

Qw3r7yU10p!

Jun 24, 2004 at 7:10 AM

Since 32 bit unsigned ints can only have 13 different factorials you could have a small set of results.

Is this a competition? I don't feel like competing. Maybe we can compete to see how (genuinely) friendly we can be to each other... that sounds good [smile]

#pragma warning (disable : 4786)#include <set>#include <iostream>#include <exception>#include <algorithm>typedef unsigned int FactorialType;typedef std::set<FactorialType> Factorials;typedef Factorials::iterator FactorialsItr;FactorialType g_factorials[12] = {	1,						2,						6,						24,						120,						720,						5040,						40320,						362880,						3628800,						39916800,						479001600						};FactorialType nextFactorial(FactorialType test) {    static Factorials factorials(g_factorials, g_factorials+12);	FactorialsItr result = factorials.upper_bound(test);	if(result != factorials.end())		return *result;	throw std::logic_error("FactorialType doesn't have value in set of factorials");}void printNextFactorial(FactorialType test) {	std::cout << test << ":" << nextFactorial(test) << std::endl;}int main() {	printNextFactorial(10);	printNextFactorial(5192);	printNextFactorial(3499684);	printNextFactorial(193450993);	printNextFactorial(479001601);	return 0;}

you get the idea, it could be neater and extended to doubles, and the array could be generated instead of hard-coded, etc.

You could just use the array with std::upper_bound(array, array+12) but I like the idea of std::set enforcing uniqueness.

DigitalDelusion

Jun 24, 2004 at 9:36 AM

In the spirit of petewoods solution but with generation of values.

#include <algorithm>#include <stdexcept>template <unsigned N>struct Factorial{	enum {val = N * Factorial<N - 1>::val};};template <>struct Factorial<0>{	enum { val = 1};};class cNextFactorial{	template <unsigned N, bool B = true>	struct FindMax{ enum {val = FindMax<N + 1, Factorial<N>::val < Factorial<N + 1>::val >::val};};	template <unsigned N>	struct FindMax<N,false> { enum {val = N - 1};};	static const unsigned size = FindMax<1>::val;	unsigned data[size];	unsigned *end;	template <unsigned N>	void init(unsigned *pu){ pu[N - 1] = Factorial<N>::val; init<N-1>(pu);}	template <>	void init<0>(unsigned*){}public:	cNextFactorial(void): end(data + size){ init<size>(data);}	unsigned operator()(unsigned u)	{		unsigned *p = std::lower_bound(data, end, u);		if( p != end)			return *p;		throw std::logic_error("next factorial not found");	}}NextFactorial;

sample usage

#include <cstdlib>#include <iostream>int main(void){	std::cout 		<< NextFactorial( 6) << std::endl		<< NextFactorial( 25) << std::endl		<< NextFactorial( 700) << std::endl;	system("pause");}

I leave it as an exercise for the reader to expand it to other datatypes something that should be fairly trivial.

DigitalDelusion

Jun 24, 2004 at 10:11 AM

Better, in release build data gets compiletime generated.

template <unsigned N>struct Factorial{	enum {val = N * Factorial<N - 1>::val};};template <>struct Factorial<0>{	enum { val = 1};};class cNextFactorial{	template <unsigned N, bool B = true>	struct FindMax{ enum {val = FindMax<N + 1, Factorial<N>::val < Factorial<N + 1>::val >::val};};	template <unsigned N>	struct FindMax<N,false> { enum {val = N - 1};};	static const unsigned size = FindMax<1>::val;	static unsigned data[size];	static unsigned *end;	template <unsigned N>	static unsigned init(unsigned *pu){ pu[N - 1] = Factorial<N>::val; return init<N-1>(pu);}	template <>	static unsigned init<0>(unsigned*){ return 0;}public:	unsigned operator()(unsigned u)	{		unsigned *p = std::lower_bound(data, end, u);		if( p != end)			return *p;		throw std::logic_error("next factorial not found");	}};unsigned *cNextFactorial::end = data + size + init<size>( data);unsigned cNextFactorial::data[size];cNextFactorial NextFactorial;

Qw3r7yU10p!

Jun 24, 2004 at 10:35 AM

nice

VBBR

Jun 24, 2004 at 5:46 PM

Quote:
Original post by wolverine
well, just for fun:
1000! =
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[wow]

out of curiosity, how did you find that?

wolverine

Jun 25, 2004 at 2:46 AM

Quote:
Original post by VBBR
Quote:
Original post by wolverine
well, just for fun:
1000! =
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[wow]

out of curiosity, how did you find that?

It's for a course i'm having at college about compilers!
I'm doing a small dsl in maths that is translated to java code.
It handles things like ints, fracs, reals, complexs and matrices. (Actually the language isn't that great since one semester with other courses doesn't give you much time)
Since java has numbers with arbitrary precision (BigInteger/BigDecimal) using big numbers in my dsl isn't a problem :).
All i did in the original code was "print 1000!;"

Wyrframe

Jun 25, 2004 at 2:59 AM

Quote:
1000! = 402387260077093773543702433923003985719374864210714632543799910...

2568 digits. Wow. I think somebody got bored on some long winter night... either that, or needed to really stress-test a variable-size math library.

I know that's what I would've used to test the "multiply" performance of such a library.

Oh, and just because the asinine joke must be made...

"Of course 1000 != 4023872600770937735437... is true! You can tell with only the first digits!"

wolverine

Jun 25, 2004 at 3:34 AM

Quote:
Oh, and just because the asinine joke must be made...

"Of course 1000 != 4023872600770937735437... is true! You can tell with only the first digits!"

Actually, when i first looked at it i had some doubts about digits nr 27 and 51. But then i blinked my eyes and when i looked at it the second time, it was ok. [smile]

DrPizza

Jun 25, 2004 at 4:24 AM

Quote:
Original post by Anonymous Poster
Use the gamma function to solve for k where k! = N, where N is the starting number. N', your target number, is then ceil(k)!. Although I have a hunch there is a direct integer solution to this... the table lookup and generative solutions are just lame.

Yeah, because simple correct implementations and constant runtime performance sure do suck.

Charles B

Jun 25, 2004 at 6:05 AM

I would try a constant time solution. To approximate the inverse function (using the famous formula ??? mem leak for the name of the mathematician) for a quick guess, then use a lut of factorial and compare to check the approximation (max deviation known and bounded) does not create an error.

i=inv_fact(x);
if(x > lut_fact)
{
if( x <= lut_fact )
{
return lut_fact;
}
}
else
{
... // obvious completion;
}

But I won't spend time trying to see if such an inv_fact can be found with efficient code. I am nearly certain yes, with quick log2 (FPU exponent tricks) again. I bet for 10-20 cycles again. The two consecutive tests can be parallelized with integer logical operations on sign bits or carries (sbb in asm), and the code can be reduced to a single branch. If someone is courageous and has time to do it ...

There are many client solutions using a LUT, probably even faster ones. Analyse the curve. Segment the domains, etc... So it's certainly a technic based on look up table that wins in this case.

BTW Since "T CR oops does it again" : the digits I willingly did not give just in case he might become less lazy. Each time he added a if() to DDR3, 3 cycles penalty. Great. As I had predicted and explained well above. 6, 9, 11 cycles. Funny to see someone still does not understand what's written in preamble any optimization guide such as :

AMD Athlon Processor
x86 Optimization Guide.
Chapter 2 : Top Optimizations
Group II secondary Optimizations : "Avoid Branches dependant on Random Data"

But Thomas CR kicks the *ss of the AMD or Intel engineers, no doubt, he's over...qualified.

I could mention the K6, Pentium, Pentium4, etc ... It's a general constant on superscalar processors. Series of conditionnal jumps can only kill parallelism. Which is damn obvious to understand for anyone with 100 IQ or more.

Nonetheless the if serie should work rather well again since the progression of the function is quasi-exponential and if the domain is restricted to 2^32=!n, n is rather small ain't it ? 11 Digital Dellusion ? This makes around 30-40 cycles at worst again for a distribution of small numbers. so this can be easilly beaten ... once again.

Anyway I doubt anyone needs such a fuction for speedy real time applications.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.