Wikipedia:Reference desk/Archives/Mathematics/2007 November 12

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 12

Java code for sieve of atkin

I searched all over the internet for the sieve of atkin java implementation and could not find any. Did I miss any web pages or something? This is supposed to be the fastest/most powerful prime sieve algorithm and yet there aren't any java code implementations (all implementation are annoyingly in c++ or python). 24.250.139.137 04:26, 12 November 2007 (UTC)lmaoman

A c++ implementation of a simple numerical algorithm like this that doesn't really require classes or anything like that should be fairly close to copy-and-paste compatible with Java. Have you tried just copying the C++ code into a Java class, hitting compile, then cleaning up the errors? Are you completely unfamiliar with C++? - Rainwarrior 05:23, 12 November 2007 (UTC)

This algorithm is fairly complicated and simple translation is impossible because most c++ implementations are over optimized and use weird tricks/asm which cannot be converted from c++ to java. I will try to use sieve of Aristophanes instead because this algorithm might be an overkill. 24.250.139.137 07:22, 12 November 2007 (UTC)lmaoman

Do you mean Eratosthenes? If you are having trouble understanding a particular piece of code I wouldn't mind helping you decipher it, but the applications of a prime number sieve that is faster than Eratosthenes' are kind of rare, in my opinion. What do you need this for? - Rainwarrior 08:16, 12 November 2007 (UTC)

Our Sieve of Atkin article includes some Pseudocode for the algorithm. It looks easy enough it implement this in java. Apparently it does need some optimisation (especially Wheel factorization) to make it efficient. --Salix alba (talk) 09:15, 12 November 2007 (UTC)

Complex number

why does i² equals to -1 not -2 or -3...-n Please tell me. —Preceding unsigned comment added by Kunthea dd (talk • contribs) 15:01, 12 November 2007 (UTC)

By definition, the imaginary unit i is that complex number such that i² equals -1. This is the most convenient definition, having i²=-2 would create all sort of complications when working with complex numbers. --Salix alba (talk) 15:50, 12 November 2007 (UTC)

Well, there are two complex numbers squaring to -1, so i cannot be defined as "the complex number whose square is -1". If we construct the complex numbers somehow, we choose an element whose square is -1 and define i to be it; if we use an axiomatic approach, we would possibly take "$i^{2}=-1$" as an axiom. -- Meni Rosenfeld (talk) 16:06, 12 November 2007 (UTC)

It's a matter of convention, albeit a convenient convention. The complex numbers can be created as an algebraic extension of the real numbers by adjoining a solution of the equation x²+1=0, which we call i. Instead, we could adjoin a solution x²+2=0, and call it j, so that j²=-2. But then there is a straightforward isomorphism between the two fields, given by a + bj → a + bsqrt(2)i, so they are essentially the same extension field over the reals. Gandalf61 17:37, 12 November 2007 (UTC)

I think the first definition given is the simplest one, but it lacks an important detail. It must also state the ${\sqrt {-1}}=i$ not the the square root here is the POSITIVE root, this distinguishes between the two solutions to $i^{2}=-1$. A math-wiki 09:29, 13 November 2007 (UTC)

Math-wiki - are you saying that i is a positive number ? If so, can you explain what you mean by that in more detail ? You can distinguish between the two solutions to x²=1 because both solutions are real numbers and the reals are an ordered field, so you can say that one solution is greater than the other. But how exactly do you propose to distinguish between the two solutions to x²=-1 ? Gandalf61 13:09, 13 November 2007 (UTC)

Question, if we changed the definition of complex number so -i → i. Would there be any difference? --Salix alba (talk) 18:10, 13 November 2007 (UTC)

No, see Imaginary unit#i and -i. Simply put, there is no way to distinguish i from -i in any way that doesn't lead back to the original aribtrary selection of one of them to be denoted with a special symbol. -- Meni Rosenfeld (talk) 18:38, 13 November 2007 (UTC)

