Strange Roots

[storm5510]

Can anyone tell me what these expressions mean?

4Sqr(x) and 4Sqr(x) log n)

I think "log n" is natural logarithm. The "4" in front of "Sqr", I have no idea.

[NickThissen]

Can you supply us with a little more information?

I was tempted to say that it was probably the base-4 root of x:
⁴√x = x^1/4

But, the sqrt is called a square root because it is the base-2 root:
²√x = √x = x^1/2

Similarly, you also have a cube root:
³√x = x^1/3

And a ... dunno what to call it... quartic root maybe? No idea:
⁴√x = x^1/4 = (x^1/2)^1/2 = √(√x)


So, writing 4sqrt(x) when you mean the 'quartic root' does not make sense..


Maybe it's just 4 times the square root?


---
Also, the log n might be the usual base-10 log, or it might be the natural log. However, the natural log is usually written as ln instead of log. But I have seen many people, especially physicists for some reason, use log when they actually mean ln.

The natural log is the base-e log, where e is the natural number 2,71828183.

[Justa Lol]

sqr(2) = 1.41421356
4sqr(2) = 5.65685425

so
sqr(2) = 1.41421356
4sqr(2) = 4*1.41421356
4sqr(2) = 5.65685425


(log n)
http://en.wikipedia.org/wiki/Binary_logarithm

[NickThissen]

What makes you think it's the binary (base-2) log? It could be the base-10 as usual, or the base-2, or the base-e.

[storm5510]

I saw it here:

http://primes.utm.edu/prove/prove4_3.html

[jemidiah]

The article goes on to say

But of course when actually finding primes it is the unlisted constants1 that make all of the difference! We will have to wait for efficient implementations of this algorithm (and hopefully clever restatements of the painful for loop) to see how it compares to the others for integers of a few thousand digits. Until then, at least we have learned that there is a polynomial-time algorithm for all integers that both is deterministic and relies on no unproved conjectures!

Note: D. J. Bernstein's exposition of the Agrawal-Kayal-Saxena theorem (mentioned above) contains improvements by many diferent researchers which reduce the constants involved in the time analysis by at least a factor of 2,000,000. This is perhaps the best source for the present state of the algorithm.

Personally, I wouldn't bother trying to implement this beast myself for fear of mistakes and gross inefficiencies.