Wikipedia:Reference desk/Archives/Mathematics/2006 July 17

Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.

< July 16 Mathematics desk archive July 18 >

Linux: Clock speed

What's the Linux command for finding out how fast my computer is? I don't know what to google! moink 00:04, 17 July 2006 (UTC)

cat /proc/cpuinfo, or cat /proc/cpuinfo|grep MHz if you want to get specific. grendel|khan 02:18, 17 July 2006 (UTC)

It's /proc/cpuinfo on my Kubuntu machine.-gadfium 05:56, 17 July 2006 (UTC)

It's also cpuinfo on mine as well. Fixed above. Probably typed it short because I'm used to typing /proc/cpu<tab>. Darn. grendel|khan 13:32, 17 July 2006 (UTC)

Thank you! moink 13:43, 17 July 2006 (UTC)

Remember that grep can read from other than standard input: you save a process by just doing grep MHz /proc/cpuinfo. Even without that, cat file | foo is never necessary with any reasonable shell: use foo < file instead. Not the most important concern in the world, but it's just good to remember what your tools can do. --Tardis 16:51, 17 July 2006 (UTC)

When using several pipes in a shell script, it is often convenient to list each in a line of its own, terminated by the pipe sign. If you start this chain with "cat xxx |", you don't need to move "< xxx" around if you change the order or insert a filter on top of the chain.--gwaihir 17:14, 17 July 2006 (UTC)

please Help, math!

Do all infinite sets have the same number of elements?

      Thank-you

No. A set $S$ and its power set $2^{S}$ are not equinumerous. --71.246.9.190 02:22, 17 July 2006 (UTC)

You might want to read the article conveniently titled Infinite set and the article on Aleph numbers. --George 02:52, 17 July 2006 (UTC)

To be able to answer this question we must be able to "count" or "measure" the number of elements. (There is a technical distinction between these two terms!) The usual method of counting leads to the concept of cardinal number. It tells us that there are equally many natural numbers as even natural numbers, and as rational numbers; but the "number of" real numbers is greater. The famous proof for the latter involves Cantor's diagonal argument. If we measure rather than count, a 2×2 square has four times as many points (loosely speaking) as a 1×1 square, but both measures are finite. (Yet the count, or cardinality, for both is the same infinity.) Formal discussion of infinity tends to be disorienting at first! Still, whether we count or measure, we can detect differences between infinite sets. --KSmrq^T 02:57, 17 July 2006 (UTC)

Ask User:BenCawaling, I'm sure he'll give you an interesting answer. =P —Keenan Pepper 03:12, 17 July 2006 (UTC)

Perhaps you might be interested in reading my manuscripts refuting Cantor's transfinite theory and Frege's modern logic at this website. Read my arguments and you decide. All determinate infinite sets have cardinal numbers the same as the natural or counting numbers. Indeterminate "set" (that is, a variable collection of mathematical objects and not truly a set) -- such as the "set of all even numbers satisfying Goldbach's conjecture" {2, 4, 6, 8, …} or the "set of all twin prime numbers" {3, 5, 7, 11, 13, 17, 19, …} -- do not have cardinal numbers. A determinate infinite set is one that is computably generalizable. -- [BenCawaling@Yahoo.com 19 Oct 2006].

maths geniusses where are yous

heres a sequence thats baffled loads of guys..just give me the next two.numbers.. 50,350,3850,65450,...

—The preceding unsigned comment was added by 196.202.223.82 (talk • contribs) 06:07, July 17, 2006 (UTC).

It is described by the polynomial 9150x³-53300x²+96150x-51950 for x={1,2,3,4}. For x={5,6}, the polynomial gives 240050 and 582550.

—The preceding unsigned comment was added by 203.129.47.238 (talk • contribs) 06:32, July 17, 2006 (UTC).

You also asked this question on July 14, with one term less given: Wikipedia:Reference desk/Mathematics#help,,maths sequence.

