Documents
Demo
Demo
On Universal Codes for Integers: Wallace Tree, Elias Omega and Beyond
- Citation Author(s):
- Submitted by:
- Arun Konagurthu
- Last updated:
- 24 February 2021 - 4:14pm
- Document Type:
- Demo
- Document Year:
- 2021
- Event:
- Presenters:
- Lloyd Allison
- Paper Code:
- DCC21 Paper ID: 139
- Categories:
Comments
Slides and presentation talk
Slides and presentation talk video for the paper:
On Universal Codes for Integers: Wallace Tree, Elias Omega and Beyond
to be presented by Lloyd Allison
Computation Time
Your results are very interesting!
Now having even more universal codes at hand, I think it would be time to have a comprehensive list of integer codes with a recommendation which code fits best to which integer domain (in case that a use case is restricted to dealing with integers in a certain domain).
I would like to ask about the $O(\lg^2 n)$ time bound on slide 16 whether there is some detailed explanation available.
Do you know whether there exists a repetitive subtree structure in the constructed WTC trees such that you can decompose a path traversal into a traversal in subtrees and glue the computed bits together? (For instance with the clustering described in "The Tree Inclusion Problem: In Linear Space and Faster" by Philip Bille and Inge Li Gørtz)?
If so, you could build lookup tables for the small subtrees, and maybe achieve $O(\lg n)$ time?
I am also wondering whether bit-parallel techniques could be applied to compute the WTC codes for multiple integers in parallel as long as they fit into a machine word.