convert real number to radicals

Question

Suppose I have a real number. I want to approximate it with something of the form a+sqrt(b) for integers a and b. But I don't know the values of a and b. Of course I would prefer to get a good approximation with small values of a and b. Let's leave it undefined for now what is meant by "good" and "small". Any sensible definitions of those terms will do.

Is there a sane way to find them? Something like the continued fraction algorithm for finding fractional approximations of decimals. For more on the fractions problem, see here.

EDIT: To clarify, it is an arbitrary real number. All I have are a bunch of its digits. So depending on how good of an approximation we want, a and b might or might not exist. Brute force is naturally not a particularly good algorithm. The best I can think of would be to start adding integers to my real, squaring the result, and seeing if I come close to an integer. Pretty much brute force, and not a particularly good algorithm. But if nothing better exists, that would itself be interesting to know.

EDIT: Obviously b has to be zero or positive. But a could be any integer.

Answer 1

No need for continued fractions; just calculate the square-root of all "small" values of b (up to whatever value you feel is still "small" enough), remove everything before the decimal point, and sort/store them all (along with the b that generated it).

Then when you need to approximate a real number, find the radical whose decimal-portion is closet to the real number's decimal-portion. This gives you b - choosing the correct a is then a simple matter of subtraction.

Answer 2

This is actually more of a math problem than a computer problem, but to answer the question I think you are right that you can use continued fractions. What you do is first represent the target number as a continued fraction. For example, if you want to approximate pi (3.14159265) then the CF is:

3: 7, 15, 1, 288, 1, 2, 1, 3, 1, 7, 4 ...

The next step is create a table of CFs for square roots, then you compare the values in the table to the fractional part of the target value (here: 7, 15, 1, 288, 1, 2, 1, 3, 1, 7, 4...). For example, let's say your table had square roots for 1-99 only. Then you would find the closest match would be sqrt(51) which has a CF of 7: 7,14 repeating. The 7,14 is the closest to pi's 7,15. Thus your answer would be:

sqrt(51)-4

As the closest approximation given a b < 100 which is off by 0.00016. If you allow larger b's then you could get a better approximation.

The advantage of using CFs is that it is faster than working in, say, doubles or using floating point. For example, in the above case you only have to compare two integers (7 and 15), and you can also use indexing to make finding the closest entry in the table very fast.

Answer 3

This can be done using mixed integer quadratic programming very efficiently (though there are no run-time guarantees as MIQP is NP-complete.)

Define:

d := the real number you wish to approximate
b, a := two integers such that a + sqrt(b) is as "close" to d as possible
r := (d - a)^2 - b, is the residual of the approximation

The goal is to minimize r. Setup your quadratic program as:

x := [ s b t ]
D := | 1 0 0 |
     | 0 0 0 |
     | 0 0 0 |
c := [0 -1 0]^T
with the constraint that s - t = f (where f is the fractional part of d) 
and b,t are integers (s is not)

This is a convex (therefore optimally solvable) mixed integer quadratic program since D is positive semi-definite.

Once s,b,t are computed, simply derive the answer using b=b, s=d-a and t can be ignored.

Your problem may be NP-complete, it would be interesting to prove if so.

Answer 4

Some of the previous answers use methods that are of time or space complexity O(n), where n is the largest “small number” that will be accepted. By contrast, the following method is O(sqrt(n)) in time, and O(1) in space.

Suppose that positive real number r = x + y, where x=floor(r) and 0 ≤ y < 1. We want to approximate r by a number of the form a + √b. If x+y ≈ a+√b then x+y-a ≈ √b, so √b ≈ h+y for some integer offset h, and b ≈ (h+y)^2. To make b an integer, we want to minimize the fractional part of (h+y)^2 over all eligible h. There are at most √n eligible values of h. See following python code and sample output.

import math, random

def findb(y, rhi):
    bestb = loerror = 1;
    for r in range(2,rhi):
        v = (r+y)**2
        u = round(v)
        err = abs(v-u)
        if round(math.sqrt(u))**2 == u: continue
        if err < loerror:
            bestb, loerror = u, err
    return bestb

#random.seed(123456)     # set a seed if testing repetitively
f = [math.pi-3] + sorted([random.random() for i in range(24)])
print ('    frac     sqrt(b)       error       b')
for frac in f:                   
    b = findb(frac, 12)
    r = math.sqrt(b)
    t = math.modf(r)[0]         # Get fractional part of sqrt(b)
    print ('{:9.5f}  {:9.5f}  {:11.7f}  {:5.0f}'.format(frac, r, t-frac, b))

