Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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<d;i+=0.0001)
{
   if(b/i is a whole number)
   {
      i have a solution
   }
}

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

share|improve this question
    
I'd look at the whole numbers $\frac{bc}{a} \le n \le \frac{bd}{a}$ and check whether for any such $n$ the fraction $\frac{10000an}{b}$ is a whole number. That should be faster. Are you interested in all solutions or do you only need one? –  m_l Apr 18 '12 at 7:47
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"? –  Marc van Leeuwen Apr 18 '12 at 9:33

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
1  
perhaps it 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. –  Shitikanth Apr 18 '12 at 10:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.