Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 Re: Coder's Corner » time complexity of divisibilty/primality » 2008-11-21 13:40:20

Yes, the choice of "n" is arbitrary; however, in this case, it seems to make more sense for "n" to be the number of digits than the number itself.
And yes, I am using n as the number of digits.

And what do you consider to be an operation?

Could you clarify your question? I am not really an expert in complexity theory (which I have already amply demonstrated), and thus am not certain exactly what you mean by the term.

#2 Re: Coder's Corner » time complexity of divisibilty/primality » 2008-11-20 13:54:50

Ah, my mistake. I was not thinking when I wrote that; the point I was trying to make is untrue. But yes, comparison to existing algorithms is probably the most relevant metric.

I talked this over with a friend, and the problem is the units we've been measuring complexity in. For numerical algorithms, the "n" in complexity is measured as the number of digits (in binary, usually); if "n" were simply the number, many very slow algorithms (such as prime factorization) would appear to have very good time (essentially, functions of numbers which seem fairly small, such as the square root, become quite large eventually, and adjusting the units to the number of digits helps reflect this). In this system, your algorithm for finding a divisor is O(n), which is pretty good. Prime factorization would then be O(n2^(2n)), which is about what other prime factorization algorithms get. An O(√n) complexity for the brute force strategy would result in O(2^(5/2)).

Supposedly, a primality test in polynomial time was announced a few days ago. I'll post more info here once I get the link from my friend. This test, however, doesn't give a polynomial time method for prime factorization.

#3 Re: Exercises » Vector Multiplication and Equality » 2008-11-19 10:54:15

Hmm...bumbling around the forums a bit, I realize this should probably go in the "Exercises" section. Sorry about that.

Topic moved - Ricky

#4 Exercises » Vector Multiplication and Equality » 2008-11-18 14:39:43

Amalcas
Replies: 1

A challenge inspired by a test I took a month or so ago:

Given three vectors a, b, c in real Cartesion 3-space (three real number components), such that a ≠ 0, a × b = a × c, and a * b = a * c, where × is the exterior (cross) product, and * is the interior (dot) product, formulate three separate proofs of that b = c, without resorting to components.

All three proofs are quite simple, and two are fairly immediately obvious if you are familiar with V3 vectors, but the third is apparently less obvious, as my teacher said I'm the only person who he'd ever seen prove it that way. tongue
If it's a hint, the third way isn't geometric (which is probably why it's not often seen, given that it's just as simple as the other two, if not more).

#5 Re: Dark Discussions at Cafe Infinity » Bill Gates' Rules » 2008-11-18 14:26:18

I disagree with rule 8. Schools haven't done away with winning and losing; they've made everyone look like winners at the price of training any real "winners" or making any "losers" into winners. I have seen many poor students pushed through the system because they could be, and so many smart students breeze by with top marks for no effort whatsoever. Smart students shouldn't get better grades; they should take harder courses. Teaching "smart" students that they don't need to try is a travesty, as much as failing to teach poor students at all, or nearly so, as combined they cut the legs out from under society from both the top and bottom.

#6 Re: Dark Discussions at Cafe Infinity » love and feelings » 2008-11-18 14:02:32

