Wikipedia:Reference desk/Archives/Mathematics/2009 April 2

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.

April 2

sorting quadratic irrationals with Maple 9

Suppose you generate with Maple 9 a list of quadratic irrationals; for instance use the code:

L:=[]: for n from 1 to 10 do L:=[op(L), n*sqrt(5)-floor(n*sqrt(5))]: od: L;

I would like to sort these values accordingly to the ordering of real numbers. Any idea? Carminat (talk) 07:23, 2 April 2009 (UTC)

It is hard in general to rigorously compare surd expressions. However, if floating point comparison is good enough for your purposes, use

sort(L,(x,y)->evalb(evalf(x<y)));

McKay (talk) 09:30, 2 April 2009 (UTC)

Great: it works! But -I geess- the syntax should be

sort(L,(x,y)->evalb(evalf(x)<evalf(y)));

For my porpouses exploting evalf is just fine, but now I know this ordering trick I think I will be able to do with evala (and a simple procedure).Carminat (talk) 13:17, 2 April 2009 (UTC)

evalf(x<y) and evalf(x)<evalf(y) have identical result in Maple 12. I don't have Maple 9 any more to check. McKay (talk) 23:24, 2 April 2009 (UTC)

Plotting implicit functions

I was wondering how one would go about plotting 3D functions like $x^{2}+y^{2}+z^{2}=1$ or $x+y+z=1$ in, for example, gnuplot (I hope I'm not mistaken that those are implicit functions). I read some tutorials where one was supposed to substitute $x$ for $r\cos \theta \,$ and $y$ for $r\sin \theta \,$ and set r as some constant.. and even then it didn't work, that's rubbish! There has got to be a more simple way of doing this. --BiT (talk) 12:01, 2 April 2009 (UTC)

The plotting of the functions you have given is rather simple. The first function given is simply an equation representing a 2D sphere (of radius 1), and the second function represents a 2D plane. Usually, if you access any textbook on multivariable calculus, you should obtain methods concerning the plotting of simple functions (in terms of formulae, not in the measure theoretical sense of course). Generally, it is helpful to recall the analagous 2D case when plotting such functions.--PST 12:10, 2 April 2009 (UTC)

A 2D sphere? Noo.. $x^{2}+y^{2}+z^{2}=1$ is a function for a 3D sphere right? --BiT (talk) 14:18, 2 April 2009 (UTC)

Our File:Gnuplot ellipsoid.svg contains gnuplot code for plotting an ellipsoid. Removing the '2*' and '3*' will get you a unit sphere. This code works by parametrizing the sphere with spherical polar coordinates. Algebraist 12:13, 2 April 2009 (UTC)

No that's my point, there has to be a way of plotting this without having to parametrize the plot manually. The function $x^{2}+y^{2}+z^{2}=1$ only has one solution; one way of plotting it, why can't I write something like "set implicit", "splot z**2+x**2+y**2=1" in gnuplot? --BiT (talk) 14:20, 2 April 2009 (UTC)

I know nothing about gnuplot, but there are many ways of plotting a sphere. The ellipsoid I linked is plotted as a collection of lattitude and longitude lines; that is, it is plotted in accordance with the specific parametrization used. I can't see a way to make a useful 2d plot of a sphere that doesn't depend on a parametrization in some way. Algebraist 14:28, 2 April 2009 (UTC)

One difficulty is that the actual solution to the formula will almost certainly pass between adjascent pixels almost everywhere. That is, an actual sphere would be invisible. By specifying a parametrization, you describe in what way you want to approximate the sphere to make it visible. Another difficulty is that solution sets of a lot of formulas are very difficult to find. By specifying a parametrization, you tell the computer explicitly how to calculate the answer. One way to bypass these problems is to allow for generically approximate solutions. That is, you could go through a gridwork of points in the graph, and for each one calculate whether the implicit formula is "almost" satisfied, and color that point in if it is. This tends to produce an ugly, fuzzy-looking graph, but it works. Usually. I don't know if gnuplot has that built in. Black Carrot (talk) 17:51, 2 April 2009 (UTC)

Wait, just to be sure; x²+y²+z²=1 is a three-dimensional sphere right? --BiT (talk) 20:31, 2 April 2009 (UTC)

It's the two-dimensional surface of a three-dimensional ball, or, in a standard terminology, a 2-sphere. Algebraist 20:34, 2 April 2009 (UTC)

But if you solve the equation for z it becomes $z={\sqrt {1-x^{2}-y^{2}}}$ and if you plot that you get half a sphere. Could you explain a little how this function isn't a sphere? If you plot every point (x=[-1..1], z=[-1..1] and y=[-1..1]) you should get a sphere; even my textbook has the same equation and plots a sphere with the radius ${\sqrt {1}}$. --BiT (talk) 21:10, 2 April 2009 (UTC)

It is a sphere. Where did I say it wasn't? Algebraist 21:17, 2 April 2009 (UTC)

There's no need to be rude, I misunderstood what you said. --BiT (talk) 23:29, 2 April 2009 (UTC)

That is the equation for a 2D sphere. A sphere is a surface, it doesn't include the inside, so you only need two coordinates to describe a point on it (longitude and latitude, for example), so it is 2D. --Tango (talk) 21:28, 2 April 2009 (UTC)

Aah ok, I knew it wasn't a solid sphere (wouldn't that be "x²+y²+z² < 1"). Ok so by 2-sphere and 'two-dimensional surface' you were simply referring to the surface of the sphere, it seems obvious to me but it was kind of confusing when I wasn't sure what you were talking about. --BiT (talk) 23:27, 2 April 2009 (UTC)

