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

21–30 of 74 posts

Re: Galactic Algorithm

#21

Post by tripzilch »

nabla9 wrote: post #16
edanm wrote: post #8

Earlier quoted context omitted.

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.

1729 has no special meaning for the multiplication algorithm. In the paper Harvey writes: > In Section 5 we establish (1.3) with the explicit constant K= 1728, and in Section 5.4 we list some optimisations that improve it to K= 8. > In Section 5, we will simply take d:= 1729 (any constant larger than K would do)

This is the curse, there are not enough small(ish) numbers for the enormous number of properties they could have, that we come up with :)

Re: Galactic Algorithm

#22

Post by n4r9 »

tripzilch wrote: post #20
zaroth wrote: post #9

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 full anecdote as told by Hardy is

> I remember once going to see him when he was ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavorable omen. “No,” Ramanujan replied, “it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.

Re: Galactic Algorithm

#23

Post by Sharlin »

alanbernstein wrote: post #17
gmoot wrote: post #7

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

What was shocking about this? Seems like something you could always solve by hand, even if you couldn't quite enumerate the steps you need to take to do it. I guess that's sort of my baseline for whether I expect an algorithm to exist.

In linear time was the key part.

Re: Galactic Algorithm

#25

Post by mfabbri77 »

gmoot wrote: post #7

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

Fast and robust polygon triangulation was the hardest challenge in the period when we developed the OpenGL version of our 2D vector graphics engine (www.amanithvg.com), it was in the early 2000.

I clearly remember all such research papers. After studying all of them and after three complete rewrite of the engine, we finally implemented a classic 2 step algo: sweepline polygon decomposition to monotone polygons, and then monotone polygons to triangles.

We had really heavy headaches dealing with intersections, autointersections, splitting edges, comparing and merging original vertexes with vertexes created by splitting edges, managing edges connectivity and topology.

After some try, we totally discarded the idea to write it in floating point arithmetic, preferring fixed point integers instead (and this was a real turning point for the robustness!).

Anyway, good times to remember!

Re: Galactic Algorithm

#26

Post by BlueGh0st »

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.

The 1729 link has since been removed, likely for the reasons user saagarjha stated -- wrong context.

Re: Galactic Algorithm

#27

Post by asdaddasdad »

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.

Re: Galactic Algorithm

#28

Post by Gunax »

function_seven wrote: post #18
saagarjha wrote: post #13

Earlier quoted context omitted.

You could say so: > As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham's number would itself be a number so large that its digital representation cannot be represent…

> for a number of times far exceeding the total number of Planck volumes in the observable universe. Just so I'm clear. They're saying that not only can I not fit Graham's Number in all the Planck volumes of the universe; and I can't even count the digits of GN and write that in the Planck volume of the universe (and so on), but the number of "indirections" is itself so large as to not fit in the universe? Like: 1. G…

Yes. log(log(log... GN))) applied X times (where X is the number of planck volumes in the universe) is still greater than X.

Where log = base 10 logarithm.

Hofstadter talks a bit about this abstraction in his article 'On Number Numbness'

> If, perchance, you were to start dealing with numbers having millions or billions of digits, the numerals themselves (the colossal strings of digits) would cease to be visualizable, and your perceptual reality would be forced to take another leap upward in abstraction-to the number that counts the digits in the number that counts the digits in the number that counts the objects concerned.

Re: Galactic Algorithm

#29

Post by saagarjha »

BlueGh0st wrote: post #26
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.

The 1729 link has since been removed, likely for the reasons user saagarjha stated -- wrong context.

Interestingly, the change that added it was also quite recent: https://en.wikipedia.org/w/index.php?title=Galactic_algorith...

Re: Galactic Algorithm

#30

Post by _kst_ »

nabla9 wrote: post #16
edanm wrote: post #8

Earlier quoted context omitted.

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.

1729 has no special meaning for the multiplication algorithm. In the paper Harvey writes: > In Section 5 we establish (1.3) with the explicit constant K= 1728, and in Section 5.4 we list some optimisations that improve it to K= 8. > In Section 5, we will simply take d:= 1729 (any constant larger than K would do)

So 1729 is the 42 of 4-digit numbers.
Post reply on HN