Hacker News Reader

Comment by kats | Hacker News Reader

> proved that an algorithm devised a decade ago beats Christofides’ 50% factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.

That is 0.0000000000000000000000000000000002% better than the existing solution.

View on HN

So much less than the 0.01% of the variation in identical computers due to 100ppm crystal variation. Also less than the 0.0001% variation due to the temperature in the room changing 1 degree.

Wonder if it's less than the probability of getting hit by a cosmic ray flipping a bit somewhere in the implementation and changing the result.

This is very interesting.

Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?

XEONs use a 100MHz referenced called "BCLK" and scale this up to the different frequencies it needs internally (core, dram, pci, etc.). Typically this info is found in the datasheet, but only the DC parameters (voltage min/max) etc were found in the first datasheet I found. Timing is so important that often processor manufacturers will have an apnote discussing it in detail, often with suggested parts and circuit layouts.

https://www.intel.com/content/www/us/en/products/docs/proces...

That’s might be all they were able to prove, although in practice the results may be much better.

Are you missing two zeros or am I counting incorrectly? The paper claims an improvement of 10-36 or smaller

Percent moves two zeros over factor

Is it a probabilistic improvement, like over millions of iterations?

It does mention choosing tree paths at random... so couldn't that be an improvement by chance?

No, they don't just random sample the base trees and hope for a better result. Their "actual work" is providing a 80 page proof for their improvement.

Reply on news.ycombinator.com