On perfect hashing of numbers with sparse digit representation via multiplication by a constant |
| |
Authors: | Maurizio Monge |
| |
Institution: | Scuola Normale Superiore di Pisa - Piazza dei Cavalieri, 7 - 56126 Pisa, Italy |
| |
Abstract: | Consider the set of vectors over a field having non-zero coefficients only in a fixed sparse set and multiplication defined by convolution, or the set of integers having non-zero digits (in some base b) in a fixed sparse set. We show the existence of an optimal (or almost-optimal, in the latter case) ‘magic’ multiplier constant that provides a perfect hash function which transfers the information from the given sparse coefficients into consecutive digits. Studying the convolution case we also obtain a result of non-degeneracy for Schur functions as polynomials in the elementary symmetric functions in positive characteristic. |
| |
Keywords: | Magic multiplier Hash function Bitboard Schur function |
本文献已被 ScienceDirect 等数据库收录! |