Code covered by the BSD License

### Highlights from Fractions Toolbox

5.0
5.0 | 8 ratings Rate this file 13 Downloads (last 30 days) File Size: 55.6 KB File ID: #24878 Version: 1.8

# Fractions Toolbox

### Ben Petschel (view profile)

30 Jul 2009 (Updated )

create and manipulate fractions (K+N/D) using exact arithmetic

File Information
Description

The fractions toolbox allows users to create and manipulate fractions and fraction arrays of the form K+N/D, e.g.

fr(1,3) % returns 1 / 3
fr(pi) % returns 3 + 4703 / 33215

All the standard arithmetic and comparison operations are valid:
fr(1,3)+fr(1,2) % returns 5 / 6
fr(1,3)>0.3 % returns 1

Linear equations:
A = fr(ones(2),[2,3;5,7]);
B = fr(ones(2,1),[11;13]);
A\B % returns [-3+49/143; 4+37/143]
lsq(fr([1;1]),[0;1]) % returns 1/2

The treatment of singular and non-square systems is different from that of the built-in "\" so please read the documentation, e.g. for reasons of personal preference "\" does not do least-squares by default - use lsq instead.

Partial fractions and arbitrary-base digits can be computed:
[d,r]=digits(fr(1,7),4,3) % 4 digits of base-3 expansion of 1/7 plus remainder
% returns d=[0,1,0,2] and r= 4/567

Continued fractions expansions of fractions and square roots:
[cf,rep] = cfracsqrt(fr(13,5)) % continued fraction of sqrt(13/5)
[r1,r2] = bestrat(cf,rep,1000) % best rational approximations with denominator limit 1000

A powerful feature of the toolbox is that the numerator and denominator can theoretically be any data types that accept the standard arithmetic and comparison operations as well as gcd and mod. For example, if you have John D'Errico's Variable Precision Integer Toolbox (20 July 2009 release or later; see link below):

prod(fr(1,vpi(2:7)).^10)

ans =
1 / 10575608481180064985917685760000000000

If there exists a suitably defined polynomial object, this toolbox could be used to perform partial fraction and series expansions of rational functions.

See the demo and help files for a full list of features.

The functions have been tested with doubles and vpi integers, but message me if you encounter any problems, and let me know how it goes with other data types.

Acknowledgements

Variable Precision Integer Arithmetic inspired this file.

This file inspired The Computation Of Pi By Archimedes.

MATLAB release MATLAB 7.9 (R2009b)
05 Jun 2015 nikhil pachauri

### nikhil pachauri (view profile)

HOW I CAN ADD THIS TOOLBOX IN MY MATLAB

Comment only
19 Jul 2013 Jared

### Jared (view profile)

Ben, very useful tool. I wanted to alert you to what looks to be a small bug:

In @fr/rat, I think line 54 should read:

varargout{1}=N+K.*D;

rather than

varargout{1}=N+K*D;

I am happy so far and will provide more feedback one I have more time to play with it.

Comment only
06 Oct 2012 Ben Petschel

### Ben Petschel (view profile)

Richard/Nathan, thanks for the suggestions - I've submitted a new update for fr.m and freduce.m. I got around the performance issue in fr.m by using a persistent variable to ensure that the calls to superiorto are done only once.

Comment only
03 Oct 2012 Richard Crozier

### Richard Crozier (view profile)

One more thing, even with my change, I still find that about 60% of the time in fr.m is spent on the line

if exist('vpi', 'class')

at least according to the profiler. So if anyone does not have this toolbox, I'd advise just commenting this whole test out.

Comment only
03 Oct 2012 Richard Crozier

### Richard Crozier (view profile)

Sorry for the multiple posts, and a better suggestion, just:

if exist('vpi', 'class')
superiorto('vpi')
end

03 Oct 2012 Richard Crozier

### Richard Crozier (view profile)

I suggest modifying fr.m to check for the existence of the vpi class before calling superiorto like follows:

if exist('vpi', 'class')
try
superiorto('vpi')
catch
% in case VPI toolbox has never been used
end
end

the reason is that if you call fr.m many times and don't have the vpi toolbox, the call to superiorto('vpi') is incredibly slow, and in fact takes up most of the execution time.

Comment only
03 Oct 2012 Richard Crozier

### Richard Crozier (view profile)

I suggest modifying fr.m to check for the existence of the vpi class before calling superiorto like follows:

if exist('vpi', 'class')
try
superiorto('vpi')
catch
% in case VPI toolbox has never been used
end
end

the reason is that if you call fr.m many times and don't have the vpi toolbox, the call to superiorto('vpi') is incredibly slow, and in fact takes up most of the execution time.

Comment only
13 Apr 2012 Nathan Thern

### Nathan Thern (view profile)

Excellent work. I was just writing a wrapper class around java.math.BigInteger and tried creating an fr object using it. I found that your freduce function uses / (mrdivide) in three places where you really want ./ (rdivide).

11 Aug 2011 Ben Petschel

### Ben Petschel (view profile)

Ok, to do that you'd need to define a total ordering on the polynomials by partitioning R[x] into P, -P and {0}, so p(x)>0 if p(x) is in P. See Lang's Algebra chapter 11 (real fields) for examples and details on the theory - e.g. the monomial orderings used for Groebner basis calculation are valid. This way you have sign(p)=1 if p is in P, etc, and similarly abs(p)=sign(p)*p.

