A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 4 years ago

Can anyone help me find a way to write this program more efficiently? The algorithm I have works, but it doesn't work for the integer bound of 2^31-1. (I reach the CPU limit) It consumes a positive integer x and produces the minimal number of squares required to write x as a sum of squares (i.e., it produces a number between 1 and 4). To access the (up to) four numbers whose squares sum to x, after calling sumofquares(x) you use getsquare which consumes an integer i and returns the ith number whose square is summed in the sum of squares.

  • This Question is Closed
  1. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Since it's only a positive int, you could make it unsigned to extend the range to 2^32. If that's not enough, long long will give you 64 bits of room. If you need more than that, you'll have to either write some code to work with large numbers or use an existing library for arbitrary precision math such as the GMP ( http://en.wikipedia.org/wiki/GNU_Multi-Precision_Library).

  2. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    // Implementation of sumofsquares.h #include <stdio.h> #include <limits.h> #include "sumofsquares.h" // Function isqrt(n) consumes a positive int n and produces // and int x such that x*x<=n and (x+1)*(x+1)>n // Implementation uses a simple Newton iteration int isqrt (int n){ int x=n+1,y; if (n==1) return 1; else if (n==0) return 0; else if (n<0) return -1; else if (n==INT_MAX) return 46340; for (y=1; y*y<=n && (y<= (1<<15)); y=2*y); while (y<x) { x = y; y = (y+n/y)/2; } return x; } /* sumofsquares(int x) consumes x and produces the minimum number m such that x can be written as as sum of squares of m integers. */ int a1 = 0; int a2 = 0; int a3 = 0; int a4 = 0; int sumofsquares(int x) { int sqrtx = isqrt(x); for (a1 = 0; a1 <= sqrtx; a1++) { for (a2 = 0; a2 <= sqrtx; a2++) { for (a3 = 0; a3 <= sqrtx; a3++) { a4=isqrt(x-a1*a1-a2*a2-a3*a3); if (a1*a1+a2*a2+a3*a3+a4*a4 == x) { if(a3 == 0) return 1; if(a2 == 0) return 2; if(a1 == 0) return 3; else return 4; } } } } return 0; } /* Precondition: Assume sumofsquares(x) has been called and returned m so that x = a1^2+...+am^2 The function getsquare consumes i and produces ai in the above list */ int getsquare(int i) { if(i == 1) return a1; if(i == 2) return a2; if(i == 3) return a3; else return a4; } int main(void){ int number; printf("Enter a positve integer:\n"); while (1 == scanf("%d",&number)) { printf("Sum of squares for %d has %d numbers\n", number, sumofsquares(number)); printf("which are %d %d %d %d\n", getsquare(1), getsquare(2), getsquare(3), getsquare(4)); } return 0; }

  3. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the other code had some problems with it when I was trying to up effieciency. I need this to work for ints 2^31 -1 without long or longlong or unsigning it. The real problem is that at large ints the program reaches the availible CPU limit. This is because the algorthm is O(n^3) right now I think.

  4. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I included the main function which I use to test it

  5. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Oh, you're looking for optimization? Let me take a peek. There are lots of small optimizations you could perform, but you're right to look at algorithmic complexity first.

  6. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah, no matter what I do I can't figure out how to do it without the nested loops

  7. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and I haven't done a whole lot with C yet so I don't know how to use arrays. I just started learning about pointers and structs. I only know Scheme before I started learning C

  8. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    There used to be another loop for a4, but I got rid of it with the isqrt which I think makes it faster.

  9. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah, so right now you're running at the maximum sqrt(2^31-1)^3, so is roughly 9.9*10^13 iterations, which is pretty massive. Removing one of the loops is definitely the right thing to do in this case. The call to isqrt does n iterations with a division in them, but in this case the n is dependent on the loop variables which are linearly increasing, so the isqrt runtime in that loop will have a runtime of something like O(log n) but that's just a guess. The first question would be, can you remove another loop in the same fashion?

  10. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I don't see how though, really.

  11. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I tried doing that too. I had something like a1=isqrt(x); a2=isqrt(x-a1*a1); a3=isqrt(x-a1*a1-a2*a2); a4=isqrt(x-a1*a1-a2*a2-a3*a3); then checked to see if it added up to the right number. The problem is it doesn't always produce the minimum amount of squares. for example it would say that 310 is 17 4 2 1 while a smaller one is 2 9 15

  12. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    this way basically goes from the biggest square that fits in the number. But that's not always the one you need.

  13. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah, you don't have any information a priori about which numbers will fit the condition. There may be a specific algorithm for precisely this problem, but I'm not familiar with one off the top of my head. If you can't reduce algorithmic complexity any further, you could reduce the computational load in the inner loop. For example, you could replace a1*a1 with a variable a1Sqr you calculate only inside of the first loop. Do the same for a2*a2, and you'll have saved several trillion multiplications already.

  14. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah there was a complicated algorithm with prime decomposition I found online, but I couldn't make sense of it. removing the multiplications seems like a good idea

  15. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    That's a relatively small optimization though considering there's not much computation going on in the loop. Reducing the number of iterations would be a much safer bet. The overhead of the loops (each of those is a branching instruction) is probably just as large as the actual computation in the loop. You could catch the return 0 case earlier by early exiting: after incrementing a1, check if a1*a1 is already >x. If that's the case, the result of a1*a1+a2*a2+a3*a3+a4*a4 will always be >x, and you'll always return 0 (because the result of the calculation will only get larger with more iterations). The same can be done for the other variables. That only helps you exit early in the case where you won't be able to find a sum of squares, though.

  16. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    well there is apparently some proof that all numbers can be written as the sum of 4 squares so it should always find one and I alread have the condition that a1 <= sqrt(x) so a1*a1 will never be larger

  17. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah, yes. Didn't catch that - that, I think, is the also the key. Because that also means, that for a2 and a3 (and a4, if that loop was still there), you'll never have to search through the entire space. If a1==5, for example, a2*a2+a3*a3+a4*a4 must be <= x-25. So you could reduce the maximum for each nested loop based on the current iterator value of the parent loop.

  18. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think I had that in before, but then it went slower because I was adding additional calculations on each iteration

  19. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but I guess I could do it in the parent loop too

  20. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah, you can do that for a2 and a3. I'm not sure how much it will help, because it's quite possible that you'll reach the exit condition in the inner loop before a2 or a3 come even close to being sqrtx.

  21. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Also make sure you build this with compiler optimizations turned on. There's potentially quite a bit to be gained just from that ;)

  22. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I wish I could, but I don't think I'm allowed. They are really pushing the efficiency thing. The due date has actually already passed for this though. It's hust really frusterating that I couldn't figure it out.

  23. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Don't feel too bad - it's a tricky problem. I'll stew on it a little longer, there's probably a simple solution we're just not seeing.

  24. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    That's what I think too, I've asked a few of my classmates and they couldn't figure it out either. My prof said that it should be pretty easy. They provided the sqrt function so I'm thinking that is an important factor. This is what I've got so far: int sumofsquares(int x) { int sqrtx = isqrt(x); for (a1 = 0; a1 <= sqrtx; a1++) { int a1sqr = a1*a1; int limit1 = isqrt(x-a1sqr); for (a2 = 0; a2 <= limit1; a2++) { int a2sqr = a2*a2; int limit2 = isqrt(x-a1sqr-a1sqr); for (a3 = 0; a3 <= limit2; a3++) { int a3sqr = a3*a3; a4=isqrt(x-a1sqr-a2sqr-a3sqr); if (a1sqr+a2sqr+a3sqr+a4*a4 == x) { if(a3 == 0) return 1; if(a2 == 0) return 2; if(a1 == 0) return 3; else return 4; } } } } return 0; }

  25. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thank you very much for the help by the way

  26. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Not a problem!

  27. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.