Emotions are a powerful motive force for humans; hence the name. The problem is that we often confuse them as being the sole motive force; that is, the cause. I tend to view them as very high level results, to the contrary of this. Actually, emotions are, in a number of ways, safeguard mechanisms evolved to encourage us towards "good" (survivally speaking) behaviors, similar to pain, except also capable of positive reinforcement, and more complex responses.
The problem is not within emotion itself. Without emotion it would be extraordinarily difficult to simply get out of bed in the morning, much less go through the day, as we are motivated largely by reward and punishment, for which emotion is an inbuilt system; depression isn't fundamentally a disorder of sadness, but a disorder of emotions as a whole, a supression of this system of reward and punishment (which leads to a deepseated sort of sadness).
Depression, however, is not all bad; controlled depression of emotions could in fact be a useful tool to deal with the overwhelming onrush of stimuli provided by the modern world. To this end, I have spent six years or so developing, at first by the accident of becoming rather uncontrollably depressed, a system of controlled depression. After developing the rudimentary technique, I learned that it is quite similar to the meditative mindset and techniques employed by Buddhists (which, incidentally, increase activity in the brain related to happiness, not sadness). In essence, one attempts to remain in the meditative mindset while continuing about one's daily tasks, with it eventually becoming ingrained in one's general mental behavior; with greater practice, the "depth" of the mindset can be varied, from full meditation to (nearly) none, allowing almost any degree of emotional involvement.
Now, strong emotions are obviously harder to depress, and stress throws a wrench in the system; for example, I have been working the hardest I ever have, juggling multiple responsibilities, for the past few months, culminating in working 18 hour days for the past three weeks, and I have returned to just about the same level of emotional control and output as six years ago, which only makes matters worse. But not to complain.

Now, how does this relate? Having spent about two years of my life in a state where the only "emotion" I felt to more than the weakest degree was tiredness, I can assure you that emotions are quite nice, even some of the "negative" ones; some forms of sadness (the kind a good song might invoke, for example) are actually quite enjoyable, in a peculiar way.
I would encourage you to try out a little meditation if you're frustrated with emotion; you don't have to learn yoga or how to sit in the lotus position (I sure can't), but starting with the basic methods will teach you the mindset, which you can then begin to apply to your life as a whole.

#7 Re: This is Cool » Is Genius a Gift or Hard Work? » 2008-11-18 12:40:33

I'll play the devil's advocate: the study mentioned in no way proves that hard work is the key to success. Simply put, the study is retrospective; no causality is established, only correlation. It may very well be that it is genius that inspires students of a subject to work hard, or there may be an outside cause for both. Disregarding outside causes, however, the lack of any contradictions to the rule suggests--by common sense, not statistics--that work is the cause, though I would like to know how many students were included in the study.
Getting more to my own opinions, I think that "genius," possessing high abilities in the basic functioning that contributes to skill in a subject, is necessary to be truly exceptional. However, without considerable work, such innate talent won't get you very far at all; hard work is ultimately more important, especially since it's the only thing you can change. Furthermore, a hard worker with less talent is generally more likely to eventually eclipse a more lax yet talented individual, who will only excel at low levels. And as to why there were no exceptions to the correlation in the violinist set, the simplest answer is that they all had considerable innate talent--after all, they were students at a prestigious university--so the major division would in fact be the degree of effort.
On the other hand, passion and 10,000 spare hours is going to make you pretty good at most anything, independent of how much innate "talent" you have contributing to the task.

#8 Re: Coder's Corner » time complexity of divisibilty/primality » 2008-11-18 12:08:57

Prime factorization is a nondeterministic polynomial problem (NP). In short, this means that, as far as we know, a computer must have the ability to "magically" guess right answers in order to complete the algorithm in a reasonable (polynomial, or P) time (e.g. always guess an actual divisor first). Specifically, prime factorization is believed to be super-polynomial, or sub-exponential (taking a time that is somewhere between polynomial and exponential).
Assuming we had a function performing like yours, you would get polynomial complexity for prime factorization (O(log^2(n)), I think; but that might imply impossibly good complexities for naive algorithms...).
However, no one knows if NP = P or not; that is, such an algorithm could exist, though I highly doubt it, even if factorization is polynomial. Another problem is that log(n) -> n as n -> ∞...so for large numbers factorization still becomes impractical.
I would encourage you to look up computational complexity yourself. I only know a very little...and my explanation is more than likely riddled with flaws.

Also, the "lots of security" is, as far as I know, just the RSA cryptographic algorithm; it's just that it's one of the most popular cryptographic algorithms, being a public-key algorithm (thus providing both both secrecy and authenticity) that is reasonably secure. In fact, it was the first big solution to the secrecy vs. authenticity problem, to my knowledge.

Board footer

Powered by FluxBB