[스팸] 혹시 (10!)!이 몇 자리의 숫자인지 계산해 보셨나요?

dgkim의 이미지

지금 윈도우 계산기로 (10!)!을 계산하고 있습니다.

언제 결과가 나올까요..

현재 10분간(CPU시간만으로) 연산중입니다.

이런 계산을 하려면 어떤 알고리즘이 필요할까.....

dgkim의 이미지

위에 있는 것 보다 짧은 10,000!의 경우 다음과 같은 결과가

5분의 연산결과

2.8242294079603478742934215780245e+456573

envia의 이미지

만능 계산기 파이썬으로 =3 =33

import math
answer = 0.0
for i in range(1, 2*3*4*5*6*7*8*9*10): answer += math.log10(i)
print math.floor(answer)+1

결과는 22228098 자리 되겠습니다... (반올림 에러가 없다면요.)

----

It is essential, if man is not to be compelled to have recourse, as a last resort, to rebellion against tyranny and oppression, that human rights should be protected by the rule of law.
[Universal Declaration of Human Rights]

angpoo의 이미지

매스메티카로 N[(10!)!, 20]하니까 2-3분인가만에 값이 나오네요.
9.0519938354799345907*10^22228103

dgkim의 이미지

그럼 그것을 2진수로 한다면 몇 자리일까요?

(텍스트로 저장한다면 20Mbyte가 소요될테고, 비트단위라면 얼마나)

ps. 타자치다 계산을 중지시켜버렸네요........ 이런.. 몇시간 더 돌려야 겠군.

sDH8988L의 이미지

흠... 10!이라면 3628800이군요...

그렇다면, (10!)!은 (3628800)!이 되겠군요...

왜 이런 숫자가 필요하신 지는 모르겠습니다... 지금까지 있는 어떠한 학문에서도 저런 식으로 큰 숫자를 사용하지는 않겠죠...

뭐... 정확한 수치가 필요한 것이 아니고 근사값 또는 자리수만 아시면 되는 일이라면, Algorithm 중에 'Strling's Approximation'이라는 것이 있습니다...

n! = sqrt(2 * pi * n) * (n / e)^n * e

이런 연산을 하시면 됩니다... 그러나 (n / e)^n을 계산하는 것은 n!을 계산하는 것도 좀 힘들죠... 그래도 고정된 값을 계속 곱하는 것이기 때문에 n!보다는 빨리 끝나지 싶습니다...

자리수를 알고 싶으시다면, 그냥 위 식의 양변에 log를 취해 주시면 되겠네요...

그러면 (n / e)^n에서 ^n 부분이 깔끔하게 n *로 변해버리죠...

근사값의 자리수를 구하는 것은 위의 식으로 아주 쉽게 할 수 있습니다...

그럼 20000

envia의 이미지

dgkim wrote:
그럼 그것을 2진수로 한다면 몇 자리일까요?
(텍스트로 저장한다면 20Mbyte가 소요될테고, 비트단위라면 얼마나)
ps. 타자치다 계산을 중지시켜버렸네요........ 이런.. 몇시간 더 돌려야 겠군.

대략 73840142 자리 되겠습니다. 정확한 값을 바라시면 Mathematica 나 Maple 값을 쓰세요. 반올림을 하기 때문에 10초 남짓 걸렸습니다.

----

It is essential, if man is not to be compelled to have recourse, as a last resort, to rebellion against tyranny and oppression, that human rights should be protected by the rule of law.
[Universal Declaration of Human Rights]

dgkim의 이미지

계산기에서 2^x의 결과를 확인해보니

144269까지만 되는 군요..

1.9789938605962244330621526955618e+43429

즉 18kbytes로 4만자리의 숫자를...

아래는 256^x의 결과

18033까지만..

6.1843558143632013533192271736305e+43427

dgkim의 이미지

정확하게 계산한다면 얼마나 시간이 걸릴까요?

PC에서 굴려서 계산할 땐...

흔히말하는 슈퍼컴에서 계산한다면..

퀀텀컴퓨터(?)에서 계산한다면..

angpoo의 이미지

dgkim wrote:
정확하게 계산한다면 얼마나 시간이 걸릴까요?
PC에서 굴려서 계산할 땐...

위에 매스메티카로 계산한게 정확하게 계산한거에요.
자리수가 워낙 크니까 다 표시할 수 없어서 표시만 짧게 한거죠.
P3-866MHz에서 2분좀 넘게 걸립니다.

sangheon의 이미지

bc로는 계산이 끝나지 않는군요.

 10:55am  up 53 days, 21:58,  1 user,  load average: 1.00, 1.00, 1.00
50 processes: 47 sleeping, 3 running, 0 zombie, 0 stopped
CPU states: 93.2% user,  6.8% system,  0.0% nice,  0.0% idle
Mem:   513952K av,  507436K used,    6516K free,       0K shrd,  104680K buff
Swap: 1028152K av,  206356K used,  821796K free                  139128K cached

  PID USER     PRI  NI  SIZE  RSS SHARE STAT %CPU %MEM   TIME COMMAND
