There is a given list of numbers that are written in string format x^y or z!. For example 1000^1000, 954! 525^419, 89!, 427!, 428^727... x,y,z are random values within interval <0,1000>. The list may contain up to 200 of these formulas. I need to somehow sort this given string list in ascending order based on value of these formulas without calculating the values. How can one check if some factorial is greater than some power number without calculating its value?
From comment:
I need somehow to check, which is greater without having these values because there is a certain time limit for the program to complete.
To sort, you do need some kind of value. Since performance is the issue, you may have to calculate approximate values.
E.g. calculate the logarithm of the values:
For "power", that's easy: log(x^y)
= y * log(x)
For "factorial", you can use log(x!)
= Ramanujan's approximation to factorial
Alternatively, as suggested by risingStark:
There is no need of approximation. Use
log(x!)
=log(x)+log(x-1) + ... + log(1)
. Sincex
is at most 1000, precompute the cumulative sum tilllog(1000)
.