Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Galactic Algorithm

en.wikipedia.org

Post reply on HN
Print view View original

61–70 of 74 posts

Re: Galactic Algorithm

#61

Post by lidHanteyk »

cornstalks wrote: post #3

> 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.

Because 1728 is an incredibly surprising number, showing up most prominently at the center of elliptic curves, modular forms, and L-functions: https://en.wikipedia.org/wiki/J-invariant

And 1729 is 1728 + 1. Not even kidding, that is a thing that happens.

Re: Galactic Algorithm

#62

Post by cperciva »

Gehinnn wrote: post #45
cperciva wrote: post #6

In addition to galactic algorithms, there are also galactically proven algorithms. One example is the algorithm for matching with mismatches which I presented in the first chapter of my doctoral thesis; I proved that it was faster than other algorithms for inputs of at least ~10^30 bytes. In practice, it wins starting at around 10^4 bytes.

How do you prove that something is faster than everything else? Was it already running in linear-time? There aren't many non-trivial lower bounds out there, and I think they all use one of three ideas (diagonalization, crossing sequences or oracle reconstruction)!

Sorry, I was unclear. I proved that my algorithm was faster than other known algorithms; I didn't prove that it was faster than all other possible algorithms.

Re: Galactic Algorithm

#64

Post by bkanber »

asdaddasdad wrote: post #27

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.

It's really just a phrase used nearly-rhetorically in order to convey the vast scope of a thing. Everyone understands that the number of atoms in the universe is a huge number, so it's a good benchmark.

When people use this phrase they're not trying to claim that the number of atoms in the universe is directly related to the problem at hand; they're just trying to convey scale.

Re: Galactic Algorithm

#65

Post by laretluval »

asdaddasdad wrote: post #51
lonelappde wrote: post #49

Earlier quoted context omitted.

It's not states, it's logarithmic of states (# of dimensions of finite size) . Think about writing down a number. One atom per digit is a pretty natural heuristic for the optimal spatial cost of information. Yes you can get clever, but there's no point, were already at astronomical levels of imprecision.

As I said, one atom per digit is not really natural. Just two atoms could encode an infinite number of numbers, by measuring their distance. Well except quantum physics might get in the way, not allowing us to measure with arbitrary precision. But that would be another argument. Another argument would perhaps be the energy required to do the computation. Maybe that relates more directly to the number of atoms in the…

> Well except quantum physics might get in the way,

This is a pretty huge well except. When people talk about information that can be stored in the universe this is exactly the limitation they have in mind.

Re: Galactic Algorithm

#66

Post by nabdab »

angel_j wrote: post #59

If all that is required is a super large constant (as in some cases), why not assume the large constant, do the calculation, then factor out the large constant?

Because the “faster” algorithm is faster than the “slow” algorithm in the range where this constant is added... but not faster than just applying the “slow” algorithm directly. So the only thing you would achieve is to slow down the calculation overall.

Re: Galactic Algorithm

#67

Post by asdaddasdad »

marzell wrote: post #58
asdaddasdad wrote: post #27

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.

How would you read that? (Distance between two distinct atoms) doesn't seem practical

Doing computations with single atoms also doesn't sound very practical.

Measuring distances, I suppose there could be numerous ways, like measuring the gravity or electric pull (not sure what it is called in English). I think only Quantum theory says we can not measure to arbitrary precision, or at least if we do, there are other issue. Still, that would be another argument than simply pointing at the number of atoms.

Re: Galactic Algorithm

#68

Post by asdaddasdad »

platz wrote: post #55
asdaddasdad wrote: post #53

Earlier quoted context omitted.

What counts as an interaction? It seems to me there can be an infinite number of interactions between just two atoms.

Number of states of the universe is a quantum value, not a classical one.

So what quantum value is it? Shouldn't the argument then at least say "the number is greater than the number of possible states of the universe", or something like that?

Re: Galactic Algorithm

#69

Post by nine_k »

Retric wrote: post #32
asdaddasdad wrote: post #27

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.

It’s 2^1729 digits, (vastly) more digits than there are atoms in the universe. 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 unive…

You forgot about ordering.

8 binary bits in order can encode 256 states, as if every bit was capable of encoding 32 states.

Re: Galactic Algorithm

#70

Post by [deleted] »

nine_k wrote: post #69
Retric wrote: post #32

Earlier quoted context omitted.

It’s 2^1729 digits, (vastly) more digits than there are atoms in the universe. 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 unive…

You forgot about ordering. 8 binary bits in order can encode 256 states, as if every bit was capable of encoding 32 states.

[deleted]
Post reply on HN