7 ms·
>Booker found this odd trio of 16-digit integers by devising a new search algorithm to sift them out of quadrillions of possibilities. The algorithm ran on a un
by AdmiralAsshat 8y ago
>Booker found this odd trio of 16-digit integers by devising a new search algorithm to sift them out of quadrillions of possibilities. The algorithm ran on a university supercomputer for three weeks straight.
So...did he just brute force it?
EDIT: Should've read further down. Looks like, yes:
>But usually, solutions are “nontrivial.” In these cases, the trio of cubed integers — like (114,844,365)³ + (110,902,301)³ + (–142,254,840)³, which equals 26 — looks more like a lottery ticket than anything with predictable structure. For now, the only way for number theorists to discover such solutions is to play the mathematical “lottery” over and over, using the brute force of computer-assisted search to try different combinations of cubed integers, and hope for a “win.”
- MrMember 8y agoYes, but smartly. People have been brute forcing solutions to this problem using computers for decades now. The tricky part is reducing the search space.
- lmkg 8y agoI feel like we need a better name for this type of approach, because many people (myself included) take "brute force" to mean naively checking every solution candidate. If you're doing something clever like reducing the search space and/or lowering the big-O, that doesn't seem "brute." Even if you're throwing dozens of core-years at the problem, that seems like "force" but not "brute." I can't think of anything snappy, though. "Clever brute force" is the best I've got, and it's a mouthful. I tried looking for antonyms for "brute," the options aren't great. Well-bred? Polished? Humanitarian?
- jonsen 8y agoCute force
- iokevins 8y agoGroot force
- StrictDabbler 8y agoCivilised force is accurate but sadly colonial... I think "refined force" is a solid option. Selective works well but might be too literal since "select" is a common algorithm verb. "Judicious force" is my favorite and "prudent force" comes second.
- gibolt 8y agoReduced force
- jhncls 8y agoThe Numberphile video, mentioned elsewhere, explains how a search of O(n^3) is reduced to a linear search via some clever tricks. From there, the linear search is quite brute force. Several numbers are searched at the same time, indicating that no solution for 42 could be found under 10^16. Some supercomputer infrastructure seems to be necessary ("don't try this at home").
- SilasX 8y agoWow, linear? I had recognized this as a variant of the interview problem where you try to find a triple that sums to zero in a list, but that only shrinks it to quadratic. https://www.geeksforgeeks.org/find-triplets-array-whose-sum-equal-zero/ https://www.geeksforgeeks.org/find-triplets-array-whose-sum-...
- ConceptJunkie 8y agoThe paper ends with "The total computation used approximately 23 core-years over one month of real time.", so yes, I think running this on your 8-core desktop is not going to cut it.
- Rychard 8y ago1 core year = 12 core months 23 core years = 276 core months So, 276 cores running for one month? Is this right?
- dragontamer 8y agoBut what about a $400 GPU with 4096 shaders? I haven't looked at the algorithm, but a linear search probably can be GPGPU computed in parallel. A Vega64 is around $400 and runs 16384 threads on 4096 physical shaders at roughly 1.2GHz. The main issue is if whatever data-structures used for this search will actually fit inside the microscopic amount of memory that is available to each shader.
- ars 8y ago> I haven't looked at the algorithm You can see it here: https://youtu.be/ASoz_NuIvP0?t=393 https://youtu.be/ASoz_NuIvP0?t=393 Rewind a couple of minutes if you want the explanation.