10만 팩토리얼 계산 속도

ifree의 이미지

심심해서 해봤습니다.

하드웨어: 바톤 2600+
OS: 윈도우즈 XP

(1) 윈도우즈 기본 계산기
1분 35초

(2) Clojure
(apply * (range 1 100001))
2분 57초(출력시간 미포함)
6분 20초(출력시간 포함)

clojure 는 JVM 기반 LISP dialect 입니다.
조금 오래 걸리네요. recursion 으로 하면 좀 빨라질라나요?
자바에서 tail recursion 최적화가 안돼 있다고 하는데.

파이선도 해보고 싶은데 언어를 몰라서.

* 추가: 젠투(인텔 Q6600) 에서 clojure 돌린 결과 출력시간 포함 딱 1분 걸렸습니다.
tail recursion 을 써도 차이는 없네요.

clique의 이미지

import time;
 
result = 1
start = time.time()
for i in xrange(1, 100001):
    result  *= i
end = time.time()
print '%f s' % (end-start)
ifree의 이미지

이거 돌리려고 파이선 새로 깔았다는...

헉 50초 (바톤)
왜 이리 빠르지?

아놔. 젠투(Q6600@3.0GHz) 18초

출력시간 포함하면 한참 걸리는군요.

fm100의 이미지

한줄짜리로 만들어 봤습니다.

fm100@fm100-desktop:~/tmp$ cat facto.py
result = reduce (lambda x, y: x*y, range (1, 100001))
fm100@fm100-desktop:~/tmp$
fm100@fm100-desktop:~/tmp$ time python facto.py

real 0m18.958s
user 0m17.780s
sys 0m1.110s
fm100@fm100-desktop:~/tmp$

=================================================
Do the python !
=================================================

=================================================
Do the python !
=================================================

sjin의 이미지

위 코드로
real 2m43.489s
user 2m42.546s
sys 0m0.868s

이 나왔는데 신기한건 같은 기계 위에서
Bignum Library 같은 거 안 쓰고 C++로 한참 걸려 구현하여 돌려봤더니

[sjin@login C]$ g++ -O3 -o fact fact.cpp
[sjin@login C]$ time fact > result_c.txt

real 1m2.657s
user 1m2.608s
sys 0m0.000s

이 나오는군요.

이 결과를 보니 고생해서 C++로 만들 필요 없는 경우가 많을 것 같습니다.
이런걸 보고 스크립트 언어의 생산성이 좋다고 하나 봅니다.

molla의 이미지

1분 2초와 2분 43초면 두배 이상 차이나는 것인데, 그정도 차이면 차이가 많이 난다고 봐야할 듯 합니다.
물론 스크립트 언어는 최적화 등에 신경을 전혀 쓰지 않은 단순한 코드라 더 차이가 나겠지만요. (전 1.5배 차이만 나도 많이 난다고 생각했는데, 생각보다 차이가 크네요.)

여튼 점점 컴퓨터가 빨라져서, 굳이 성능을 신경쓸 필요가 없어져 가는 것은 사실인 듯 합니다. 실행 속도를 조금 높이기 위해 한참 애써서 프로그램 만들 필요는 점점 줄어간다고 봐야겠지요.
물론 일부 분야... 서버나 엔진 쪽에 들어가는 분야 등엔 아직도 생산성 보다는 성능을 중요시 여기는 분야가 있을 수 있습니다. 하지만 이쪽은 상대적으로 작은 분야라 할 수 있을 듯 합니다.

oppor의 이미지

우분투 64비트 듀얼코어에서 파이선 돌리니까 22초 나오는군요.

저도 심심해서...ㅋㅋㅋ

warpdory의 이미지

약 39초 ..


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

즐겁게 놀아보자.
http://akpil.egloos.com

댓글 첨부 파일: 
첨부파일 크기
Image icon f100000.jpg93.74 KB


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

즐겁게 놀아보자.

jaurang2908의 이미지

없으십니다 그려 ㅋㅋ

mentoso의 이미지

같은 댓글이 또 달릴 것 같은 불길한 예감이..

snowall의 이미지

1분간 할일이 없으셨나보죠. ㅋㅋ

--------------------------
피할 수 있을때 즐겨라!
http://snowall.tistory.com

피할 수 있을때 즐겨라! http://melotopia.net/b

warpdory의 이미지

