Karatsuba 알고리즘 질문이요.. kjunking2002 구종만씨의 블로그에서 예제 코드를 봤는데 질문이 있습니다. 주소 : http://jmk.pe.kr/pages/read/logs/library/karatsuba-fast-integer-multiplication normalize() 함수 부분에서 for(int i = 0; i < num.size(); i++) { 가 아니라 num.size()-1 이 아닌가 해서요.. num[i+1]에 값을 넣어 가다보면 마지막에 잘못된 주소를 참조 하지 않나요?? 11년 전
1개의 댓글이 있습니다. 일루 일단 그 버그가 생기려면 normalize 과정에서 제일 윗자리에서 아래쪽 캐리가 일어나야 하니 전체 결과가 0 미만이어야 합니다. 필자가 의도한 바는 아닌지 모르겠으나(?) (a0+a1)*(b0+b1)-a0*b0-a1*b1 = a0*b1+a1*b0 >=0 이라서, 그렇게 되는 경우는 없어보입니다. 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kjunking2002
구종만씨의 블로그에서 예제 코드를 봤는데 질문이 있습니다.
주소 : http://jmk.pe.kr/pages/read/logs/library/karatsuba-fast-integer-multiplication
normalize() 함수 부분에서
for(int i = 0; i < num.size(); i++) {
가 아니라 num.size()-1 이 아닌가 해서요..
num[i+1]에 값을 넣어 가다보면 마지막에 잘못된 주소를 참조 하지 않나요??
11년 전