In elementry algebra the two different solutions to a square root were distinguished by the use of the signs + and -. Since by default the plus sign is dropped in front of a number unless theres a second number that + is operating on (if this number/variable expression is is zero then both the number and the plus sign are removed). So this means the saying ${\sqrt {-1}}=i$ say that the "positive" solution to the root is i and the negative solution is -i. Now the meaning is not exactly comprehensible in the same way that + and - is for real numbers, but keep in mind that imaginary numbers always have a real coefficient (often 1 or -1) so Imaginary numbers can be ordered (by their real coefficient), but NOT Complex numbers. I also don't see how it is not possible to distinguish between i and -i since the Cartesian Plane for Complex Numbers gives an easy way to distinguish between them. As for linking the graphical distinction directly to the algebraic roots I could see that being impossible. A math-wiki 08:36, 14 November 2007 (UTC)

Math-wiki - here is a thought experiment. You have a number i that satisfies i²=-1. I have a number j that satisfies j²=-1. Clearly either j= i or j = -i - but how can we tell which ? If you say "look at the coefficient of i in j" or "see whether j is above or below the real axis in the complex plane" then that is equivalent to evaluating j/i, which is begging the question. Gandalf61 10:30, 14 November 2007 (UTC)

Did you read the section I linked to?

Here is another nice thought experiment, seeing that you have mentioned the Cartesian complex plane allows you to distinguish between i and -i. Suppose someone draws the complex plane on a transparency, a sheet of transparent paper. He draws a horizontal real axis and a vertical imaginary axis, but doesn't specify which is which. He also doesn't specify the direction of the axes - he counts on the fact that he knows the correct one. He marks 2 points in the plane with a black pen, and then marks their product with a red pen. If I take a look at his drawing, I see that everything is as I would expect - assuming that the number 1 is on the right and i is on the top, the number represented by the red dot is exactly tha product of the numbers represented by the black dots. Now, assume that before I enter the room, the transparency is flipped around the vertical axis (so right becomes left and vice versa). Will I still, looking at the drawing, see that "everything is in order"? How about if the transparency is rotated 90° or 180°? And now for the interesting part, will the drawing still look correct if it was flipped around the horizontal axis?

I won't give the answers just yet, since, as the name "thought experiment" suggests, I want you to think about it. -- Meni Rosenfeld (talk) 13:29, 14 November 2007 (UTC)

Your right it is impossible to know which i is which, but it is possible to make a distinction since $i\neq -i$ but of course the choice is arbitrary but it can be made. A math-wiki 23:29, 14 November 2007 (UTC)

Yes, once we have arbitrarily chosen one of them to be denoted i, we can obviously know which one is the one we chose, and which one is the other one. But before this choice is made, there is absolutely no qualitative difference between them (they are of course different quantitatively, not being the same number and all). -- Meni Rosenfeld (talk) 23:33, 14 November 2007 (UTC)

It may interest you that complex numbers other than sqrt(-1) have been given specific symbols. For instance, the cube roots of 1 are 1, w, w^2. (Those should be omegas.) Black Carrot 21:22, 15 November 2007 (UTC)

differentiability and derivatives

