정수 곱셈 한계 κ, 0.003 벽을 넘다
Κ = 0.003 for integer multiplication crossed
CrocSwap/integer-mult-bounds 저장소의 PR #4441은 query thinning과 helper retiming을 결합해 조건부 κ를 0.00300105까지 끌어올렸다. 이는 #4440의 0.00296보다 1.3868% 높은 값으로, T(n) = O(n (log n)^(1 - 0.00300105))라는 경계를 제시한다. 유료 호출은 72,902에서 69,273으로 줄었고, 저자는 이 결과가 검토 대기 중인 조건부 구성이며 무조건적 정리나 실제 런타임 개선을 주장하지 않는다고 밝힌다.
이는 검토를 기다리는 저자 검증 조건부 구성이다. 선택된 프런티어의 변경, 무조건적 정리, 실용적 런타임 주장, 전역 최적성, 형식적 또는 독립적 인간 검증은 주장하지 않는다.
HN 토론
21- jdb1729
@platypii와 저는 여기서 kappa 개선에 대한 Lean 검증을 진행해 왔습니다: https://github.com/platypii/integer-mult-bounds-lean
캠페인의 현재 상태: kappa >= 2^-14.38이 Mathlib의 TM2 머신에서 무조건 증명되었습니다. 기여를 환영합니다!
- joeldw
이 속도 향상이 정확히 어떻게 작동하는지 이해할 수 있는 간단한 방법이 있는지 아는 사람 있나요? 표준 O(N log N) 곱셈은 iiuc, FFT를 통한 주파수 분해를 사용하는데, 이 구성은 어떤 모습일까요?
- readthenotes1
"#4440의 p17 쿼리-씬드 복합 컨트롤러에 대한 19개의 전체 네이티브 호출 모두에 검증된 fresh-helper 리타이밍을 적용합니다. 16개의 유료 쿼리 시어, 전체 유휴 호출, 메인 오퍼레이터 및 더 강력한 BIT 공급업체는 유지됩니다."
저는 그 단어들 중 많은 것을 이해하지만, 문맥 안에서는 분명히 아무것도 이해하지 못하는 것 같습니다...