Discovered a faster way to Rationalize
- To: mathgroup at smc.vnet.net
- Subject: [mg16743] Discovered a faster way to Rationalize
- From: "Ersek, Ted R" <ErsekTR at navair.navy.mil>
- Date: Wed, 24 Mar 1999 02:23:54 -0500
- Sender: owner-wri-mathgroup at wolfram.com
It seems the Rationalize algorithm is very good at finding a rational number
with a small numerator and denominator, and ensuring the rational number is
sufficiently close to the number given to Rationalize. I once read a
precise statement explaining how the result from Rationalize is (in some
sense) the simplest possible rational number, but I don't recall where I
read this.
One would expect a faster version of rationalize could be made with very
little trouble. The fast version would be based on a very simple
algorithm, and would pay no attention to how "simple" the rational number
is. Well It turns out you don't have to write a C program and call it with
MathLink to get a faster version of Rationalize.
You simply set the precision to Infinity.
For example the next line will rationalize (14.7).
In[1]:=
x=14.7;
SetPrecision[x,Infinity]
Out[1]=
4137682157646643/281474976710656
--------------------
The timing tests below show that SetPrecision is about 26 times faster than
Rationalize.
In[2]=
lst=Table[Random[], {3000}];
In[3]:=
lst2=Rationalize[#,10^-16]& /@lst; //Timing
Out[3]=
{34.49 Second,Null}
In[4]:=
lst3=SetPrecision[#, Infinity]& /@lst;//Timing
Out[4]=
{1.32 Second,Null}
---------------------
Below we see the numbers returned by Rationalize are more concise than those
returned by SetPrecision.
In[5]:=
Take[lst2, 4]
Out[5]=
{56688213/67091543,
65249023/101559912,
23505441/36375899,
35052879/79826210}
In[6]:=
Take[lst3, 4]
Out[6]=
{7610527453306575/9007199254740992,
5786839903309269/9007199254740992,
5820287511177617/9007199254740992,
7910390975729053/18014398509481984}
-----------------------
In the next line we see that SetPrecision doesn't change the numerical value
of the number.
In[7]:=
err=lst-lst3;
Take[err,4]
Out[7]=
{0.,0.,0.,0.}
---------------------------------
I find the trick above very useful. Maybe you will too.
Reagrds,
Ted Ersek