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 a_n=2ⁿ. This problem has many applications
in the compiler area. The lookup table is a one-to-one function, mapping the finite sequence a_n on to the set of integer
numbers {0, 1, ..., N-1}. The technique of fast mapping of the sequence a_n=2ⁿ, n=0,1,..., N-1, where N=2^k, 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.