[FUN] CodeGolf: solve equation x^x=C

classic Classic list List threaded Threaded
46 messages Options
123
Reply | Threaded
Open this post in threaded view
|

[FUN] CodeGolf: solve equation x^x=C

Egor Skriptunoff-2
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
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
Le mer. 26 juin 2019 à 22:47, Egor Skriptunoff <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Coda Highland


On Wed, Jun 26, 2019 at 6:23 PM Philippe Verdy <[hidden email]> wrote:
Le mer. 26 juin 2019 à 22:47, Egor Skriptunoff <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Soni "They/Them" L.


On 2019-06-26 8:32 p.m., Coda Highland wrote:

>
>
> On Wed, Jun 26, 2019 at 6:23 PM Philippe Verdy <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Le mer. 26 juin 2019 à 22:47, Egor Skriptunoff
>     <[hidden email] <mailto:[hidden email]>> 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.

Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Gé Weijers
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. <[hidden email]> wrote:


On 2019-06-26 8:32 p.m., Coda Highland wrote:
>
>
> On Wed, Jun 26, 2019 at 6:23 PM Philippe Verdy <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Le mer. 26 juin 2019 à 22:47, Egor Skriptunoff
>     <[hidden email] <mailto:[hidden email]>> 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.



--
--

Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
Le jeu. 27 juin 2019 à 01:51, Gé Weijers <[hidden email]> a écrit :
It also does not solve the problem, Phillippe program would generate the square root of C.
Yes I know, and that what I wrote. But it's the basic idea, using a convergent loop. But this requires dividing by the derivate function of x => x^x, which requires the log function (which would then require some Taylor series for an approximation).
I wonder if the author of the problem just wants an approximation. You're right for the missing "end" keyword for the function. But my main comment was "what is the program", does it include the required header/trailer and the statement to print the result on a console (which almost completely eats the 36 bytes), or just the expression that computes the result? He speaks about a preexisting "global" variable C, so there's an environment already loaded, and it conditions the way we can feed the computing expression or we can output the result.
In just 36 bytes it's just impossible to write a complete program, but it may be possible to write a statement that computes the result within a function with a predefined name.
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Dirk Laurie-2
In reply to this post by Egor Skriptunoff-2
Op Wo. 26 Jun. 2019 om 22:47 het Egor Skriptunoff
<[hidden email]> geskryf:
>
> 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

That constant 15.5 sticks out like a sore thumb.

The solution to the problem is likely to be non-iterative: some
truncated asymptotic expansion, accurate enough for C>15.5. The dirty
trick may be the replacement of some annoying number by a simpler one,
e.g. 839/5040 by 1/6. Rather like Henrici's program for calculating
the gamma function on the HP 25 pocket calculator.

But right now I don't have the energy to pursue the idea.

Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
but a basic asymptotic approcimation cannot work for any number x that sastisfies x^x > 15.5 (which can be very large).
So let's see where x^x does not return  positive infinite (starting at 2^1024).
We need the mathematic solution for x^x = 2^1024.

But let's start by how we can compute the base-2 exponent (which will be betwen 3 and 1024 for this problem) to get a rough estimate of the order of magnitude
log_2(x^x) =x*log_2(x) = 1024
so x= 1024/log_2(x). and then x must be below 

