Sometimes it's actually a useful convention to choose. For instance, if you're talking about the interval [0,1], it's sometimes nice to put everything in the form 0.d_1 d_2 d_3..., in order to avoid talking about the integer part.
Indeed, as a mathematician, I would never write 0.5 when I meant 1/2. While they're the same number, the former hints at an approximation, while the latter is certainly exact. I tend to use the convention that finite decimal expansions are treated as approximations unless otherwise noted. Of course, they almost never come up anyway, so it's a bit of a moot point. If I really wanted to write down 1/2 as an exact decimal expansion for some reason, I'd write either 0.5000... or 0.4999...
Finding twin primes like this is mostly just an elaborate computational game which doesn't really tell much about the mathematical structure of twin primes. It doesn't help at all with knowing whether there are infinitely many or not, for example. The same goes for other searches for large primes.
Also, if you're asking about real-world practical considerations, the primes used in practical work by comparison are tiny. Using such large primes for things like cryptography would be stupid for a number of reasons, not the least of which being that there are only so many known such primes out there, the size of your key would give it away. Personally, I don't know of any practical use for twin-primes or Mersenne primes, or any of the other classes of large primes being searched for.
It's really more just for fun, like computing digits of pi. However, devising new ways to access large twin primes, for instance, results in improvements of our knowledge of them. It's those new theorems and algorithms which people might get excited about. Running a computer for hours or days or months to actually find the things is less interesting.;)
Sorry to nitpick, but the probability of the date falling in a larger interval could only be higher.
However, it probably really is an approximation to 2 places of a confidence interval where the probability that the actual value lies within that interval is high enough (maybe 95%) not to be too worried about the tails. I'm not a statistician though.
Gapminder is a group of people working on interesting ways to visualise data from the UN, as well as databases from national, and non-governmental organisations. The results are pretty interesting to see, and actually quite hopeful in terms of the world outlook. There seem to be a lot of incorrect preconceptions most people have about global socioeconomics which come from the way things were 30 to 40 years ago.
Here are a couple of rather interesting talks about what they've been working on. There's quite a bit of overlap between the two, but the Google Techtalk is longer and more complete. In Hans' talk at TED, in order to back up the claim that there are incorrect preconceptions, he shows how some of the brightest Swedish students scored a statistically significant margin worse than random when asked to choose the country with the highest child mortality rate from pairs selected such that one of each pair had double the child mortality rate of the other.
Indeed, most of the new techniques for constructing embedded domain specific languages are being stolen from, or at least are completely explicable in terms of category theory.
There are quite a number of completely practical techniques for structuring programs -- monads being the star player at the moment, and of course, their dual, comonads, as well as applicative functors, and Hughes' Arrows which have their foundations in category theory. One doesn't need to understand category theory in order to understand the way in which these abstractions apply to programming, but it certainly helps. I certainly don't think that even these things have been completely mined -- for instance, we only have a few ideas so far about how comonads help programming, but what's there is interesting. Essentially comonads abstract certain kinds of dataflow programming languages. There's a lot of possible interesting research for people who know both category theory and computer science.
If you want to try some of it out and see, have a look at Haskell.:) The community around Haskell is taking these abstractions and turning them into practical libraries which basically anyone can learn to use, regardless of their background. Of course it will take more or less work to learn depending on what that background is, how old you are, etc. It's certainly no harder than learning your first imperative programming language was, and it's definitely worthwhile. With monads in particular, you'll wonder what you ever did without them.
For the unfamiliar, monads, and even more specifically, monad transformers, basically give you really effective ways to quickly construct embedded domain-specific languages. You can very quickly create an EDSL which is the perfect language in which to solve your problem, and you get really nice maintainable code, and lots of correctness guarantees for free or almost free, and you get to borrow all the control structures which people have written for other monadic languages already.
The toy example I like to give people of this is of constructing an EDSL for solving Sudoku puzzles (of course nothing special about Sudoku, any combinatorial constraint problem will do). With a couple of monad transformers, you get a language with state for maintaining the current state of the board, and nondeterminism, allowing you to say in your language "x is one of this list of values", and having the language try all possibilities, in the end performing a depth-first search. You can then, in about as much code as it takes to program the Sudoku constraints, restrict access to the state, so that attempting to make a move which would invalidate the solution causes backtracking to occur right away. In this EDSL, you can write a Sudoku solver like this (the rest of the code is here):
solve = forM [(i,j) | i <- [1..9], j <- [1..9]] $ \(i,j) -> do
v <- valAt (i,j) -- ^ for each board position
when (v == 0) $ do -- if it's empty (we represent that with a 0)
a <- option [1..9] -- pick a number
place (i,j) a -- and try to put it there
(Jeez, it's hard to post properly formatted code on slashdot. Isn't this supposed to be a site for nerds? For those interested, I ended up using blockquotes and explicit line breaks, as well as having to escape the less-than symbols.)
That's actual code -- it's a rather naive algorithm to use, essentially equivalent to brute force search with backtracking, but more clever ones could again easily be written in the same monad. The nice thing is that whatever algorithm you use, if it manages to fill the whole board, must fill the board correctly. The 'forM' in that code is a function implementing a foreach loop which works in any monad, similarly 'when' is another such function, and 'option' is a function which works in
The title of the thread gives the way to do nth roots in general: Newton's method.
Newton's method is a root-finding algorithm which tends to work well for this sort of thing. What it says is that to approximate a root for the differentiable function f, take your guess x_0, and define x_(n+1) = x_n - f(x_n)/f'(x_n). The sequence of x_n's will tend to approximate a root of the function. If the root in question is of multiplicity 1, then there is a guarantee of some neighbourhood around the root so that if you put your guess in that neighbourhood, you'll get at least quadratic convergence (that means the number of correct digits will roughly double on each step).
So how do we use this for finding nth roots? Well, an nth root of a number a, is a number x such that x^n - a = 0. That is, we want to find a root of f(x) = x^n - a. The derivative is f'(x) = n x^(n-1). So we take our initial guess for x_0, (which should be positive if we want the positive root when n is even, but other than that, doesn't matter so much), and we compute:
x_1 = x_0 - ((x_0)^n - a)/(n (x_0)^(n-1))
x_2 = x_1 - ((x_1)^n - a)/(n (x_1)^(n-1))
and so on...
Generally the convergence is quite fast. Actually carrying it out by hand is a little tedious, but if you start with a reasonable guess, it's not that bad.
In Haskell, we can write the algorithm as follows:
rootApprox n a = iterate refine 1 -- taking our initial guess to be 1.
where refine x = x - (x^n - a)/(n * x^(n-1))
Used to compute the third root of 8 (which we all know is 2), it looks like this:
Here, you can see the number of correct places roughly doubling once it gets close enough to 2, as the number of zero digits after the decimal goes from 1 to 2 to 5 to 10, and finally the number settles down on 2.0 because the precision isn't high enough to represent the remaining error.
In practice, of course, you probably eventually want definite results, rather than an infinite list of converging values, so you'd write a function to stop either when the values are correct to within a sufficiently small margin (it's easy to test by raising them to the nth power), or else when they aren't changing enough on each step. For example, in Haskell, you'd write something like:
root n a = head . dropWhile (\x -> abs (x**n - a) > 1e-10) $ rootApprox n a
to throw away values which are too far from being the root, and then take the first of what's left.
Will a continued fraction do instead? It's just [1,2,2,2,2...].
Actually, this is a somewhat interesting question, as I don't think any BBP-type formula for sqrt(2) is yet known. Such a formula would allow the computation of specific digits of sqrt(2) without requiring storage of the others (in a particular base, not necessarily base 10, base 16 is common).
Personally, I like monadic parser combinators, like those provided by the Parsec library for Haskell. You can parse arbitrary context free grammars, and even many sensible context-sensitive ones with little difficulty, you get to write your parsers in the language (Haskell) and you get meaningful parse error reports for free.
A major downside to the approach is that Parsec itself lacks a symmetric choice combinator, having only left-biased conjunction, together with a combinator which causes a parser not to consume input when it fails. Though other libraries, like Koen Claessen's ReadP rectify this, the associated performance costs tend to be higher.
I tend to use Parsec even for some tasks where many people would use regular expressions. It might not be quite as fast as statically building your parser, but it's possible to get really quite decent performance out of it, and the convenience level is quite high.
Another interesting thing to look at are arrow-based parser combinators, like PArrows -- these allow for a greater level of optimisation at runtime, so you can get really good performance while allowing for things like symmetric choice. They also can allow for cool features like the ability to inspect the parser and emit code in various languages for that parser. (The one I linked to has the ability to compile parsers to JavaScript code in fact.) The downside is that arrows tend to be a little more inconvenient to program with than monads.
While all these libraries are in Haskell, there's no strict reason that the technique couldn't work in another language. The only trouble is that most other languages haven't jumped on the monad bandwagon yet, so programming with monads in something like Java can be somewhat awkward (though one could make the claim that this isn't only true of monads.;) However, it can be done in Java as well as in Python and (very roughly, not quite monadic) in C
Re-reading the above, I realised that I should perhaps emphasize the point that to be a manifold, it has to look like 3-dimensional space at every point -- so there are no "walls" where the space just stops, or else at the wall, it would look like half of R^3 instead.
Two spaces X and Y are homeomorphic when there's a continuous function f: X -> Y which has a continuous inverse. Basically, spaces are homeomorphic when you can bend one into the other without gluing things together or cutting them apart.
It's saying that if you have a 3-manifold which is compact and simply connected, then it's possible to bend it nicely into the 3-sphere.
Saying that it's a 3-manifold means that at every point in the space, it sort of locally looks like the usual Euclidean 3-space. A reasonable analogy is the surface of the Earth is a sort of 2-manifold, since it locally looks like a plane -- enough so that it took us a long time to discover that it's actually connected up like a sphere.
With the 3-sphere, if you, as a 3-dimensional object, were floating inside it, it would be rather like being in ordinary 3-dimensional space that you're used to, but the space would be bent in such a way so if you travelled in any one direction for long enough, you'd end up back where you started. (Kind of like what happens in 2-dimensions while travelling on the surface of the Earth.) Rather than being on the surface of a 3-dimensional ball, you'd be *in* the surface of a 4-dimensional one.
Now, the words "compact" and "simply connected"...
"Compact", you basically might think of that geometrically as meaning that if you have an infinite sequence of points in the space, then some subsequence of those points will be converging on some point. It sort of means that the space must be "small" in some sense, because the points can't head off to infinity, and it also means that if a sequence of points are getting closer to each other, then they must be converging on some point. (The space includes its boundary.)
"Simply connected", basically means that if you're floating in this 3 dimensional space, and you have a stretchy loop of rope, you can move and stretch the rope without cutting it to be anywhere in the space. As an example of where you couldn't, if you were inside of a doughnut-shaped room, the rope might go around the "hole" in the middle, and you wouldn't be able to get it off without cutting it. (This can be expressed mathematically by talking about continuous functions from the circle into the space.) Another example of a not-simply connected space is just two ordinary rooms which are not connected to each other (like there's a wall between them). If the rope is in one room, you can't move it to the other. Of course, the individual rooms in this case might be simply connected, but considered together, they're not.
So, really loosely, the theorem is kind of telling you that if you're in a strange 3-dimensional space which seems to have a finite amount of room, and you can't seem to get a rope hooked on to anything, then you must be in the 3-sphere, there's no other strange way for a space to be connected up to itself.
It's interesting that the theorem has long been known to be true for 2 dimensional surfaces, and for 4 and higher dimensional manifolds for quite some time now, but the 3-dimensional case had eluded proof for quite a long time.
That's just because it's not 4-D Euclidean space. Space-time is still considered as a 4-dimensional manifold, it just has a different metric on it. The term used is Minkowski space.
Friend, you have no idea how "tricky" it is. The retina itself does massive pre-processing of the signal: color detection, edge detection, and motion detection are all done inside the eye.
Can you give a reference for this? I was under the impression that this sort of thing is mostly carried out in V1 through V5 in the visual cortex (in the occipital lobe of the brain). As far as I know, the input from the retina is spatially mapped onto V1 almost directly, after being sorted into visual fields in the optic chiasma.
V1 then does something similar to many local Fourier transforms, encoding visual frequency with much more detail than actual brightness before passing the information forward to further visual processing areas. Simple motion is processed by V2-V4, and V5 is thought to handle complex motion, though some research indicates that some of this may already be available to the system as early as V1 (though V1 also receives feedback from V5, among many other regions)
However, I've never heard the claim that any such processing is actually done in the eye itself. As far as I've heard, the signals leaving the eye encode only information about brightness. (Of course in varying degrees to monochromatic stimuli across the three cone types and in rods.) It would be quite interesting to hear that any processing of the sort you describe is done prior to V1, where did you read this?
How about defining (most of) your computation in a way which doesn't indicate the order in which evaluation must occur, and allowing the compiler to do data dependency analysis on the code, and determine good ways to break it into threads on its own? I can almost guarantee that whatever a human comes up with will usually be nowhere near optimal, especially if you also want to try to put Altivec into heavy use. In a lot of cases, that's some pretty heavy analysis even for a machine, but if the final optimised compile takes a few days, who cares? You'll only have to do it once.
I've actually written a pipeline scheduler for PPC+Altivec, in Haskell, for a "high level assembly" intermediate language that allowed for multiple ways to compute the same result. In a few weeks of Haskell coding (and a couple months of thinking), we managed to get to the point of scheduling some code for computing sine/cosine pairs so that it ran at about 2.7 clocks/float (using lots of vector instructions), which is 50 to 100 times faster than libm, iirc, and many times faster than even other vectorised versions which were available at the time (I seem to recall hearing 14x). That part of the search actually ran pretty quickly -- it could emit schedules as a lazy list (in order of decreasing algorithm greediness) at a rate of around 20 per second running on my G5.
I'm due to rejoin that project soon, and we'll apparently be targeting the Cell. The overall long-term goal of the project is to have a very high level mathematical language in which to specify signal processing applications, along with successively lower level languages in which components will be written, together with a directed search mechanism at each layer, choosing fast implementations of the higher level code in terms of lower level parts, and doing various optimisations at every stage. The choices the compiler makes will be dependent on the network setup and processor architecture being used, and what code and transformations are available to it.
Firstly, Haskell isn't strict, it's lazy. Secondly, this isn't funny.
Code written in languages with strong algebraic properties like referential transparency is ideal for doing automatic high-level transformations of code in order to increase parallelism.
As architectures get more complicated with multiple processors and multiple pipelines, we will more and more want to rely on automatic tools to search for good ways to structure code, from breaking up major processes right down to instruction level scheduling. Using high-level information about the task at hand and the components which make it up, which isn't present in lower level languages will be important in this task.
As a precursor to this, have a look at FFTW, the Fastest Fourier Transform in the West. On the surface, it appears to be written in C, but that C code is not entirely written by hand, it is machine generated by an O'Caml program with some very specific high-level knowledge of the problem (applying some mathematics to do a directed search for an implementation of an FFT of any size which is fast on the given platform). Basically, it's using high-level properties of the problem in order to obtain very fast code implementing a solution. The more information available to a compiler, the better.
Haskell itself already provides higher level information about the overall structure of a computation, leaving more of the details to the compiler than say, your average C++ or Java program. The implementations aren't totally killer yet, but there's a *lot* of untapped potential there.
(Even now, GHC is placing first and second on the computer language shootout with default settings.)
Haskell itself isn't quite ideal for high-level machine transformation of code, but I'd contend that it's certainly a practical starting point, and it's certainly my favourite programming language to actually get things done in.
No, it's the fact that up until recently *no* falsifiable claims had been made regarding string theory, and to present, none have been tested. Thus, at present, string theory is not science. The article claims that a difference of prediction has been found and an experiment devised to test it.
Higher dimensional theories of the universe are fine. If they work, and provide an elegant framework in which to make predictions, then that's great. However, if they're more complicated than existing theories and make no new predictions, they are not so useful.
There is no "truth" about the dimension of the universe. To ask the *real* dimension of the universe is to ask a question which doesn't even mean anything. (After all, the word 'dimension' in this sense only means anything if you have a mathematical manifold or vector space about.) The dimension of the universe at any given time is whatever it happens to be in any given model of the universe one is using.
Higher dimensional models of the universe have *nothing*at*all* to do with the existence or non-existence of gods. Besides, gods tend not to be falsifiable, so there's no way that any scientific model could say anything about their existence. Basically, you get to choose if they exist, because you get to choose which statements you'd like to call 'true'.
Truth is what you make it. In the long run, the only measuring stick by which statements attain the labels 'true' and 'false' is success: real-world usefulness, mathematical elegance, or otherwise.
Yes! This is Insightful, more than it is Funny. The amount of needless damage that cars are doing to the environment is ridiculous. People drive every day to jobs, in cars which are way less fuel-efficient than necessary, to offices where they sit at a computer, and where there's hardly any actual need to interact face-to-face with people. At least, not enough of a need that they shouldn't be able to work from home. Sure, for many jobs, say, where you need special heavy equipment, if you're building things on-site, or which involve moving things from point to point, you're going to need to be on the road. If you're just manipulating information like in many office jobs, there should be no need to come in to work every single day. Get these people off the roads by providing meaningful tax incentives to companies which encourage their workers to do their work from home, and base it on the number of employees which actually do so.
Tried freenode? Many of my friends use freenode anyway, so I don't have to bother with IM systems. Even if that isn't the case for you, freenode has the nice property of having quite a lot of high quality topic-directed channels, without so many h4x0rs and pervs.
Of course, one can define the symbols to mean whatever one would like, but there are usually good reasons for the definitions one makes. There are quite a large number of reasons why 0^0 = 1 is a sensible definition. I'll give a few.
If A and B are sets, a function f: A -> B is a set of pairs (a,b), a in A and b in B such that
If (a,b) and (a,c) are in the set, then b = c.
For every a in A, there is some b such that (a,b) is in the set.
When (a,b) is in the set, we write f(a) = b.
If A is a set with m elements, and B is a set with n elements, then n^m is the number of functions from A to B, at least for all integers n,m > 0.
What happens with empty sets? If A and B both contain 0 elements, then there actually is one function between them: the empty function, that is the empty set of pairs. You can verify that it (trivially) satisfies the two conditions above to be a function. Also, there cannot be another function, because there are actually no pairs which could be in the set anyway, that is, if A and B are empty, then AxB = {(a,b) | a in A, b in B} is empty. So there is exactly one function from the empty set to itself, and hence it would make sense that 0^0 = 1 is a good definition.
There are also good reasons analytically to set 0^0 = 1. Although there is a conflict between the two limits:
limit as x -> 0+ of limit as y -> 0 of x^y = 1
limit as y -> 0 of limit as x -> 0+ of x^y = 0
It turns out that the directional limit approaching 0 of the function f: (R^+) x R -> R, f(x,y) = x^y from any other direction than the latter limit above gives a limit of 1. That is, the limit as x -> 0+ of f(x,ax) = 1, for every a in R.
Further, there is a good algebraic reason why x^0 is always 1, regardless of x. That is the fact that one wants the identity x^(a+b) = x^a x^b to hold as far as possible. If x^0 = 0 (or any other value than 1) this property would fail: use a = 0 and b = 1. Then x = x^1 = x^(0 + 1) = x^0 x^1 = x^0 * x. The only value we can give to x^0 which makes this equality work is 1.
Hope this clears things up a bit why it's a sensible thing to define. Just remember that mathematics is largely arbitrary. So long as you say clearly what you are doing, and follow the rules that you set for yourself, it's fine. You can even change the rules of logic if you like. (Though to get others to work with you, you'll probably have to agree on conventions of course.)
Would you say that a lock obstructs breaking and entering? Or that self defense obstructs assault? Perhaps good server administration obstructs the stealing of private data.
Of course, because those statements are true, and use the word "obstructs" correctly. Have you checked the definition recently? It ought to be quite obvious to everyone that it is considered "good" to block, impede, hinder, or stand in the way of something which is "bad". The word "obstruct" only has a negative connotation when it is applied to some process which is considered "good".
If you'd like to learn mathematics properly, one book that I'd suggest wholeheartedly is Michael Spivak's "Calculus" (note that this is a different book from "Calculus on Manifolds", which is a good book, but not a place to start). It starts off by defining things like the real numbers, functions, limits and so on very carefully, and proceeds very logically.
I have found that mathematics is treated in a very illogical and irresponsible fashion in highschool, and often continues in this way in the engineering sections. You might be happier with a more structured logical presentation of it. My friend at one point dropped out of Engineering after failing his mathematics classes, went into mathematics, and just recently graduated as a pure/applied math double major. It might not be your fault that you're doing poorly.
I agree that students are very badly prepared after leaving highschool.
I think his is an honest attempt at compromise. His issue isn't just that trig functions are hard to compute by hand. It's that they are impossible to even define without first introducing some notions from analysis and/or Calculus. (You can't talk about angles without arc length.)
Personally, I think that the schools should be more concerned with preserving the logical dependencies between concepts in mathematics. That said, I think it's not unreasonable for them to do proper trigonometry, and do it right -- after defining the real numbers correctly, studying sequences and functions, and limits of each, and defining at least arc length properly in terms of the limit superior, if not a proper Riemann integral.
It's hard to enact all this change though, and hard to convince people that students would do better with this "harder" curriculum, when they already struggle. I contend that the reason for their struggling is that things are not being taught in a logical fashion. Whether this means of accomplishing common tasks in trigonometry without the usual notion of angle is the right thing to teach is questionable, but the way things are currently taught is wrong as well.
Notice that you hardly ever hear the question of usefulness in the real world in a music or art class.
I think one big problem is that people are given the impression that mathematics has something to do with the real world, and that it's supposed to be "useful". (Well it is, but not for the obvious reasons.)
Mathematics really just consists of a bunch of structures. These structures can be really quite beautiful on their own, and if it's presented the right way, people should see some reason to study mathematics without any reference to application.
The problem is that, in highschools, it is usually presented as a jumbled mess of formulas with almost no logical stucture to it at all.
There are huge gaps in the reasoning, partly owing to the fact that calculus is left entirely to the end, and then largely mistreated. You can't talk about angles without first talking about limits, and you can't really talk about limits until you understand what the real numbers are (hint: if you were confused about the 0.9999... = 1 thing, you've probably never been given a proper definition of the real numbers).
Angles need some notion of arc length, which needs at least the concept of a limit superior. (If not an integral.) The book in the article shows how to accomplish the tasks normally associated with trigonometry without needing the concept of an angle (or really anything from calculus or analysis).
If you look at the things that students have trouble with, it's usually the curriculum's fault for not explaining things in a reasonable logical order.
One of the things many people have trouble with in highschool is the whole issue surrounding the logarithm and exponentiation with a positive real exponent. The reason why they struggle is that these things get defined circularly. Nobody ever really tells you what the expression 2^(sqrt(2)) or 5^pi is supposed to represent. You need to know things about limits and convergence of series in order to define a^b where a is real, and b > 0 is real.
I was lucky, and found things to read on my own which described enough of mathematics to me to get me interested, and then went to university for pure mathematics.
The reason why mathematics should be taught in highschool is that people should gain some concept of logic, which is useful no matter where you're headed, and by proving propositions and theorems, one eventually gains an incredible grasp of logic. This isn't currently done though.
Mathematics is basically presented as an awful illogical mess where at best, the students are taught to solve some very specific problems in a mechanical, unthinking fashion, and at worst, their self-esteem is damaged and they come away thinking that they are bad at something which they've never been exposed to. I've seen some very bright people who thought that they were terrible at math, and for this reason avoided going into fields of study that they'd otherwise have been interested in.
I hope we can eventually do something about this because, as a student of mathematics, I can say that the present state of affairs at the elementary and highschool level is terrible, and while I can easily see ways in which it could be made better, actually carrying it out is another thing altogether.
Slashdot Mirror
At which place does that 1 occur? Remember that every digit occurs at some finite integer position, determining its place value.
Sometimes it's actually a useful convention to choose. For instance, if you're talking about the interval [0,1], it's sometimes nice to put everything in the form 0.d_1 d_2 d_3 ..., in order to avoid talking about the integer part.
Indeed, as a mathematician, I would never write 0.5 when I meant 1/2. While they're the same number, the former hints at an approximation, while the latter is certainly exact. I tend to use the convention that finite decimal expansions are treated as approximations unless otherwise noted. Of course, they almost never come up anyway, so it's a bit of a moot point. If I really wanted to write down 1/2 as an exact decimal expansion for some reason, I'd write either 0.5000... or 0.4999...
Finding twin primes like this is mostly just an elaborate computational game which doesn't really tell much about the mathematical structure of twin primes. It doesn't help at all with knowing whether there are infinitely many or not, for example. The same goes for other searches for large primes.
;)
Also, if you're asking about real-world practical considerations, the primes used in practical work by comparison are tiny. Using such large primes for things like cryptography would be stupid for a number of reasons, not the least of which being that there are only so many known such primes out there, the size of your key would give it away. Personally, I don't know of any practical use for twin-primes or Mersenne primes, or any of the other classes of large primes being searched for.
It's really more just for fun, like computing digits of pi. However, devising new ways to access large twin primes, for instance, results in improvements of our knowledge of them. It's those new theorems and algorithms which people might get excited about. Running a computer for hours or days or months to actually find the things is less interesting.
Sorry to nitpick, but the probability of the date falling in a larger interval could only be higher.
However, it probably really is an approximation to 2 places of a confidence interval where the probability that the actual value lies within that interval is high enough (maybe 95%) not to be too worried about the tails. I'm not a statistician though.
Gapminder is a group of people working on interesting ways to visualise data from the UN, as well as databases from national, and non-governmental organisations. The results are pretty interesting to see, and actually quite hopeful in terms of the world outlook. There seem to be a lot of incorrect preconceptions most people have about global socioeconomics which come from the way things were 30 to 40 years ago.
Here are a couple of rather interesting talks about what they've been working on. There's quite a bit of overlap between the two, but the Google Techtalk is longer and more complete. In Hans' talk at TED, in order to back up the claim that there are incorrect preconceptions, he shows how some of the brightest Swedish students scored a statistically significant margin worse than random when asked to choose the country with the highest child mortality rate from pairs selected such that one of each pair had double the child mortality rate of the other.
Indeed, most of the new techniques for constructing embedded domain specific languages are being stolen from, or at least are completely explicable in terms of category theory.
There are quite a number of completely practical techniques for structuring programs -- monads being the star player at the moment, and of course, their dual, comonads, as well as applicative functors, and Hughes' Arrows which have their foundations in category theory. One doesn't need to understand category theory in order to understand the way in which these abstractions apply to programming, but it certainly helps. I certainly don't think that even these things have been completely mined -- for instance, we only have a few ideas so far about how comonads help programming, but what's there is interesting. Essentially comonads abstract certain kinds of dataflow programming languages. There's a lot of possible interesting research for people who know both category theory and computer science.
If you want to try some of it out and see, have a look at Haskell. :) The community around Haskell is taking these abstractions and turning them into practical libraries which basically anyone can learn to use, regardless of their background. Of course it will take more or less work to learn depending on what that background is, how old you are, etc. It's certainly no harder than learning your first imperative programming language was, and it's definitely worthwhile. With monads in particular, you'll wonder what you ever did without them.
For the unfamiliar, monads, and even more specifically, monad transformers, basically give you really effective ways to quickly construct embedded domain-specific languages. You can very quickly create an EDSL which is the perfect language in which to solve your problem, and you get really nice maintainable code, and lots of correctness guarantees for free or almost free, and you get to borrow all the control structures which people have written for other monadic languages already.
The toy example I like to give people of this is of constructing an EDSL for solving Sudoku puzzles (of course nothing special about Sudoku, any combinatorial constraint problem will do). With a couple of monad transformers, you get a language with state for maintaining the current state of the board, and nondeterminism, allowing you to say in your language "x is one of this list of values", and having the language try all possibilities, in the end performing a depth-first search. You can then, in about as much code as it takes to program the Sudoku constraints, restrict access to the state, so that attempting to make a move which would invalidate the solution causes backtracking to occur right away. In this EDSL, you can write a Sudoku solver like this (the rest of the code is here):
(Jeez, it's hard to post properly formatted code on slashdot. Isn't this supposed to be a site for nerds? For those interested, I ended up using blockquotes and explicit line breaks, as well as having to escape the less-than symbols.)
That's actual code -- it's a rather naive algorithm to use, essentially equivalent to brute force search with backtracking, but more clever ones could again easily be written in the same monad. The nice thing is that whatever algorithm you use, if it manages to fill the whole board, must fill the board correctly. The 'forM' in that code is a function implementing a foreach loop which works in any monad, similarly 'when' is another such function, and 'option' is a function which works in
The title of the thread gives the way to do nth roots in general: Newton's method.
Newton's method is a root-finding algorithm which tends to work well for this sort of thing. What it says is that to approximate a root for the differentiable function f, take your guess x_0, and define x_(n+1) = x_n - f(x_n)/f'(x_n). The sequence of x_n's will tend to approximate a root of the function. If the root in question is of multiplicity 1, then there is a guarantee of some neighbourhood around the root so that if you put your guess in that neighbourhood, you'll get at least quadratic convergence (that means the number of correct digits will roughly double on each step).
So how do we use this for finding nth roots? Well, an nth root of a number a, is a number x such that x^n - a = 0. That is, we want to find a root of f(x) = x^n - a. The derivative is f'(x) = n x^(n-1). So we take our initial guess for x_0, (which should be positive if we want the positive root when n is even, but other than that, doesn't matter so much), and we compute:
x_1 = x_0 - ((x_0)^n - a)/(n (x_0)^(n-1))
x_2 = x_1 - ((x_1)^n - a)/(n (x_1)^(n-1))
and so on...
Generally the convergence is quite fast. Actually carrying it out by hand is a little tedious, but if you start with a reasonable guess, it's not that bad.
In Haskell, we can write the algorithm as follows:
Used to compute the third root of 8 (which we all know is 2), it looks like this:
Here, you can see the number of correct places roughly doubling once it gets close enough to 2, as the number of zero digits after the decimal goes from 1 to 2 to 5 to 10, and finally the number settles down on 2.0 because the precision isn't high enough to represent the remaining error.In practice, of course, you probably eventually want definite results, rather than an infinite list of converging values, so you'd write a function to stop either when the values are correct to within a sufficiently small margin (it's easy to test by raising them to the nth power), or else when they aren't changing enough on each step. For example, in Haskell, you'd write something like:
to throw away values which are too far from being the root, and then take the first of what's left.Will a continued fraction do instead? It's just [1,2,2,2,2...].
a s.pdf doesn't list one, but does give such a formula for pi sqrt(2).
Actually, this is a somewhat interesting question, as I don't think any BBP-type formula for sqrt(2) is yet known. Such a formula would allow the computation of specific digits of sqrt(2) without requiring storage of the others (in a particular base, not necessarily base 10, base 16 is common).
http://crd.lbl.gov/~dhbailey/dhbpapers/bbp-formul
Personally, I like monadic parser combinators, like those provided by the Parsec library for Haskell. You can parse arbitrary context free grammars, and even many sensible context-sensitive ones with little difficulty, you get to write your parsers in the language (Haskell) and you get meaningful parse error reports for free.
A major downside to the approach is that Parsec itself lacks a symmetric choice combinator, having only left-biased conjunction, together with a combinator which causes a parser not to consume input when it fails. Though other libraries, like Koen Claessen's ReadP rectify this, the associated performance costs tend to be higher.
I tend to use Parsec even for some tasks where many people would use regular expressions. It might not be quite as fast as statically building your parser, but it's possible to get really quite decent performance out of it, and the convenience level is quite high.
Another interesting thing to look at are arrow-based parser combinators, like PArrows -- these allow for a greater level of optimisation at runtime, so you can get really good performance while allowing for things like symmetric choice. They also can allow for cool features like the ability to inspect the parser and emit code in various languages for that parser. (The one I linked to has the ability to compile parsers to JavaScript code in fact.) The downside is that arrows tend to be a little more inconvenient to program with than monads.
While all these libraries are in Haskell, there's no strict reason that the technique couldn't work in another language. The only trouble is that most other languages haven't jumped on the monad bandwagon yet, so programming with monads in something like Java can be somewhat awkward (though one could make the claim that this isn't only true of monads.When the researchers shortened the ants' legs the insects had trouble finding home.
Hmm, I wonder, would the researchers would have any trouble getting home if their legs were shortened instead?Re-reading the above, I realised that I should perhaps emphasize the point that to be a manifold, it has to look like 3-dimensional space at every point -- so there are no "walls" where the space just stops, or else at the wall, it would look like half of R^3 instead.
Two spaces X and Y are homeomorphic when there's a continuous function f: X -> Y which has a continuous inverse. Basically, spaces are homeomorphic when you can bend one into the other without gluing things together or cutting them apart.
It's saying that if you have a 3-manifold which is compact and simply connected, then it's possible to bend it nicely into the 3-sphere.
Saying that it's a 3-manifold means that at every point in the space, it sort of locally looks like the usual Euclidean 3-space. A reasonable analogy is the surface of the Earth is a sort of 2-manifold, since it locally looks like a plane -- enough so that it took us a long time to discover that it's actually connected up like a sphere.
With the 3-sphere, if you, as a 3-dimensional object, were floating inside it, it would be rather like being in ordinary 3-dimensional space that you're used to, but the space would be bent in such a way so if you travelled in any one direction for long enough, you'd end up back where you started. (Kind of like what happens in 2-dimensions while travelling on the surface of the Earth.) Rather than being on the surface of a 3-dimensional ball, you'd be *in* the surface of a 4-dimensional one.
Now, the words "compact" and "simply connected"...
"Compact", you basically might think of that geometrically as meaning that if you have an infinite sequence of points in the space, then some subsequence of those points will be converging on some point. It sort of means that the space must be "small" in some sense, because the points can't head off to infinity, and it also means that if a sequence of points are getting closer to each other, then they must be converging on some point. (The space includes its boundary.)
"Simply connected", basically means that if you're floating in this 3 dimensional space, and you have a stretchy loop of rope, you can move and stretch the rope without cutting it to be anywhere in the space. As an example of where you couldn't, if you were inside of a doughnut-shaped room, the rope might go around the "hole" in the middle, and you wouldn't be able to get it off without cutting it. (This can be expressed mathematically by talking about continuous functions from the circle into the space.) Another example of a not-simply connected space is just two ordinary rooms which are not connected to each other (like there's a wall between them). If the rope is in one room, you can't move it to the other. Of course, the individual rooms in this case might be simply connected, but considered together, they're not.
So, really loosely, the theorem is kind of telling you that if you're in a strange 3-dimensional space which seems to have a finite amount of room, and you can't seem to get a rope hooked on to anything, then you must be in the 3-sphere, there's no other strange way for a space to be connected up to itself.
It's interesting that the theorem has long been known to be true for 2 dimensional surfaces, and for 4 and higher dimensional manifolds for quite some time now, but the 3-dimensional case had eluded proof for quite a long time.
That's just because it's not 4-D Euclidean space. Space-time is still considered as a 4-dimensional manifold, it just has a different metric on it. The term used is Minkowski space.
Can you give a reference for this? I was under the impression that this sort of thing is mostly carried out in V1 through V5 in the visual cortex (in the occipital lobe of the brain). As far as I know, the input from the retina is spatially mapped onto V1 almost directly, after being sorted into visual fields in the optic chiasma.
V1 then does something similar to many local Fourier transforms, encoding visual frequency with much more detail than actual brightness before passing the information forward to further visual processing areas. Simple motion is processed by V2-V4, and V5 is thought to handle complex motion, though some research indicates that some of this may already be available to the system as early as V1 (though V1 also receives feedback from V5, among many other regions)
However, I've never heard the claim that any such processing is actually done in the eye itself. As far as I've heard, the signals leaving the eye encode only information about brightness. (Of course in varying degrees to monochromatic stimuli across the three cone types and in rods.) It would be quite interesting to hear that any processing of the sort you describe is done prior to V1, where did you read this?
- Cale
How about defining (most of) your computation in a way which doesn't indicate the order in which evaluation must occur, and allowing the compiler to do data dependency analysis on the code, and determine good ways to break it into threads on its own? I can almost guarantee that whatever a human comes up with will usually be nowhere near optimal, especially if you also want to try to put Altivec into heavy use. In a lot of cases, that's some pretty heavy analysis even for a machine, but if the final optimised compile takes a few days, who cares? You'll only have to do it once.
I've actually written a pipeline scheduler for PPC+Altivec, in Haskell, for a "high level assembly" intermediate language that allowed for multiple ways to compute the same result. In a few weeks of Haskell coding (and a couple months of thinking), we managed to get to the point of scheduling some code for computing sine/cosine pairs so that it ran at about 2.7 clocks/float (using lots of vector instructions), which is 50 to 100 times faster than libm, iirc, and many times faster than even other vectorised versions which were available at the time (I seem to recall hearing 14x). That part of the search actually ran pretty quickly -- it could emit schedules as a lazy list (in order of decreasing algorithm greediness) at a rate of around 20 per second running on my G5.
I'm due to rejoin that project soon, and we'll apparently be targeting the Cell. The overall long-term goal of the project is to have a very high level mathematical language in which to specify signal processing applications, along with successively lower level languages in which components will be written, together with a directed search mechanism at each layer, choosing fast implementations of the higher level code in terms of lower level parts, and doing various optimisations at every stage. The choices the compiler makes will be dependent on the network setup and processor architecture being used, and what code and transformations are available to it.
- Cale
Firstly, Haskell isn't strict, it's lazy. Secondly, this isn't funny.
Code written in languages with strong algebraic properties like referential transparency is ideal for doing automatic high-level transformations of code in order to increase parallelism.
As architectures get more complicated with multiple processors and multiple pipelines, we will more and more want to rely on automatic tools to search for good ways to structure code, from breaking up major processes right down to instruction level scheduling. Using high-level information about the task at hand and the components which make it up, which isn't present in lower level languages will be important in this task.
As a precursor to this, have a look at FFTW, the Fastest Fourier Transform in the West. On the surface, it appears to be written in C, but that C code is not entirely written by hand, it is machine generated by an O'Caml program with some very specific high-level knowledge of the problem (applying some mathematics to do a directed search for an implementation of an FFT of any size which is fast on the given platform). Basically, it's using high-level properties of the problem in order to obtain very fast code implementing a solution. The more information available to a compiler, the better.
Haskell itself already provides higher level information about the overall structure of a computation, leaving more of the details to the compiler than say, your average C++ or Java program. The implementations aren't totally killer yet, but there's a *lot* of untapped potential there.
(Even now, GHC is placing first and second on the computer language shootout with default settings.)
Haskell itself isn't quite ideal for high-level machine transformation of code, but I'd contend that it's certainly a practical starting point, and it's certainly my favourite programming language to actually get things done in.
- Cale
No, it's the fact that up until recently *no* falsifiable claims had been made regarding string theory, and to present, none have been tested. Thus, at present, string theory is not science. The article claims that a difference of prediction has been found and an experiment devised to test it.
Higher dimensional theories of the universe are fine. If they work, and provide an elegant framework in which to make predictions, then that's great. However, if they're more complicated than existing theories and make no new predictions, they are not so useful.
There is no "truth" about the dimension of the universe. To ask the *real* dimension of the universe is to ask a question which doesn't even mean anything. (After all, the word 'dimension' in this sense only means anything if you have a mathematical manifold or vector space about.) The dimension of the universe at any given time is whatever it happens to be in any given model of the universe one is using.
Higher dimensional models of the universe have *nothing*at*all* to do with the existence or non-existence of gods. Besides, gods tend not to be falsifiable, so there's no way that any scientific model could say anything about their existence. Basically, you get to choose if they exist, because you get to choose which statements you'd like to call 'true'.
Truth is what you make it. In the long run, the only measuring stick by which statements attain the labels 'true' and 'false' is success: real-world usefulness, mathematical elegance, or otherwise.
Yes! This is Insightful, more than it is Funny. The amount of needless damage that cars are doing to the environment is ridiculous. People drive every day to jobs, in cars which are way less fuel-efficient than necessary, to offices where they sit at a computer, and where there's hardly any actual need to interact face-to-face with people. At least, not enough of a need that they shouldn't be able to work from home. Sure, for many jobs, say, where you need special heavy equipment, if you're building things on-site, or which involve moving things from point to point, you're going to need to be on the road. If you're just manipulating information like in many office jobs, there should be no need to come in to work every single day. Get these people off the roads by providing meaningful tax incentives to companies which encourage their workers to do their work from home, and base it on the number of employees which actually do so.
Tried freenode? Many of my friends use freenode anyway, so I don't have to bother with IM systems. Even if that isn't the case for you, freenode has the nice property of having quite a lot of high quality topic-directed channels, without so many h4x0rs and pervs.
Of course, one can define the symbols to mean whatever one would like, but there are usually good reasons for the definitions one makes. There are quite a large number of reasons why 0^0 = 1 is a sensible definition. I'll give a few.
If A and B are sets, a function f: A -> B is a set of pairs (a,b), a in A and b in B such that
When (a,b) is in the set, we write f(a) = b.
If A is a set with m elements, and B is a set with n elements, then n^m is the number of functions from A to B, at least for all integers n,m > 0.
What happens with empty sets? If A and B both contain 0 elements, then there actually is one function between them: the empty function, that is the empty set of pairs. You can verify that it (trivially) satisfies the two conditions above to be a function. Also, there cannot be another function, because there are actually no pairs which could be in the set anyway, that is, if A and B are empty, then AxB = {(a,b) | a in A, b in B} is empty. So there is exactly one function from the empty set to itself, and hence it would make sense that 0^0 = 1 is a good definition.
There are also good reasons analytically to set 0^0 = 1. Although there is a conflict between the two limits:
- limit as x -> 0+ of limit as y -> 0 of x^y = 1
- limit as y -> 0 of limit as x -> 0+ of x^y = 0
It turns out that the directional limit approaching 0 of the function f: (R^+) x R -> R, f(x,y) = x^y from any other direction than the latter limit above gives a limit of 1. That is, the limit as x -> 0+ of f(x,ax) = 1, for every a in R.Further, there is a good algebraic reason why x^0 is always 1, regardless of x. That is the fact that one wants the identity x^(a+b) = x^a x^b to hold as far as possible. If x^0 = 0 (or any other value than 1) this property would fail: use a = 0 and b = 1. Then x = x^1 = x^(0 + 1) = x^0 x^1 = x^0 * x. The only value we can give to x^0 which makes this equality work is 1.
Hope this clears things up a bit why it's a sensible thing to define. Just remember that mathematics is largely arbitrary. So long as you say clearly what you are doing, and follow the rules that you set for yourself, it's fine. You can even change the rules of logic if you like. (Though to get others to work with you, you'll probably have to agree on conventions of course.)
- Cale Gibbard
Of course, because those statements are true, and use the word "obstructs" correctly. Have you checked the definition recently? It ought to be quite obvious to everyone that it is considered "good" to block, impede, hinder, or stand in the way of something which is "bad". The word "obstruct" only has a negative connotation when it is applied to some process which is considered "good".
Please see my other post here
If you'd like to learn mathematics properly, one book that I'd suggest wholeheartedly is Michael Spivak's "Calculus" (note that this is a different book from "Calculus on Manifolds", which is a good book, but not a place to start). It starts off by defining things like the real numbers, functions, limits and so on very carefully, and proceeds very logically.
I have found that mathematics is treated in a very illogical and irresponsible fashion in highschool, and often continues in this way in the engineering sections. You might be happier with a more structured logical presentation of it. My friend at one point dropped out of Engineering after failing his mathematics classes, went into mathematics, and just recently graduated as a pure/applied math double major. It might not be your fault that you're doing poorly.
I agree that students are very badly prepared after leaving highschool.
I think his is an honest attempt at compromise. His issue isn't just that trig functions are hard to compute by hand. It's that they are impossible to even define without first introducing some notions from analysis and/or Calculus. (You can't talk about angles without arc length.)
Personally, I think that the schools should be more concerned with preserving the logical dependencies between concepts in mathematics. That said, I think it's not unreasonable for them to do proper trigonometry, and do it right -- after defining the real numbers correctly, studying sequences and functions, and limits of each, and defining at least arc length properly in terms of the limit superior, if not a proper Riemann integral.
It's hard to enact all this change though, and hard to convince people that students would do better with this "harder" curriculum, when they already struggle. I contend that the reason for their struggling is that things are not being taught in a logical fashion. Whether this means of accomplishing common tasks in trigonometry without the usual notion of angle is the right thing to teach is questionable, but the way things are currently taught is wrong as well.
Notice that you hardly ever hear the question of usefulness in the real world in a music or art class.
I think one big problem is that people are given the impression that mathematics has something to do with the real world, and that it's supposed to be "useful". (Well it is, but not for the obvious reasons.)
Mathematics really just consists of a bunch of structures. These structures can be really quite beautiful on their own, and if it's presented the right way, people should see some reason to study mathematics without any reference to application.
The problem is that, in highschools, it is usually presented as a jumbled mess of formulas with almost no logical stucture to it at all.
There are huge gaps in the reasoning, partly owing to the fact that calculus is left entirely to the end, and then largely mistreated. You can't talk about angles without first talking about limits, and you can't really talk about limits until you understand what the real numbers are (hint: if you were confused about the 0.9999... = 1 thing, you've probably never been given a proper definition of the real numbers).
Angles need some notion of arc length, which needs at least the concept of a limit superior. (If not an integral.) The book in the article shows how to accomplish the tasks normally associated with trigonometry without needing the concept of an angle (or really anything from calculus or analysis).
If you look at the things that students have trouble with, it's usually the curriculum's fault for not explaining things in a reasonable logical order.
One of the things many people have trouble with in highschool is the whole issue surrounding the logarithm and exponentiation with a positive real exponent. The reason why they struggle is that these things get defined circularly. Nobody ever really tells you what the expression 2^(sqrt(2)) or 5^pi is supposed to represent. You need to know things about limits and convergence of series in order to define a^b where a is real, and b > 0 is real.
I was lucky, and found things to read on my own which described enough of mathematics to me to get me interested, and then went to university for pure mathematics.
The reason why mathematics should be taught in highschool is that people should gain some concept of logic, which is useful no matter where you're headed, and by proving propositions and theorems, one eventually gains an incredible grasp of logic. This isn't currently done though.
Mathematics is basically presented as an awful illogical mess where at best, the students are taught to solve some very specific problems in a mechanical, unthinking fashion, and at worst, their self-esteem is damaged and they come away thinking that they are bad at something which they've never been exposed to. I've seen some very bright people who thought that they were terrible at math, and for this reason avoided going into fields of study that they'd otherwise have been interested in.
I hope we can eventually do something about this because, as a student of mathematics, I can say that the present state of affairs at the elementary and highschool level is terrible, and while I can easily see ways in which it could be made better, actually carrying it out is another thing altogether.