Each next term is an integral multiple of the previous one: 50 × 7 = 350, 350 × 11 = 3850, 3850 × 17 = 65450. Is there an obvious rule governing the sequence 7, 11, 17, ...? All are prime numbers, but they are not quite consecutive primes, since 13 is missing. We also note that the first term 50 = 2 × 5 × 5, the product of "almost" consecutive primes except that 3 has been replaced by 5. As noted before, there are infinitely many recipes that will give a sequence starting off with these 4 numbers, but it looks as if the originator of the sequence goofed in producing consecutive prime numbers. --Lambiam^Talk 12:36, 17 July 2006 (UTC)

I beg your pardon. Perhaps I've misinterpreted your semiliterate babbling, but in what way were we "baffled"? We've given you quite a few plausible answers, and explained why there are infinitely more available. Black Carrot 15:00, 17 July 2006 (UTC)

I tend to agree with the others that it appears the sequence is either underconstrained or the last number is incorrect. However, supposing it is correct, I'd wager the next number is 87550 (though I think that should actually be the 4th number). Then the next number after that might be 16711850. Then maybe 5726666750. But my methods shall not be revealed for they are silly and fearsome, in that order! PS. Normally if a sequence appears underconstrained it's because you're looking at it the wrong way... Digfarenough 16:21, 17 July 2006 (UTC)

Actually, every sequence is underconstrained. Even if 1001 terms are given, there is no way to tell what the next terms are. Of course, usually in this case there will be one sequence the description of which is significantly shorter than any other, which may be considered the "correct" sequence. Certainly in this case not enough terms are given for this to happen - The formula given by 203.129.47.238 is possibly the simplest one, yet clearly not the intention of OP. So, anon, the question as you asked it does not have a correct answer - but if you give 2-3 more terms, we may be able to figure out what you meant. -- Meni Rosenfeld (talk) 17:38, 17 July 2006 (UTC)

Yes, you're right. I meant underconstrained in the much less formal sense that you described, wherein a "properly constrained" sequence would have a single, simplest pattern. But I still say the poster should recheck that fourth number. :) Digfarenough 17:45, 17 July 2006 (UTC)

Using multipliers of 7, 11, and 17, we could see this as a series of primes skipping 0 primes, then 1, then 2, so the next multiplier would be 29. We could also view it as a series of odd numbers skipping 1, then 2, then 3, so the next multiplier would be 25. Another way to view the series is increasing multipliers containing only 1's and 7's. Using this logic, the next multiplier would be 71. These are just a few of many possible solutions. StuRat 22:59, 20 July 2006 (UTC)

Software for and other questions about time-series forecasting, neural nets, DSP?

I would like to do some time series forecasting. Could anyone suggest some not-too-difficult-to-use free software packages please?

I did study this in the past for a few months and am aware of things like ARIMA, exponential smoothing, and so on.

As well as univariate forecasting, I would also like to experiment with forecasting by throwing a few multivariate time series together and seeing what error results I get. However, I understand that there is a problem with correlation between the independant variables, so I would ideally like something that could alert me to this if possible.

I've heard about multiple regression of course, but what about MARIMA?

A subsidary question is, if I tried forecasting from with neural nets, would they have the same problems with correlation between variables as multiple regression does?

I've also read an article here about Granger causality. I wonder if this is a solution to this problem? I don't at the moment understand it.

As well as statistical programs, are there any Digital Signal Processing programs that would be worth trying please?

Thanks. --81.104.12.26 16:30, 17 July 2006 (UTC)

