Converting float to algebraic number

[Han]

Useless trivia for the day...

Let \( n \) be in decimal representation. To find an (\( a + \sqrt{b} \))-approximation of \( n \), i.e. find integers \(a\) and \( b \) such that \( n = a+ \sqrt{b} \), we can use the following simple idea.

Since \( (n-a)^2 = b \), we simply check whether any of the values among
\[ n^2, (n-1)^2, (n-2)^2, \dotsm, (n-\lfloor n \rfloor)^2 \]
are integers.

Code:

export algn(x)
begin
  local fn:=ip(x);
  local a, b, r;
  local DIGIT:=9;

  for a from 0 to fn do
    b:=round((x-a)^2, DIGIT);
    r:=b-ip(b);
    if (abs(r) < 10^(-DIGIT+1)) then
      return({a,b});
    end;
  end;
  return({x,0});
end;

Example:
X:=1+8^.5;
algn(X); // -----> { 1, 8 } representing \( 1 + \sqrt{8} \)

[parisse]

If a and b are not too large, there is a more general algorithm that works for (a+b*sqrt(c))/d: find the continued fraction expansion and detect periodicity.