[링크]직접만든 프로그램으로 2의 1000000000 (10억)승 계산한게 자랑
글쓴이: 지리즈 / 작성시간: 화, 2011/04/19 - 1:59오전
http://gall.dcinside.com/list.php?id=hit&no=10262&page=1&bbs=
역시 디씨이네요.
결과물의 자리수가 대략 3억 자리가 넘고 텍스트 파일로 293M 라고...
저는 이글 올리는 순간 3억자리가 넘는 숫가 몇바이트인가 계산해본 것이 전부.
Forums:
이 글을 본 나는 Python에서...
이 글을 본 나는 Python에서 2 ** 1000000000을 했을 뿐이고. 그 결과를 기다릴 뿐이고. 하하..
* 수정 *
게시판에 글 올리는 사이에 결과가 나왔을 뿐이고. 하하..
저도 저글 보자 마자 똑같은 계산을 시키고
저도 저글 보자 마자 똑같은 계산을 시키고 있었습니다. ㅎㅎ;;;
그런데 생각보다 오래 걸려서 분석해 봤더니
계산 하는것( n = 2** 1000000000) 보다
인쇄하는 데 시간을 더걸리고
그것도
n을 10진 문자열로 변환하는데 가장 오랜시간이 걸리더군요. ;;;
그리고 100억을 계산 하려 했더니 메모리가 20G 넘게 필요해서 관뒀습니다. ^^
나름 제가 필요한
나름 제가 필요한 수준(실험데이터or유한요소해석데이터에서 수치 추출 및 연산 이라던가 수치 미분 적분 등 간단한 수준만...ㅎㅎ)에선 프로그래밍 좀 아는데...
이게 그냥 2^(10억)하면되나요?
c언어 배울때 가장 길이가 긴 정수형 변수도 200메가나 되는 수치를 담는다는 말은 못들어본거 같은데...
언어마다 변수 특징이 다르니 정확히 파이썬으로 해보고싶지만, 파이썬 설치하기가 귀찮아서..-_-
포트란으로 한번 해봐야겠네요..ㅎㅎ
프갤을 여기서 볼줄이야 - ㅅ-)... 그나저나
프갤을 여기서 볼줄이야 - ㅅ-)...
그나저나 사람들이 정말 신기한게,
BigInt를 왜 못짜는거죠...?
char로 10진수 하는건 또 잘하면서 int로 2^32진수로 하는건 못하더라구요...
char로 10진수 다루는 건 보통인가
char로 10진수 다루는 건 보통인가 보네요...
전 프로그래밍은 딱 필요한 만큼만 필요할때 공부해서 쓰는지라 영 깜깜하네요...
포트란으로도 못하겠어요~ㅎㅎ 이것도 사실 배운지 얼마 안됀거라...-_-
차라리 씨언어나 매트랩이 더 익숙하긴한데...왠지 2^10억은 안될거 같아서리..
십진수로 하는거는 손으로 하는 곱셈을 분석해서 짜면
십진수로 하는거는 손으로 하는 곱셈을 분석해서 짜면 됩니다.
프로그래밍이 다른 수학하고 살짝 다른게,
추상화된 작업을 특정 수준까지 깨고 내려가는거죠 ㅡ,ㅡ)
최적화의 악령에 빠져서...
저도 BigInt 만드려고 몇번 했는데 int형 array로 2진수로 나타내고 곱하고 더하기 알고리즘좀 좋은거 찾으려니 도저히 못해먹겠더라고요.. 그냥 GMP 썼음...
근데 왜 굳이 10진수로 계산하려고 하죠??
그냥 2진수로 1이 맨 앞에 있고 0이 10억 - 1개 붙어있는것 아닌가...
적당히 계산할 거리가 없어서 그런거 아닐까요
적당히 계산할 거리가 없어서 그런거 아닐까요 ㅎㅎ
원래 백만팩 천만팩 돌리고 놀았는데,
팩토리얼 특성상 숫자가 급격하게 커져버리니....
저 숫자가 적당히 크고 임팩트가 있죠 'ㅅ')
이런
이런 거죠.
http://kldp.org/node/24905
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
역시나.. 예지력이 상승했군요.. 이글 나올줄
역시나..
예지력이 상승했군요.. 이글 나올줄 알았습니다 :D
저게 힛갤 간 경위가
처음에 수작업으로 2진수 200, 300자리 정도 계산한 게 두 명 정도 힛갤 갔고
그걸 보고 프겔의 글쓴이가 원래 팩토리얼 구하는 프로그램을 2진수 구하는 프로그램으로 수정해서 만든거라 그럴겁니다.
http://en.wikipedia.org/wiki/
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
1000000000Log10[2]
http://www.wolframalpha.com/input/?i=1000000000log10%282%29
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
10만승
10억승은 좀 어렵고 (충분히 빠르게 안나오네요) 10만승은 간단히 짜봤습니다.
https://gist.github.com/926042
KLDP에서 더 많이 세면 디씨를 이겼다고 광고 될
KLDP에서 더 많이 세면 디씨를 이겼다고 광고 될 것 같은데요. ㅋㅋㅋㅋ
2의 10억승의 10억승 정도 계산하면 될 듯.
이거 API 괜찮군요.
http://www.apfloat.org/apfloat_java/
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
10억의 10억제곱이면 300MB*300MB ~
10억의 10억제곱이면 300MB*300MB ~ 100EB = 90000TB정도 됩니다. 이걸 저장하려면 하드디스크 값만 억대가 넘어가죠...
해낸다면, 여러모로 폐인소리 들을 듯...-_-
http://www.zdnet.co.kr/news/news_view.asp?artice_id=20110211172659
인간이 지금까지 만든 정보량이 300EB정도 되니까, 어마어마한 양입니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
그렇군요.
그렇군요.
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
기사 재밌었습니다.
DNA의 정보량이 인류가 만든 데이터량 295EB 의 100배정도라면,
저장장치를 DNA로 만들수는 없을까요?
DNA RAM
후후
좋은 코드입니다. 잘 보고 갑니다.
좋은 코드입니다. 잘 보고 갑니다.
컴퓨팅 파워 남는 분들 이거 계산하시면
컴퓨팅 파워 남는 분들 이거 계산하시면 좋습니다.
비트코인
http://ko.wikipedia.org/wiki/%EB%B9%84%ED%8A%B8%EC%BD%94%EC%9D%B8
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
웃긴 댓글:ㅋ 병신들아 48/2(9+3) 계산하는
웃긴 댓글:
ㅋ 병신들아 48/2(9+3) 계산하는 프로그램이나 만들어라
김유식 요즘 디시가 너무 어려워졌어요. ㅠ.ㅠ
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
시간이 꽤 걸리는군요.
저도 Python으로 계산만 해볼려고 했는데 시간이 꽤 걸려서 포기했습니다. 이런 거 다중 core 사용하면서 가장 쉽게 지원하는 언어구현이 뭘까요?
메트랩(학교서버)하고 Mathematica(놋북)에서
메트랩(학교서버)하고 Mathematica(놋북)에서 시도해봤는데
안나옵니다 - ㅅ-)ㅋㅋㅋ
범용으로는 못구해요.
언어별
언어별 라이브러리
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
GPU 가속 라이브러리
http://en.wikipedia.org/wiki/OpenCL
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
http://en.wikipedia.org/wiki/
http://en.wikipedia.org/wiki/Largest_known_prime
NHK 다큐-리만가설, 천재들의 150년의 도전 재밌네요
http://kldp.org/node/120508
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
저걸 만든 인간이 친구인데 심심 풀이로 팩토리얼 고속
저걸 만든 인간이 친구인데 심심 풀이로 팩토리얼 고속 계산을 해보자는 이유로 여러 알고리즘과 OPENMP를 써서 한적이 있습니다. 그 때 만들어진 라이브러리로 2의n승은 대충 만들어서 올린 것 같네요.
간단하게 생각하고 만들어 봤는데 생각만큼 쉽지
간단할줄 알고 그냥 대충 만들어 봤는데 생각만큼 쉽지 않네요.
http://www.indidev.net/forum/viewtopic.php?p=219
저처럼 한가하신 분들은 한번씩 손으로 직접 코딩해 보세요.
ps) 아 쓰고 보니 위에 비슷한 소스가 이미 있네요.
======== 서명 =======
주거지는 www.indidev.net 입니다.
밀은 무한대 지원하는 라이브러리가 있는데 지수를
밀은 무한대 지원하는 라이브러리가 있는데 지수를 지원하는 걸 못 찾겠습니다.
2진수 곱으로 하는 게 *0, *1이니까 간단하고 더 빠를텐데 2진수 라이브러리도 못 찾겠습니다.
실패작:
import org.apfloat.Apint; import org.apfloat.ApintMath; import java.io.Writer; import java.io.BufferedWriter; import java.io.File; import java.io.FileWriter; import java.io.FileNotFoundException; import java.io.IOException; public class twopow { public static void main(String[] args) { Apint twoPow = ApintMath.pow(new Apint(2), 10000); Writer w = null; try{ File f = new File("2pow.txt"); w = new BufferedWriter(new FileWriter(f)); twoPow.writeTo(w,true); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } finally { try { if (w != null) { w.close(); } } catch (IOException e) { e.printStackTrace(); } } } }재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
간단할줄 알았는데.. 심플한 알고리즘으로는
간단할줄 알았는데..
심플한 알고리즘으로는 100만승까지는 도는데 그 이상은 머리 좀 써야되겠네요 ㅋ
IronPython은 금방 계산하네요.
계산 후에 400MB(32bit), 540MB(64bit) memory를 점유하고 있는 것을 보면 적시계산을 위한 준비를 하고 있는 것 같지는 않네요. 하지만 출력은 도저히 못하겠네요. math.log10 을 하니 301029995.~ 이 나오는 것을 보면 정확히 계산한 듯 합니다.
CPython 64bit는 1억거듭제곱까지는 계산할 수 있군요. 시간은 좀 걸리지만.... 3.2가 2.7.1 보다 좀더 빠른 듯...
제가 알기로 IronPython은 C#으로 구현한 것으로 아는데 C#을 쓰면 괜찮은 성능이 나오지 않을까요? 출력은... -_-.
Python은 내부적으로 2진법 체계로 계산하는거 같네요
그래서 계산 시켜놓으면 빠르게 계산은 해놓는데
10진수로 출력 시키면 진수 변환시키느라 한참 걸리더군요
그냥 처음부터 10진법으로 구해서 결과 뱉는 시간이 더 빠르네요 -_-;
힛갤에 올라가신 분꺼는 아예 처음부터 10진 체계로 계산하는거 같네요.
출력을 염두한다면 그럴겁니다.
feanor 님이 작성하신 source를 참고해서 10000진법을 사용하고, Strassen이나 카라츠바 곱셈 algorithm을 적용하면 10억거듭제곱을 구하는데 문제는 없을 거라고 봅니다.
큰 수의 진법변환은 매우 시간이 오래 걸리는 작업이죠. 괜히 C 표준에 10진 부동형을 넣을려는게 아닐겁니다.
카라슈바 나 톰쿡 보단
역시 FFT가 진리죠
이 글을 쓰신분 공비군 입니까? 분위기가 팍
이 글을 쓰신분 공비군 입니까?
분위기가 팍 느껴지네요
ㅎㅎㅎㅎ
아니요 프갤 자주 눈팅하던 사람입니다. 공비님이 이야기 하는걸 자주 봤어요
음.. 제가 실수했군요.
3의 천만거듭제곱을 하니 결과가 안 나오는군요. 오히려 CPython이 빠른데... IronPython과 CPython의 구현을 확인해야 정확하겠지만 IronPython의 거듭제곱은 2가 밑일 때 자리수를 이동시키는 기법을 쓰는게 아닌가 하네요.
IronPython도 거듭제곱을 할 때 다중 thread 를 쓰지 않는 것으로 보이고 Karatsuaba algorithm 만 가지고는 단일 thread 로 계산해낼 수 없는 것 같군요. 밑이 2일 때를 가정하지 않고서는 말이죠.
Apint twoPow =
Apint twoPow = ApintMath.pow(new Apint(2), 10000);
를 10억으로 고치면 결과가 나옵니다.
100억으로 고치면 int 범위 넘는다고 에러.
Apint twoPow = ApintMath.pow(new Apint(2), new Long("10000000000"));
으로 고치면,
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at org.apfloat.internal.IntMemoryDataStorage.implCopyFrom(IntMemoryDataStorage.java:63)
at org.apfloat.spi.DataStorage.copyFrom(DataStorage.java:611)
at org.apfloat.internal.Int3NTTConvolutionStrategy.autoConvoluteOne(Int3NTTConvolutionStrategy.java:196)
at org.apfloat.internal.Int3NTTConvolutionStrategy.autoConvolute(Int3NTTConvolutionStrategy.java:178)
at org.apfloat.internal.Int3NTTConvolutionStrategy.convolute(Int3NTTConvolutionStrategy.java:117)
at org.apfloat.internal.IntApfloatImpl.multiply(IntApfloatImpl.java:1156)
at org.apfloat.Apfloat.multiply(Apfloat.java:733)
at org.apfloat.Apint.multiply(Apint.java:313)
at org.apfloat.ApintMath.pow(ApintMath.java:66)
at twopow.main(twopow.java:13)
이런 에러가 납니다.
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
말그대로 Out of memory네요
말그대로 Out of memory네요
컴파일러-Xms m-Xmx m읍션 최대로
컴파일러
-Xms m
-Xmx m
옵션 최대로 잡아도 안돼서 64bit java 깔아야 될 듯.
32bit랑 같이 깔면 충돌날 듯한데...
64bit로 하니 다른 에러가 납니다.
Exception in thread "main" org.apfloat.internal.TransformLengthExceededException: Maximum transform length exceeded: 100663296 > 50331648
at org.apfloat.internal.IntFactor3SixStepNTTStrategy.transform(IntFactor3SixStepNTTStrategy.java:132)
at org.apfloat.internal.Int3NTTConvolutionStrategy.autoConvoluteOne(Int3NTTConvolutionStrategy.java:197)
at org.apfloat.internal.Int3NTTConvolutionStrategy.autoConvolute(Int3NTTConvolutionStrategy.java:178)
at org.apfloat.internal.Int3NTTConvolutionStrategy.convolute(Int3NTTConvolutionStrategy.java:117)
at org.apfloat.internal.IntApfloatImpl.multiply(IntApfloatImpl.java:1156)
at org.apfloat.Apfloat.multiply(Apfloat.java:733)
at org.apfloat.Apint.multiply(Apint.java:313)
at org.apfloat.ApintMath.pow(ApintMath.java:66)
at twopow.main(twopow.java:13)
1504780000승까지만 계산됩니다.
크기는 431메가 나오고, AMD Athlon II X3 440 에서 1분 45초 걸렸습니다.
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
공비님 2의 30억승 구하셨네요
공비님 2의 30억승 구하셨네요
http://gall.dcinside.com/programming/246509
참고로 이건 제가 짠겁니다.
참고로 이건 제가 짠겁니다. http://codepad.org/kM1NUDxH
코멘트는 신경 안쓰셔도 됩니다.
뭐 예전일이라 ㅡ,ㅡ);;
기억으로는 저걸 이진수 버전으로 변경해서
64bit 환경에서 백만팩인가 천만팩인가 구하는데 17초가 걸렸습니다.
32bit의 경우는 memcpy를 사용하는게 더 빠르더군요.
공비님이 프갤에 올린 코드
unsigned long long a[99999]={1,},p=1,r,s,c;main(n){for(scanf("%d",&n);n>1;r?a
이런 짤렸네요
http://ideone.com/UIJze
이 코드 입니다.
이건 팩토리얼이네요..
이건 팩토리얼이네요..
======== 서명 =======
주거지는 www.indidev.net 입니다.
단순히 빅인트에 대한 얘기인지라.... 원래 프겔에서
단순히 빅인트에 대한 얘기인지라....
원래 프겔에서 이 떡밥(!?)으로 돌기도했고,
팩토리얼이나 2의 10억승이나 단순히 적당히 큰 값을 뽑기위한 도구에 불과하죠.
저 분은 빅인트에 fft, multi-thread(쿼드코어 지원)를 추가한걸로 알고있습니다.
아마 이번 계산에서 멀티쓰레드는 빠지지 않았나 싶지만.
10만 팩토리얼 계산
10만 팩토리얼 계산 속도
http://kldp.org/node/107470
재미있는 놀이: 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