lua-users home
lua-l archive

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


Le mer. 26 juin 2019 à 22:47, Egor Skriptunoff <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