6 ms·
The 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
by jhncls 8y ago
The 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.
- dragontamer 8y agoThat's actually really simple and clever. That definitely makes the search space much smaller and brute-force is now possible.
- Jweb_Guru 8y agoYou should probably assume that people using supercomputers have thought about "just using a GPU."
- xiphias2 8y agoDon't assume anything. They are not using GPUs and from the paper it looks like they haven't thought about it. I think a GPU cluster would be a speedup, but big number multiplication is relatively slow on GPUs, so maybe not as big speedup as with other algorithms.
- Jweb_Guru 8y agoA GPU cluster, sure. But the discussion was about running the algorithm on a single GPU on your desktop.
- xiphias2 8y agoSure, you're right I was comparing cost of the 2 systems, with 1 GPU it's an interesting question, but as the author had CPU cluster available, it was the logical choice for him.
- dragontamer 8y agoWhy? GPU Programmers cost a lot more than a month-worth of supercomputer time. Its probably cheaper and easier to just port your code to Amazon cloud or Google Cloud for a month, rather than to port your code to a GPU.
- deleted 8y ago[deleted]
- waynecochran 8y agoYes, but I am left hanging on the specific details. He factors to yield (x + y)(x^2 - xy + x^2) = 42 - z^3 He brute force searches over values d and finds a value z such that d divides 42 - z^3 (evidently these are rare and easy to find) and then solves the following two equations for x and y (which is easy): d = x + y x^2 - xy + x^2 = (42 - z^3)/d The part I don't get is how to find the z's given d. Does anyone know where to find these details?
- deleted 8y ago[deleted]