오후 5시에 칼퇴근해서 집에 도착하면 6시쯤 되고 ...
씻고, 밥먹고 ... 대충 6시 30분 ~ 7시쯤 됩니다.
그리고 밖에 나가서 한시간쯤 운동하고 들어와서 샤워하고, 애들하고 좀 놀아주다보면 9시 뉴스 하죠.
9시 뉴스 보면서 애들하고 좀 놀아주고 ... 이러다가 10시쯤 애들 잠들면 ... 뭐 그다지 할 일은 없습니다.
얼마전부터 보고 있던 책 몇권도 다 읽어서 책도 고를 겸, 인터넷 좀 뒤젹거리고, PC 앞에 앉아서 이것저것 좀 하다가 11시쯤 자러 가니깐 ...

뭐 밤 10시 반경에는 빈둥 거리고 있을 시간이니깐 별로 할일 없던 건 맞는 것 같습니다.

칼퇴근이 장려되는 회사를 다니니깐(제조업입니다. 오후 5시 15분 되면 사무실 전기를 꺼버리기 때문에 강제로라도 퇴근해야 합니다.) 공부도 하고 좋네요 뭐. 대신 아침에 출근이 8시까지이긴 하지만, 일찍 자고 일찍 얼어나서 회사 와서 일 끝내고 칼같이 퇴근하니깐 좋습니다.

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

즐겁게 놀아보자.
http://akpil.egloos.com


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

즐겁게 놀아보자.

Hyun의 이미지

부럽습니다.


나도 세벌식을 씁니다
sephiron의 이미지

$ time perl -Mbigint -e '$a=1;$a*=$_ foreach (1..100000);'
 
real    10m48.907s
user    10m42.640s
sys     0m0.031s

bigint로 해봐야 의미가 있을 것 같네요.

ydongyol의 이미지

컥~ 임베디드 리눅스 컴파일 용도로 쓰는 p4-2.8g입니다..

real 49m19.880s
user 49m13.521s
sys 0m1.546s

--
Linux강국 KOREA
http://ydongyol.tistory.com/

--
Linux강국 KOREA
http://ydongyol.tistory.com/

poss의 이미지

윈도우 계산기가 시간이 오래걸리는데 계속할거냐구 자꾸 찡얼거려서 1분정도 참다가 그냥 종료했습니다..

;ㅡㅡ

studenes의 이미지

gcalctool 5.26.2

1초.

superwtk의 이미지

import time
from multiprocessing import Pool
from math import log, floor
 
def partial_factorial(bound):
    fact = bound[0]
    for i in xrange(bound[0]+1, bound[1]+1):
        fact *= i
    return fact
 
if __name__ == '__main__':
    pool = Pool(processes=2)
    start = time.time()
    results = pool.map(partial_factorial, [(1, 50000), (50001, 100000)])
    end = time.time()
 
    result = 1
    for i in range(0, len(results)):
        result *= results[i]
 
    exponent = floor(log(result))
 
    print '%d digits (%f sec)' % (exponent+1, end-start)

Intel Core 2 Duo 2.66GHz 인데, 하나의 코어만 사용할 경우 평균적으로 41.5초 근처가 나오는 반면, 두개의 코어를 모두 사용할 경우 7.0초 정도가 나오네요.

--------------------------------------------------------------------------------
http://blog.sumin.us

ifree의 이미지

싱글 코어에서도 분할 계산을 하면 시간이 많이 단축되네요.
Big integer 다루는 오버헤드 탓인가요?

ruinfire의 이미지

이거 쿼드코어로 하니까.. 1.4초 나오네요 ^^
쿼드 2.6 입니다 ^^

------------------------------------------------------
팔 어딘가가 간지러운데 찾아 긁을 수 없는? 그런 기분??

댓글 첨부 파일: 
첨부파일 크기
Image icon 11.JPG0바이트

------------------------------------------------------
팔 어딘가가 간지러운데 찾아 긁을 수 없는? 그런 기분??

Hyun의 이미지

0.67초 나왔습니다.
Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz, 하이퍼쓰래딩까지 합쳐 8개입니다. 4개보다 딱 2배네요.

[hyun@hyun ~]$ python 123.py 
1051300 digits (0.710708 sec)
[hyun@hyun ~]$ python 123.py 
1051300 digits (0.673217 sec)
[hyun@hyun ~]$ python 123.py 
1051300 digits (0.678486 sec)
[hyun@hyun ~]$ cat 123.py 
import time
from multiprocessing import Pool
from math import log, floor
 
