Help With Simple Math Problem


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 6 of 6

Thread: Help With Simple Math Problem

  1. #1
    Join Date
    Sep 2004
    Posts
    103

    Question Help With Simple Math Problem

    I'm Dumb let's face it, My Brains fried for finals, We have this little baby problem and I can't figure it out, Here is the example

    All you have to do is find the value of Y on the 1,000th repetition 'Y=X^3-(X+Y)' start with Y=1, X=1 then increment X and keep recalculating Y until X reaches 1,000

    If you're lost you need to do something like this:
    set X to 1
    set Y to 1
    repeat this until X is greater than 1000
    set Y to X^3 - (X + (the old value of Y))
    increase X by 1
    end of the repeated bit
    print X and Y


    This is what I have, I guess it's wrong cause were supposed to submit the answer and I get the wrong one, Anyone tell me what i'm doing wrong or supply the correct answer, I get = -37390? ANyone else get the same thing or something different, Please help.



    public class test1 {

    public static void main(String[] args) {

    int y = 1;
    int x;
    for (x = 1;x < 1000; x ++)
    y = x ^ 3 - (x + y );
    System.out.println("Value of X" + x);
    System.out.println("Value of y" + y);
    }
    }

  2. #2
    Join Date
    Nov 2004
    Location
    Norway
    Posts
    1,560
    Being concius of ones own stupidity is vital, I've been told. The math problem here was finding the value of Y on the 1000th repetition of the incrementation, wasn't it ? - Well you don't have to loop anything to do that, but I've included the loop anyway.

    From what I can see you are blowing the integer limits in your calculation, you can't do this math (1000**3) with int's

    Code:
    public class Looper {
    
      public static void main(String[] args) {
    
        double y = 1.0d;
        double x;
    
        for (x = 1.0d;x < 1000.0d; x++) {
          y = Math.pow(x,3.0d) - (x + y);
        }
        System.out.println("y: "+y);
      }
    }
    eschew obfuscation

  3. #3
    Join Date
    Sep 2004
    Posts
    103
    It still says the answer is incorrect, can't figure out why, any other ideas?

  4. #4
    Join Date
    Nov 2004
    Location
    Norway
    Posts
    1,560
    k\integers r nasty when they cant contain,,,,,
    eschew obfuscation

  5. #5
    Join Date
    Mar 2005
    Location
    Sendling, MUC, .de
    Posts
    100
    Oooh, uuhh! Read your own words, sjalle!

    1.) It is NOT a matter of values getting to large to be held in int-type variables.

    2.) It is a discrete problem ie. it's about integers, not real numbers. So we expect the solution to be also an integer and employing floating point arithmetic is no good idea at all (although, here, doubles provide enough precision - but just try floats...). At last, as of 1.) ints can be used.

    3.) You are right, sjalle, in that there is a closed formula. So what is it?
    BTW: Even if you do the loop with BigIntegers (!) it's not really a problem. My Pentium II 400 (!!) did it up to the 100000th iteration in 0.7 sec.

    4.) It's not perfectly clear if it's the 1000th iteration or rather the 999th that is in question but regarding the pseudo-code given I tend to the former. According to this, in the for-loop it must read x <= 1000 rather than x < 1000.

    5.) The reason for RPBLEA's getting wrong results is due to the use of the ^-operator which in java does NOT mean exponentiation but bit-wise XOR.


    To get hands on this problem I slightly reformulate it as a function y: Nat -> Z with recursive definition:

    y(0) := 1 ; and for all x>0: y(x) := x - x - y(x-1)

    ...which is easily checked equivalent with the above specification. Now the question is: what is y(1000)? Or y(999), whichever interpretation of the original posting you prefer.
    Well, to make it short: the closed formula - in java and avoiding too large intermediate results - is:
    Code:
    public static int theFunctionY(int n) {
      int m = n/2; // int-divide by 2, ie. round result to floor
      return ((n&1)==0) ? m*(m*(m*4+3)-1)+1 : m*(m*(m*4+9)+5)-1;
    }
    ...which in either case - n being odd ( (n&1)==1 ) or n being even ( (n&1)==0 ) - is a polynomial of degree 3 in m or n respectively (please excuse the renaming of x to n, it's just what I'm used to). So we can use the rule-of-thumb "10**n is approximately 2**(3n)" to estimate:
    y(1000) < y(2**10) ~= 4*(((2**10)/2)**3) = 4*((2**9)**3) = (2**2)*(2**27) = 2**29
    Therefore, since there are 31 bits available in an int to represent positive integers, the result is definitely within the range representable by an int.

    Actually, y(999)=499249499 and y(1000)=500749501; int overflow occuring at y(1625).

    As you might have noticed, it's necessary to differentiate between odd and even n; the polynomials in n rather than in m=floor(n/2) are:
    y(n) = (2n+3n-2n+4)/4 if n is even
    y(n) = (2n+3n-2n-7)/4 if n is odd
    BTW: With these we'd get intermediate results about four times larger than the final result yielding an int overflow already at y(1024). That's why I use the form given above - the name of which I have forgotten...

    Should you be wondering how to prove this or even how to derive it - I'll have to convert my scribblings into somewhat readable and as soon as this is done it'll be posted here.

    ---
    p.s.: I know I'm about 5 months late, but what's gotta be said, gotta be said, ya know.
    Last edited by meisl; 04-08-2005 at 10:05 PM.

  6. #6
    Join Date
    Mar 2005
    Location
    Sendling, MUC, .de
    Posts
    100
    Here you are. It's two packed pages as a zipped pdf. Lots of \sigma
    Attached Files Attached Files

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center