Sage Notebook 에서의 2000000! 의 신비로움

글쓴이: dymaxion / 작성시간: 수, 2012/12/12 - 3:07오후

어제 재미삼아 제 노트북(리눅스민트)에 Sage를 인스톨해 봤습니다.
(참고 http://sagemath.org )

매쓰매티카 대체품으로 수학에 특화되어 있어서
고등수학, 심지어 현대수학 문제까지 다룰 수 있는 강력함을 가지고 있다길래
호기심으로 깔아서 써보고 있는데요.

전에 여기 나빌레라님께서 '50000!'을 계산하는 알고리즘을 각 언어별로 짜 보고 비교분석 해 보신 글을
재미있게 읽었기 때문에, Sage에서는 어떨까 하고 해 봤습니다.

( 나빌레라님의 글 참고
http://kldp.org/node/129116
http://kldp.org/node/129379
http://kldp.org/node/129900 )

sage에 들어가서 factorial(50000) 하고 딱 때려 보니깐 헐! 순식간에 답이 턱 나오는 거에요.
그럼 이거 한 번 먹어봐랏 하면서 factorial(200000) 딱 때리니깐 0.5초만에 답이 나오는거에요.
그것도 숫자가 너무 많다면서 자동으로 텍스트파일을 만들어내더군요.
factorial(2000000) 때리니깐 한 5초 정도 소요되고...
factorial(20000000) 은 3분 정도 하더니 지가 알아서 포기하더군요. ㅠㅠ

헌데 나빌레라님은 분할정복 알고리즘 같은걸로 하니깐 이보다 훨씬 느리던데...
파이썬 기반이라는 Sage는 뭔 약을 먹었는지 이렇게 빠른가 하는 궁금증이 생겼습니다.

factorial.py 파일을 찾아보니깐 몇 개 나오던데
그중에 sympy 라이브러리에 들어있는 것도 있길래
Sage 말고 일반 파이썬 콘솔에서

from sympy import factorial
factorial(200000)

이렇게 계산 해 보니깐 2분 정도 걸리더라구요.
sympy 라이브러리 안의 factorial.py 안에 코멘트를 읽어 보니깐

"Computation of the factorial is done using two algorithms. For
small arguments naive product is evaluated. However for bigger
input algorithm Prime-Swing is used. It is the fastest algorithm
known and computes n! via prime factorization of special class
of numbers, called here the 'Swing Numbers'."

라고 해서 "현재까지 알려진 가장 빠른 Prime-Swing 알고리즘을 사용하고 있다"
라고 적혀 있는데, Sage 자체적인 factorial() 함수는 이것보다 훨씬 더 빠르다는거죠.

Sage 자체 알고리즘과 구현은 어떻게 되어 있는지는 모르겠는데
sympy에서 2분 소요된 것을 Sage로는 5초만에 끝나버리니............

* 한 줄 요약

Sage에서는
2000000! 계산을 10초도 안 걸려서 끝내버리는 신비로움... 두둥

Forums:

자유 게시판

어딘가에 적어놓은거 아닐까요?

글쓴이: snowall / 작성시간: 수, 2012/12/12 - 4:04오후

어딘가에 적어놓은거 아닐까요?

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

설마요~~~ ^^

글쓴이: DebPolaris / 작성시간: 수, 2012/12/12 - 5:19오후

설마요~~~ ^^

-----------------------------------------------------
남이 가르쳐주는 것만 받아들이는 것이 아니라, 스스로 만들고, 고쳐가는 사람을 '해커'라고 부른다.
그리고 자신이 쌓아온 노하우를 거리낌없이 나눌 줄 아는 사람을 '진정한' 해커라고 한다.
-Rob Flickenger 'Linux server hacks'

DEBIAN TESTING, KDE...
debpolaris.blogspot.kr

아양 떨듯이 해보게 되네요;;;

글쓴이: shint / 작성시간: 수, 2012/12/12 - 10:57오후

//
http://www.wolframalpha.com/input/?i=factorial%2810000000%29
울프램 알파도 빠른듯 해보입니다. 같은건가?? ㅡ_ㅡ;;;

factorial(10000000)
show(plot(sin(x) + sin(1.6*x), 0, 40)) 잘 되네요.

//
- GRUB 리눅스 3.6.6-1.fc16.i686.PAE cpu0 tty1
- 램디스크 초기화
- SMBus
- 페도라 16
- 부팅 시간이 3분 정도 걸리는 느낌 입니다.
- 처음 화면은 크롬 브라우저입니다.

- 텍스트를 복사하려면. 가상 환경과 복사가 안되서 곤란합니다.
- 그럴땐. 머신 설정 - 일반 - 고급 - 클립 공유 - 양방향 하세요. 적용되려면 껏다 켜야합니다.
- ALT+ F4를 누르면 환경이 종료되고. OpenBox 팝업이 띄워집니다.
- Ctrl + Tab 을 누르면 Plain Text 화면과 전환 됩니다.

제 컴퓨터 사양은
Core2 Duo E7400 2.8GHz
GeForce 9600 GT
RAM 1GHz 입니다.

sage-5.4.1.ova 파일을 다운받아 클릭하면. VBox가 설치해 줍니다. 1.46GB 입니다.
vmdk 파일이 생성되는데 4.7GHz 정도 됩니다.

Sage-5.4.1.vbox-prev -4251037바이트 8.59KB (VBox 실행시. 파일 크기가 주기적으로 변경 됩니다.)
sage-5.4.1-disk1.vmdk 4.7GB
Sage-5.4.1.vbox -9297309바이트 8.59KB (VBox 실행시. 파일 크기가 주기적으로 변경 됩니다.)

//중복 실행. 때문인지. 아니면. VBox라서 하드 영역이 동적이라 그런지.
//매우 오래 걸리며. 하드를 읽는 현상이 보였습니다. 30분 정도...

//테스트 결과 : 100,000 / 1초

factorial(100000)

WARNING: Output truncated!
full_output.txt

282422940796034787429342157802453551847749492609122485057891808654297795\
090106301787255177141383116361071361173736196295147499618312391802272607\
340909383242200555696886678403803773794449612683801478751119669063860449\
261445381113700901607668664054071705659522612980419583567789090475415128\
711408369242515352930962606722710387442460886354543639829317477617755326\
218511264748558649181803815198771612196815141299023044638240688965083575\
002296499396423642566352716149352078013312029433930594819960435396942025\
476101873825217271196652422246297861322189750497401951716531530489874836\
050566952715480176512162138004109816807973453547851752024621945048345013\
773263106939093503598859882632105284141400157567860960902916507469661354\

...

000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000
full_output.txt

//테스트 결과 : 1,000,000 / 30초
factorial(1000000)

WARNING: Output truncated!
full_output.txt

826393168833124006237664610317266629113534797896387304516777588556337961\
103564508444653051131146397335160680421087858854146474695064783618230121\
097542329959011564174624917379888389269193414176545783239319872802472198\
939643654445521615339205835199387989417742062408415939877018188072231692\
520577371284368598152223893115212552795468297422821642927484938877847124\
435722859509343621176452544930522658411976299056190121202414190025341283\
194330650762070040515959151171866138447509007558340374271376868770420937\
510235026334012483413149102176845494312736363990669719529613457333185577\
827926166902990562020543694097070666478519504010036753819785496799502593\
466664256139785735597641420835062544508843337001910346467387684551438607\
977529149091464312409535521184547553216224150396869723374549983306717288\
095362464807781832028542637742169723687519641684758647108242100299778180\

...

full_output.txt

//
오늘은 머리가 어정쩡 하고. 어제 나무 늘보 머리에 뭔가 심는 영상에. 사약 같은 콜라 대접
밖에서는 전투기인지 비행기 소리에 자동차 경적 소리까지. 참 다양하게 수준이 떨어지는 날입니다.

전력 수급이 부족하다고 하던데... ㅡ_ㅡ;;; 저는 죄인이군요...

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

VBOX에서 하면 약한가 보군요...

글쓴이: dymaxion / 작성시간: 목, 2012/12/13 - 12:31오전

제가 빠뜨렸는데, 제 환경은
HP430 노트북입니다. (인텔 i5 2.5GHz, 램4GB + 리눅스민트14나디아)
램을 많이 쓰는 건가 싶어서 모니터링을 해 보면
램 사용량의 증가율은 미미하고,
CPU는 4개 코어 중에 1개만 100%로 치솟았다가 곧바로 연산 끝내고 내려앉습니다.
factorial(1000000) --> 2~3초 정도 걸립니다.... ㅠㅠ

shint님의 테스트에서
VBOX 때문에 30초로 확 느려진건지, CPU가 E7400 이라서 그런건지.. (-,.-);
차이가 너무 많은 듯 합니다..

아무튼 제 통빡(?)으로는 너무 신비로와서리 ....

울프램알파도 서버의 하드웨어적인 우월성 때문에 결과가 빨리나오는 것만은 아니겠죠 아마?
수학용 소프트웨어에서 구사하는 알고리즘적인 방법이 따로 존재하는건가 하고 궁금해 집니다.

진짜 따로 결과값 테이블 같은걸 미리 만들어놨다가 뿌려주는 건감... (=,.=);

======================================
Mechanical Engineer
DymaxionKim.github.io
======================================

sage 내부에서도 GMP 알고리즘을 쓰는 것

글쓴이: bluekyu / 작성시간: 목, 2012/12/13 - 1:08오전

sage 내부에서도 GMP 알고리즘을 쓰는 것 같습니다.
http://www.sagemath.org/doc/reference/sage/rings/arith.html#sage.rings.arith.factorial

그리고 gmpy를 설치해서 실행해보니, 2000000! 과 20000000!이 다음과 같네요... (200000! 이 아닙니다.)

from gmpy import fac
fac(2000000)
 
real    0m0.699s
user    0m0.676s
sys     0m0.020s
 
from gmpy import fac
fac(20000000)
 
real    0m11.587s
user    0m11.417s
sys     0m0.148s

그리고 범위를 분할 시켜서 곱하는 함수를 단순하게 구현하고, 8 프로세스로 병렬하는 방식으로 실행하면 2000000!이 19초 정도 걸렸습니다.
역시 알고리즘이 중요하네요.

ps. 테스트 환경은 core i7-3770 (3.4 GHz), RAM 16GB, Kubuntu 12.04, Python 2.7 입니다.

/*** Signature ******************
* blog: http://blog.bluekyu.me/ *
********************************/

역시 고수분들이 많으셔서 감사드립니다..

글쓴이: dymaxion / 작성시간: 목, 2012/12/13 - 1:22오전

제가 찾지 못한 부분을 찾아주셔서 정말 감사드립니다.
GMP 라이브러리라는 걸 사용하는가 보군요...
이게 뭔지 정확히 모르는지라 구글링 해 보고 대충 감 잡아보고 있는 중입니다.
http://www.cs.fsu.edu/~langley/COP4342-2006-Fall/30-numericaltools3.pdf
나름대로 소소한 호기심 차원이었는데, 역시 kldp 만한 데가 없는 것 같아요!
감사합니다.

======================================
Mechanical Engineer
DymaxionKim.github.io
======================================

부 메뉴