Help With Simple Math Problem

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

Thread: Help With Simple Math Problem

1. Registered User
Join Date
Sep 2004
Posts
103

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. 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);
}
}

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

4. k\integers r nasty when they cant contain,,,,,

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 09:05 PM.

6. Here you are. It's two packed pages as a zipped pdf. Lots of \sigma

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise