Re: converting arbitrary long decimals to hex?
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: converting arbitrary long decimals to hex?
- From: Doug Currie <doug.currie@...>
- Date: Fri, 8 Jan 2010 15:52:18 -0500
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