In case you want to know the precise terminology: careful writers would say x²+y²+z² < 1 defines an open 3-ball (or just open ball), x²+y²+z² ≤ 1 defines a closed 3-ball (or just closed ball), and x²+y²+z² = 1 defines a 2-sphere (or just sphere). I believe these distinctions are due to Bourbaki. Of course, in many situations it is not necessary to be so careful. Algebraist 23:35, 2 April 2009 (UTC)

I was actually going to use ≤ but I couldn't be arsed so I just used <, didn't really think it made any difference. Could you explain to me exactly in what way x²+y²+z² ≤ 1 is different from x²+y²+z² < 1? --BiT (talk) 01:54, 3 April 2009 (UTC)

The former inequality defines a set containing its boundary (so it contains the point (1,0,0) for example), while the latter does not. As I said, this often doesn't matter, but sometimes it is of crucial importance. For example, a continuous function on the first set is necessarily bounded, while one on the second set need not be (e.g. 1/(1-r), where r is distance from the origin). Algebraist 06:39, 3 April 2009 (UTC)

The object described by the first equation is compact as a topological space, whereas the object described by the second equation is not. Or, the object described by the first equation is an orbifold under an action by the two element cyclic group on Euclidean 3-space (i.e a manifold with boundary), whereas the object represented by the second equation is a manifold, i.e an orbifold under the action by the trivial group on Euclidean 3-space. There is no more to say, I presume. --PST 04:05, 3 April 2009 (UTC)

There are several techniques for plotting such, things are easier if you have polynomials rather than general functions. Raytracing solutions are the most common, POV-Ray can do these. The basic technique for working out if a ray hits the surface is to use Sturm's theorem by counting number of sign changes in the coefficients you can determin the number of zeros of the polynimial. You can then find segments on the ray so they each only contain one zero and use some convergence algorithm to find the actual zero, (within a given tollerance).

The other approach is the get a polygonal representation of the surface. Marching cubes is one algorithm for doing this. I've developed an algorithm for doing this which uses convexity properties of Bernstein polynomials to test for the presence of zeros with in a given range.

For the x²+y²+z²=1 surface any algorithm should do. Things get more interesting when the surface has singularities like x²+y²-z²=1. --Salix (talk): 16:36, 3 April 2009 (UTC)

