Timeline for Disproving Euler proposition by brute force in C
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 2, 2016 at 12:21 | comment | added | jwg |
@5gon12eder I doubt that sqrt uses binary search internally. There are quicker ways of finding square roots which are optimized for this specific problem.
|
|
| Oct 28, 2016 at 14:03 | comment | added | Deduplicator | \$c < d < c * \sqrt[4]3\$ | |
| Oct 27, 2016 at 15:51 | comment | added | Mark K Cowan |
One could also create a look-up-table for pow4, possibly using 128-bit integers (x86 64x64bit multiply produces a 128bit result across two registers, right? combine with the ADD/ADC pattern for adding in the loop)
|
|
| Oct 26, 2016 at 10:45 | comment | added | Martin Bonner supports Monica | Final comment: given a value of x, and x⁴, (x+1)⁴ == x⁴ + 4x³ + 6x² + 4x + 1 (and the lower powers can be calculated incrementally in the same way). That would avoid any bignum multiplications - it all becomes bignum addition and bignum × scalar. However, I suspect it would make filtering (as sugggested by mascoj) difficult - (which feels like it would be an even bigger win). | |
| Oct 26, 2016 at 10:38 | comment | added | Martin Bonner supports Monica |
Another comment: It's probably worth storing a4 == pow4(a) and a4b4 == a4 + pow4(b). Still need to make O(n³) calls to pow4 for c and d but it still saves approximately half the calls.
|
|
| Oct 26, 2016 at 10:35 | comment | added | Martin Bonner supports Monica |
Rather than binary search for a d whose fourth power is equal to the sum of a⁴+b⁴+c⁴ in general, it might be worth remember the value of d that was just larger than the sum (call it dlast), then the next time round the loop for c check if this is now equal to the sum (win!), still greater (leave it alone), or now less than the sum (in which case increment by one and try again). That should require only one or two tries in the inner loop (rather than O(log(n)))
|
|
| Oct 26, 2016 at 0:12 | comment | added | 5gon12eder |
A sqrt implementation likely uses binary search internally so doing two sqrts instead of one binary search probably won't be a win.
|
|
| Oct 25, 2016 at 20:56 | history | edited | Eric Lippert | CC BY-SA 3.0 |
added 173 characters in body
|
| Oct 25, 2016 at 20:35 | comment | added | Aidenhjj | Yes sorry that's what I meant. | |
| Oct 25, 2016 at 20:22 | comment | added | Ben Voigt |
@Aidenhjj: Eric isn't suggesting sqrt(sqrt(pow(pow(x, 2), 2))) but pow(pow(sqrt(sqrt(x)), 2), 2). The order is extremely important.
|
|
| Oct 25, 2016 at 19:14 | vote | accept | Aidenhjj | ||
| Oct 25, 2016 at 21:59 | |||||
| Oct 25, 2016 at 19:14 | comment | added | Aidenhjj |
Which would be faster? A binary search or the sqrt(sqrt(pow(pow(x, 2), 2))) that you suggest first? I suppose the answer is for me to implement both and see. Great answer. Thanks man.
|
|
| Oct 25, 2016 at 18:13 | history | answered | Eric Lippert | CC BY-SA 3.0 |