# [FUN] CodeGolf: solve equation x^x=C Classic List Threaded 46 messages 123
Open this post in threaded view
|

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

 Global variable "C" contains numeric value > 15.5The solution of math equation x^x=C must be printedYour code must fit into 36 bytesDirty tricks are allowed
Open this post in threaded view
|

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

 Le mer. 26 juin 2019 à 22:47, Egor Skriptunoff <[hidden email]> a écrit :Global variable "C" contains numeric value > 15.5The solution of math equation x^x=C must be printed. Your code must fit into 36 bytes Dirty tricks are allowedMy 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
Open this post in threaded view
|

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

 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.5The solution of math equation x^x=C must be printed. Your code must fit into 36 bytes Dirty tricks are allowedMy 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 simplerIt 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
Open this post in threaded view
|

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

 On 2019-06-26 8:32 p.m., Coda Highland wrote: > > > 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 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.
Open this post in threaded view
|

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

 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] > > 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 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. -- --Gé
Open this post in threaded view
|

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

 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.
Open this post in threaded view
|

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

 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.
Open this post in threaded view
|

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

 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 magnitudelog_2(x^x) =x*log_2(x) = 1024so 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.
Open this post in threaded view
|

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

 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 magnitudelog_2(x^x) =x*log_2(x) = 1024so 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
Open this post in threaded view
|

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

 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.
Open this post in threaded view
|

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

 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*xi.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 <= xor 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/xThis 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 magnitudelog_2(x^x) =x*log_2(x) = 1024so 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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 < 1Further 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 boundSo 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 :-)
Open this post in threaded view
|

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

 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_functionx^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
Open this post in threaded view
|

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

 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) returnx^x*(x*math.log2 x div 512)endand to get the value just call "f f f f f f x"
Open this post in threaded view
|

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

 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.
Open this post in threaded view
|

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

 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 fSo 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 approximationAnd 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) returnx^x*(x*math.log2 x div 512)endand to get the value just call "f f f f f f x"