Discrete Mathematics and Optimization Seminar
Alex Kreinin |
Algorithmics
Friday April 23rd at 1.30pm
McConnell 320
Title. Lookup Tables, Magic Numbers and Hamiltonian Paths.
Abstract.
We consider the problem of finding lookup tables for a sequence
an=2n. This problem has many applications
in the compiler area. The lookup table is a one-to-one function, mapping
the finite sequence an on to the set of integer
numbers {0, 1, ..., N-1}. The technique of fast mapping of the
sequence an=2n, n=0,1,..., N-1, where N=2k, is
considered in the talk. The algorithm is based on the transformation
that is a composition of the usual integer multiplication
and shift
operator. The problem appeared to be related to the finding Hamiltonian
path in a certain class of graphs.