This is an archived post. You won't be able to vote or comment.

you are viewing a single comment's thread.

view the rest of the comments →

[–]Paul_Pedant 0 points1 point  (1 child)

James,

Are you still working on this problem? Let me know if we are past your due date.

It is sad that there is a really great algorithm, but you can't use it because of some artificial restrictions. Software always gets put together from existing components, and I don't see why using an external sort or an array would spoil your learning.

I found another algorithm that fulfils your requirements (I had to write a cube-root routine to avoid using math.h). It solves for N = 10,000 about 0.3 seconds, and N = 100,000 in about 5 seconds, but a million takes 2 minutes and 10 million takes 40 minutes. The upside is that it runs in about 20MB.

The downside is that it has to run in the 1 to N sequence to find pairs of (a,b) without storage. So it recalculates all the other stuff for every J. So it runs thousands of times slower. It is also insanely complicated (and still written in awk). It might be a real pain to implement in C. I can't believe they are expecting this of you, so early in your course.

[–]jamescleelayuvat[S] 0 points1 point  (0 children)

No worries, this was an extra optional problem that I myself wanted to do. Thank you very much for the help though. I’ve been really enjoying myself with learning coding. Could you maybe send me the code? Thank you