Also I forgot to mention that MOD is required, but once this is defined then it's easy to write a GCD function. To define MOD you just need to define the representative elements of the cosets R[x]/p(x), such that MOD(q,p)>=0.

If you're willing to put in the effort implementing this, I'd be keen to see the results, but otherwise you're probably better off with a professional package such as Mathematica (which has an affordable home-use version) or the Symbolic Toolbox.

Comment only
11 Aug 2011 Christophe Lauwerys

### Christophe Lauwerys (view profile)

Great stuff, but I wonder how your two statements quoted below can be unified.

In other words: how can you define for instance SIGN and ABS for objects that represent polynomials? Not to mention GCD for multivariate polynomials ... Not an expert but do you need Groebner bases for this?

Thanks

Christophe

A)

% Non-standard objects must include 0, 1, -1 and require the following
% operations to be defined in order to create a fraction object:
% gcd
% rem
% sign
% abs
% +, - , .*, ./
% ==, <, <=, >, >=, ~=
%
% The following additional operation definitions are recommended:
% *, .^
% sort
% floor
% factor
% gcd (3-output form)
% rat (if floor(x) or mod(x,1) is not always equal to x)

B) If there exists a suitably defined polynomial object, this toolbox could be used to perform partial fractions.

Comment only
23 Jun 2011 Bill McKeeman

### Bill McKeeman (view profile)

I used this toolbox in the computation of pi (see FX 29504).

18 Aug 2009 Erdal Bizkevelci

### Erdal Bizkevelci (view profile)

01 Aug 2009 Matt Fig

### Matt Fig (view profile)

Great work!

01 Aug 2009 Derek O'Connor

### Derek O'Connor (view profile)

This is a very useful toolbox, especially when used with
John D'Errico's Variable Precision Integer Toolbox.

Here are two tests I ran :

function z = RumpFrac(x,y)

% Testing John D'Errico's Variable Precision Integer Toolbox
% and Ben Petschel's Fractions Toolbox using
% Rump's polynomial. Derek O'Connor Aug 01 2009

x = fr(vpi(x));
y = fr(vpi(y));

R1 = (33375/100)*y^6+ x^2*(11*x^2*y^2-y^6- 121*y^4- 2)
R2 = (55/10)*y^8
R3 = x/(2*y)
z1 = R1+R2
z = z1 + R3;

%
% R1 =
% -7917111340668961361101134701524942850
% R2 =
% 7917111340668961361101134701524942848
% R3 =
% 1 + 11425 / 66192
% z1 =
% -2
% z =
% -1 + 11425 / 66192 = -54767/66192 --- Correct.

% z = -1.180591620717411e+021 without first two statements

and

function z = JuddFrac(x,y)
% Testing John D'Errico's Variable Precision Integer Toolbox
% and Ben Petschel's Fractions Toolbox using
% Judd's polynomial. Derek O'Connor Aug 01 2009

x = fr(vpi(x));
y = fr(vpi(y));

J1 = 1682*x*y^4
J2 = 3*x^3
J3 = 29*x*y^2
J4 = - 2*x^5
z1 = J1+J2
z2 = z1+J3
z3 = z2+J4
z4 = z3+832
z = z4/107751

% z = JuddFrac(192119201,35675640);
% J1 =
% 523460426438903533308340192814390277120000
% J2 =
% 21273236588999014470832803
% J3 =
% 7091078862999671298158400
% J4 =
% -523460426438903561672655644813075853992002
% z1 =
% 523460426438903554581576781813404747952803
% z2 =
% 523460426438903561672655644813076046111203
% z3 =
% 192119201
% z4 =
% 192120033
% z =
% 1783 --- Correct.

% z = 7.721506064908910e-003 without first two statements

31 Jul 2009 Khaled Hamed

### Khaled Hamed (view profile)

Very useful toolbox, especially with the added precision of the vpi toolbox.

I think the demo_fr.m file needs an "echo on" at the beginning to see the header of each of the demo problems, rather than answers only (followed by echo off at the end).

31 Jul 2009 Ben Petschel

### Ben Petschel (view profile)

Hi Khaled, thanks for pointing that out (I forgot to run "rehash path" when testing without the vpi toolbox). I've submitted an update which should become available soon. Let me know if you have any further problems.

Comment only
31 Jul 2009 Khaled Hamed

### Khaled Hamed (view profile)

It seems to require vpi to be in the Matlab path, or a previous instance of a vpi.

>> fr(1,7)
??? Error using ==> superiorto
Unknown class 'vpi' listed in 'SUPERIORTO'.

Error in ==> fr.fr at 201
superiorto('vpi','double','single','int8','uint8','int16', ...

Comment only
30 Jul 2009 John D'Errico

### John D'Errico (view profile)

Nifty

31 Jul 2009 1.1

fixed bug that can occur when users do not have the VPI toolbox.

17 Aug 2009 1.2

added functions mldivide (\), rref, lsq

25 Aug 2009 1.3

Improved performance of times and other operations; added functions for dealing with continued fractions

14 Dec 2009 1.4

added rank function; bugfix for frinv handling non-double arrays

08 Oct 2012 1.8

Improved performance of fr.m (thanks to Richard Zapor); bugfix in freduce.m affecting objects that do not have mrdivide defined (thanks to Nathan Thern); bugfix in frinv.m to allow rdivide with fraction arrays.