30683 bookworm  17   0  395M 209M   820 R    99.6 41.6  1616m bc
    6 root       9   0     0    0     0 SW    0.4  0.0 302:10 kscand

--

Minimalist Programmer

sangheon의 이미지

angpoo wrote:
dgkim wrote:
정확하게 계산한다면 얼마나 시간이 걸릴까요?
PC에서 굴려서 계산할 땐...

위에 매스메티카로 계산한게 정확하게 계산한거에요.
자리수가 워낙 크니까 다 표시할 수 없어서 표시만 짧게 한거죠.
P3-866MHz에서 2분좀 넘게 걸립니다.

매스매티카가 무한정도 계산기였었나요?

--

Minimalist Programmer

douner의 이미지

angpoo wrote:
매스메티카로 N[(10!)!, 20]하니까 2-3분인가만에 값이 나오네요.
9.0519938354799345907*10^22228103

역시 매스메티카~ 굿~
지금 열심히 매스메티카 랩 올리는 중..^^;;

인생, 쉬운 것만은 아니네..

ihavnoid의 이미지

노가다 C로 짠다면 어떻게 될까요... 으흐흐.

Consider the ravens: for they neither sow nor reap; which neither have storehouse nor barn; and God feedeth them: how much more are ye better than the fowls?
Luke 12:24

차리서의 이미지

ihavnoid wrote:
노가다 C로 짠다면 어떻게 될까요... 으흐흐.

헉! 럴쑤럴쑤 이럴~쑤!
/*
 * Simple factorial calculator
 */
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

int
main(int argc, char **argv)
{
        mpz_t result;

        mpz_init(result);
        mpz_fac_ui(result, atol(argv[1]));
        mpz_out_str(stdout, 10, result);
        printf("\n");
        mpz_clear(result);

        return (EXIT_SUCCESS);
}

reeseo@www:~/work/factorial> time ./factorial 10
3628800
0.001u 0.000s 0:00.00 0.0%      0+0k 0+0io 101pf+0w
reeseo@www:~/work/factorial> time ./factorial 3628800 > result.txt
Segmentation fault (core dumped)
259.628u 2.968s 4:23.68 99.5%   0+0k 0+0io 93pf+0w
reeseo@www:~/work/factorial>

어째서...? :cry:

--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!

warpdory의 이미지

bookworm wrote:
angpoo wrote:
dgkim wrote:
정확하게 계산한다면 얼마나 시간이 걸릴까요?
PC에서 굴려서 계산할 땐...

위에 매스메티카로 계산한게 정확하게 계산한거에요.
자리수가 워낙 크니까 다 표시할 수 없어서 표시만 짧게 한거죠.
P3-866MHz에서 2분좀 넘게 걸립니다.

매스매티카가 무한정도 계산기였었나요?

계산기... 라기보다는 계산용 프로그램이죠. 엄청난 놈입니다.


---------
귓가에 햇살을 받으며 석양까지 행복한 여행을...
웃으며 떠나갔던 것처럼 미소를 띠고 돌아와 마침내 평안하기를...
- 엘프의 인사, 드래곤 라자, 이영도

즐겁게 놀아보자.

차리서의 이미지

차리서 wrote:
ihavnoid wrote:
노가다 C로 짠다면 어떻게 될까요... 으흐흐.

헉! 럴쑤럴쑤 이럴~쑤!
/*
 * Simple factorial calculator
 */
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

int
main(int argc, char **argv)
{
        mpz_t result;

        mpz_init(result);
        mpz_fac_ui(result, atol(argv[1]));
        mpz_out_str(stdout, 10, result);
        printf("\n");
        mpz_clear(result);

        return (EXIT_SUCCESS);
}

reeseo@www:~/work/factorial> time ./factorial 10
3628800
0.001u 0.000s 0:00.00 0.0%      0+0k 0+0io 101pf+0w
reeseo@www:~/work/factorial> time ./factorial 3628800 > result.txt
Segmentation fault (core dumped)
259.628u 2.968s 4:23.68 99.5%   0+0k 0+0io 93pf+0w
reeseo@www:~/work/factorial>

어째서...? :cry:

stdout으로 뿌려지는 22메가바이트짜리 스트림을 파이프로 파일로 쓰려는 것이 문제였나보군요. 너무 긴 결과(예를 들어 1000자리 이상)는 출력하지 않고 자리수만 구하면 되긴 됩니다:
/*
 * Simple factorial calculator
 */
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

void result_base(mpz_t, int);

int
main(int argc, char **argv)
{
        mpz_t result;

        mpz_init(result);
        mpz_fac_ui(result, atol(argv[1]));

        result_base(result, 10);
        result_base(result, 2);

        mpz_clear(result);

        return (EXIT_SUCCESS);
}

