One possible approach would be to use Karatsuba or Toom-Cook at the top level to break the product into several smaller products for which floating-point FFT is accurate. IIRC this was used for the trillion-digit pi calculation by Kanada. If a GPU could multiply, say, 1 million bits accurately, a 60 million bit product could be broken into ~ 60^1.6 = 700 "single digit" products. This might be faster than the CPU FFT if the GPU FFT were, say, 10x faster.
The Lucas-Lehmer test for Mersenne primes consists of repeated multiplication (modulo a fixed large number). Large-integer multiplication is done via floating-point FFT, which is nothing but massive amounts of operations on small numbers. I don't know how FFT implementations for GPUs compare, but intuitively I think they ought to be at least as fast as for CPUs. The primes tested by GIMPS are small enough to fit entirely in GPU memory, so latency doesn't seem like a problem.
(I don't really know much about any of this, so feel free to correct/enlighten me.)
I stared at your post for 10 seconds before realizing that 2j was supposed to represent an integer and that you were in fact not calling upon the quater-imaginary numeral system to prove the evenness of zero. Now that would have been overkill:-)
The license plate issue, by the way, is actually discussed in the "evenness of zero" Wikipedia article:
The nominal evenness of zero is relevant to odd-even rationing systems. Cars might be allowed to drive or to purchase gasoline on alternate days, according to the parity of the last digit in their license plates. Half of the numbers in a given range end in 0, 2, 4, 6, 8 and the other half in 1, 3, 5, 7, 9, so it makes sense to include 0 with the other even numbers. The relevant legislation sometimes stipulates that zero is even to avoid confusion.[25] In fact, an odd-even restriction on driving in 1977 Paris did lead to confusion when the rules were unclear. On an odd-only day, the police avoided fining drivers whose plates ended in 0, because they did not know whether 0 was even.[26]
...but you missed my first point: the real constituent particles are the quarks and gluons which as far as we know have no size.
As I said in another comment, what's relevant is how these constituent particles form structures. It is meaningless to speak of the radius of a quark (with current knowledge), but it makes sense to speak of the (statistical average) distance between two quarks within a nucleus.
sure, quarks and neutrinos are a few billion times smaller than the nucleus.
As far as anyone knows (aside from pure speculation) quarks and neutrinos are point particles with no internal structure. When they do get together, they form structures of the magnitude of a nucleus. The term "structure" is important, because the suggestion made by the article summary is that structures on this scale, which by definition would have comprise multiple particles, could be created. That is going to be hard if no physical mechanisms are known that could form such structures.
Secondly, if you regard the nucleus as made up of protons and neutrons, the radius is still not the same as that of a proton. The liquid drop model of the nucleus shows how you can roughly treat the nucleus as a drop of liquid with a constant density and so the radius of the nucleus is proportional to the cube root of the number of protons and neutrons (the mass).
That's why I said "about the size", not "exactly the size". The relevant information is the order of magnitude; a proton has a radius of roughly 1 fm and nuclei have radii in the range of a few fm (depending on the mass number).
The size of the atomic nucleus, not 100,000 times smaller. One femtometer is roughly the radius of one atomic nucleus. And unlike the atom as a whole, the nucleus is very compact, about the size of its constituent particles. I don't think any kind of structure 100,000 times smaller than a nucleus has been detected experimentally.
In theory, waste can be used as projectiles for a mass driver. Ejecting the waste backwards at high velocity would simultaneously accelerate the station (to help maintain orbit) and decelerate the waste (causing it to fall back to Earth). In practice, this is probably rather inefficient.
Soon we will be able to test 2^N possibilities in 2N time, but my question is where does that information come from? There's a lot of hand-wavyness on how that actually happens...
Phenomena like superposition and entanglement are not fully understood from the metaphysical point of view, and there is some hand-waving about that. But the mathematics agrees perfectly with experiment, and that's all we need to know to put the theory to use.
One possibility is that we ask the 'computer' of the universe to do too much computation and end up in an infinite loop, crashed universe, 'dark' part of a mandlebrot-like fractal, etc.
Another possibility is that the 'computer' of the universe will simply abort operations that take 'too long', the quality of our simulation will degrade, and our complex quantum math will result in randomish results.
How do we know building a quantum computer won't break the universe? Well, the things that go on in a quantum computer are the same things that go on in ordinary matter all the time. A speck of dust consists of some 10^20 particles that continually interact with each other according to the same quantum-mechanical laws that govern the interaction of qubits used in integer factorization. Why should the universe care what purpose we use those interactions for?
And in the end, a size/time-N quantum computation can be simulated with 2^N space and in 2^N time on a classical computer (I might be wrong about the exact form of those expressions). Would the universe collapse if we run a quantum algorithm on a PC?
And then there is the possibility held by quantum researchers that somehow the universe can magically perform any amount of complex computation with no cost at all.
This isn't true. Quantum algorithms have real costs that grow with the size of the problem, just like on ordinary computers. (Concretely speaking, we can simulate them on classical computers in deterministic time.)
As others have said, Sage glues together existing high-quality software. Asking why William Stein opted to start a new project instead of contributing to established projects is a bit like asking why Mark Shuttleworth started Ubuntu instead of contributing to Linux.
My favorite Data disaster horror story is 6x08 - A Fistful of Datas.
Re:Why I don't trust Python
on
Open Source Math
·
· Score: 2, Informative
cripple itself with IEEE-754 standards needlessly
The IEEE 754 standard is very well designed and ensures floating-point arithmetic to be accurate, efficient, and compatible across platforms.
But it does mean that when there is a precise answer and it is calculatable (I think the former demands the latter), that I do minimally want Python to store it fully in memory and to not print out questionable and/or incorrect answers.
So you'd be happy if Python generates an exact answer when you ask it to compute 1 + 1e-100000 and it allocates several kilobytes of memory to represent the result? Would you still be happy with this behavior if you are doing a numerical computation involving a million numbers? Exact rational arithmetic is, in general, much slower than floating-point arithmetic, and the cost grows the more operations you perform.
But in a mathematician's/user's eyes, software should "just work".
In a perfect world, it would. Numbers, interestingly, are one of the hardest things to get to "just work". As simple as numbers are as a concept (or are they?), computer arithmetic involves very sharp tradeoffs between speed, precision, simplicity, predictability, compatibility, and other factors. Python's float type was chosen for speed, simplicity (of implementation) and compatibility (with C software). If these are your requirements, Python float arithmetic does "just work". If you expect to get all features at once, you are expecting much.
I'm not saying Python's solution is the best possible, but it is one solution. Most computer algebra systems have more sophisticated number systems, but they still have limits and sometimes don't "just work" as expected. The solution is education; until we get perfect AI, anyone who programs a computer for scientific work must be aware that a computer does what you tell it to do, not what you think you tell it to do.
But what is important according to this article is whether the AVERAGE math or physics grad, without a CS background, is going to know that.
You seem to be saying that the problem is that users of mathematicial software aren't smart enough to look up what a function does before using it. I've read the article, and I find nothing to support this interpretation. What it says is that users of closed-source mathematical software can't look up what a function does since the source code is not available.
Try using PHP to calculate the distance between 2 geographical points across the country... oh, wait a minute, you can't! Why? Because the number gets really big, then really small, then really big, etc. You're left with a number that has lost all of its floating point precision... thus being wrong!
This is an elementary property of floating-point arithmetic. The problem happens because you use the wrong tool to solve the problem. If you need exact arithmetic, you should use exact arithmetic, not floating-point arithmetic, or if you're happy with high finite precision, you should rewrite your algorithm so that it doesn't suffer from cancellation.
It's like referring to theorems that don't apply in the present situation to prove a theorem. If you say "the sum x1 + x2 +... + x3 is y because I added up the numbers with floating-point arithmetic", and the value is wrong due to cancellation, that's like saying "the Riemann hypothesis is true because so-and-so, and then f(z) = C according to theorem T" where your proof assumes that z can be any complex number while T was only proved for the case when z is nonzero.
A mathematician who does this is simply a careless mathematician and his errors will usually be caught in peer review. A mathematician who does this a lot without being able to notice his own errors didn't earn his degree.
Wait a minute, are you saying that the right formula gives the wrong results? YES!!
How do mathematicians know that they can trust the results of formulas they put into software? The answer: They can't.
No, the problem is that you used the wrong formula. The formula 1 - 0.01 in Python does not mean the same as it does on paper. There is no "failure" here other than a failure to read the Python documentation to learn the semantics of its number literals and arithmetic operators.
2.999999999... == 1, so the answer is still correct. This is only by accident. The precise value in this case is 0.9899999999999999911182158029987476766109466552734375. Another time, the printed result will be something like 0.98999999999999966.
Re:Why I don't trust Python
on
Open Source Math
·
· Score: 4, Informative
Python calculated exactly what its documentation says it will do: ((1 minus the IEEE-754 double closest to 1/100) rounded to the nearest IEEE-754 double). It's not Python's fault if you don't know the basics of floating-point arithmetic. Mathematicians who use or write numerical software do.
Slashdot Mirror
Ah, the heat from the lamps causes the air to rise, providing upward suction on the wings. Brilliant!
I did work on another project, Plutonia 2, that was released a few months ago. My first contribution was in mid-2001, IIRC, which makes 7.5 years.
In fact, I did join the Mordeth team a couple of years ago, but quit...
The Doom mod Mordeth has been in development for over 12 years.
Should they need a new quantum number, irony would make a nice flavor.
Yes, that clears it up, thanks!
One possible approach would be to use Karatsuba or Toom-Cook at the top level to break the product into several smaller products for which floating-point FFT is accurate. IIRC this was used for the trillion-digit pi calculation by Kanada. If a GPU could multiply, say, 1 million bits accurately, a 60 million bit product could be broken into ~ 60^1.6 = 700 "single digit" products. This might be faster than the CPU FFT if the GPU FFT were, say, 10x faster.
The Lucas-Lehmer test for Mersenne primes consists of repeated multiplication (modulo a fixed large number). Large-integer multiplication is done via floating-point FFT, which is nothing but massive amounts of operations on small numbers. I don't know how FFT implementations for GPUs compare, but intuitively I think they ought to be at least as fast as for CPUs. The primes tested by GIMPS are small enough to fit entirely in GPU memory, so latency doesn't seem like a problem.
(I don't really know much about any of this, so feel free to correct/enlighten me.)
I stared at your post for 10 seconds before realizing that 2j was supposed to represent an integer and that you were in fact not calling upon the quater-imaginary numeral system to prove the evenness of zero. Now that would have been overkill :-)
The license plate issue, by the way, is actually discussed in the "evenness of zero" Wikipedia article:
...but you missed my first point: the real constituent particles are the quarks and gluons which as far as we know have no size.
As I said in another comment, what's relevant is how these constituent particles form structures. It is meaningless to speak of the radius of a quark (with current knowledge), but it makes sense to speak of the (statistical average) distance between two quarks within a nucleus.
sure, quarks and neutrinos are a few billion times smaller than the nucleus.
As far as anyone knows (aside from pure speculation) quarks and neutrinos are point particles with no internal structure. When they do get together, they form structures of the magnitude of a nucleus. The term "structure" is important, because the suggestion made by the article summary is that structures on this scale, which by definition would have comprise multiple particles, could be created. That is going to be hard if no physical mechanisms are known that could form such structures.
Secondly, if you regard the nucleus as made up of protons and neutrons, the radius is still not the same as that of a proton. The liquid drop model of the nucleus shows how you can roughly treat the nucleus as a drop of liquid with a constant density and so the radius of the nucleus is proportional to the cube root of the number of protons and neutrons (the mass).
That's why I said "about the size", not "exactly the size". The relevant information is the order of magnitude; a proton has a radius of roughly 1 fm and nuclei have radii in the range of a few fm (depending on the mass number).
The size of the atomic nucleus, not 100,000 times smaller. One femtometer is roughly the radius of one atomic nucleus. And unlike the atom as a whole, the nucleus is very compact, about the size of its constituent particles. I don't think any kind of structure 100,000 times smaller than a nucleus has been detected experimentally.
Unless the bacteria eat gravity.
In theory, waste can be used as projectiles for a mass driver. Ejecting the waste backwards at high velocity would simultaneously accelerate the station (to help maintain orbit) and decelerate the waste (causing it to fall back to Earth). In practice, this is probably rather inefficient.
The main argument is that proofs are "not encyclopedic".
Soon we will be able to test 2^N possibilities in 2N time, but my question is where does that information come from? There's a lot of hand-wavyness on how that actually happens...
Phenomena like superposition and entanglement are not fully understood from the metaphysical point of view, and there is some hand-waving about that. But the mathematics agrees perfectly with experiment, and that's all we need to know to put the theory to use.
One possibility is that we ask the 'computer' of the universe to do too much computation and end up in an infinite loop, crashed universe, 'dark' part of a mandlebrot-like fractal, etc.
Another possibility is that the 'computer' of the universe will simply abort operations that take 'too long', the quality of our simulation will degrade, and our complex quantum math will result in randomish results.
How do we know building a quantum computer won't break the universe? Well, the things that go on in a quantum computer are the same things that go on in ordinary matter all the time. A speck of dust consists of some 10^20 particles that continually interact with each other according to the same quantum-mechanical laws that govern the interaction of qubits used in integer factorization. Why should the universe care what purpose we use those interactions for?
And in the end, a size/time-N quantum computation can be simulated with 2^N space and in 2^N time on a classical computer (I might be wrong about the exact form of those expressions). Would the universe collapse if we run a quantum algorithm on a PC?
And then there is the possibility held by quantum researchers that somehow the universe can magically perform any amount of complex computation with no cost at all.
This isn't true. Quantum algorithms have real costs that grow with the size of the problem, just like on ordinary computers. (Concretely speaking, we can simulate them on classical computers in deterministic time.)
As others have said, Sage glues together existing high-quality software. Asking why William Stein opted to start a new project instead of contributing to established projects is a bit like asking why Mark Shuttleworth started Ubuntu instead of contributing to Linux.
My favorite Data disaster horror story is 6x08 - A Fistful of Datas.
cripple itself with IEEE-754 standards needlessly
The IEEE 754 standard is very well designed and ensures floating-point arithmetic to be accurate, efficient, and compatible across platforms.
But it does mean that when there is a precise answer and it is calculatable (I think the former demands the latter), that I do minimally want Python to store it fully in memory and to not print out questionable and/or incorrect answers.
So you'd be happy if Python generates an exact answer when you ask it to compute 1 + 1e-100000 and it allocates several kilobytes of memory to represent the result? Would you still be happy with this behavior if you are doing a numerical computation involving a million numbers? Exact rational arithmetic is, in general, much slower than floating-point arithmetic, and the cost grows the more operations you perform.
Thank you, I'm glad we agree.
Pleasant to argue with you.
But in a mathematician's/user's eyes, software should "just work".
In a perfect world, it would. Numbers, interestingly, are one of the hardest things to get to "just work". As simple as numbers are as a concept (or are they?), computer arithmetic involves very sharp tradeoffs between speed, precision, simplicity, predictability, compatibility, and other factors. Python's float type was chosen for speed, simplicity (of implementation) and compatibility (with C software). If these are your requirements, Python float arithmetic does "just work". If you expect to get all features at once, you are expecting much.
I'm not saying Python's solution is the best possible, but it is one solution. Most computer algebra systems have more sophisticated number systems, but they still have limits and sometimes don't "just work" as expected. The solution is education; until we get perfect AI, anyone who programs a computer for scientific work must be aware that a computer does what you tell it to do, not what you think you tell it to do.
But what is important according to this article is whether the AVERAGE math or physics grad, without a CS background, is going to know that.
... + x3 is y because I added up the numbers with floating-point arithmetic", and the value is wrong due to cancellation, that's like saying "the Riemann hypothesis is true because so-and-so, and then f(z) = C according to theorem T" where your proof assumes that z can be any complex number while T was only proved for the case when z is nonzero.
You seem to be saying that the problem is that users of mathematicial software aren't smart enough to look up what a function does before using it. I've read the article, and I find nothing to support this interpretation. What it says is that users of closed-source mathematical software can't look up what a function does since the source code is not available.
Try using PHP to calculate the distance between 2 geographical points across the country... oh, wait a minute, you can't! Why? Because the number gets really big, then really small, then really big, etc. You're left with a number that has lost all of its floating point precision... thus being wrong!
This is an elementary property of floating-point arithmetic. The problem happens because you use the wrong tool to solve the problem. If you need exact arithmetic, you should use exact arithmetic, not floating-point arithmetic, or if you're happy with high finite precision, you should rewrite your algorithm so that it doesn't suffer from cancellation.
It's like referring to theorems that don't apply in the present situation to prove a theorem. If you say "the sum x1 + x2 +
A mathematician who does this is simply a careless mathematician and his errors will usually be caught in peer review. A mathematician who does this a lot without being able to notice his own errors didn't earn his degree.
Wait a minute, are you saying that the right formula gives the wrong results? YES!!
How do mathematicians know that they can trust the results of formulas they put into software? The answer: They can't.
No, the problem is that you used the wrong formula. The formula 1 - 0.01 in Python does not mean the same as it does on paper. There is no "failure" here other than a failure to read the Python documentation to learn the semantics of its number literals and arithmetic operators.
Another time, the printed result will be something like 0.98999999999999966.
To clarify, the result may be different if some other sequence of operations is performed. Floating-point rounding is of course deterministic.
Python calculated exactly what its documentation says it will do: ((1 minus the IEEE-754 double closest to 1/100) rounded to the nearest IEEE-754 double). It's not Python's fault if you don't know the basics of floating-point arithmetic. Mathematicians who use or write numerical software do.
I recommend reading What Every Computer Scientist Should Know About Floating-Point Arithmetic.
Hah, this won't hold a candle to GhostBusters DooM2!
Yes, let's call it lawpoop's law. That sounds really good.