I have truoble understanding this. If function is differentiable at some point, then it must have a derivative at same point or not? And why f(x) = x^(1/3) is not differentiable at zero? (see: http://en.wikipedia.org/wiki/Derivative). I can calculate derivative, which is zero there. What's wrong? —Preceding unsigned comment added by 88.118.101.107 (talk) 18:37, 12 November 2007 (UTC)

The derivative may be undefined at the point that you're looking at. For your case $f'(x)={\tfrac {1}{3}}x^{-2/3}={\frac {1}{3x^{2/3}}}$. Now do you see why there is no derivative at that point? You might also find it instructive to compare the derivative at 0 of the inverse function $f(x)=x^{3}$. Donald Hosek 18:53, 12 November 2007 (UTC)

I have corrected an error (one that does not invalidate the point being made).  --Lambiam 22:20, 12 November 2007 (UTC)

Hi! Some notes: The method of using the derivative calculator is only valid if the derivative is continuous at the point of calculation. It's clear from the above comment that this is not the case for $f(x)=x^{1/3}$ at $x=0$.

If the derivative is not continuous, you may try to get the derivative by its definition (as a limit). If you try this approach, you will get in this case $+\infty$ as an answer.

Last, but not least, some words on vector-valued functions (you may ignore this if you don't work with them). The notion of differentiability is not precisely that of existence of derivatives, except for the case of only one domain variable (functions over Reals). For variables over $\mathbb {R} ^{n}$, differentiability implies that an hyperplane of dimension $\mathbb {R} ^{n}$ is tangent to the graph at the point. Put it simply, for functions over $\mathbb {R} ^{2}$ differentiabilty demands that a plane be tangent to the function surface at the point. Pallida Mors 76 19:27, 12 November 2007 (UTC)

Perhaps you can tell us how did you try to calculate the derivative of $x^{1/3}$, and we will try to spot the mistake.

If for some reason Pallida's reply was unclear, I'll reiterate that, unless you are dealing with functions of several variables (which I think is safe to assume you are not), then yes, a function is differentiable at a point if and only if it has a derivative there. -- Meni Rosenfeld (talk) 21:34, 12 November 2007 (UTC)

Thanks Meni for your clear(er) remark :). Pallida Mors 76 23:02, 12 November 2007 (UTC)

We might want to add a note of caution about, say, ƒ(x) = |x| at x = 0. --KSmrq^T 23:50, 12 November 2007 (UTC)

Well, here it goes: The function absolute value, given by

$f(x)=$|x|

is differentiable at any point to the left of zero, being in that interval the derivative equal to -1. Notice that in that interval, $f(x)$ is precisely $-x$.

Something similar happens on the other half of the real line. The function is also differentiable at any value of x greater than zero, the derivative being there equal to 1. Again, notice that $f(x)$ is just $x$ there.

It is evident that the derivative can't be continuous in zero. Indeed, it takes the value $-1$ for negative values of x close to zero, and it is valued 1 for positive values of x near the origin. Furthermore, if we calculate the one-sided derivatives at zero (by definition, e. g. as the corresponding limits), we get -1 and 1, which means the derivative (as a bi-directional limit does not exist). Would that be enough? The articles absolute value and derivative are worth a look --Pallida Mors 76 03:31, 13 November 2007 (UTC)

With one further remark. Remember that suggestion that the real line was special compared to the plane and higher dimensions? I would make the point that even on the line the direction of approach can give different results, which is really the same issue. --KSmrq^T 05:26, 13 November 2007 (UTC)

Well, it is true that different directions show different results even in the real line, but consider this example (which knocked my head off), to see the difference between the line and the plane (and more dimensions):

$f(x,y)=(x^{2}-y)(4x^{2}-y)$

This function has a critical point at the origin. In every direction of the form

$y=ax$

around the origin, the function has a minimum.

However, the function does not have a minimum at the origin. If you take directions of the form

$y=ax^{2}$

...Then for some values of a the function has an inflection point in that direction.

So, in the plane there are many directions or ways to reach a point. Not merely two (left and right).

Sorry for having stretched a bit off-topic Pallida Mors 18:15, 13 November 2007 (UTC)

Yeah, nice example. It reminds me of the cannonical example for a function with directional derivatives equal to the inner product of the direction and the gradient not having to be continuous:

$f(x,y)={\begin{cases}1&x>0\ {\textrm {and}}\ y=x^{2}\\0&{\textrm {otherwise}}\end{cases}}$

-- Meni Rosenfeld (talk) 18:30, 13 November 2007 (UTC)

ANOVA with ordinal data

Is there a slick way to deal with ordinal predictors (which have rank but no specific value) in a statistical regressions context? Or is it better to deal with the predictors as (unordered) factors? Thanks, --TeaDrinker 20:24, 12 November 2007 (UTC)

Our article on the Kruskal-Wallis one-way analysis of variance may be useful. Gandalf61 15:11, 13 November 2007 (UTC)

Thanks, although I think the WK ANOVA is for ordinal response, rather than predictor (perhaps I am mis-reading it). One approach is to replace the predictor with the rank and do a continuous (potentially generalized) linear regression. However this approach is fairly ad hoc. Thanks, --TeaDrinker 07:27, 14 November 2007 (UTC)