god10hour   1년 전

순수 FFT로 문제를 처리하되 10비트씩 나눠서 합성곱을 구하는 방식으로 코드를 작성하였습니다.

그러나 N=1000, M=1000, f[i]=1000000, g[i]=1000000 등 케이스에서 올바른 결과를 출력하나

N=500000, M=500000등의 충분히 큰 케이스에서 오차가 발생합니다.

해결 아이디어를 얻고싶습니다..

zenith82114   1년 전

계수들은 전범위 랜덤으로 하고 N,M 10**5 이하의 랜덤 데이터를 넣으면 전부 정답이 나오는데, N,M=10**6으로 올리면 거의 매번 미세하게 차이나는 값이 나오는 것을 관찰했습니다. double형의 정밀도 문제가 있는지 점검해 보시면 좋을 것 같습니다.

god10hour   1년 전

저도 double형의 정밀도 문제를 생각해서 질문글 작성 이후 long double로 교체해봤으나 여전히 오차가 해결되지 않았습니다.

azberjibiou   1년 전

정밀도 관련 문제라면 아래 블로그를 읽어보면 좋을 것 같습니다.

https://algoshitpo.github.io/2...

chleee   1년 전

저도 같은 문제로 많이 고민했는데요, 똑같은 에러가 나신 것 같습니다.

해당 코드에서 17번째줄의 ang의 타입을 long double로 고쳐보시겠어요?

god10hour   1년 전

가장 최근에 작성한 코드는 제출번호 96083577를 참고하시면 됩니다.

나누는 비트를 2^16으로 해보고 ang의 타입을 long double로 고쳐보는듯 여러 시도를하였으나 모두 틀린 답을 내놓았습니다..

chleee   1년 전

올려주신 코드에서 long double만 고치고 제출했을땐 AC를 받았습니다.

http://boj.kr/78dc7f5bf9ab44aa...

혹시 수정하시다가 다른 부분을 바꾸신게 아닌가 싶은데, 위에 코드 한 번 확인하시면 좋을 것 같습니다.

저도 실수 오차때문에 많이 애먹었어서 ㅠㅠ... 

god10hour   1년 전

수정한 코드에서는 CVL 함수에서 원본을 참조하면서 원본 v, u에 변형이 생기는것을 무시해서 오류가 생기는 것이었는데, 그 점을 간과한 것이었습니다.. 첫 코드에서 long double로 바꾸니까 되네요..

chleee   1년 전

넵.. 수고하셨습니다

댓글을 작성하려면 로그인해야 합니다.