Fast Polynomial Evaluation - Compute polynomials twice as fast
Fast Polynomial Evaluation은 호너(Horner) 방식보다 훨씬 적은 곱셈으로 다항식을 계산할 수 있는 혁신적인 도구입니다. 계수를 전처리하여 단항 다항식의 경우 ⌊n/2⌋+1번의 곱셈만으로 계산을 끝낼 수 있으며, 이는 기존 방법의 약 절반 수준입니다. 웹사이트에서 다항식을 입력하고 필드를 선택하면 자동으로 최적의 평가 체인을 생성해 줍니다. exp, sin, cos 같은 함수 근사나 암호학, 해싱, 코딩 이론에 활용할 수 있습니다. 수학적 체인, C 코드, 그래프 등 다양한 형태로 결과를 확인하고 다운로드할 수 있습니다. 이 프로젝트는 arXiv에 게재된 논문을 기반으로 하며, GitHub에서 소스 코드도 공개되어 있습니다.
놀라운 발견입니다. 계수를 조금만 전처리하면 어떤 단항 다항식이든 ⌊n/2⌋+1번의 곱셈만으로 평가할 수 있습니다. 이는 기존 호너 방법의 절반에 불과합니다.
HN 토론
41- emil-lp
어제(아니면 그저께였나) 당신의 arxiv 논문을 읽었습니다.
이걸 k-path에 대한 대수적 방법을 가속하는 데 사용할 수 있다고 생각하시나요?
그렇다면 내년 PACE 챌린지에 참가해 보세요.
- IsTom
꽤 멋지네요, 특히 유한체에서요. 그런데 Q에서는 계수가 꽤 빨리 커지는 것 같지 않나요?
- pvillano
정말 멋집니다. 데모를 가지고 놀면서 많이 배웠어요. Horner와 Estrin만 알고 있었는데, 이제 대부분을 이해한 것 같아요.
한 가지 작은 개선을 제안하자면, 그래프 시각화에서 각 x, x^2, x^4에 대해 별도의 소스 노드를 두는 것입니다. 단일 x 소스는 그래프를 복잡하게 만들고 구조를 가립니다.
- throwaway81523
다항식을 전처리할 거라면, 여러 다른 점에서 평가하고 싶을 수도 있겠네요. 그런데 그렇다면 왜 FFT를 사용하지 않나요?
- voxelghost
알고리즘을 전환할 때 'monic'에서 예를 들어 'ln(1+x)'로 계속 되돌아가다가, 그러고 나서 'monic'에 고정되는 것 같습니다? (제가 뭔가 놓치고 있는 걸까요?)
또한 궁금한데, 당신 버전과 horner에서 두 알고리즘이 fmadd 연산 수에 어떻게 대응되나요?