lua-users home
lua-l archive

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


It also does not solve the problem, Phillippe program would generate the square root of C.

On Wed, Jun 26, 2019 at 4:41 PM Soni "They/Them" L. <fakedme@gmail.com> wrote:


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.



--
--