• Subject: Re: [FUN] Compress number in 2 bytes
• From: Egor Skriptunoff <egor.skriptunoff@...>
• Date: Fri, 2 Jul 2021 22:44:47 +0300

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.