31–40 of 74 posts
Ah. I still remember my computational geometry professor telling us about an algorithm to do triangulation (composing a polygon into triangles) in linear time: "It's very complex. I don't think anyone has actually implemented it". It shocked me at the time that there were algorithms like this. https://en.wikipedia.org/wiki/Polygon_triangulation#Computat...
I've never understood the "number of the atoms in the universe" argument. The number of states the universe can be in doesn't seem to be equal to the number of atoms. For example, just two atoms could encode lots of numbers simply by using their distance. Quantum physics would affect it, but I mean in principle: we are not switching atoms on and off to encode state.
The vastly bit is kind of an understatement.
Each stable isotope is indistinguishable from every other carbon isotope. So, you can probably encode a few bits per atom assuming you can somehow read this data. However they are talking vastly larger numbers of digits here. Where there are only ~10^80 digits worth of atoms in the visible universe, but hey bump that to 10^90 it does not help.
Sure you might encode 10^6 or hell I will give you 10^100 bits of data per atom or something but that’s not even close to helpful. It’s still on the order of K atoms in the universe and you want to encode 10^400+ * K bits of data. So each atom needs to encode 10^400+ bits and remember each stable isotope is indistinguishable from every other atom of that stable isotope.
I've never understood the "number of the atoms in the universe" argument. The number of states the universe can be in doesn't seem to be equal to the number of atoms. For example, just two atoms could encode lots of numbers simply by using their distance. Quantum physics would affect it, but I mean in principle: we are not switching atoms on and off to encode state.
Earlier quoted context omitted.
“But it’s not dull at all,” Ramanujan replies, “it’s actually the first number that can be written as the sum of two cubes, two different ways!”
But imagine he had said, "it's the number of dimensions your Fourier transform needs for the fastest way to multiply two numbers" :) BTW who things the other person was really just baiting Ramanujan to say something like this?
The real question is, did he know of this fact already or did he come up with it on the spot after hearing what Hardy said?
> 1729 Why is this hyperlinked? I was hoping the link would help explain why 1729 and not some other number, but it’s just trivia... > One immediate practical effect would be to earn the discoverer a million dollar prize from the Clay Mathematics Institute. I mean, I can’t argue with the practicality of that.
I also wonder why that number. But as others said, it's a pretty famous number all by itself so it makes sense for there to be some notice paid to that- if there were no hyperlink I would've thought it's weird and maybe someone made a mistake.
Ah. I still remember my computational geometry professor telling us about an algorithm to do triangulation (composing a polygon into triangles) in linear time: "It's very complex. I don't think anyone has actually implemented it". It shocked me at the time that there were algorithms like this. https://en.wikipedia.org/wiki/Polygon_triangulation#Computat...
They mention O(n log* n) being quasi linear time, I had to look up log * n because I never saw this before.
In practical algorithms, one does not ignore constants, one takes into account actual hardware (particularly cache effects), and one does not ignore real world distributions of inputs.
https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
If and when practical quantum computers are built Peter’s algorithm will be one of the first algorithms run on them. Right now it is a galactic algorithm. But, perhaps it is the best example of the importance of galactic algorithms."
However, its runtime is only guaranteed to be in polytime, if someone guarantees that P = NP.