def partial_factorial(bound):
    fact = bound[0]
    for i in xrange(bound[0]+1, bound[1]+1):
        fact *= i
    return fact
 
if __name__ == '__main__':
    pool = Pool(processes=8)
    start = time.time()
    results = pool.map(partial_factorial, [(1, 12500), (12501, 25000), (25001, 37500), (37501, 50000), (50001, 62500), (62501, 75000), (75001, 87500), (87501, 100000)])
    end = time.time()
 
    result = 1
    for i in range(0, len(results)):
        result *= results[i]
 
    exponent = floor(log(result))
 
    print '%d digits (%f sec)' % (exponent+1, end-start)
 
[hyun@hyun ~]$ 

나도 세벌식을 씁니다
Scarecrow의 이미지

제가 아직 싱글코어 시퓨를 쓰고 있어서 몰랐었는데...
예전에 Python의 GIL때문에 떠들썩 했던거 같은데
2.6과 3.0에 multiprocessing 패키지가 포함되었군요.

http://www.python.org/dev/peps/pep-0371/

위 코드를 보니 41초에서 7초라니... 성능도 참 예쁘네요. ^^

youknow의 이미지

저같은 경우에는 딱히 필요한 기능이 없으면 안정된 구버전을 쓰자는 쪽이어서
파이썬 2.5를 지금까지 계속 사용하고 있었는데,
저 패키지 때문에 2.6으로 갈아탈까말까 고민되더군요ㅋ

kasworld의 이미지

일단 시간 계산이 result 값을 구한 뒤쪽으로 이동해야 할것 같구요.
수정후에 쿼드 코어에서 2.5초 정도가 나오는 군요.
아무튼 덕분에 multiprocessing 을 어떻게 쓰는지 좋은 공부가 되었습니다.

import time
from multiprocessing import Pool
from math import log, floor
 
def part_fact( pfargs ):
    fact = 1
    for i in xrange( *pfargs ): 
        fact *= i
    return fact
 
def calc_part_fact( ):
    pargs = []
    numthread = 10
    for a in range(numthread) :
        b = ( a+1 , 100000+1 , numthread)
        pargs.append( b )
 
    pool = Pool(processes=numthread)
    results = pool.map(part_fact, pargs )
 
    result = 1
    for i in results:
        result *= i
    return result
 
if __name__ == '__main__':
    start = time.time()
    result =calc_part_fact() 
    end = time.time()
    exponent = floor(log(result))
 
    print '%d digits (%f sec)' % (exponent+1, end-start)
superwtk의 이미지

감사합니다.

result = 1
    for i in range(0, len(results)):
        result *= results[i]

대신

 result = 1
    for i in results:
        result *= i
    return result

처럼 작성했어야 됐는데, 매일 Java 나 Objective C 같은 언어만 다루다 보니까 그쪽 문화(?)가 머리에 박혀버린것 같네요^^;;

--------------------------------------------------------------------------------
http://blog.sumin.us

kasworld의 이미지

이런 식으로 조금씩 수정하고 노는 걸 원래 좋아 합니다. ^^

import time
from multiprocessing import Pool
from math import log, floor
import sys
 
if sys.version_info >= ( 3 , 0 ):
    xrange = range
 
def part_fact( pfargs ):
    return reduce( lambda x,y : x*y , xrange( *pfargs ) )
 
def calc_part_fact(numthread = 10,numfact = 100000 ):
    start = time.time()
 
    pargs = map( lambda a : ( a+1 , numfact +1 , numthread) ,range(numthread) ) 
 
    pool = Pool(processes=numthread)
    results = pool.map(part_fact, pargs )
 
    middle = time.time()
 
    result = reduce( lambda x,y : x*y , results )
 
    end = time.time()
    return result,start,middle,end
 
if __name__ == '__main__':
    nf = 100000
    for nt in range(2,17) :
        result,start,middle,end =calc_part_fact(nt,nf)
        exponent = floor(log(result,10))
        print( 'fact %d : thread %d :partial(%f sec):merge(%f sec):total(%f sec):digit %d' % 
                (nf , nt,middle - start ,end-middle, end-start,exponent+1 ) )                 

코드를 더 압축 할수도 있겠지만 너무 압축하면 가독성이 너무 떨어 지는 관계로 이정도만 해봤습니다.

듀얼 코어 에서 실행해봤는데 특이히게도
6,12 쓰레드(정확히는 프로세스)에서 가장 빠르군요.
신기해 하고 있습니다.
이유가 뭘지 혹시 알려주실분 없으실까요?

