LinuxQuestions.org
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Use the maximun processing power to calculate the factorial of 80,000. How? (https://www.linuxquestions.org/questions/programming-9/use-the-maximun-processing-power-to-calculate-the-factorial-of-80-000-how-388872/)

TruongAn 12-03-2005 10:59 AM
Use the maximun processing power to calculate the factorial of 80,000. How?
 
Hello everyone,
I 've got a problem which seem to be very simple but I am unable to deal with.
In C++, we have the "long double" data type, which can store the factorial of 1,700.
But what I want to do is calculate the factorial of 80,000.
I use these simple code to calculate the factorial of a given number, but it was too simple to calculate the factorial of 80,000.
I think there must be a way to calculate it because our PC today are powerful enough to do such calculation in a couple of minutes, it is just the problem of programing skill.
I include the code here:
Code:
long double fact(int n){
        long double result = 1;
        int k;
        for (k=1; k<=n;k++){
                result *=k;
        };
        return result;
};
Do you have any idea.
You can give me a new way to use the data types, change the code, guide me to use a another built-in function, show me some software (open source or free), any way...
I appreciate any suggestions.


Extra info:
The following explain why do I ask such things, you don't need to read it.
A friend of mine, a windoze user, said that Linux softwares are too bad compare to windows' ones.
He pointed out that even calc.exe, a small calculator software in windoze can calculate the factorial of 80,000 within a few seconds.
But this number is out of range in any linux calculator software.
I was so angry to hear that.
I told him that linux can handle this number and even larger number.
But when I tried, neither gclactool nor openoffice calc can do so.
The best the can do is the factorial of 200.
So I wrote the code myself, it can calculate the factorial of 1,700 but this is not what I want to do.
Do you have any advices?

primo 12-03-2005 11:57 AM
80000! is a grotesquely high number. Does calc.exe really give you all the digits? You'd have to use a big-number library to do this and compile it with the most optimization.

dmail 12-03-2005 11:57 AM
http://www.codeguru.com/Cpp/Cpp/algo...icle.php/c2041
windows calc gives 3.0977222516622492863982132799138e+357506

graemef 12-03-2005 04:09 PM
I've just tried it on my window box. I would say that you friend is a little prone to exaggeration. It took my machine about a minute to come up with the answer. Anyway the answer was using, as other posters have suggested, floating point arithmetic. So if you wanted just to emulate the windows solution, there is your answer, change your data types to double.

The link dmail gave is interesting, and obviously with care it could be improved upon, so instead of one node per digit it could be one node holds, say, six digits.

Finally is the answer that the Windows calculator provided useful?
Not really, factorials are well known representation of numbers and typically they are held as factorials until the end of the calculation and then the properties of factorials are used to evaluate the sum. For example – a very basic one just to illustrate my point the number of combinations of m object from a universe of k objects is given as n!/k!(n!-k!). So if n is 80,000 and k is 2 I don’t calculate 80,000! and 79,998! rather I know that 80,000!/79,998! is equal to 80,000 * 79,999, and with 2! being 2 then the number of combination is 40,000 * 79,999 now I get my calculator out.

As aside ask your friend if excel can handle 80,000! Since I’m on windows at the moment I just tested it. The largest factorial that Excel will display is 170, exactly the same for OO.org Calc. I’ve not looked at what OO.org Calc can do under Linux I’d suspect it would be the same.

graeme

TruongAn 12-04-2005 01:18 AM
Quote:
Originally Posted by graemef
I've just tried it on my window box. I would say that you friend is a little prone to exaggeration. It took my machine about a minute to come up with the answer. Anyway the answer was using, as other posters have suggested, floating point arithmetic. So if you wanted just to emulate the windows solution, there is your answer, change your data types to double.
I know that no one will calculate the factorial of such huge number in a formula.
But I just want to find out a way to calculate it because if windows calc can do it, there must be some way to do it in linux.
And I also aware that my computer is not able to calculate all the digit. But I accept the float point, long double data type also store float point number. I don't think hange data type to double is an answer because double have the range of 1,2e+4000 which is about the factorial of 170.
I think that I will try the link dmail give me and I will post back if it work

TruongAn 12-04-2005 09:06 AM
Thank dmail.
The link you giv me have worked.
Though it has some spelling mistake, I can manage to fix it.
But 80,000 was a really large number.
The code run for 50 minutes but I still don't get the result.
I think my PC was too slow to think about such calculation.
Thank for your support.

Dodgeram01 12-04-2005 09:36 AM
KCalc in KDE is able to calculate it, giving the same answer as the Windows calculator reportedly gave.

TruongAn 12-04-2005 10:34 AM
Quote:
Originally Posted by Dodgeram01
KCalc in KDE is able to calculate it, giving the same answer as the Windows calculator reportedly gave.
Really??
It didn't work on my PC.
It can calculate the factorial 1.700 only.
I try 80,000 it say err, I try 2,000 the same thing happen
I look at the about page of Kcalc, It said that it was built with 96 bit (long double) precision
That was what I have try.

So I think that the problem may come from the hardware as well.
Can you tell me something about your system Dodgeram01?
Mine is:
CPU: Intel celeron 600MHz
RAM: 192 bus 133.
It is too slow, isn't it?

wapcaplet 12-04-2005 11:12 AM
You could use 'bc' to get around the precision problem. I found a short factorial script that appears to work for at least fact(8000), and doesn't truncate the result. Pretty fast, too. It failed with fact(20000), probably because it's using a recursive algorithm. Here's a much simpler 'bc' script for calculating factorial that doesn't use recursion:

Code:
define fact(n) {
    ans=1;
    while (n > 1) ans *= n--;
    return(ans);
}
Dumb approach, but it seems to work for at least fact(20000), which produces a 77,000-digit number in about 1 minute.

Hko 12-05-2005 06:37 AM
There's a special library from GNU for really HUGE numbers. It's called "libgmp".

It is capable of calculating arbitrary length integers, the number of digits only limited by available memory!

Install libgmp, and the package with its header files (and probably the documentation package for it). On Debian: "apt-get install libgmp3 libgmp3-dev libgmp3-doc".

When installed, compile the program below with the "-lgmp" option:
Code:
gcc -Wall -lgmp -o bigfactorial bigfactorial.c
The program will even print all 357507 digits of the factorial of 80000. Have your friend try that on Windows...

Code:
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int main(int argc, char *argv[])
{
    long int i, n;
    size_t digits;
    mpz_t result;
   
    if (argc != 2) {
        fprintf(stderr, "%s - Calculate huge factorial\nUsgage: %s <integer>\n", argv[0], argv[0]);
        return 1;
    }
    n = atol(argv[1]);
    mpz_init(result);
    mpz_set_ui(result, 1L);
    for (i = 1; i <= n; i++) {
        mpz_mul_si(result, result, i);
    }
    printf("Factorial of %ld = ", n);
    digits = mpz_out_str(stdout, 10, result);
    mpz_clear(result);
    printf("\n(%d digits)\n", digits);
    return 0;
}
Calculating all 357507 digits of fact(80000) took little more than 3 seconds on my laptop.

TruongAn 12-05-2005 09:31 AM
It sound great Hko.
Do you think it will really work for me.
However, send me the download link please.
I don't use debian.
I use FC4.

Hko 12-05-2005 10:29 AM
I think you could have easily found them yourself, but anyways:

gmp-4.1.4-6.i386.rpm
gmp-devel-4.1.4-6.i386.rpm

(these are links to a mirror in Europe, maybe you should get these packages from an Asian mirror instead)

Hko 12-05-2005 10:58 AM
Quote:
Originally Posted by TruongAn
It sound great Hko.
Do you think it will really work for me.
Of course.
On my PC (Pentium 3, 650Mhz, 256 Mb RAM) it takes less than 15 seconds to calculate 80000! using the program I posted.

King of Men 12-05-2005 11:32 AM
If you just wanted a quick approximation with floats, you could use Stirling's formula, ln n! \approx n ln n - n. Then convert e^{823183} to base ten; that would give you a very nice exponent. God knows how accurate the mantissa would be, but then again, who knows how accurate the Windows version is?

TruongAn 12-06-2005 05:58 AM
Thanks for your link Hko but I have found out why couldn't find the download link for FC4.
It is because those library is already installed on FC4.
But when I compile the code, it report the undefined reference error.
It seem that all the function start with mpz is not defined.
Do I have to replace my already installed lib with those you give?


All times are GMT -5. The time now is 07:55 AM.
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page