The problem states that x^x>15.5, so x >15.5/log_2(x) (this will be used for tuning the value of the mantissa and correct the effect of the approximate base-2 exponent.

There's not a lot of values of x that can qualify, it is in a small range in the open range (3.3, 395)
If x is to be restricted to be an integer, this x is in the integer range 4..394 (because 395^395>2^1024 and gives a positive infinite value for 64-bit IEEE doubles)

But in that case a table lookup is not possible (the integer range 4..394 would contain 390 double values in a static table)

So what is to approximate if the base-2 integer exponent of x^x and then we can correct the mantissa; and this requires amultiplication from the correct mantissa, by the approximation of the base-2 exponent.

This will still produce large errors compared to the recursive method using the derivative function of (x => x^x), which is (x => (ln(x) + 1) * x^x).

The recursive function will then loop by dividing the current approximation of x^x, by (log(x)+1), to form the new approximation by taking the average (it will have a fast convergence, but now you need a way to compute ln(x) or you can use math.ln(x).





Le jeu. 27 juin 2019 à 09:14, Dirk Laurie <[hidden email]> a écrit :
Op Wo. 26 Jun. 2019 om 22:47 het Egor Skriptunoff
<[hidden email]> geskryf:
>
> 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

That constant 15.5 sticks out like a sore thumb.

The solution to the problem is likely to be non-iterative: some
truncated asymptotic expansion, accurate enough for C>15.5. The dirty
trick may be the replacement of some annoying number by a simpler one,
e.g. 839/5040 by 1/6. Rather like Henrici's program for calculating
the gamma function on the HP 25 pocket calculator.

But right now I don't have the energy to pursue the idea.

Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Coda Highland


On Thu, Jun 27, 2019 at 9:57 AM Philippe Verdy <[hidden email]> wrote:
but a basic asymptotic approcimation cannot work for any number x that sastisfies x^x > 15.5 (which can be very large).
So let's see where x^x does not return  positive infinite (starting at 2^1024).
We need the mathematic solution for x^x = 2^1024.

But let's start by how we can compute the base-2 exponent (which will be betwen 3 and 1024 for this problem) to get a rough estimate of the order of magnitude
log_2(x^x) =x*log_2(x) = 1024
so x= 1024/log_2(x). and then x must be below 

The problem states that x^x>15.5, so x >15.5/log_2(x) (this will be used for tuning the value of the mantissa and correct the effect of the approximate base-2 exponent.

There's not a lot of values of x that can qualify, it is in a small range in the open range (3.3, 395)
If x is to be restricted to be an integer, this x is in the integer range 4..394 (because 395^395>2^1024 and gives a positive infinite value for 64-bit IEEE doubles)

But in that case a table lookup is not possible (the integer range 4..394 would contain 390 double values in a static table)

So what is to approximate if the base-2 integer exponent of x^x and then we can correct the mantissa; and this requires amultiplication from the correct mantissa, by the approximation of the base-2 exponent.

This will still produce large errors compared to the recursive method using the derivative function of (x => x^x), which is (x => (ln(x) + 1) * x^x).

The recursive function will then loop by dividing the current approximation of x^x, by (log(x)+1), to form the new approximation by taking the average (it will have a fast convergence, but now you need a way to compute ln(x) or you can use math.ln(x).

Thanks to your discovery of the upper bound, I can write a solution that (technically) works in 52 bytes.

x=0;while x*x~=C do x=math.random()*395 end return x

;)

/s/ Adam
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Dirk Laurie-2
In reply to this post by Dirk Laurie-2
Op Do. 27 Jun. 2019 om 09:14 het Dirk Laurie <[hidden email]> geskryf:

> That constant 15.5 sticks out like a sore thumb.

It is safely higher than e^e = 15.154262241479.

Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
In reply to this post by Coda Highland
excellent ! (note that your did not include the function header "function f(x)" and trailer "end" and the code "=x" to print the result on the Lua console).
It works because the range from 0 to 395 is small enough and it assumes that math.random() will return an exact value.

This can create an infinite loop if this condition x*x=C is never reached exactly, because:
- random() will not explore all the possible bits, as random() does not return all the possible values for the 52 bits of numbers in (0,1).
- even if you have the best approximation possible of x, x^x=C may still be wrong (and there's no upper bound of the relative error on the value of x).

So let's assume that random() is able to generate at least 31 bits of precision with a resonably flat distribution, the exact value of log2(x^x) may be different from log2(C) by a relative factor of up to 15.5*x
i.e. you must stop the loop when log2(x^x)/log2(C) <= 15.5*x,

i.e. equivalently when ln(x^x)/ln(C)/15.5 <= x
or when ln(x^x)/x <= 15.5*ln(C)

You can see here why 15.5 is used in the problem, it's not "magic" but it's log2(31)

----

And why using random(), which is unnecessarily slow ?

We could just enumerate the 31 bits of precision in the open range (from 3.0 to 395.0). And this exploration can be much faster if you have a starting approximate (but lower) bound of the solution so that it will enumerate from a better start position (in which case it will require much less loops to reach the best lower bound that matches the expected precision of the result.

What is needed is only to estimate the lower bound of the base-2 integral exponent of x.
Interestingly, we have : x= 1024/log_2(x) so log_2(x)=1024/x

This allows starting the "for" loop to explore the 31 bits of precision of values of x (from 3.0 to 395.0) at a known integer position which is (1024 div x).

You just need an integer "for" loop (and your loop will not explore bits for very long because you are quite near from the expected precision at the start !).

Lets say that (exponent=1024 div x) is the starting value for your integer for-loop, the for-loop will run for at most log2(exponent), and given that exponent is below 1024, it will never run for more than 10 times (and 5 times on average)... and it is warrantied to give a correct result of x with at last 31 bits of precision.

now the 10 loops can be easily unrolled into inline code performing successive tests. But an even better solution is to perform a binary search in the small constant table of 10 constant values.




Le jeu. 27 juin 2019 à 17:11, Coda Highland <[hidden email]> a écrit :


On Thu, Jun 27, 2019 at 9:57 AM Philippe Verdy <[hidden email]> wrote:
but a basic asymptotic approcimation cannot work for any number x that sastisfies x^x > 15.5 (which can be very large).
So let's see where x^x does not return  positive infinite (starting at 2^1024).
We need the mathematic solution for x^x = 2^1024.

But let's start by how we can compute the base-2 exponent (which will be betwen 3 and 1024 for this problem) to get a rough estimate of the order of magnitude
log_2(x^x) =x*log_2(x) = 1024
so x= 1024/log_2(x). and then x must be below 

The problem states that x^x>15.5, so x >15.5/log_2(x) (this will be used for tuning the value of the mantissa and correct the effect of the approximate base-2 exponent.

There's not a lot of values of x that can qualify, it is in a small range in the open range (3.3, 395)
If x is to be restricted to be an integer, this x is in the integer range 4..394 (because 395^395>2^1024 and gives a positive infinite value for 64-bit IEEE doubles)

But in that case a table lookup is not possible (the integer range 4..394 would contain 390 double values in a static table)

So what is to approximate if the base-2 integer exponent of x^x and then we can correct the mantissa; and this requires amultiplication from the correct mantissa, by the approximation of the base-2 exponent.

This will still produce large errors compared to the recursive method using the derivative function of (x => x^x), which is (x => (ln(x) + 1) * x^x).

The recursive function will then loop by dividing the current approximation of x^x, by (log(x)+1), to form the new approximation by taking the average (it will have a fast convergence, but now you need a way to compute ln(x) or you can use math.ln(x).

Thanks to your discovery of the upper bound, I can write a solution that (technically) works in 52 bytes.

x=0;while x*x~=C do x=math.random()*395 end return x

;)

/s/ Adam
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Coda Highland
On Thu, Jun 27, 2019 at 10:47 AM Philippe Verdy <[hidden email]> wrote:
excellent ! (note that your did not include the function header "function f(x)" and trailer "end" and the code "=x" to print the result on the Lua console).

Oh right, I meant to write print(x) instead of return x, that way it doesn't have to be a function. I just forgot that was my plan when I started writing it.

It works because the range from 0 to 395 is small enough and it assumes that math.random() will return an exact value.

This can create an infinite loop if this condition x*x=C is never reached exactly, because:
- random() will not explore all the possible bits, as random() does not return all the possible values for the 52 bits of numbers in (0,1).
- even if you have the best approximation possible of x, x^x=C may still be wrong (and there's no upper bound of the relative error on the value of x).

I knew it was terrible when I submitted it. :P

/s/ Adam
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Roberto Ierusalimschy
In reply to this post by Philippe Verdy
> - random() will not explore all the possible bits, as random() does not
> return all the possible values for the 52 bits of numbers in (0,1).

Not true if you are using 5.4 :-)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
In reply to this post by Coda Highland
Note that the idea of the table may not be good, by my idea of exploring bits of precisions with a binary search can be implemented easily by a recursive function. In which case it becomes possible to explore the whole 52 bits of precision in the result in at most log2(52) recursions.

Le jeu. 27 juin 2019 à 17:51, Coda Highland <[hidden email]> a écrit :
On Thu, Jun 27, 2019 at 10:47 AM Philippe Verdy <[hidden email]> wrote:
excellent ! (note that your did not include the function header "function f(x)" and trailer "end" and the code "=x" to print the result on the Lua console).

Oh right, I meant to write print(x) instead of return x, that way it doesn't have to be a function. I just forgot that was my plan when I started writing it.

It works because the range from 0 to 395 is small enough and it assumes that math.random() will return an exact value.

This can create an infinite loop if this condition x*x=C is never reached exactly, because:
- random() will not explore all the possible bits, as random() does not return all the possible values for the 52 bits of numbers in (0,1).
- even if you have the best approximation possible of x, x^x=C may still be wrong (and there's no upper bound of the relative error on the value of x).

I knew it was terrible when I submitted it. :P

/s/ Adam
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
In reply to this post by Roberto Ierusalimschy
Disregard random() which is a bad idea (and which is an unnecessary external dependancy). Using a binary search with trailing recursive calls, and at most log2(52) trailing recursions, means that you'll need at most 6 recursions to get the best approximation for 64-bit doubles.

At each recursion, you normally need to evaluate the stop condition on the maximum relative error, which is  log_2(x)=1024/x, but you can just continue to perform the 6 recursions based on the lowerbound/upperbound test of the value of log2(x)*x, depending if it is lower than 1024 or not.

And this test can be optimized because actually we just need to know  if floor(log2(x)*x)<1024:
we just need the 10 first bits of log2(x)/x, i.e. testing if log2(log2(x)*x)<10, or just log2(log2(x))<10*x, or of log2(log2(x))*x/10 < 1

Further tricks will immediately follow to optimize this test: we know that x is between 3.0 and 395.0, so log2(log2(x)/x/10 is also bound
So we just need its integer upper bound to compare it with the integer 1:

In summary we need only 1 bit of precision for log2(log2(x)/x/10 for any x in (3.0..395.0) to perform the boolean test needed for the  recursion of a standard recursive binary search (which will run 6 times always). I bet that you can optimize the two branches of the "if" in a single one, using bit fiddling to determine which value to pass to the trailing recursion (so that you'll eliminate the if/else and just recurse on f(new value of x).

And don't forget that we know in advance the number (6) of recursions that can then be unrolled, each recursion computing 10 bits of mantissa in the approximation of x; you get the result then by just outputing the result of "f f f f f f(some value)".

The trick is to find the bit fiddling to compute if we need, to pass (value1 or value2) where value1 and value2 are the ower and upper bound.
But may be we don't even need this fiddling when value1 and value2 are just values of (x^x) and (x*x^x),
i.e. it's enough to pass to the recursion call the value x^x*(1+(log2(x)*x<1024 and 1 or 0))

I must not be very far from the solution !

Le jeu. 27 juin 2019 à 17:55, Roberto Ierusalimschy <[hidden email]> a écrit :
> - random() will not explore all the possible bits, as random() does not
> return all the possible values for the 52 bits of numbers in (0,1).

Not true if you are using 5.4 :-)
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Albert Chan
In reply to this post by Dirk Laurie-2

> Op Do. 27 Jun. 2019 om 09:14 het Dirk Laurie <[hidden email]> geskryf:
>
>> That constant 15.5 sticks out like a sore thumb.

My guess is >15.5 for approximate lambert W function as straight line.
https://en.m.wikipedia.org/wiki/Lambert_W_function

x^x = c --> x = e^W(log(c))

Example, if c=100, from Wolfram Alpha, we get x=3.597285

http://m.wolframalpha.com/input/?i=E%5EProductLog%5BLog%5B100%5D%5D



Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
In reply to this post by Philippe Verdy


Le jeu. 27 juin 2019 à 18:30, Philippe Verdy <[hidden email]> a écrit :
i.e. it's enough to pass to the recursion call the value x^x*(1+(log2(x)*x<1024 and 1 or 0))
correction: pass the value x^x*(x*log2 x<1024 and 1 or 0)
So you get an anwer:
f f f f f f(x^x*(x*log2 x<1024 and 1 or 2))

I think that (x*log2 x<1024 and 1 or 2) can be implemented using an integer division to remove the "and"/"or":
(x*math.log2 x div 512) 

And we get something like:
f f f f f f(x^x*(x*math.log2 x div 512))

function f(x) return
x^x*(x*math.log2 x div 512)
end

and to get the value just call "f f f f f f x"


Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
Sorry replace  "x^x*(x*math.log2 x div 512)" by  "(x*math.log2 x div 512)/x^x" (it's a division, not a multiplication).
This can be tested, I must have made some error.
Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
In reply to this post by Philippe Verdy
also this solution still uses the exact value "x^x" which is the searched value; as we dont know it first, we can pass it as a second parameter y to function f
So to get the value it's a bit more complex:

function f(x,y)return(x*math.log2 x div 512)*y, y end
(54 bytes)
and to get the value just call "f f f f f f(x 3)" where we provide the initial approximation

And do we need the explicit "return" statement, can't the function use recursive call to itself, something like:

   function g(x,y)(x*math.log2 x div  512)*y,y end  
   function f(x)g g g g g x,3 end
   and get result with just "f x"
(untested, I've probably oversimplified the dependancies, but I must not be very far from the final solution, may be we can drop the second parameter by assuming oit is in a global constant, by transforming a bit the formula inside g)

Now we also need to "optimize" the code size for "math.log2" and the constant "512".
That's where the global constant C=15.5 may play a role, allowing us to use the standard log function (but its name may also be in a global to avoid access to "math.").

The bit fiddling used may also be implemented using the "%2" (modulo 2) operator instead (to replace the initial "and 1 or 2" condition which just needs 1 bit of precision to test if we pass the lower bound or the upper bound of the new approximation when comparing to the value 1024)

There are several tracks to analyse.


Le jeu. 27 juin 2019 à 18:43, Philippe Verdy <[hidden email]> a écrit :


Le jeu. 27 juin 2019 à 18:30, Philippe Verdy <[hidden email]> a écrit :
i.e. it's enough to pass to the recursion call the value x^x*(1+(log2(x)*x<1024 and 1 or 0))
correction: pass the value x^x*(x*log2 x<1024 and 1 or 0)
So you get an anwer:
f f f f f f(x^x*(x*log2 x<1024 and 1 or 2))

I think that (x*log2 x<1024 and 1 or 2) can be implemented using an integer division to remove the "and"/"or":
(x*math.log2 x div 512) 

And we get something like:
f f f f f f(x^x*(x*math.log2 x div 512))

function f(x) return
x^x*(x*math.log2 x div 512)
end

and to get the value just call "f f f f f f x"


Reply | Threaded
Open this post in threaded view
|

Re: [FUN] CodeGolf: solve equation x^x=C

Philippe Verdy
My exposed solution may have applications outside Lua itself:

- it just depends on a integer log2 function which is easily implemented by using bits directly from the exponent part of the "double", using only integer arithmetics.
- it avoids all dependencies on tests (and a modulo 2 is just reading a single bit)
- it can be efficiently implemented in hardware (in a FPU) to support x^x with any non-integer floatting-point value of x, with the best precision and excellent speed (and instead of 6 recursive calls needed for IEEE 64-bit doubles, you just need 6 stages of arithmetic gateways; for IEEE 32-bit doubles you just need 5 stages, for 128-bit long doubles, you need 7 stages)
- it can be implemented in high-precision math libraries, the cost will be linearily proportional to the log2(precision bits wanted for the result) if you can compute a fixed number of bits at each recursion, or proportional to the precision bits if you get one 1 bit of precision at each stage, and in any language. It will be normally immune to "time-based attacks" with a predetermined performance for a predetermined precision required in the result.

And probably similar tricks can be used to implement various math primitives with one argument (sinus, cosine, log/ln, tan, log10, exp...) that can be approximated with arbitrary precision and excellent performance, over a kwown range of source values where the function is strictly monotonic (strictly growing or falling, so that the convergence is warrantied), using a binary search and some bit fiddling (like the modulo 2) I exposed, so that their execution time (or number of stages in hardware) depends only on the needed precision (and will be constant for common constant precisions used by all IEEE floats). The number of precision bits you get at each steps depends only on the value of the derivative function on that range (which should be > 1/2 so that you'll get at least 1 bit at each step; if the lower bound of the derivative value is higher, you get more bits at once and you need less stages to get the final result).

All the rest of the implementation is to determine the suitable range where the function is monotonic and has the best derivative value) and only integer arithmetic operations (addition/substraction, multiplication/negation, Euclidian division/rest) and binary ops which are even simpler by hardware (like bitand, bitor, bitxor, bitnot, bitshifts).

So this "optimization" problem is not "stupid" but is a very serious one that can find many practical applications. I wonder if such technics are not already patented by chip makers like Intel, IBM, AMD, or by math library and tools providers (like Mathlab or proprietary Fortran and C/C++ libraries optimized for perfomance, precision and security). But if not, I revendicate the authorship to open it to the world... unless someone demonstrates that he found this trick before (may be the author of this problem already knows that solution and its possible important applications?)


123