4 ms·
> 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 trilli
by kats 6y ago
> 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.
- blackbear_ 6y agoAre you missing two zeros or am I counting incorrectly? The paper claims an improvement of 10-36 or smaller
- triclops200 6y agoPercent moves two zeros over factor
- morcheeba 6y agoSo 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.
- jobigoud 6y agoWonder 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.
- bitcharmer 6y agoThis is very interesting. Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?
- morcheeba 6y agoXEONs 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/processors/xeon/2nd-gen-xeon-scalable-datasheet-vol-1.html https://www.intel.com/content/www/us/en/products/docs/proces...
- jquery 6y agoThat’s might be all they were able to prove, although in practice the results may be much better.
- gitgud 6y agoIs 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?
- lamchob 6y agoNo, 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.