(Note 1: This code is in demo form; the parameters to findb() are y, the fractional part of r, and rhi, the square root of the largest small number. You may wish to change usage of parameters. Note 2: The
if round(math.sqrt(u))**2 == u: continue
line of code prevents findb() from returning perfect-square values of b, except for the value b=1, because no perfect square can improve upon the accuracy offered by b=1.)

Sample output follows. About a dozen lines have been elided in the middle. The first output line shows that this procedure yields b=51 to represent the fractional part of pi, which is the same value reported in some other answers.

    frac     sqrt(b)       error       b
  0.14159    7.14143   -0.0001642     51
  0.11975    4.12311    0.0033593     17
  0.12230    4.12311    0.0008085     17
  0.22150    9.21954   -0.0019586     85
  0.22681   11.22497   -0.0018377    126
  0.25946    2.23607   -0.0233893      5
  0.30024    5.29150   -0.0087362     28
  0.36772    8.36660   -0.0011170     70
  0.42452    8.42615    0.0016309     71
   ...
  0.93086    6.92820   -0.0026609     48
  0.94677    8.94427   -0.0024960     80
  0.96549   11.95826   -0.0072333    143
  0.97693   11.95826   -0.0186723    143

With the following code added at the end of the program, the output shown below also appears. This shows closer approximations for the fractional part of pi.

frac, rhi = math.pi-3, 16
print ('    frac        sqrt(b)         error          b     bMax')
while rhi < 1000:
    b = findb(frac, rhi)
    r = math.sqrt(b)
    t = math.modf(r)[0]         # Get fractional part of sqrt(b)
    print ('{:11.7f}  {:11.7f}  {:13.9f}  {:7.0f}  {:7.0f}'.format(frac, r, t-frac, b,rhi**2))
    rhi = 3*rhi/2

    frac        sqrt(b)         error          b     bMax
  0.1415927    7.1414284   -0.000164225       51      256
  0.1415927    7.1414284   -0.000164225       51      576
  0.1415927    7.1414284   -0.000164225       51     1296
  0.1415927    7.1414284   -0.000164225       51     2916
  0.1415927    7.1414284   -0.000164225       51     6561
  0.1415927  120.1415831   -0.000009511    14434    14641
  0.1415927  120.1415831   -0.000009511    14434    32761
  0.1415927  233.1415879   -0.000004772    54355    73441
  0.1415927  346.1415895   -0.000003127   119814   164836
  0.1415927  572.1415909   -0.000001786   327346   370881
  0.1415927  911.1415916   -0.000001023   830179   833569

Answer 5

I do not know if there is any kind of standard algorithm for this kind of problem, but it does intrigue me, so here is my attempt at developing an algorithm that finds the needed approximation.

Call the real number in question r. Then, first I assume that a can be negative, in that case we can reduce the problem and now only have to find a b such that the decimal part of sqrt(b) is a good approximation of the decimal part of r. Let us now write r as r = x.y with x being the integer and y the decimal part.

Now:
b = r^2
  = (x.y)^2
  = (x + .y)^2
  = x^2 + 2 * x * .y + .y^2
  = 2 * x * .y + .y^2 (mod 1)

We now only have to find an x such that 0 = .y^2 + 2 * x * .y (mod 1) (approximately).

Filling that x into the formulas above we get b and can then calculate a as a = r - b. (All of these calculations have to be carefully rounded of course.)

Now, for the time being I am not sure if there is a way to find this x without brute forcing it. But even then, one can simple use a simple loop to find an x good enough.

I am thinking of something like this(semi pseudo code):

max_diff_low = 0.01 // arbitrary accuracy
max_diff_high = 1 - max_diff_low
y = r % 1
v = y^2
addend = 2 * y
x = 0
while (v < max_diff_high && v > max_diff_low)
    x++;
    v = (v + addend) % 1
c = (x + y) ^ 2
b = round(c)
a = round(r - c)

Now, I think this algorithm is fairly efficient, while even allowing you to specify the wished accuracy of the approximation. One thing that could be done that would turn it into an O(1) algorithm is calculating all the x and putting them into a lookup table. If one only cares about the first three decimal digits of r(for example), the lookup table would only have 1000 values, which is only 4kb of memory(assuming that 32bit integers are used).

Hope this is helpful at all. If anyone finds anything wrong with the algorithm, please let me know in a comment and I will fix it.

EDIT: Upon reflection I retract my claim of efficiency. There is in fact as far as I can tell no guarantee that the algorithm as outlined above will ever terminate, and even if it does, it might take a long time to find a very large x that solves the equation adequately.

One could maybe keep track of the best x found so far and relax the accuracy bounds over time to make sure the algorithm terminates quickly, at the possible cost of accuracy.

These problems are of course non-existent, if one simply pre-calculates a lookup table.