 |
lua-l archive |
|
|
||
|
On 2019-06-26 8:32 p.m., Coda Highland wrote:
>
>
> On Wed, Jun 26, 2019 at 6:23 PM Philippe Verdy <verdy_p@wanadoo.fr
> <mailto:verdy_p@wanadoo.fr>> wrote:
>
> Le mer. 26 juin 2019 à 22:47, Egor Skriptunoff
> <egor.skriptunoff@gmail.com <mailto:egor.skriptunoff@gmail.com>> a
> écrit :
>
> Global variable "C" contains numeric value > 15.5
> The solution of math equation x^x=C must be printed. Your code
> must fit into 36 bytes Dirty tricks are allowed
>
>
> My answer (for x*x=C):
> local s;s=function(p,n)return p==n and n or s(n,(C/p+n)/2)
> Well it's the double, but just the header for the function "local
> s;s=function(p,n)return ", and the code to print the result on a
> Lua console "=s(1,C)" consumes 30 bytes, leaving only 6 bytes to
> "the program" (the internal part of the function, an _expression_).
>
> Even with "dirty tricks" you can't find a correct solution with
> just 6 bytes (only 2 variables and a function name uses 3 bytes,
> it remains just 3 bytes for some operators between the 3 bytes; if
> the program uses recursive trailing call, 2 bytes are used, there
> remains only 1 character for a single operator, you can"t compute,
> or determine a break condition, so your goal is simply not
> reachable in Lua).
>
> Or what do you call a "program"? If I remove the required headers,
> the rest is
> p==n and n or s(n,(C/p+n)/2)"
> which is 28 bytes and does not use any "dirty quirk", but just
> classic Lua syntax, and the classic solution (working to invert
> every strictly monotonic function) to compute a square root in a
> fast converging loop: even for 64-bit doubles, with 52 bits of
> precision, only 52 loops or trailing recursions are needed (the
> convergence is quite rapid); there's no constraint at all on the
> value of C and we get the gest precision as possible for computing
> its square root.
>
> Now for x^x the convergence is even faster; we know that x > 2.75
> and already the function x^x at this value has a steep growth, so
> approximation can be done even faster (with less loops) but the
> code is similar to approximate its inverse function (just compute
> the mean between the previous approximation and the goal value
> divided by the first derivative at the current approximation) at
> each loop and then looping but not much more complex (as the
> growth rate of x^x is already>16 it will be 16 times less loops
> than for the square root to get the same precision.
>
> With trailing calls, Lua allows these loops to be transformed in
> recursive function calls, which is simpler
>
>
> It doesn't have to be a local function so you could just write
> "function s(p,n)return" and save 8 bytes. However, you forgot the
> "end", so that eats into the savings somewhat.
>
> /s/ Adam
or just skip that entirely and s=load'p,n=...return p==n and n or
s(n,(C/p+n)/2)'
but probably too long still.