imyejin의 이미지

Intel Core Duo CPU T2450 2.00GHz 랩탑에서 리눅스 데비안 언스테이블 최신 하스켈 컴파일러 패키지 GHC 6.10.4 로 컴파일하여 실행한 결과, 출력시간까지 포함해서 35초입니다.

real 0m35.511s
user 0m35.146s
sys 0m0.040s

소스는 단 한 줄 아무 옵티마이즈 옵션 없이 그냥 기본으로 ghc --make 로 컴파일한 겁니다. (사실 라이브러리 루틴 product 부르는 거라 옵티마이즈 해도 별 차이 없이 35초.)

main = print (product [1..100000])

.
.
.

하지만 제가 직접 세네 줄로 날코딩했더니 출력시간까지 포함해서 승리의 6초!!! 하스켈 구현이 느리다는 건 어디까지나 옛날 이야기.

real 0m6.209s
user 0m6.100s
sys 0m0.056s

fac 0 acc = acc
fac k acc = fac (k-1) $! (k*acc)
 
main = print (fac 100000 1)

@ 참고로 GHC에서 임의 크기 정수인 Integer 타입은 gmp를 쓰는 걸로 알고 있습니다.

@@ 코어 두 개 쓰는 건 귀찮아서 안해봤지만 http://www.haskell.org/haskellwiki/Haskell_in_5_steps 에 보면 Parallel Haskell 라이브러리를 써서 구현하는 예제가 있으니 심심한 분들은 해보시길 ... (링크한 URL에 나오는 건 꼬리 되돌기가 아니라 좀 느릴테니 제가 한 것처럼 꼬리되돌기로 바꾼 다음 저런 식으로 돌리면 더 빨리 할 수 있다고 누가 해 놓은 걸 본 적이 있는 거 같은데 다시 찾으려니 못찾겠군요.)

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

ifree의 이미지

저 속도의 차이는 Tail Call Optimization 의 결과인가요?
대단하군요.

imyejin의 이미지

왜냐하면 product 구현도 tail call로 되어 있긴 할테니 그 이유는 아닌 것 같고, 리스트 노드 십만개를 만들었다 없앴다 하는 삽질 때문인 건지 어쩐지는 ... 하여간 저도 무슨 이유인지는 잘 모르니 GHC 메일링 리스트에다 질문 함 올려봐야죠.

=====================================================