I don't know much about this sort of thing, but one idea does come to mind. You might want to try Andrew McCallum's USM algorithm on the data (I think that's the one, his thesis available on his website has 4 algorithms, I think it's the 3rd one that would be best), if you have a long time series (not sure if you'd want to try it on the dependent variable or the derivative of the dependent variable, though). Basically it is an adaptive history/memory approach to prediction. If used on the derivative of the dependent variable, it would learn, for instance, that if an increase of 1 unit followed by an increase of 2 units is always followed by an increase of 3 units, to expect that any time it sees an increase of 1 then 2 to expect an increase of 3. But if the change before the increase of 1 unit is correlated with the later increase, it would learn to take that into account for making predictions. It's made for learning Markov decision processes, but it may work with your data, depending on how deterministic it is. Digfarenough 16:48, 17 July 2006 (UTC)

Where to find BASIC computer code for a multi-layered percepton?

I would like to experiment with neural nets. I can program in BASIC but not in other languages, although I could probably translate a few lines of code from eg. Fortan if given enough time.

Could anyone suggest where to find some code for a MLP that I could incorporate into my own programs please?

I would have done this in the past from algorithmns I have seen published in books (now lost), and it was the coding of the sigmoidal function that stumped me.

thanks very much. --81.104.12.26 16:49, 17 July 2006 (UTC)

The sigmoid function is easy enough; in BASIC it should just be 1/(1+EXP(x)). Depending on the flavor of BASIC, you just want to define a TYPE (QBasic), a class (Visual Basic), or parallel arrays (other, older BASICs). Then you want functions which accept either an object (for a TYPE or class) or an index into the arrays and compute the output of the perceptron (or more general neuron) specified. On top of that you would build feedback functions for training, etc. It shouldn't be too hard even without pre-cooked code. --Tardis 20:39, 17 July 2006 (UTC)

Thank you. As I know it would take me several days of work to code it, does anyone know of any per-existing code that I could use? There is lots of BASIC code on the internet, although its difficult to find the subroutines you want. Thanks.

Euclidean Algorithm

I have two questions:

1. I've read that the original Euclidean algorithm to find the greatest common divisor was done geometrically. It's pretty easy to see how - just keep drawing the difference of two line segments back onto one of the originals until you can't anymore, and you have the longest segment that can, laid end-to-end, be made into both of the originals. So, how would the Extended Euclidean algorithm be described geometrically?
2. It seems like Euclid's algorithm must be, essentially, a complete description of the relationship between the divisibilities of two numbers. You can extract so much from it, and I can see why. Why, then, can't you extract the factors of a number from it? I mean, if it can find the factors two numbers have in common, and a lot more besides, why can't it find the factors they don't have in common, or at lest some relationship (like difference, say) between them? Black Carrot 21:49, 17 July 2006 (UTC)

Not much of answer, but here is something you CAN do: you can calculate the product of the first few thousand prime numbers (say all the primes less than 10,000) and store it as N, and then when you have a big number M you want to factorise, you can start by finding the GCD of N and M. This will quickly find all the small factors of M, but I don't believe there is any obvious way to use the GCD algorithm to get any hint about big factors of M, unfortunately. (Maybe I mean 'fortunately', for if there was a quick way to factor big numbers, some of my data would be very insecure!). Madmath789 20:48, 18 July 2006 (UTC)

Quite true, but there are some difficulties with that. The first is that the primorial of 10,000 is incredibly large, and takes a very long time to compute exactly. That isn't really necessary, though, because thanks to how the GCD algorithm works, all you need is X such that X = N (mod M). That's the next number you would calculate anyway, and from there the algorithm flows smoothly. That takes care of the size problem, since you don't need to work with numbers larger than M, but not the time problem, and nobody's been able to make it go much faster. The other problem is that it requires knowing all the primes less than 10,000, which is a tad inconvenient, but since the factorial of 10,000 would work as well as the primorial for this, that's not really a problem either. Black Carrot 21:54, 18 July 2006 (UTC)

Not really convinced by your arguments, I'm afraid - even on my rather old laptop, these things do not take very long to calculate, and are not that big: 10000! only has a little over 82,000 digits (I wouldn't call this incredibly large), and only takes 2-3 seconds to calculate - which doesn't class as "a very long time to calculate" Madmath789 22:22, 18 July 2006 (UTC)

First, I think the statement in the article Euclidean algorithm about the original problem or algorithm being geometric is wrong. This is a proposition from Book VII of Euclid's Elements, which deals strictly with number theory. There is a diagram there (in Proposition 2) to illustrate the algorithm in which the size of the numbers is displayed as a line segment, but it is clear that these segments are supposed to have a length that is an integral multiple of a common unit.

