lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Doug Currie wrote:
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)

GNU MP bignum library (GMP)'s method is in gmp-5.0.0/mpn/generic/set_str.c
(called from gmp-5.0.0/mpz/set_str.c)

Doesn't look like any special magic is used, or that it will fit into a script using doubles...

Kein-Hong Man (esq.)
Kuala Lumpur, Malaysia