Re: [FUN] Compress number in 2 bytes

[Egor Skriptunoff <egor.skriptunoff@...>]

On Fri, Jul 2, 2021 at 9:58 PM Xmilia Hermit wrote:

-- compressor.lua

local num_bits = 64

local function Encode(what)
    local tab = {}
    for i = 3, num_bits * 4 + 4, 2 do
        tab[i] = 1
    end
    local top = num_bits * 4 - 4
    for i = 1, num_bits do
        if (what & (1 << (i - 1))) ~= 0 then
            tab[top] = 1
        end
        top = top - 2
    end
    for k, v in pairs(tab) do
        tab[k] = nil
    end
    return tab
end

return Encode(...)

-- decompressor.lua
local num_bits = 64

function Decode(tab)
    for i = 3, num_bits * 4 + 4, 2 do
        tab[i] = 1
    end
    local pow2 = next(tab, num_bits * 4 - 3) == num_bits * 4 + 3
    local top = num_bits * 4 - 5
    local step = (num_bits * 4) - (pow2 and 0 or 1)
    tab[step * 2] = 1
    tab[step * 3] = 2
    if not pow2 then
        tab[step * 4] = 2
    end
    local num = 0
    for i = 1, num_bits do
        local k, v = next(tab, top)
        if v == 1 then
            num = num | (1 << (i - 1))
        else
            tab[step * (i + 4)] = 2
        end
        top = top - 2
    end
    return num
end

return Decode(...)

SOLVED!
The solution of Xmilia Hermit is clever, rather complex, and too memory-consuming: required hash part size is 256.

Problem #2:
Solve the problem #1 for N = math.maxinteger by abusing table's hash part of a much lesser size.