How to find the numbers that satisfy (x - y * sqrt(2016.0)) / (y + sqrt(2016.0)) = 2016 using loops in C

Question

I'm trying to find numbers that satisfy the clause (x - y * √ 2016) / (y + √ 2016) = 2016. Number x and y can be rational numbers.

That's what I already tried:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
int x, y;
    for(x = 1; x < 10000; x++) {
        for(y = 1; y < 10000; y++) {
            if( (x - y * sqrt(2016.0)) / (y + sqrt(2016.0) ) == 2016) {
                printf("Numbers are: %d and %d.", x, y);
            }
        }
    }
    return 0;
}

From a superficial inspection, there seems to be no problem; what exactly is the question? — Codor, Oct 18 '17 at 12:09
The strict equality comparision in `(x - y * sqrt(2016.0)) / (y + sqrt(2016.0)) == 2016` looks fishy. See [this SO question](https://stackoverflow.com/questions/588004/is-floating-point-math-broken). — Jabberwocky, Oct 18 '17 at 12:13
The code looks good overall, but since sqrt (and floating point maths) isn't exact you might want to considder comparing with a small margin for error such as `fabs((x - y * sqrt(2016.0)) / (y + sqrt(2016.0) ) - 2016) < 0.000001` or some other arbitrary margin. — Diasiare, Oct 18 '17 at 12:13
A few observations: (1) This is floating point, so you are very unlikely to get an exact match. Instead, you need to allow a margin for error, (2) If you can get close enough to a root, where the function is nearly linear, you can start dividing the search space into intervals, successively narrowing it down, (3) Another approach would be to use Newton's method. In any case, you will need at least some understanding the mathematics involved. — Tom Karzes, Oct 18 '17 at 12:14
Possibly the compiler will optimize this, but you can once calculate `sqrt(2016)` before starting the loops. — Paul Ogilvie, Oct 18 '17 at 12:14
Why not solve it with math instead? There’s a unique x for every y ≠ −√2016, it’s not a tough rearrangement. — Ry-, Oct 18 '17 at 12:17
If this is a real task, you should first solve the equation for one variable, i.e. `x = 2060.9*y+90518.2`. Now you can find your x and y pairs by simply inserting arbitrary values for y. — Ctx, Oct 18 '17 at 12:17
Another observation: The function will probably be better behaved if you multiple both sides by the denominator, eliminating the division entirely and obtaining a linear equation. In fact, once you do that, you could solve it analytically without the need for a computer at all. — Tom Karzes, Oct 18 '17 at 12:18
Considering the square root of 2016 is 44.899 it might be pretty tough to find integers that solve that equation. Its early but if you break that equation down I believe you get 0=sqrt(2016)y+y-x+2016 — Dammer15, Oct 18 '17 at 12:26

Andreas H. · Answer 1 · 2017-10-19T08:16:04.367

Using floating point math and brute force search to "solve" this problem is conceptionally a bad idea. This is because with FP math round-off error propagates in a non-intuitive way, and hence many equations that are solvable in a mathematical sense have no (exact) solution with FP numbers. So using FP math to approximate solutions of mathematical equations is inherently difficult.

I suggest a simplification of the problem before programming.

If one does this and only searches for integer solutions one would find that the only solutions are

x = -2016^2 = -4064256
y = -2016

Why: Just rearrange a bit and obtain

x = 2016*y + (2016 + y)*sqrt(2016)

Since sqrt(2016) is not an integer the term in the clause before the sqrt must be zero. Everything else follows from that.

In case a non-integer solution is desired, the above can be used to find the x for every y. Which even enumerates all solutions.

So this shows that simplification of a mathematical problem before attempted solution in a computer is usually mandatory (especially with FP math).

EDIT: In case you look for rational numbers, the same argument can be applied as for the integer case. Since sqrt(2016) is not a rational number, y must also be -2016. So for the rational case, the only solutions are the same as for the integers, i.e,

x = -2016^2 = -4064256
y = -2016

Note that both of these values lie well outside the bounds that OP is using for x and y (they're both negative, and the magnitude of x is far greater than the maximum magnitude OP is checking). But it's not really clear from the question what the desired result is. — Tom Karzes, Oct 18 '17 at 12:56

score 1 · Answer 2 · answered Oct 18 '17 at 12:40

1

This is just the equation for a line. Here's an exact solution:

x = (sqrt(2016) + 2016)*y + 2016*sqrt(2016)

For any value of y, x is given by the above. The x-intercept is:

x = 2016*sqrt(2016)
y = 0

The y-intercept is:

x = 0
y = -2016*sqrt(2016)/(sqrt(2016)+2016)

answered Oct 18 '17 at 12:40

Tom Karzes

22,815
2
22
41

Identification of the integer solutions is not so easy with this approach – Andreas H. Oct 18 '17 at 12:43
Well he does not say explicitly, but `x` and `y` are declared as 'int' in his code – Andreas H. Oct 18 '17 at 12:46
Actually, looking at it now, it's clear that the only possible integer solution is one in which the roots cancel, which can only occur when y is -2016, which gives x a value of -2016**2. – Tom Karzes Oct 18 '17 at 12:48
I know :-), as I wrote in my answer. Also x is -2016^2 not +. – Andreas H. Oct 18 '17 at 12:50
@AndreasH. Thanks, yes I just caught that myself and fixed my comment. – Tom Karzes Oct 18 '17 at 12:50
@AndreasH. Actually, if you look at the ranges OP is using for x and y, there's no way he could find the integer solution, since (a) both x and y are negative, and (b) the magnitude of x is well beyond the range op is checking. – Tom Karzes Oct 18 '17 at 12:54
true, the question is very vague in the regard of the domain of the solution – Andreas H. Oct 18 '17 at 12:56
@tom Note OP does say "Number x and y can be rational numbers." and all finite `double` are rational. – chux - Reinstate Monica Oct 18 '17 at 16:53

klutt · Answer 3 · 2017-10-24T10:19:35.870

The result from operations with floats are in general not exact. Change:

if( (x - y * sqrt(2016.0)) / (y + sqrt(2016.0) ) == 2016)

to something like

if( fabs((x - y * sqrt(2016.0)) / (y + sqrt(2016.0) ) - 2016) < 0.00000001)

where 0.00000001 is a tolerance chosen by you.

But as pointed out, you don't want to search through the domains of more variables than necessary. Solve the math first. Using Wolfram Alpha like this we get y=(x-24192*√14)/(12*(168+√14))

chux - Reinstate Monica · Answer 4 · 2017-10-18T17:49:44.680

numbers that satisfy (x - y * sqrt(2016.0)) / (y + sqrt(2016.0)) = 2016

Starting with @Tom Karzes

x = (sqrt(2016) + 2016)*y + 2016*sqrt(2016)

Let y = -2016

x = (sqrt(2016) + 2016)*-2016 + 2016*sqrt(2016)
x = 2016*-2016 = -4064256

So x,y = -4064256, -2016 is one exact solution.

With math, this is the only one.
With sqrt(x) not being exactly √x and peculiarities of double math, there may be other solutions that pass a C code simulation.

As a C simulation like OP's, lets us "guess" the answer's x,y are both multiples of 2016 and may be negative.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double f(int x, int y) {
  double z = (x - y * sqrt(2016.0)) / (y + sqrt(2016.0));
  z = z - 2016;
  return z * z;
}

#define M 3000
int main() {
  double best_diff = DBL_MAX;
  int best_x = 0;
  int best_y = 0;
  int x, y;
  for (x = -M; x < M; x++) {
    for (y = -M; y < M; y++) {
      double diff = f(x * 2016, y * 2016);
      if (diff < best_diff) {
        best_diff = diff;
        best_x = x;
        best_y = y;
      }
      if (diff == 0) {
        printf("Numbers are: %d and %d.\n",  best_x*2016, best_y*2016);
      }
    }
  }
  if (best_diff != 0.0) {
    printf("Numbers are: %d and %d --> %e.", best_x*2016, best_y*2016, best_diff);
  }
  return 0;
}

Output

Numbers are: -4064256 and -2016.

I forgot to say that x, y ∈ Q (not just an int, but i thought it would be ok with an int number) — Co_Co, Oct 18 '17 at 19:06
@Co_Co post said "Number x and y can be rational numbers." All integers and finite `double` are rational numbers. There is only 1 rational solution to the math problem - it happens to be a pair of integers.. — chux - Reinstate Monica, Oct 18 '17 at 19:56
@Tom Karzes What part of the answer do you find objectionable? — chux - Reinstate Monica, Oct 19 '17 at 02:32

How to find the numbers that satisfy (x - y * sqrt(2016.0)) / (y + sqrt(2016.0)) = 2016 using loops in C

4 Answers4