1
$\begingroup$

A friend of mine asked me to help him and make a small application to solve a problem. This problem can be reduced to this equation system:

aX = Yb; Y > c; Y < d; X is a whole number (X has nothing after . ); Y*10000 is a whole number (Y has no more then 4 digits after . );

eg. for a=185.5 b=1000000 c=4.3 d=4.4 a solution is X=23200 Y=4.3036

I have solved this doing this

for(i=c;i

Is there a way to solve this more efficient? (from mathematical point of view can this be solved arithmetically?)

  • 1
    Your proposed solution certainly won't work as you wrote it. Repeatedly incrementing $i$ by $0.0001$ is a bad idea, since $0.0001$ cannot be represented exactly as a binary floating point number, so most over the time even $10000*i$ won't be a whole number. When you need to control the exact number of iterations, you should _always_ use integer counters in loops, and if necessary calculate floating point numbers from these counters. Also do you mean "$i$ is a solution" or "I have a solution"?2012-04-18

1 Answers 1

2

You don't have to work with Y not being whole numbers: multiply Y, c and d by 10000 and divide b by 10000. You still have the same problem now except that Y is a whole number. You want X = Yb/a. Next, find the gcd of a and b, call this g. Divide a and b by g, again you have the same problem as you had before except that now a and b are known to be coprime. It is easy to see now that Y = c + (a-c%a) is the smallest value of Y that can work. If this Y is less than d, then use this value to find X = Yb/a, else there is no valid Y that works.

  • 1
    perhaps $i$t is easier if after X= Yb/a, you write Y/X = b/a. Reduce b/a to the simplest form p/q. And then check if there is a multiple of p between c and d.2012-04-18