(*:Mathematica Version: 2.0 *)

(*:Copyright: Copyright 1988-1999, Wolfram Research, Inc. *)

(*:Package Version: 1.1 *)

(*:Name: NumberTheory`Recognize` *)

(*:Context: NumberTheory`Recognize` *)

(*:Title: Recognition of Polynomials *)

(*:Author: Adam Strzebonski, Daniel R. Grayson *)

(*:Keywords:
	Polynomial, Degree, Minimal polynomial, Algebraic number
*)

(*:Requirements: None. *)

(*:History:
  Version 1.0, 1988 by Daniel R. Grayson.
  Version 1.0.1, 1991 by Wolfram Research, Inc.
      -- modified package structure to standardize it
  Version 1.1, July 1995 by Adam Strzebonski.
	The While loop at the end was added to avoid trouble with bignums:

	Recognize[ 902589045298.90329599084,10,t]
        Recognize[ 902589045298.90329599084,15,t]

	now give nontrivial polynomials.
*)

(*:Sources:

*)

(*:Summary:
This package allows you to find a "small" polynomial (in the
sense of the LLL algorithm) of which a given number approximates a root. For
algebraic numbers, the polynomial found is often the minimal polynomial.
The minimal polynomial can be guaranteed to be a factor of the polynomial
found, provided the degree allowed is high enough, and the precision given
is sufficient.
*)

(*:Remarks:
The LLL algorithm is a lattice reduction algorithm by
A.K.Lenstra, H.W.Lenstra and L.Lovasz.
*)

BeginPackage["NumberTheory`Recognize`"]

Recognize::usage =
"Recognize[x, n, t] finds a polynomial of degree at
most n in the variable t, which is approximately satisfied by the
number x. Recognize[x, n, t, k] also finds a polynomial of degree at
most n in the variable t, but with a penalty of weight k against
higher degree polynomials. k must be a nonnegative integer."

Unprotect[ Recognize ]

Begin["`Private`"]

Recognize[x_, n_Integer?Positive, t_Symbol, k_Integer:0]/;
    (If[NumberQ[x], True, Message[Recognize::nodec, x]; False]) := 
    Block[{data, i, scale, p=-1, dt, flag=True},
          If[x==0., Return[t]];
	  If[Accuracy[x]===Infinity,
	     If[Head[x]===Complex && n>1,
	        FactorTermsList[(t-x)(t-Conjugate[x])][[2]], 
	        Numerator[x] - Denominator[x] t],
	     dt = Table[x^i, {i, 0, n}];
	     dt = Round[dt 10^Max[Accuracy /@ Rest[dt]]];
	     scale = Table[(k+1)^i, {i, 0, n}];
	     If[FreeQ[dt, Complex] || n==1,
	        dt = {dt},
		dt = {Re[dt], Im[dt]}; p=-2];
	     While[flag,
		   data = Transpose[Join[DiagonalMatrix[scale], dt]];
	           data = Drop[LatticeReduce[data][[1]], p];
		   While[First[data]===0, data = RotateLeft[data]];
	           data = Table[t^i, {i, 0, n}] . (data/scale);
		   If[!NumberQ[data], flag=False, dt=10^6 dt]];
	     data]
	   ]

	
Recognize::nodec = "`1` is not a decimal number."

End[ ]   (* NumberTheory`Recognize`Private` *)

Protect[ Recognize ]

EndPackage[ ]   (* NumberTheory`Recognize` *)

(*:Limitations: None known. *)


(*:Examples:

Recognize[1.17,3,t]

Recognize[984.945,10,t,3]


*)



