Wikipedia:Reference desk/Archives/Mathematics/2011 May 25

Mathematics desk
< May 24	<< Apr | May | Jun >>	May 26 >

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.

May 25

floating point multiplication

For an exponential number like 39^42 would it be designated as requiring 42 floating point multiplications and if so how would it be converted to number of required FLOPS or would that be per the machine it was calculated on? --DeeperQA (talk) 01:10, 25 May 2011 (UTC)

39^42=(39*((39*(39^2)^2)^2)^2)^2 requires 7 multiplications. Bo Jacoby (talk) 06:04, 25 May 2011 (UTC).

(((39^3)^3)(39^3)(39^2))^3 requires eight multiplications; is it the case that using only ^2 and only two multiplicands will always yield a minimum number of required multiplications?—msh210℠ 19:52, 25 May 2011 (UTC)

No, it's not. ((39^3)^3)^3 requires six multiplications, while doing it Bo Jacoby's way would require seven: 39(39((39(39^2))^2)^2)^2. In that case, Bo Jacoby, do you know seven is minimal for 39^42?—msh210℠ 22:41, 25 May 2011 (UTC)

No msh210, I don't know that. Bo Jacoby (talk) 06:49, 26 May 2011 (UTC).

39^42=(((((39^2)^2)^2)/39)^2)^3. Still 7 FLOPs. Bo Jacoby (talk) 08:12, 26 May 2011 (UTC).

It is, according to this.

See also Addition-chain exponentiation. -- Meni Rosenfeld (talk) 08:47, 26 May 2011 (UTC)

Puzzled why this question is headed "floating point multiplication". As long as you use a language that supports arbitrary-precision arithmetic, the problem given only requires integer arithmetic. Gandalf61 (talk) 08:24, 25 May 2011 (UTC)

In general, exponential (and logarithmic) functions in computer math coprocessors are only implemented in floating-point form. The reason is, as you implied, the result will very likely overflow the bounds of any integer being used. -- kainaw™ 19:27, 25 May 2011 (UTC)

But the OP refers (twice) to "floating point multiplication", so they obviously weren't thinking about using exponential or logarithm functions. Bottom line is if they want to calculate 39^42 using multiplications they shouldn't be using floating point arithmetic; if they want to use floating point arithmetic they shouldn't use multiplication; and in either case they shouldn't be mutiplying 39 by itself 42 (or even 41) times. Gandalf61 (talk) 20:29, 25 May 2011 (UTC)

$39^{42}=\exp(42\log 39)$ requires one logarithm, one multiplication and one exponentiation, but will only give you finite precision. -- Meni Rosenfeld (talk) 08:31, 25 May 2011 (UTC)

However log is a function not a primitive. So I don't think it is considered as a single FLOP. Taemyr (talk) 08:44, 25 May 2011 (UTC)

The calculation 39^42 would be a single FLOP if we used a logarithmic number system, and since this is the maths ref desk rather than the Computing reference desk being theoretical rather than living in the real world is my prerogative. :) Dmcq (talk) 09:43, 25 May 2011 (UTC)

Not a single FLOP, but a constant number of FLOPs. This is better than linear (per OP) or logarithmic (per Bo). -- Meni Rosenfeld (talk) 12:33, 25 May 2011 (UTC)

A constant number of FLOPs is better than 7 FLOPs only if the constant is smaller than 7. You may be considering a generalized problem. FLOPs will generally only give you finite precision. Bo Jacoby (talk) 21:11, 25 May 2011 (UTC).

The OP asked a generalized problem: "For an exponential number like 39^42..." (emphasis added).—msh210℠ 22:48, 25 May 2011 (UTC)

If its know that the exponent is a positive whole number then most modern algorithms will use a process similar to Bo's solution. They take the binary representation of the exponent and depending on whether each bit is 0 or 1 either square the answer or square and then multiply by the number. See power algorithm.--Salix (talk): 09:51, 26 May 2011 (UTC)

That was an interesting enough problem for me to try to run a program to exhaust possible combinations of multiplications. So I got the following numbers for a given number of multiplications.

