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
