I came across a mathematical statement in the form of:
(log x)^-1 log y log log z
Is that equivalent to the C expression:
pow(log(x), -1)*log(y)*log(log(z))
Printable View
I came across a mathematical statement in the form of:
(log x)^-1 log y log log z
Is that equivalent to the C expression:
pow(log(x), -1)*log(y)*log(log(z))
Hmm. Using Google's calculator, it resolves to the code that I posted, with one important difference: it's assuming I mean log10, not the natural logarithm. Is that a fairly standard assumption in mathematical notation?
According to the standard([EDIT]: Copy of C99 that I have[/EDIT]) log(x) computes log base e (natural) log of x. log10 functions return the log base 10 of x.
I'm pretty sure that's what the equation in question implies, too, but there does seem to be some inconsistencies in convention. For example, you often see "ln" used to distinguish natural logarithm, and now that I think of it, most hand calculators use "log" for log10. Argh!
If log rather than lg or ln is used, I think that that depends on context. Perhaps the author specified the base elsewhere, or the base does not matter in the big picture (e.g., this is part of some notation for algorithmic complexity), or the author assumed the base due to convention in his/her specialisation.Quote:
Originally Posted by gardhr
Incidentally, I would translate x^-1 as (1/x) to avoid a function call that seems overkill.
Assuming ^ is "to power of", then p^-1 is equivalent to 1/p (if p is a real or complex value).
As to "log y log log z" you need to be clear what that means. It is ambiguous, mathematically, as brackets or anything else that might give context (such as font sizes) have been left out. It could be log(y)*log(log(z)) or it could be log(y*log(log(x))
Mathematically, "log" can mean common logarithm (log10() in C) or natural logarithm (log() in C). Conventionally, common logarithm is the more usual meaning. But, to be sure, you need to read the article (or whatever) that you got the formula from.
Okay, so I guess I'll assume log == natural logarithm since that seems to be the most common usage.
I'm pretty sure now that the correct interpretation here is log(y)*log(log(z)), too, from the context of the article.
Thanks for the input everyone!
Then when it turns out that your assumption is wrong... if the base really was not specified anywhere, is there an example of the calculation that you can refer to? Is this "pure" mathematics? Is this engineering?Quote:
Originally Posted by gardhr
Umm....Laser the base is assumed per the standard....: confused : <on purpose>
I'm basing it on the heuristic that most papers written about number theory seem to use that convention. :p
Specifically, it's a lower bound given for the Miller-Rabin primality test, described here. I'm trying to work out an approximation using only integer math.
The expression is in the context of computational complexity, and indeed it is used in "big-O" notation throughout the paper. Basically, the base does not matter since they are considering things "asymptotically".Quote:
Originally Posted by gardhr
The equation in question relates to the actual lower bound of trial number bases, not the complexity of the algorithm. Or am I reading it wrongly?
"For an integer n , let G(n) denote the smallest x such that the
primes < x generate the multiplicative group modulo n . We offer heuristic
arguments and numerical data supporting the idea that
G(n) < (log 2)^-1 log n log log n"