1. 2
2. 3 4
3. 5 6 8
4. 7 9 10 12 16
5. 11 13 14 15 17 18 20 24 32
6. 19 21 22 23 25 26 27 28 30 33 34 36 40 48 64
7. 29 31 35 37 38 39 41 42 43 44 45 46 49 50 51 52 54 56 60 65 66 68 72 80 96 128

Bo is right, 42 requires 7 multiplications, but msh is also right - for 27 the power method fails miserably. (Igny (talk) 23:45, 26 May 2011 (UTC)) After a glance on this table, I think the numbers for which the power method is not optimal are 15, 23, 27, 39, 43, 45, 51. Any idea why?(Igny (talk) 23:54, 26 May 2011 (UTC))

See OEIS: A003313 and follow the links there for more information.--RDBury (talk) 03:41, 27 May 2011 (UTC)

See also Addition chain.--RDBury (talk) 03:43, 27 May 2011 (UTC)

area of sine using real numbers (maybe radians)

integral of sin x dx = -cos x + c; range 0 , 2pi, get 0 for -1 - -1 = 0 cos 2pi=cos 0=1. in other words area of circle = pir^2 so unit circle area pi but when i try to use integral of sine or cosine for area of these curves my answers appear ridiculous. obviously not very skilled but would like to interate sine cosine over 0 to 2pi and get pi; if this makes sense. trying with 0 to 90 degrees is not much better. thank you. — Preceding unsigned comment added by Staub2222 (talk • contribs) 19:08, 25 May 2011 (UTC)

$\int \sin x\ dx=-\cos x+c$ so that on the range $\left[0,2\pi \right]$ we have $\int _{0}^{2\pi }\sin x\ dx=-1-(-1)=0$ because $\cos \left(2\pi \right)=\cos 0=1$. In other words, the area of a circle is $\pi r^{2}$ so the unit circle's area is $\pi$, but when I try to use the integral of sine or cosine to find the area of that curve my answer appears ridiculous. Obviously, I'm not very skilled, but would like to integrate sine or cosine over $\left[0,2\pi \right]$ and get $\pi$, if that makes sense. Trying it over $\left[0,90\right]$ (degrees) is not much better. Thank you. Translation into English provided free, as a courtesy, with formatting of mathematical formulas thrown in, too.—msh210℠ 19:43, 25 May 2011 (UTC)

Why do you think the integral of sine over that interval should give you the area of the unit circle? Integral of a function over an interval gives you the (signed) area under the graph of the function itself, not some related graph.—msh210℠ 19:43, 25 May 2011 (UTC)

• The problem is that you're integrating in terms of Cartesian coordinates. If you want to know the area of a circle then you need to integrate using polar coordinates. There are standard formulas for converting integrals in one coordinate system into an integral in another coordinate system. The important section is this section, and this subsection. Using the formulas in those sections we have

${\frac {1}{2}}\int _{0}^{2\pi }\!\!r^{2}\,\operatorname {d} \theta =\pi r^{2}\,.$

Take a look at those sections, and let us know what help you need. — Fly by Night (talk) 21:00, 25 May 2011 (UTC)

Degenerate Hopf Bifurcation

A Hopf Bifurcation is the bifurcation of a fixed point to a limit cycle, but what is a "degenerate Hopf Bifurcation"? — Preceding unsigned comment added by Thorstein90 (talk • contribs) 22:04, 25 May 2011 (UTC)

Probability question

Hi. Suppose we have a black box that sometimes produces a 0 and sometimes a 1, according to some probabilistic process whose operation we know nothing about. Suppose in m + n trials we observe m 0s and n 1s (the order in which these appear is not relevant to my question). Let p be the probability of getting 1. If we have to guess at p, then it seems sensible and "obvious" to guess p = n/(m + n). On the other hand, if we assume that the "a priori" distribution of p is uniform over the interval 0 to 1, and we then condition this on the observation of m 0s and n 1s, it comes out that p = (n + 1)/(m + n + 2). Is there any reason to suppose that one method is better than the other? In fact, why are they even different?

