x=y^y so, given x how to find y ?

[meow]

say we have x which for example is 10000, then how to find a value y
so that y^y = 10000 ?

(thats y to the power of y)

x can be any number from about 10 to 1000000

I don't know if it can be done directly so i had to use an iteration loop, where you start off with a guess, then look at the error, then move the guess in (hopefully) the correct direction by an amount that doesn't make the error bigger.

well Ive come up with a very surprisingly good way of moving the guess that comes close to doing it in one go, but for the life of me I cant think why it is so close, can any one shed any light on this ?

n=3; // <- good place to start

...loop
x2=n^n;
...check error and break if good
n=n+Log10(x/x2)
..rinse and repeat

[Ixpah]

No idea, but look at:
http://www24.wolframalpha.com/input/?i=x%3Dy^y

it never was supposed to be a search engine, but its good at maths.

y = (log(x))/(W(log(x)))

although I didn't follow exactly what the W() function did, something about product log function.

[meow]

cool, but it seems the W function is just as difficult to calculate.

Lambert W function - Wikipedia, the free encyclopedia

I think i was quite lucky in working out the next step, to start with i used this as it made sense...

n=3;
//start of loop
n1=Pow(x,1/n); //n1=nth root of x
n=n +(n-n1)/k;

this relies on the result is defiantly going to be in between n and the nth root of x.
where k seemed to be good at about 3.

I cant find any way of deriving how the function i used is so good,
also usually you can use log10 and natural logs interchangeably,
however my solution requires log10, wheres as many places need logn if they need a particular base.
maybe base 10 might be not be the optimum, however although this works good
its quite interesting trying to work out why,,,

maybe Ive stumbled on something new !

[Ixpah]

That article has got 2 code sample which could easily be converted to whatever language you are using, plus if you are using a maths library surely its got the function anyway.

"something new"... probably not.

[meow]

yeah , i looked for W but c# .net doesnt seem to have it.
I looked at the iterative routines for W but my code is simpler,
only 2 functions to call per loop
and i did work out the performance of it,

for an initial gues of y=3
if y is realy 2 ie x=4 then the actual error is -1, log x1/x2 is -.77
if y is realy 4 ie x=256 then the actual error is +1, log x1/x2 is +.976 which is quite close
if y is realy 5 ie x=3125 then the actual error is +2 , log x1/x2 is 2.06 which is very close
if y is realy 6 ie x=46656 then the actual error is +3, log x1/x2 is 3.2


I think the wolfram site is realy good , i think thats were ive found my most usefull source of 3d maths algorithms. for things like closest point between 2 lines etc.

oh another good site or 2:-
http://www.euclideanspace.com/maths/...ourD/index.htm
http://local.wasp.uwa.edu.au/~pbourk...try/planeline/
I put the source of the algorithms in my comments.
although the plane <-> plane <-> plane intersect doesnt seem to have it listed thats a doozy of a function

[LippoW]

x to the power of x = y

For a qbasic source code (switch x with y in this case). Google, I love it.

[Sash]

ohhh I think you're lovely Meow but you don't half make me feel thick! lol

[meow]

sorry lol

[meow]

Originally Posted by LippoW

x to the power of x = y

For a qbasic source code (switch x with y in this case). Google, I love it.

thanks, sorry wont let me karma you :s

I had a look and it took me a while to get my head around, but the iteration loop is for 3000 lol.

actually after some time looking it seems this is exactly the same as I did it initially:-
its taking the nth root of y and averaging the result with n for the next guess, as y seems to always be inbetween these two values. ie if n is too low the result is going to be to high.

whereas I used Pow(x,1/n), this example uses logs to achieve the same thing.
however the convergence can be quite slow,

(if n2 is the n1th root of x)
using n=n+log(n1^n1/n2^n2) is actually very fast :- jumping almost directly to the value even on the first pass of the loop.

I just stumbled across this by accident when trying any different function I could think of that was a closer fit of the 2 results to the actual error. but I'm puzzled as to why it is so uncannily close.

[Seth]

...and that's the reason I dislike pure mathematics.

[Ixpah]

Using the simple approximation one I get:-
x=4,y=2.20681623447875
x=256,y=4.15330265177627
x=3125,y=5.13365919367039
x=46656,y=6.11794457569541

using the more complex iterative one, you can get the correct answer in 6 iterations for the above examples.

If you range of values for x is limited, e.g. its always an integer, and precision doesn't matter much maybe a quick look up table would be a quicker solution? If its time critical code.

		static void Main(string[] args)
		{
			TestW(4);
			TestW(256);
			TestW(3125);
			TestW(46656);
		}
		static void TestW(double In)
		{
			double Out;

			Out = Math.Log(In) / desy_lambert_W(Math.Log(In));

			Console.WriteLine("x=" + In.ToString() + ",y=" + Out.ToString());
		}

		static double LambertW(double x)
		{
			double w = 0.0;
			double we;
			double w1e;
			double prec = 1E-14;
			for(int i=1; i<100; i++)
			{
				we = w * Math.Pow(Math.E, w);
				w1e = (w + 1) * Math.Pow(Math.E, w);

				if (prec > Math.Abs((x - we) / w1e))
					return w;

				w -= (we - x) / (w1e - ((w + 2) * (we - x)) / (2 * w + 2));
			}
			return w;
		}
		static double desy_lambert_W(double x)
		{
			double lx1;
			if (x <= 500.0)
			{
				lx1 = Math.Log(x + 1.0);
				return 0.665 * (1 + 0.0195 * lx1) * lx1 + 0.04;
			}
			return Math.Log(x - 4.0) - (1.0 - 1.0 / Math.Log(x)) * Math.Log(Math.Log(x));
		}

[meow]

thanks, well my input is integer based, so although the result has to be floating point, if y^y is within 0.5 then thats as close as one could expect anyway. Ive yet to see my loop reach above 6.


I could use something simpler, its simply used for calculating the base number of the vertex space partition tree. ie the classical trees are either binary or octal, a binary space partition tree has a base of 2 and an octal tree has a base of , well 8.

they differ in how fast they are to build and search, so my tree should be somewhere between the two.
however my tree is rather radical different to either anyway.

ie for x entries in the table, there will be y levels each node containing y items.
its all about trading off search time and build time so that its best overall.

getting an optimum value cuts down both the time to build it and search it.
well thats what I'm hoping, it does seem to so far, the profiler says its
spending less than 1% time here now which is ok.

the cache gets used and rebuilt a lot. theres upto 300k vertexes
each vertex has to be compared with every other vertex,
this alone would take ages if it didn't filter only the ones close by.

not only that but the vertexes are built up from thousands of model objects, the cache gets rebuilt every time a model object is added, so it gets both built a lot and used a lot.

I would like to build a dynamic partition tree, but thats really too difficult for me,
unless anyone fancies a go at it ?