void
result_base(mpz_t res, int base)
{
        size_t len;

        printf("In %d-based:\n\tResult: ", base);
        len = mpz_sizeinbase(res, base);
        if (len < 1000) {
                mpz_out_str(stdout, base, res);
                printf("(%d)\n", base);
        } else
                printf("Too long to show!\n");
        printf("\tCipher: %d\n", len);
}

실행 결과:
reeseo@www:~/work/factorial> make
cc -c factorial.c
cc -o factorial factorial.o -lgmp
reeseo@www:~/work/factorial> time ./factorial 10
In 10-based:
        Result: 3628800(10)
        Cipher: 7
In 2-based:
        Result: 1101110101111100000000(2)
        Cipher: 22
0.001u 0.000s 0:00.00 0.0%      0+0k 0+0io 106pf+0w
reeseo@www:~/work/factorial> time ./factorial 3628800
In 10-based:
        Result: Too long to show!
        Cipher: 22228105
In 2-based:
        Result: Too long to show!
        Cipher: 73840164
259.804u 2.687s 4:22.69 99.9%   0+0k 0+0io 109pf+0w
reeseo@www:~/work/factorial>

참고로, 계산한 기계는 core 128 Mbytes의 450 MHz 펜티엄 III였습니다.

--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!

eungkyu의 이미지

angpoo wrote:
dgkim wrote:
정확하게 계산한다면 얼마나 시간이 걸릴까요?
PC에서 굴려서 계산할 땐...

위에 매스메티카로 계산한게 정확하게 계산한거에요.
자리수가 워낙 크니까 다 표시할 수 없어서 표시만 짧게 한거죠.
P3-866MHz에서 2분좀 넘게 걸립니다.

정말 정확하게 계산한건가요?

진짜 답을 보고 싶네요 ;;;

kcho의 이미지

Quote:
지금 윈도우 계산기로 (10!)!을 계산하고 있습니다.

언제 결과가 나올까요..

현재 10분간(CPU시간만으로) 연산중입니다.

이런 계산을 하려면 어떤 알고리즘이 필요할까.....

이렇게 상상을 초월하는 계산을 하기 위해서는 "고속 푸리에 변환"을 씁니다. 이런 것을 high precision computation 또는 multiprecision computation 이라고 합니다. 이것에 관한 책도 있습니다. 제목은 "고속 푸리에 변환으로 구현하는 무한정밀도"입니다.

나는 열정적인 사람이다. 열정은 내가 가지고 있는 에너지의 원동력이다.

dgkim의 이미지

위의 소스를 보고 코드 돌려서 해봤는데..

신기하네요..

몇 만까지는 정확한 것 같은데,
(10k, 20k, 30k 이런 값을 넣으니 주루룩 결과를 보여주네요)

계산기 만드는 것도 만만치 않은 것 같습니다.

angpoo의 이미지

차리서 wrote:
reeseo@www:~/work/factorial> time ./factorial 10
3628800
0.001u 0.000s 0:00.00 0.0%      0+0k 0+0io 101pf+0w
reeseo@www:~/work/factorial> time ./factorial 3628800 > result.txt
Segmentation fault (core dumped)
259.628u 2.968s 4:23.68 99.5%   0+0k 0+0io 93pf+0w
reeseo@www:~/work/factorial>

어째서...? :cry:

이것은 stack사이즈때문인듯 합니다.
ulimit -s 102400을 해주니 파일로 저장이 됩니다.

차리서 wrote:
reeseo@www:~/work/factorial> time ./factorial 3628800
In 10-based:
Result: Too long to show!
Cipher: 22228105
In 2-based:
Result: Too long to show!
Cipher: 73840164
259.804u 2.687s 4:22.69 99.9% 0+0k 0+0io 109pf+0w

여기서 자리수가 22228105라고 나왔습니다.
매스메티카로 계산한 값은 9.0519938354799345907*10^22228103니까 22228104가 나와야 할텐데요.
저장된파일을 보니 앞자리수도 일치하고 파일크기도 22228104입니다.
아마도 mpz_sizeinbase()의 버그인것 같아서 구글을 통해검색해봤더니 메뉴얼에 다음과 같은글이 있네요.

Quote:
size_t mpz_sizeinbase (mpz_t op, int base) Function
Return the size of op measured in number of digits in base base. The base may vary from 2 to 36. The sign of op is ignored, just the absolute value is used. The result will be exact or 1 too big. If base is a power of 2, the result will always be exact. If op is zero the return value is always 1.
This function is useful in order to allocate the right amount of space before converting op to a string. The right amount of allocation is normally two more than the value returned by mpz_sizeinbase (one extra for a minus sign and one for the null-terminator).
cleansugar의 이미지

10만 팩토리얼 계산 속도
http://kldp.org/node/107470

재미있는 놀이: C, Python, Erlang으로 50000! 해보기 #0
http://kldp.org/node/129044

직접만든 프로그램으로 2의 1000000000 (10억)승 계산한게 자랑
http://kldp.org/node/122726

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com