I notice that if we observe one success in one trial, then the second formula gives a superficially more reasonable answer of p = 2/3, as opposed to p = 1. However, I'm not sure if the number 2/3 has any actual meaning or justification. 86.176.208.187 (talk) 22:14, 25 May 2011 (UTC)

One approach is frequentist the other is Bayesian. In the Bayesian approach the estimate depends on the apriori distribution, so if you pick a different apriori distribution you would be getting a different estimate every time. In the frequentist approach, p is not random, but its estimate is (it depends on the random sample). But even in the frequentist approach there are different estimates of the parameters of the distribution, such as the maximum likelihood estimator or the method of moments (statistics), which give sometimes different results but in this particular case, most of the good estimators would be the same because the estimate of p can not get any better than n/(m+n). (Igny (talk) 22:34, 25 May 2011 (UTC))

We have a related article: sunrise problem. Michael Hardy (talk) 03:01, 26 May 2011 (UTC)

I find this whole topic conceptually very problematic. I am inclined to think that the Bayesian approach is bogus if it requires one to assume an a priori uniform distribution for a probability about which we have, at that point, zero knowledge. I don't know on what basis one can assume that, or why any consequent results (like "2/3" above) should be meaningful. Of course, with many trials the answer (in my case) differs little from the "frequentist" approach, but that hardly seems a justification of its logical basis. 86.176.208.187 (talk) 03:37, 26 May 2011 (UTC)

Isn't a uniform distribution a rather obvious way to represent the fact that you have no information on the basis of which to prefer any particular value? 130.188.8.12 (talk) 09:37, 26 May 2011 (UTC)

Despite the uniform assumption superficially appearing to represent "zero information", it seems to me that it actually does contain information -- information that we don't actually have. 86.160.209.202 (talk) 12:23, 26 May 2011 (UTC)

Among m+n+1 items there are either m+1 0s and n 1s, or m 0s and n+1 1s. In the first case the observation (m 0s and n 1s) could occur in m+1 ways, and in the second case the observation could occur in n+1 ways. So the probability p that the next observation is '1', is p=(n+1)/(m+n+2). The problem of assuming a uniform prior distribution of p arises only because you unnecessarily consider an infinite number of possible values of p, rather than only the two possible values of the next observation. Bo Jacoby (talk) 06:30, 26 May 2011 (UTC).

Infering from a population to a sample is called deduction, while infering from a sample to the population is induction. The probability that a random trial within the m+n known trials, is '1', is p_deduction=n/(m+n), while the probability that a random trial outside the m+n known trials, is '1', is p_induction=(n+1)/(m+n+2). Bo Jacoby (talk) 07:22, 26 May 2011 (UTC).

Thanks Bo, your comments are very informative. 86.160.209.202 (talk) 12:23, 26 May 2011 (UTC)

Even if different, the German tank problem may be of interest to the OP. Grandiose (me, talk, contribs) 09:39, 26 May 2011 (UTC)

I agree, the german tank problem is a very nice induction problem. However, the article is somewhat messy, and I did some cleanup, but it is still messy. Bo Jacoby (talk) 22:29, 29 May 2011 (UTC).

Mathematics equivalent of the scientific method

In the natural sciences, discoveries are made and truth is established by means of the scientific method, however the scientific method is not the methodology used in developing mathematics. Does the methodology used in mathematics have a name? Widener (talk) 23:08, 25 May 2011 (UTC)

You probably want Axiomatic method.--RDBury (talk) 00:17, 26 May 2011 (UTC)

You might also be interested in Experimental mathematics and for something more abstruse Reverse mathematics. Actually its quite like in science where the scientific method is used more to confirm or refute ideas rather than generate them. Dmcq (talk) 10:14, 26 May 2011 (UTC)

For philosophical analysis, the article abductive reasoning might interest you. For what mathematicians actually do, try Bill Thurston's article On Proof And Progress in Mathematics (arXiv:math/9404236). I haven't yet read The Mathematical Experience by Reuben Hersh and have heard mixed things about it. 67.117.147.144 (talk) 17:45, 29 May 2011 (UTC)