You can't plot a 3D function on a paper 2D plane until you change one of its variables to a constant. Make $z^{2}$ constant in your function $x^{2}+y^{2}+z^{2}=1$ and you have defined a circle of radius $sqrt(1-z^{2})$. You may have noticed the radius is like the hypotenuse in Pythagoras theorem. Here are two ways you might plot the circle:

• On a cartesian grid using Bresenham's_circle_algorithm That's tedious by hand but it's how computers usually draw circles.
• Use Polar_coordinates. This is where the conversions $x$ for $r\cos \theta \,$ and $y$ for $r\sin \theta \,$ are useful. The polar form describes the circle in terms of its radius which can rotate to any angle $\theta$. That is a nicer method for plotting by hand because you plot only as many points as needed to make the circle appear sufficiently smooth (but you need tables or a calculator to get the $\sin$ and $\cos$ values, each of which would take an infinite series to calculate "exactly").Cuddlyable3 (talk) 19:35, 3 April 2009 (UTC)

calendar question

How many Friday the 13ths will there be between now and December 2050? 65.121.141.34 (talk) 20:25, 2 April 2009 (UTC)

71. See Friday the 13th. Algebraist 20:31, 2 April 2009 (UTC)

Unless you're talking about sequels of the slasher movie. See Friday the 13th (disambiguation). If so, assuming that they continue to be churned out at the same historical rate, there have been 12 movies made between 1980 and 2009, with a gap of around 29/12 years between each. Divide 41 years by that and we get (41×12)/29, or about 17 gaps. Since we just had the last version come out, that would mean we could expect, much to my horror, 16 more. StuRat (talk) 18:21, 6 April 2009 (UTC)

Composed ceilings

Is it true that

ceiling(ceiling(x/y)/z)

equals

ceiling(x/(yz))

for all natural numbers x, y, and z? 72.197.202.36 (talk) 21:23, 2 April 2009 (UTC)

Yes it is, and this rule is useful for analysis of algorithms like binary search and quicksort. Assume y,z are positive integers, but allow x to be any real number (even negative). Then x can be written uniquely as x = A*y*z - B*y - C where A,B are integers with 0≤B≤z-1, and C is a real number in the half-open interval [0,y). Now it is easy to check that both your expressions equal A. It is also true that floor(floor(x/y)/z)=floor(x/(yz)). McKay (talk) 23:21, 2 April 2009 (UTC)

Thanks! 72.197.202.36 (talk) 02:39, 3 April 2009 (UTC)

By the way, the book Concrete Mathematics has a whole section on manipulating floors and ceilings, especially with a view towards analysis of algorithms. It has some mnemonics designed to help remember the mixed rules, but they would have been more appropriate for Wednesday. JackSchmidt (talk) 03:09, 3 April 2009 (UTC)

Excuse me Jack, what does this expression mean (more appropriate for Wednesday)? thanks--pma (talk) 16:19, 3 April 2009 (UTC)

The rules are a mixture of truth, humor, and insanity more appropriate for April Fools' Day. One of the mneumonics given is "In fourteen hundred and ninety-three, Columbus sailed the deep blue sea." Another is something like "and since we know that nothing ever works they way we want, we reverse the inequalities." JackSchmidt (talk) 17:43, 3 April 2009 (UTC)

Game theory terminology

I'm doing a course on game theory and have come across a term known as an "S-game" between two players in a zero-sum game. A wants to maximize payoffs; B minimize payoffs. If A chooses a randomized strategy:

$\alpha =\left(p_{1},\dots ,p_{n}\right)$

across its pure strategies, and B chooses a point s in the risk set, then the payoff is:

$g\left(\alpha ,\beta \right)=\alpha \cdot s$

However, I can't find the concept of an "S-game" anywhere on the Internet, including Wikipedia. So I was wondering if anyone was familiar with this under a different name so I could do more research.

Much thanks. 128.86.152.139 (talk) 23:37, 2 April 2009 (UTC)

This[1] may or may not interest you. Cheers. Cuddlyable3 (talk) 18:36, 3 April 2009 (UTC)