Re: converting arbitrary long decimals to hex?

[Doug Currie <doug.currie@...>]

On Jan 8, 2010, at 1:29 PM, KHMan wrote:
> Norbert Kiesel wrote:
>> On Sat, 2010-01-09 at 02:04 +0800, KHMan wrote: 
>>> Norbert Kiesel wrote:
>>>> [snipped all]
>> Yeah, tabs went missing.  I include an untabbed version below (otherwise
>> unchanged).  Regarding the "real slow": it is guaranteed to decrease the
>> length of the decimal every round (due to the div:match() at the
>> bottom), so it's O(n^2).  Can you come up with something better?
> 
> The algorithm still works if you calculate for multiple hex digits at a time, e.g. using 65536 will get you 4 hex digits at a time. I think it works with 24 bits at a time too (53/2 > 24, still safe). You can grab more source digits at a time too. Curious... going to find some of those arbitrary prec code to learn something new...

Using KHMan's ideas, this version takes about 1/3 the time of Norbert's (both in LuaJIT2) for 19 digit numbers, and about 1/15 the time for 96 decimal digit numbers...

function tohex_e (decimal)
  local base = 2^24
  local function adddigit (t, d)
    local carry = d
    for i = 1, #t do
      local p = t[i] * 1000000 + carry
      t[i] = p % base
      carry = math.floor(p/base)
    end
    if carry ~= 0 then
      t[#t+1] = carry
    end
  end
  if type(decimal) == 'number' or #decimal < 15 then
     return ('%x'):format(decimal)
  end
  local thex = {}
  local j = #decimal % 6
  if j ~= 0 then
    thex[1] = tonumber(decimal:sub(1, j))
  end
  for i = j+1, #decimal, 6 do
    adddigit (thex, tonumber(decimal:sub(i, i+5)))
  end
  local hex = ''
  for i = 1, #thex-1 do
    hex = ('%06x'):format(thex[i]) .. hex
  end
  return ('%x'):format(thex[#thex]) .. hex
end

e