FANMEETING, Karatsuba Algorithm 관련질문. canuyes 안녕하세요. 알고리즘 문제해결전략 책으로 공부중인 학생입니다. 공부중 너무 궁금한 점이 생겨 질문올립니다. 종만님의 책 p204 에서 문제해결의 힌트를 karatsuba 알고리즘에서의 '자리올림 생략으로' 설명하신것을 보았습니다. 자리올림을 생략했을때 C의 원소들이 C[7] : A[2]B[5] C[6] : A[2]B[4]+A[1]B[5] C[5] : A[2]B[3]+A[1]B[4]+A[0]B[5] .... (p204 그림 7.10기준) 위와 같이 더한 값 자체(올림처리 하지 않은)를 저장하고 있다는 말씀으로 이해했습니다. (틀렸다면 알려주십시오.) 위와 같이 이해하면 FANMEETING의 해답도, 종만님의 설명도 모두 이해가 갑니다. 그런데 kabatsura 알고리즘을 찬찬히 뜯어보던중, 만약 위 처럼 자리올림을 생략했을 때 C가 위와 같은 정보를 가지고 있다면, normalize를 마지막에 단 한번만 해도 되지 않을까 하는 생각이 들었습니다. 여러가지 방법으로 고민해보고, 종만님이 책에서 알려주신 스캐폴딩으로 반례를 찾아보려해도 잘 찾아지지가 않습니다. 우연히 구글링중 찾아낸 링크(아마도 종만님의 것 같습니다.) http://jmk.pe.kr/pages/read/logs/library/karatsuba-fast-integer-multiplication 에서는 add,sub,multiply함수에서 모두 normalize처리가 이뤄지고 있습니다. add,sub,multiply 등에서 normalize처리를 해주지 않고, karatsuba호 출 후에 karatsuba가 리턴한 값에 대해서만 normalize를 하는 것은 틀린 생각인가요?. 실력이 부족하다보니 검증이 안됩니다..ㅜㅜ 겸손한마음으로 종만님의 답변 기다립니다..ㅠㅠㅠ 10년 전
2개의 댓글이 있습니다. canuyes 댓글이 전혀 달리지를 않네요 ㅠㅠ 책과 관련된 질문은 어디에 해야하나요??ㅠㅠ 왠지 제가 번지수를 잘못 찾은듯한 느낌이... 10년 전 link JongMan 여기가 질문하실 곳이 맞긴한데요, 답이 쉽지 않다 보니 늦었습니다. 오버플로우가 나지 않는 한 아마도 괜찮을거라고 생각이 됩니다. 노멀라이즈를 하지 않으면 계산 중간값이 커지고 커져서 정수 범위를 넘을 수도 있겠죠. 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
canuyes
안녕하세요.
알고리즘 문제해결전략 책으로 공부중인 학생입니다.
공부중 너무 궁금한 점이 생겨 질문올립니다.
종만님의 책 p204 에서 문제해결의 힌트를
karatsuba 알고리즘에서의 '자리올림 생략으로' 설명하신것을 보았습니다.
자리올림을 생략했을때 C의 원소들이
C[7] : A[2]B[5]
C[6] : A[2]B[4]+A[1]B[5]
C[5] : A[2]B[3]+A[1]B[4]+A[0]B[5]
....
(p204 그림 7.10기준)
위와 같이 더한 값 자체(올림처리 하지 않은)를 저장하고 있다는 말씀으로 이해했습니다. (틀렸다면 알려주십시오.)
위와 같이 이해하면 FANMEETING의 해답도, 종만님의 설명도 모두 이해가 갑니다.
그런데 kabatsura 알고리즘을 찬찬히 뜯어보던중, 만약 위 처럼 자리올림을 생략했을 때 C가 위와 같은 정보를 가지고 있다면, normalize를 마지막에 단 한번만 해도 되지 않을까 하는 생각이 들었습니다.
여러가지 방법으로 고민해보고, 종만님이 책에서 알려주신 스캐폴딩으로 반례를 찾아보려해도 잘 찾아지지가 않습니다.
우연히 구글링중 찾아낸 링크(아마도 종만님의 것 같습니다.)
http://jmk.pe.kr/pages/read/logs/library/karatsuba-fast-integer-multiplication
에서는 add,sub,multiply함수에서 모두 normalize처리가 이뤄지고 있습니다.
add,sub,multiply 등에서 normalize처리를 해주지 않고, karatsuba호 출 후에 karatsuba가 리턴한 값에 대해서만 normalize를 하는 것은 틀린 생각인가요?.
실력이 부족하다보니 검증이 안됩니다..ㅜㅜ
겸손한마음으로 종만님의 답변 기다립니다..ㅠㅠㅠ
10년 전