유리수 전처리로 9차 다항식 평가를 곱셈 8회에서 5회로 줄인 인터랙티브 데모

CRC8처럼 테이블을 쓰는 방식보다도 빠른 건지 궁금함.

CRC8은 입력을 다항식 계수로 보고 고정 다항식으로 나머지를 구하는 문제라 다름. 여기서는 계수를 미리 알고 있는 다항식을 전처리해 빠르게 계산하며, 논문 5.9절은 CRC에 가까운 범용 해싱도 다룸.

WyHash나 xxh3 같은 빠른 해시에 적용되는지, 아니면 주로 암호 해시용인지 궁금함.

Poly1305나 Polymur 같은 범용 해시에는 적용 가능함. 다만 실제 최고 성능을 이기는지는 아직 불분명하고, WyHash와 xxh3은 다항식 구조가 아님.

WyHash와 xxh3이 빠른 이유 중 하나는 실제 체 곱셈 대신 휴리스틱을 쓰기 때문임. 그래서 무작위 키에서도 충돌 확률을 비정상적으로 높이는 적대적 입력을 만들 수 있고, 논문 165쪽에서 둘 다 분석함.

알고리즘을 바꾸면 예제 함수가 ln(1+x) 같은 선택값에서 monic으로 계속 돌아가고 나중엔 고정되는 듯함. Horner와 비교해 FMA 연산 수는 어떻게 되는지도 궁금함.

monic은 예제 함수 선택과 별도 스위치임. 켜면 선행 계수를 제거함.

곱셈 수와 덧셈 수를 맞바꾸는 이유가 뭔지 궁금함. 요즘 컴퓨터에선 곱셈이 덧셈보다 빠르지 않나?

부동소수점이라면 FMA, 수치 안정성, 파이프라이닝 면에서 Estrin 방식을 쓰는 편이 낫다고 봄. 하지만 해싱과 암호에 쓰는 유한체에서는 곱셈이 덧셈보다 훨씬 비싸서 이 알고리즘의 주된 대상이 됨.

현대 CPU도 곱셈은 덧셈보다 지연 시간이 1-2클록 큰 경우가 많고, 덧셈 실행 유닛이 더 많은 CPU도 있음. 예를 들어 AMD Zen은 벡터 덧셈 4개와 곱셈 또는 FMA 2개를 클록당 처리할 수 있음.

미리 전처리할 거면 여러 점에서 계산할 테니 FFT 다점 평가를 쓰면 되지 않나?

FFT 다점 평가는 모든 평가점을 미리 알 때 좋음. 해시맵의 다항식 해시나 표준 라이브러리 exp 근사처럼 입력이 스트리밍으로 들어오는 경우에는 맞지 않음.

유한체에서는 특히 흥미롭지만, 유리수 Q에서는 계수가 너무 빨리 커지는 듯함.

다항식 역함수도 같은 차수라 가장 큰 계수가 커지는 문제가 있음. Knuth-Eve와 Pan은 차수 d 다항식의 근을 써서 조금 작지만, 여전히 실용적이지 않음.