IdeaWell

Project ideas from Hacker News discussions.

Show HN: Compute polynomials twice as fast

Original Article

Hacker News Discussion

📝 Discussion Summary (Click to expand)

Theme 1 – Applicability to hashing / universal hashing
Many commenters debate whether the preprocessing‑based speedup is worthwhile for streaming hash functions.

“This method is useful only when with a given polynomial, i.e. set of polynomial coefficients, you want to evaluate that polynomial many times, so the cost of the preprocessing is amortized.” – adrian_b
“It is applicable to fast universal hashes like Poly1305 and Polymur … however it's not clear … whether this work improves over the state of the art for that purpose.” – orlp

Theme 2 – Hardware performance considerations
Discussion centers on multiplication vs. addition costs, FMA usage, and execution‑unit throughput on modern CPUs.

“Just a few years ago, mults were slower, but I think now (Intel i9) mult, add and fma are the same.” – nraynaud
“Current timings on uops.info now show FP fma 4c and mul 3c over two multiply units, and add 2c over two separate addition units.” – ack_complete
“Many CPUs, like the AMD Zen CPUs, have more execution units that can do additions, than those that can do multiplications.” – adrian_b

Theme 3 – Theoretical constructions and alternatives
The paper’s injective polynomial hashing, its relation to Bernstein’s NH/Rabin‑Winograd, and alternatives like FFT multipoint evaluation are frequently mentioned.

“We also give an injective polynomial construction for universal hashing that uses N multiplications to hash 2N values with a single random key. This improves the best previous construction by Daniel J. Bernstein.” – thomasahle
“If you're going to preprocess the polynomial, maybe you want to evaluate it at many different points. But then why not use the FFT?” – throwaway81523
“FFT multipoint evaluation is great when you know all the evaluation points in advance. However, for many practical applications the input is only streamed to you.” – thomasahle

🚀 Project Ideas

PolyBench: Interactive Polynomial Evaluation Benchmarker & Visualizer

Summary

  • A web-based tool that lets developers benchmark and visualize polynomial evaluation algorithms (Horner, Estrin, Rabin-Winograd, etc.) across different hardware and data types.
  • Provides side-by-side comparison of operation counts, latency, throughput, and dependency graphs to help choose the optimal method for a given use case (e.g., hashing, function approximation).

Details

Key Value
Target Audience Developers working on cryptographic hashes, universal hashing, numerical libraries, or performance-critical polynomial evaluation
Core Feature Interactive benchmarking suite with visualizable instruction schedules, operation counting, and hardware-specific timing (via WebAssembly benchmarks)
Tech Stack TypeScript, Rust/Wasm for kernels, D3.js for graphs, Web Workers for parallel benchmarks
Difficulty Medium
Monetization Hobby

Notes

  • HN users expressed interest in seeing how algorithms map to fmadd operations and parallelism (gigatexal, hyperhello) and wanted better graph visualization (pvillano).
  • Could spark discussion on trade-offs between multiplication-heavy vs. addition-heavy methods on modern CPUs (adrian_b, Someone).

PolyHash: Fast Universal Hash Library using Injective Polynomials

Summary

  • A lightweight cryptography library implementing the injective polynomial hashing scheme from the paper (n/2 multiplications for 2N values) optimized for universal hashing in MACs (Poly1305, GCM) and hash table hashing.
  • Includes SIMD/FMA acceleration and optional preprocessing for fixed polynomials (e.g., Taylor coefficients) to amortize cost over many evaluations.

Details

Key Value
Target Audience Cryptography engineers, hash table implementers, developers needing high-speed universal hashing with strong collision guarantees
Core Feature Universal hash function achieving near-optimal multiplication count via injective polynomial construction, with AES-NI/CLMUL and AVX2/FMA backends
Tech Stack Rust (with stdsimd), C++ (with intrinsics), C bindings
Difficulty Medium
Monetization Revenue-ready: Dual licensing (FOSS + commercial support)

Notes

  • Commenters highlighted the utility for universal hashing in TLS/SSH (adrian_b) and the need for methods that improve over state-of-the-art for Poly1305/Polymur (orlp, thomasahle).
  • Addresses the frustration that preprocessing hurts streaming hashes (adrian_b) by offering a streaming-friendly variant (section 5.9) that uses n/2 multiplications without large key material.

PolyEval: Adaptive Polynomial Evaluation Engine for Math Libraries

Summary

  • A runtime code generation library that selects and applies the fastest polynomial evaluation algorithm (Estrin, Rabin-Winograd, etc.) for a given set of coefficients and evaluation pattern, targeting math library functions (exp, sin, Bessel) and special function approximations.
  • Integrates with existing math libraries (Boost, Cephes) via drop-in replacement for polynomial evaluation kernels.

Details

Key Value
Target Audience Maintainers of mathematical libraries, performance engineers working on scientific computing, GPU compute, or embedded math
Core Feature JIT/AOT compiler that generates optimized evaluation code (using FMA, instruction scheduling, and parallelism) based on coefficient structure and target ISA
Tech Stack LLVM/MIR for codegen, C/C++ headers, optional CUDA/HIP backends
Difficulty High
Monetization Hobby

Notes

  • Thomasahle suggested using Estrin's method for Boost math functions and noted interest in practical details (github.com/boostorg/math/issues/924).
  • Users discussed coefficient blow-up in rational approximations (IsTom) and the desire to accelerate algebraic methods like k-path (emil-lp), showing demand for adaptive, high-precision polynomial evaluation.

Read Later