HN 日本語サマリー

← 一覧へ戻る
プログラミング

Show HN: 多項式計算を2倍高速化

Show HN: Compute polynomials twice as fast (thomasahle.com)

109 pointsby thomasahle34 コメント

要約

この記事は、ハッシュアルゴリズムで使用される乗算の回数を削減する方法について、著者らが長年研究してきた成果を紹介しています。完全なLean証明を経て、多項式評価をより効率的に行うための新しい方法をウェブサイトで公開し、Knuthらの既存手法と比較できるようにしています。

全文翻訳

数年前に、共同研究者とハッシュアルゴリズムで使用される乗算の回数を減らせないかと思っていました。私たちは構築方法と100ページに及ぶ証明を持っていましたが、それが正しいかどうか100%確信が持てませんでした。今ではLeanによる完全な証明があるので、公開することにしました。

このウェブサイトは、多項式を評価する必要がある人が誰でも、私たちの手法や、Knuthらによる数多くの従来のアプローチと比較してどのように評価されるかを簡単に確認できるように作成しました。