last day (15 days later) » 

01:08
-7
Q: What should I do to speed up this code to find values for a, b, c, d that satisfy the following equation (a^4 + b^4 + c^4 = d^4)?

Youssef AshrafI wrote this code to find the variables that will satisfy the diophantine equation a^4 + b^4 + c^4 = d^4, for all variables belong to: (0 , 430000), and it takes forever to find the answer (I left the code running for two hours and got nothing). I know that this is caused by the algorithm or the ...

Looks like a typo in the ctor. You don't use c or d.
Beware that comparing double by equality will sometimes fail unexpectedly.
You will need a Minimal, Complete, and Verifiable example. Provided there is no bugs, you will also at least need to include your system specs, compiler flags etc
You never seem to initialize a, b, c, d, e, j, k or l.
Given the inherent inaccuracies in base 2^n floating point numbers I'd say you'll be extremely lucky to ever get an answer. You've also got a nasty little array bounds problem in the constructor.
01:08
@FrançoisAndrieux Not in this case; they’re all generated the same way and should have exactly the same values. The addition won’t work, though; at 430000⁴ a double is a lot less precise than an integer (and even uint64_t can’t store these values correctly; you need to go up to unsigned __int128 if your compiler supports it, and do the exponentiation yourself).
@BobJarvis All the actual values constructed by this method will, in fact, be exact integers. Not necessarily the correct integers because some of them will go beyond when doubles have integer precision, but I’d expect that to make it more likely to get an answer even if it isn’t correct, in this case.
Given that direct computer search failed, what makes you think you can succeed with your search? Based on your paper, it looks like the smallest solution is much bigger than your search bounds, and your search bounds are already so big I’d expect you to take a while to exhaust the search space.
You access your arrays beyond their last element which results in undefined behaviour.
May be faster to a*a*a*a than pow(a,4)
Arrays in C++ start at 0, not 1, and you go beyond the bounds of your arrays, causing undefined behavior. So performance is a moot point -- get a program that works properly first, does not cause undefined behavior, but is just slow. Also where is main() and the data to test your code? Post a Minimal, Complete, and Verifiable example.
@BobJarvis Yes, I agree that it won’t produce the desired results. I just think it’s more likely to produce some results because of the truncation, not less; I expect most actual solutions (or something that was rounded from them) and several non-solutions would be found if this program had infinite runtime.
If the code works, consider posting to Code Review for a code inspection.
As with all optimizations, start by profiling your code. Determine where the bottleneck is, then optimization that section.
Try assigning the numeric constants to a variable. This is an optimization, however the compiler may perform this depending on the optimization setting. Check the assembly language listing for the optimized code.
01:08
@PaulMcKenzie yes I'm aware of that, yet I didn't access any [0] of any array that I've made. I don't do anything in main() but creating an object and calling the calcDiophEq().
@YoussefAshraf You access the element 43000 in your arrays which is out of bounds.
You might be interested in a reviewed C variant. Especially the pow remark might be helpful (just write a * a * a * a).
You create the same array 4 times. That seems unnecessary.
@FrançoisAndrieux I don't. I made the if conditions to modify the variable's value whenever it reaches 430000, in other words, it reaches 429999 max.
@JohnnyMopp it is necessary. please read the question again (4 different variables)
−1 If the code works "perfectly fine" it's by accident. Downvote because the code is incomplete and the claims not believable. Note: pow does not usually produce an exact integer power.
01:08
@Zeta would it really make that much of a difference if I didn't use pow? the problem isn't in the constructor anyways, it does initialize the 4 arrays and everything as soon as I run the program...
@Cheersandhth.-Alf can you please specify what is incomplete? and the code actually works...I tried plugging in the correct variables (that I'm looking for) and it indeed gave me an output so...
@YoussefAshraf You do, in the first loop in the constructor which uses count as the iterating variable.
@YoussefAshraf The example is not compilable. Anyone should be able to take a MCVE, put it in a source file, compile and and reproduce the problem. The supplied code is not enough to compile an executable.
@JohnnyMopp yes, thank you. it is a typo but it doesn't make any difference after all :) a = b = c = d
Have you fixed the array bounds error in your constructor? Hint: C++ array indexes start at 0 and go to array-limit minus one; thus, the valid indexes on your arrays are 0 through 429999.
@FrançoisAndrieux ok I'll edit this and re-post the question. thanks for your concern :)
@YoussefAshraf -- yet I didn't access any [0] of any array that I've made -- But you access one beyond the boundaries of your array. Array indices in C++ range from 0 to n-1, where n is the total number of entries.
01:08
@BobJarvis Yes I'm totally aware of that, the thing is I don't access any array[0] in my code, I did this to make it easy for me to read and nothing more, yet I'll fix this and repost the question, thanks! :)
@YoussefAshraf -- did this to make it easy for me to read and nothing more -- But that has its consequences, such as causing buffer overruns, which your code is doing now. Doing things like this invalidates your entire question concerning performance, since you introduced undefined behavior. As to your code "working" -- switch those new[] calls to use std::vector, and you will see that it does not work (it aborts) using a runtime that has bounds checking for containers turned on (such as Visual Studio and g++ using a command-line option).
@PaulMcKenzie Didn't know that...thanks for the tip!
Can you guys please check the updated code? I edited it based on your -1s, please consider undoing it if it now is an "MCVE", and thanks.
@YoussefAshraf count <= 430000; -- You're still wrong in the for loop. In addition, there are still places where you're accessing arrays at index 430000, which is out-of-bounds.
@PaulMcKenzie ok I edited them. does it seem to be fine now?
LHS = arrA[a] + arrB[b] + arrC[c]; and what happens if a, b, c, or d is equal to 430000? Out-of-bounds.
01:08
@PaulMcKenzie that's why I wrote the if conditions ... whenever a or b or c equals 430000, I re-assign them to be equal to 0. and the while loop breaks whenever d reaches that limit.
You add 1 to d making it 430000. What happens when this is executed RHS = arrD[d]; when d is 430000? Better yet, drop the raw arrays and really have your code checked by using vectors.
@PaulMcKenzie ok so I tried vectors as you've advised, and it worked fine really... The thing is a, b, c, or d never actually make it to 430000.
The thing is a, b, c, or d never actually make it to 430000 -- Hopefully you don't say things like this if you get hired for a programmers job. Your code is written to handle up to 430000, and if that happens, then a memory overwrite.
@PaulMcKenzie ok allright fine, the d might get to 430000, I should've made another if condition for it... what I REALLY meant by what I said is that it shouldn't even reach 430000, as that the solution value for d is way below 430000 (422000 or something). I will put that one more if condition, you're right anyways, but this wasn't my concern, you know?

last day (15 days later) »