The meaning of "why" in the question is not perfectly clear, as in "2 plus 3 is not equal to 2 times 3. OK, but why?". If you perform the extended algorithm on the input (a, 1), it will tell you that a×0 + 1×1 = 1, and it should be clear "why" that does not help you to factorize a. If performing the extended algorithm on input (a, b) results in Bézout's identity ax + by = d, then doing the same on input (ac, bc) will result in (ac)x + (bc)y = dc, with the same x and y as before. In getting there, the algorithm jumps through the same hoops in the same sequence, so it is in some sense oblivious to the common factor c, which should explain that it can only find the largest common factor. --Lambiam^Talk 11:00, 19 July 2006 (UTC)

Euclid's algorithm will tell you the gcd of two numbers which is the multiply of the common prime divisors raised to the larger power, but if you want to factor a number which has a large prime factors, you cannot easily find another number that shares one of the large prime divisors with that number but not all of them. If you choose a second number that has none of the prime divisors (just choose a random number), or has all of them (choose a multiple of the number), you won't get any useful information from the output of the Euclidean algorithm.

While it's easy to compute the factorial of 10000 and find the gcd with it, that can find only factors smaller then 10000 and you could find those somewhat faster by just dividing the number with each of the numbers up to 10000.

On the other hand, if you want to factor polynomials, not numbers, that is possible to do efficently, and then the Euclidean algorithm can help. Indeed, in that case an important step of the factoring algorithm is finding other polynomials that are likely to share some factors of the original one, and using the Euclidean algorithm to calculate the greatest common divisor. – b_jonas 11:17, 19 July 2006 (UTC)

Madmath789: So, your laptop is storing all 82,000 digits? Alright. How high a factorial would it have to be to max out the entire harddrive, maybe twenty, thirty digits? Remember, you need the exact number to run this algorithm. And a five-digit number is, as you say, not much. You could do that with trial multiplication just as fast. However, when you get to the area where trial multiplication is impractical, up in the dozens and hundreds and thousands of digits, taking a factorial of the square root becomes impractical as well. Black Carrot 19:23, 19 July 2006 (UTC)

Lambiam: Curious. I'd assumed they knew what they were talking about. It does, however, still have a geometric interpretation, so my first question stands. For your second paragraph, I think you misunderstood my question. I don't see any way for it to determine what factors two numbers have in common, other than the largest. I'm asking about the factors they don't share, which it treats quite differently. As for why, there are plenty of whys in mathematics. Sure, you can't write the square root of two as a fraction, but why does it not fit that mold? I can understand that. I've seen myself the inherent contradiction that requires, or the similar infinite descent it would cause. In a similar way, your little demonstration shows why it couldn't be expected to break the gcd down farther. The algorithm quite clearly treats gcf(a,b) and gcf(ac,bc) identically. It, as you put it, "jumps through the same hoops" for both. However, there doesn't seem, to me, to be a similar explanation for why it ignores the other factors, the ones they don't have in common. Black Carrot 19:23, 19 July 2006 (UTC)

b_jonas: Exactly. The factorial clearly is easy to locate (it's at exactly x!), but difficult to compute in practice. There are other numbers with the prime factors needed, that would be very easy to compute if they could be found, but they can't be found. I mean, how could they? However, it's incredibly easy, given a number, to find numbers that share no factors at all. Hell, they're right next to it. I'd like to disagree with you on one point, though. You say that, given two numbers with no common factors, the Euclidean algorithm outputs nothing useful. However, it is in fact a small gold mine of other information. Which leads back to my original question. Black Carrot 19:23, 19 July 2006 (UTC)

If gcd(a, b) = d, then the factors a and b do not have in common are a/d and b/d. What you won't get are further factorizations of these factors. --Lambiam^Talk 20:52, 19 July 2006 (UTC)

Indeed. I'm aware nobody's found a way to do that, yet. The why still escapes me, as it seems to escape you. It's good, though, that you're at least responding to the right question now. Oh, and I hope you don't mind that I moved your post. I don't like people breaking up continuity. Black Carrot 16:12, 20 July 2006 (UTC)

Yes, because if there are no common factors, you get the inverse of each number modulo the other, and the Euclidean algorithm (or variants of it, see Knuth) is indeed the simplest way to compute these. – b_jonas 13:10, 27 July 2006 (UTC)