Show HN: Compute polynomials twice as fast

6 comments

• voxelghost 2 hours ago
  It keeps flipping back to 'monic' from e.g. 'ln(1+x)' when switching between algorithms, and then seems to lock to 'monic'? (Am I missing something?)

  Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?

  [-]
  • gowld 1 hour ago
    "monic" is a separate switch from the example functions radio-selector. Enabling "monic" removes the leading coefficient.
• vlovich123 2 hours ago
  Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
• aetherspawn 2 hours ago
  I guess it’s not faster than using a table for CRC8?
• gowld 1 hour ago
  From the abstract, a name that many on HN would recognize:

  > 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 (this http URL).
• gowld 2 hours ago
  What is the tradeoff between multiplication and addition?
  [-]
  • nraynaud 1 hour ago
    Just a few years ago, mults were slower, but I think now (Intel i9) mult, add and fma are the same.

    https://stackoverflow.com/a/39135689
  • gigatexal 1 hour ago
    I think multiplications are faster to do in computer land than adds? I too am curious.
    [-]
    • hyperhello 1 hour ago
      Also could use analysis of dependencies to see what can happen in parallel. Or for that matter, some real benchmarks.