아 자문자답입니다. IRC 채널에서 놀다가 하스켈 해커들한테 금방 답을 얻었는데 product는 고정 크기 정수 타입인 Int에 대해서만 lazy evaluation없는 루틴으로 계산(foldl 대신 foldl'을 사용하는 효과)을 해준다는군요. (그것도 -O2를 했을 때만 된다 그냥 된다 의견은 분분했지만 어쨌든 간에) 그냥 정의는 product = foldl (*) 1 이고 컴파일러가 Int인 경우에는 특별히 product = foldl' (*) 1 처럼 계산하는 루틴으로 링크를 시켜준답니다 -_-;; 그러니까 foldl의 strict 버전인 foldl'을 써서 foldl' (*) 1 [1..100000] 를 계산하니 제가 그냥 날코딩한 거랑 차이 없네요.

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

imyejin의 이미지

매뉴얼 보니 쓰는 법도 간단하네요.

import Control.Parallel
import Data.List
 
main = a `par` b `par` c `par` d `pseq` print (a * b * c * d)
     where
       a = foldl1' (*) [1,5..99997]
       b = foldl1' (*) [2,6..99998]
       c = foldl1' (*) [3,7..99999]
       d = foldl1' (*) [4,8..100000]

이번에도 "출력 시간 포함"해서 같은 CPU(코어2듀오 2.0GHz)에서 2초 이내로 찍습니다 ㅎㅎ

real 0m2.015s
user 0m1.949s
sys 0m0.040s

@ 쿼드코어니 하이퍼쓰레딩이니 그런 건 없어서 더 못돌려보겠습니다 -_-;;

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

lifthrasiir의 이미지

>>> import time
>>> def k():
...     r = 1
...     for i in xrange(1,100001): r *= i
... 
>>> a = time.time(); k(); time.time() - a
60.521805047988892
>>> def kk():
...     r = 1
...     for i in xrange(1,50001): r *= i * (100001-i)
... 
>>> a = time.time(); kk(); time.time() - a
43.965256929397583

이제는 낡아버린(코어 2 듀오 2.16GHz, 2기가 램. 요즘은 좋은 컴이 많아서..) 맥북 프로에서 돌려 봤습니다. 아랫쪽 코드는 사실 어떻게 보면 당연한 최적화일지도 모르겠군요.

Hyun의 이미지

근데, 윈도 계산기에서는 어떻게 계산하나요?


나도 세벌식을 씁니다
comlegi의 이미지

윈도우 계산기의 매뉴의 보기항목에서 공학용을 선택하시면 됩니다.

참고로 전 진수 변환시 이거 유용하게 써먹습니다.
--------------------------------------------------------------
말은 생각을 변형, 왜곡해서 고정하는 도구이다. 글은 더하다.

//-----------------------------------------------------------------------------------
말은 생각을 변형, 왜곡해서 고정하는 도구이다. 글은 더하다.

swirlpotato의 이미지

아니면 간단하게 100000! 라고 입력하셔도 됩니다.

글 도배 해보세... 룰루랄라

Hyun의 이미지

“!”는 버튼으로 없나요? 숨겨진 기능인가요?
----
버튼이 있었군요...


나도 세벌식을 씁니다
aero의 이미지

Perl에서 수치계산용 모듈들로는

Math::GSL ( http://search.cpan.org/dist/Math-GSL/ ) - Perl interface to the GNU Scientific Library (GSL)
Math::Pari ( http://search.cpan.org/dist/Math-Pari/ ) - Perl interface to PARI.
등이 있고 arbitrary size한 숫자를 계산하기 위해서는 GMP라이브러리를 wrapping한
Math::GMP ( http://search.cpan.org/dist/Math-GMP/ ) - High speed arbitrary size integer math
가 있습니다.

Perl은 Math::GMP 모듈이 깔려있으면 arbitrary size한 숫자를 계산하기 위해 BigInt(Float)계 모듈을 사용하면
GMP를 사용해서 성능을 높입니다. GMP모듈이 없으면 pure perl 구현을 통하기 때문에 속도가 좀 느려집니다.

다음은 제일 처음 python 코드가
60.803870 s 라고 결과를 뱉은 머신에서 돌린 결과입니다.

time perl -e 'use Math::BigInt lib=>"GMP"; $f=Math::BigInt->new("100000"); $f->bfac();'
 
real    0m0.195s
user    0m0.110s
sys     0m0.080s

빠르죠? :)

Scarecrow의 이미지

$f->bfac();

sangheon의 이미지

좋습니다.

--

B/o/o/k/w/o/r/m/

--

Minimalist Programmer

다콘의 이미지

python도 mxNumber를 사용하면 무지 빠릅니다.
이것도 GMP를 사용합니다.

aero의 이미지

어떤 언어든 binding library 를 사용하면 똑같지만
Perl은 GMP모듈을 사용하기 위해 위 소스를 수정할 필요없이 그대로 두고

cpan Math::GMP
명령만 내리면 모듈이 바로 설치되고 그 후 실행시
뒷단은 Perl이 알아서 해주기 때문에 간단하다는 거죠 :)

익명 사용자의 이미지

말씀하신 것이 에러없이 실행되려면 Math::BIgInt::GMP 모듈을 설치해야 하네요. Math::GMP 모듈만 설치한 경우에는 안 되네요.

keedi의 이미지

Math::BigInt++
bfac++

----
use perl;

Keedi Kim

youknow의 이미지

단순한 성능테스트가 아니라 팩토리얼을 빠르게 계산하는거라면 더 빠른 방법도 있습니다.

수학과 교수님 한분이 얘기해 주신건데,

팩토리얼을 계산하기위한 approximation이 있습니다.

그 교수님이 예~전에 비싼 워크스테이션에서 성능테스트용으로

만인가 십만 팩토리얼을 계산해봤는데 10분인가 걸렸는데

집에와서 pc로 해보니 금방 나오길래 '어라?' 했었는데,

알고보니 집에있는 소프트웨어는 팩토리얼을 approximation으로 구하는거였다시더군요.ㅋ

근데 approximation이긴 해도 팩토리얼 같은 경우에는 워낙에 값이 띄엄띄엄 있어서

적당히 구한다음에 타당한쪽으로 반올림 비슷하게 하는식으로

정확한 값을 구할 수가 있다고 합니다.

글쓰다가 방금 구글링 해봤더니 Stirling's approximation 이라는게 나오는데,

이게 그건지는 모르겠습니다.

ps. KLDP는 구경만하다가 처음 올려보는 글이네요 ㅋ

Scarecrow의 이미지

gmp에 있는 factorial함수도 단순히 그냥 곱하지 않죠.
그래서 매우 빠릅니다.

http://mgccl.com/topics/factorial

imyejin의 이미지

펄에서 GMP라이브러리로 한 코드에서 $f->bfac() 인가 하는 함수가 그걸 부른 것 같군요. 펄 구동 시간이 더 오래 걸렸을 것 같습니다.

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

aero의 이미지

바퀴를 재발명하지 않고 가능한 기존 리소스를 이용해서 최대의 결과를 내는게 컴퓨팅의 미덕이지요
그것이 CPAN이란 것을 가지는 Perl의 장점이라 그것을 잘 이용했을 뿐입니다. :)
Perl이 가능한 최선책을 사용해서 알아서 하니깐 ( GMP가 사용가능 하지 않다면 코드가 에러나며 정지하지 않고 기본모드로 자동 fall back합니다. ) 위 코드에서 GMP모듈이 없다고 코드를 수정할 필요도 없구요.

Perl 구동시간과 계산시간 비교

$time perl -e ''
 
real    0m0.018s
user    0m0.000s
sys     0m0.010s
 
$time perl -e 'use Math::BigInt lib=>"GMP"; $f=Math::BigInt->new("100000"); $f->bfac();'
 
real    0m0.197s
user    0m0.120s
sys     0m0.080s

Perl구동시간은 계산시간의 1/10정도네요.

imyejin의 이미지

음 ..댓글은 삭제가 안되니

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

imyejin의 이미지

펄에서 GMP라이브러리로 한 코드에서 $f->bfac() 인가 하는 함수가 그걸 부른 것 같군요.

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

Scarecrow의 이미지

http://gmplib.org/manual/Factorial-Algorithm.html

gmp 메뉴얼에 보면 알고리즘 설명도 있으니 관심있으신 분들에게는 좋은 자료가 될 듯합니다.

johan의 이미지

sbcl:

(defun n!-loop (n)
  (loop with result = 1
        for i from 1 to n
        do (setf result (* result i))
        finally (return result)))
 
(defun n!-tail (n)
  (labels ((n! (i result)
             (if (> i n)
                 result
                 (n! (1+ i) (* i result)))))
    (n! 1 1)))
 
(compile 'n!-loop)
(compile 'n!-tail)
 
(time (progn (n!-loop 100000) nil))
Evaluation took:
  15.989 seconds of real time
  14.596912 seconds of user run time
  0.63204 seconds of system run time
  [Run times include 1.26 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  9,029,652,712 bytes consed.
 
(time (progn (n!-tail 100000) nil))
Evaluation took:
  16.115 seconds of real time
  14.684918 seconds of user run time
  0.592037 seconds of system run time
  [Run times include 1.344 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  9,029,668,056 bytes consed.

processor : 0
vendor_id : AuthenticAMD
cpu family : 15
model : 44
model name : AMD Sempron(tm) Processor 3300+
stepping : 2
cpu MHz : 1800.000
cache size : 128 KB
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 1
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 syscall nx mmxext fxsr_opt lm 3dnowext 3dnow up pni lahf_lm ts fid vid ttp tm stc
bogomips : 3618.71
clflush size : 64

johan의 이미지

(time (progn  (n!-recursive 100000) nil))
 
Evaluation took:
  78.105 seconds of real time
  74.90868 seconds of user run time
  2.288143 seconds of system run time
  [Run times include 17.501 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  9,029,649,400 bytes consed.
 
 
 
(defun count-digits (n)
  (assert (> n 0))
  (1+ (truncate (log n) (log 10))))
 
;; 검산
(count-digits (n!-recursive 100000))
456574

그런데 cpu가 두개로 나오네요. 코어가 두개인가? 처음 알았네요 Atom cpu가 코어 두개인지...

processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 28
model name : Intel(R) Atom(TM) CPU N270 @ 1.60GHz
stepping : 2
cpu MHz : 800.000
cache size : 512 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 1
apicid : 0
initial apicid : 0
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe constant_tsc arch_perfmon pebs bts pni dtes64 monitor ds_cpl est tm2 ssse3 xtpr pdcm lahf_lm
bogomips : 3192.10
clflush size : 64
power management:

processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 28
model name : Intel(R) Atom(TM) CPU N270 @ 1.60GHz
stepping : 2
cpu MHz : 800.000
cache size : 512 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 1
apicid : 1
initial apicid : 1
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe constant_tsc arch_perfmon pebs bts pni dtes64 monitor ds_cpl est tm2 ssse3 xtpr pdcm lahf_lm
bogomips : 3191.93
clflush size : 64
power management:

sylphong의 이미지

(defun n!-tail (s n)
  (labels ((n! (i result)
             (if (> i n)
                 result
                 (n! (1+ i) (* i result)))))
    (n! s 1)))
 
(time
 (let ((threads
        (list (sb-thread:make-thread (lambda () (n!-tail 1 50000)))
              (sb-thread:make-thread (lambda () (n!-tail 50001 100000))))))
   (print
    (1+ (floor (/ (log (apply #'* (mapcar (lambda (x)
                                            (sb-thread:join-thread x))
                                          threads)))
                  (log 10)))))))
 
456574 
Evaluation took:
  21.603 seconds of real time
  30.101882 seconds of total run time (29.049816 user, 1.052066 system)
  [ Run times consist of 1.460 seconds GC time, and 28.642 seconds non-GC time. ]
  139.34% CPU
  34,477,350,672 processor cycles
  4,588,274,728 bytes consed

조금 빠르네요. 아톰N230에서 30초 나오네요.
SBCL에서 큰수에 대한 곱하기 연산이 생각보다 느린것 같네요.
마지막에 apply *를 빼면 20초 나오는군요.
purluno의 이미지

Scala 단순 곱셈

purluno@tiger:~/tmp$ cat 100kfac.scala
def fac(n: Int): BigInt = fac(n, 1)
def fac(n: Int, res: BigInt): BigInt = {
    if (n == 0)  res
    else         fac(n - 1, res * n)
}
 
val startTime = System.nanoTime
val res = fac(100000)
val computingTime = System.nanoTime - startTime
println(res)
val afterPrint = System.nanoTime - startTime
println("Computing   : " + computingTime)
println("After print : " + afterPrint)
purluno@tiger:~/tmp$ scala 100kfac.scala
...
Computing   : 42500003352
After print : 94366682457

AMD Athlon64 3800+ (코어 1개)

계산은 42.5초. 출력하는데만 50초가 넘게 걸리니 BigInt의 문자열 처리 과정이 비효율적인 것 같습니다.

purluno의 이미지

foldLeft를 사용해본 것.

오름차순으로 계산해서 그런지 몇 초 단축이 되네요.

val startTime = System.nanoTime
val res = (1 to 100000).foldLeft(BigInt(1))(_ * _)
val computingTime = System.nanoTime - startTime
println(res)
val afterPrint = System.nanoTime - startTime
println("Computing   : " + computingTime)
println("After print : " + afterPrint)

...
Computing   : 37084145636
After print : 98054981864

purluno의 이미지

이번엔 Scala의 actor를 이용해서 작업을 2개로 분할해본 것입니다.

약 26.7초로, 코어가 하나라도 꽤 단축되네요.

import scala.actors.Actor._
 
val startTime = System.nanoTime
 
val a0 = self
 
val a1 = actor {
    val res = (1 to 50000).foldLeft(BigInt(1))(_ * _)
    a0 ! res
}
 
val a2 = actor {
    val res = (50001 to 100000).foldLeft(BigInt(1))(_ * _)
    a0 ! res
}
 
def recv = receive { case x: BigInt => x }
val res = recv * recv
val computingTime = System.nanoTime - startTime
println(res)
val afterPrint = System.nanoTime - startTime
println("Computing   : " + computingTime)
println("After print : " + afterPrint)

Computing   : 26681934903
After print : 88231200115

purluno의 이미지

싱글코어임에도 불구하고 256개의 actor를 사용하니 효율이 크게 증가하네요.

약 4초만에 계산했습니다.

문자열로 변환하는 것이 너무 오래 걸려서 bit 개수를 이용해 자릿수 근사치를 계산했습니다.

import scala.actors.Actor._
import scala.Math._
 
val start = 1
val end = 100000
val numWorkers = 256
 
val startTime = System.nanoTime
 
val a0 = self
 
def runActor(start: Int, end: Int, step: Int): Unit = {
    actor {
        val res = (start to end by step).foldLeft(BigInt(1))(_ * _)
        a0 ! res
    }
}
 
def runActors(start: Int, end: Int, numWorkers: Int): Unit = {
    for (i <- 0 until numWorkers) {
        runActor(start + i, end, numWorkers)
    }
}
 
def recv = receive { case x: BigInt => x }
 
runActors(start, end, numWorkers)
val res = (0 until numWorkers).map(_ => recv).reduceLeft(_ * _)
 
val computingTime = System.nanoTime - startTime
println("Computing              : " + (computingTime * pow(10, -9)) + " s")
println("N-digits approximation : " + res.bitLength * log(2) / log(10))

Computing              : 3.9088685630000004 s
N-digits approximation : 456573.69957353856

danskesb의 이미지

예제 코드도 많이 나와서 도대체 어떤 코드로 어떻게 테스트를 해야 하는가가 감이 안 서네요. 이게 KLDP의 매력 같습니다.

---- 절취선 ----
http://blog.peremen.name

세벌의 이미지

엠에스윈도 엑스피의 계산기로
2.8242294079603478742934215780245e+456573
오래 걸리니 계속할 거냐는 메시지 몇번 나오네요.
근데... 시간을 안 쟀네요 하여간 오래 걸린 거 같네요. 계산기 돌려놓고 하던일 하면서...
http://sebul.sarang.net/

Hyun의 이미지

위에 python으로 계산했을 땐 1051300자릿수가 나왔는데, 윈도 계산기의 결과는 다르네요...
누가 거짓말을 하고 있을까요?

----
위에 python 스크립트에서 자릿수 계산을 잘못했네요. 다음과 같이 수정해야겠군요.

exponent = floor(log(result)/log(10))

나도 세벌식을 씁니다
imyejin의 이미지

456575자리가 맞습니다.

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

Hyun의 이미지

456574 자리인 듯.


나도 세벌식을 씁니다
aero의 이미지

검산

perl -e 'use Math::BigInt lib=>"GMP"; $f=Math::BigInt->new("100000"); print length $f->bfac();'
456574
imyejin의 이미지

전 귀찮아서 wc 로 세었더니 newline 이 포함되어 하나 더 많이 세었습니다 ㅠ.ㅠ ㅈㅅ

456574 가 맞습니다.

제대로 검산!!

GHCi, version 6.10.4: <a href="http://www.haskell.org/ghc/" rel="nofollow">http://www.haskell.org/ghc/</a>  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :m Data.List
Prelude Data.List> print $ length $ show $ foldl1' (*) [1..100000]
456574

임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin

programmeryh의 이미지

사양은...
[programmeryh@main-server ~]$ cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Pentium(R) Dual-Core CPU E5200 @ 2.50GHz
stepping : 6
cpu MHz : 2500.000
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni dtes64 monitor ds_cpl est tm2 ssse3 cx16 xtpr pdcm lahf_lm
bogomips : 5012.51
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:

processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Pentium(R) Dual-Core CPU E5200 @ 2.50GHz
stepping : 6
cpu MHz : 1203.000
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
apicid : 1
initial apicid : 1
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni dtes64 monitor ds_cpl est tm2 ssse3 cx16 xtpr pdcm lahf_lm
bogomips : 5012.02
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:

[programmeryh@main-server ~]$

winner의 이미지

계산시간보다 출력시간이 많이 걸리는군요. 2진 -> 10진 전환이 시간이 많이 걸리는 듯...

isty2e의 이미지

4.2초 정도 나오네요. 생각보다 빨라서 놀랐습니다.

cleansugar의 이미지

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

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

혹시 (10!)!이 몇 자리의 숫자인지 계산해 보셨나요?
http://kldp.org/node/31380

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

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

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

andysheep의 이미지


recursive 깊이로 먹통되는 경우도 피할 수 있고 꿩먹고 알먹는 법이지요.
보통 512에서 1012번 넘어가면 파이썬은 에러 납니다.

숫자 계산 recursive 함수는 이전 값은 배열이나 list에 저장해서 쓰면 수십배 빨라집니다.

Devuan 1.0 (Debian without systemd)
amd64 station: AMD FX(tm)-6100 Six-Core Processor, 8 GB memory, 1 TB HDD
amd64 laptop: HP Touchsmart

글쇠판: 세벌 최종식, 콜맥 (Colemak)

viper9의 이미지

저 위에 파이선 스크립트로 계산해보았습니다.

2011년형 17인치 맥북프로 2.2GHz Core i7, OSX 10.7.2입니다.

3번 했는데 평균 1.1초 정도네요.