Mombu2007-12-19 20:02:40

I’ve been looking for a means to implement a numerical linear algebra

algorithm, but without the concomitant round-off error (I’m fortunate

enough that my initial matrices are of integer type). . So, with an

instinctual reaction to check SICP, I remembered the good ‘ole days of

implementing rational arithmetic (2.1.1).

I needed a more general library, though. I had the linear algebra

algorithm all coded up, but I simply wanted to exchange the arithmetic

operators to ones which would understand & simplify both rational

numbers and integers.

I couldn’t find anything online, so I took the basics of SICP 2.1.1,

and made some extensions:

http://thar.lbl.gov/~taltman/rational.scm.html

So, what’s my point?

1) The fun of implementing rational arithmetic in Scheme from scratch

aside, is there a library already implemented?

2) Please reply to me with feedback

(questions/suggestions/comments/criticism).

3) Are there packages for this kind of symbolic/numerical work in GNU

Maxima (maxima.sf.net)? Or in other environments?

Many thanks,

~Tomer Altman

—

()

Rahul jain2007-12-19 20:03:08

taltman@noshpam.lbl.government writes:

Most implementations of Scheme already have rationals. From what I

gather, scheme doesn’t require rationals, but requires certain

relationships with other numerical types to hold, if those other types

are implemented.

Common Lisp requires support for rationals as well as floats and complex

numbers.

Since Maxima is implemented in Common Lisp, and, as far as I know, uses

the arithmetic operators of the host Lisp, it should support your

operations automatically. The algebraic operators are implemented

internally, of course, but fall back to the arithmetic operators when

possible.

—

Rahul Jain

rjain@nyct.net

Professional Software Developer, Amateur Quantum Mechanicist

Rlewis2007-12-20 09:00:16

Hi,

Look into the computer algebra system Fermat, for Windows, Mac,

Unix, and Linux. It’s shareware.

Robert H. Lewis

Department of Mathematics

Fordham University

New York City

Mombu2007-12-20 09:00:28

Rahul Jain

I took a second look at R5RS, and I realized my confusion; I guess my

current implementation-of-choice, Guile, doesn’t support ‘numerator’,

‘denominator’, or ‘rationalize’! So I tried some others:

*DrScheme: yes

*Guile: no

*Chicken: no

*Bigloo: yes

*Scheme48/Scsh: yes

*SCM: no

Is there any more definitive information about this kind of “optional

standard” across various Scheme implementations? Specifically, are

there implementations which internally represent the division of

integers as the creation of a rational number, with both the numerator

and the denominator being bignums? If there’s a limit to an

implementation’s ability to store rationals (due to the numerator

and/or the denominator being fixnums), then they’re useless for the

scientific application I had in mind.

So I guess this is standard in CL. Does the HyperSpec mandate this?

And are both the numerator and the denominator required to be

represented as bignums? I read the HyperSpec, and it didn’t seem to

mention either way…

Would I be better off just using a CAS like GNU Maxima?

~Tomer

Joe marshall2007-12-20 09:00:28

taltman@noshpam.lbl.government writes:

MIT Scheme: yes

Scott g. mille2007-12-20 09:00:30

SISC does what you say. Exact division is equivalent to creating a

rational number and simplifying. But R5RS doesn’t require any specific

precision, just a vague notion of consistency throughout the

implementation and respective to its goals.

Scott

Cstacy2007-12-20 09:00:32

taltman> If there’s a limit to an implementation’s ability to store

taltman> rationals (due to the numerator and/or the denominator being

taltman> fixnums), then they’re useless for the scientific

taltman> application I had in mind.

There’s always a limit to any implementation’s ability to

store rationals: resources are not infinite.

taltman> So I guess this is standard in CL. Does the HyperSpec mandate this?

taltman> And are both the numerator and the denominator required to

taltman> be represented as bignums? I read the HyperSpec, and it

taltman> didn’t seem to mention either way…

Yes, Common Lisp has rational numbers, no kidding.

What CLHS says is:

Rational computations cannot overflow in the usual sense

(though there may not be enough storage to represent a

result), since integers and ratios may in principle be

of any magnitude.

Mombu2007-12-20 09:00:33

cstacy@news.dtpq.com (Christopher C. Stacy) writes:

Oh, I’m sure. But all I want is something where integer division is

represented as a tuple of bignums “in simplified form”, and where it

“promotes” to an integer (fixnum or bignum) when appropriate.

Is there a single Scheme that can do this? I think Scott said that

SISC can do this; am I quoting you correctly?

Thanks,

~Tomer

Scott g. mille2007-12-20 09:00:35

Yes, thats exactly what SISC does. The rationals have bignum

components, which are limited to 2^32 bits (i.e. 2^(2^32) is the largest

representable number).

You should continue searching though if you’re doing high performance

computation. While SISC’s bignum arithmetic is competitive, the rest of

the Scheme system is not compiled, but rather interprets a high

performance intermediate form (micro-expressions). This may not matter

if bignum arithmetic dominates the time spent.

Scott

Mombu2007-12-20 20:20:47

taltman@noshpam.lbl.government writes:

I made a mistake: Bigloo does not support rationals:

1:=> rationalize

*** ERROR:bigloo:eval:

Unbound variable — rationalize

#unspecified

1:=> numerator

*** ERROR:bigloo:eval:

Unbound variable — numerator

#unspecified

1:=> denominator

*** ERROR:bigloo:eval:

Unbound variable — denominator

#unspecified

1:=> (/ 10 3)

3.3333333333333

1:=> (/ 1111111111111111111 999999999999999999999999)

*** ERROR:bigloo:/:

not a number — #l1111111111111111111

#unspecified

—

~T

Devore2007-12-20 20:20:48

Check out www.linalg.org. You can download extensive C++ code there

for the exact solution of matrix problems. Rational arithmetic is

usually not the best thing to use for integer matrix problems, execpt

perhaps that it may be required in the final steps if the answers

themselves are rational.

Marco antoniot2007-12-20 20:20:52

But any CL implementation does. A piece of advice: bite the bullet!

Switch to CL ðŸ™‚

Cheers

—

Marco

Mombu2007-12-20 20:21:20

devore@math.udel.edu (Carl Devore) writes:

Why so? I need the answers to be exact, not approximate. My matrix

starts with positive & negative integers between -2 and 2. In the

worst-case, I can imagine a bignum implementation chewing up a lot of

resources. But I imagine that the average case will be acceptable (I

need accuracy, not speed).

—

()

Richard fatema2007-12-20 20:21:27

You don’t say what you are doing, or how long you expect

your computation to take.

There are studies that suggest

doing some exact operations can be done more efficiently

by using finite field arithmetic (perhaps several times)

and sticking the pieces together with the Chinese Remainder

Algorithm. e.g. McClellan’s work on exact solution of linear

equations using modular arithmetic.

You might also look at papers on “Exact Linear Algebra”

by Ashoff

(try google).

Dscheers2007-12-21 08:49:23

Perhaps i am way out of league here, if so, tell me.

We developed a library for Windows. That is for use under Visual Basic

and C++.

All functions are for big numbers (theoreticly no limit except RAM)

and

they are all based on rational number calculation.

Functions:http://www.big-numbers.com/forum/viewtopic.php?t=12

Download:http://www.big-numbers.com/forum/viewtopic.php?t=27&sid=b5588871941e2916514af64e861825fb

Site: www.big-numbers.com

David

Johan kullstam2007-12-22 11:47:21

”Scott G. Miller”

I think your definition of “bignum” differs from mine (I am coming

from common-lisp and terminology will not be the same). I take

“bignum” to mean an arbitrarily large integer (well, there is finite

memory available, but certainly thousands of bits should be viable).

I would assume that an implementation keeps track of how many words

are in the bignum. To add two bignums, it could apply machine code to

“add” followed by a series “add with carry” operations as needed.

From the CLHS

The type bignum is defined to be exactly (and integer (not fixnum)).

Where fixnum is some fixed range of integers (range at least as large

as 16 bit signed integers for common-lisp).

Being limited to a certain number of bits, e.g., 32, is what I consider

the definiting atribute of being a fixnum and, hence, specifically

disallowed by the term bignum.

Johan KULLSTAM

Christophe rho2007-12-22 11:47:27

Johan Kullstam

A limitation of 32 bits for a bignum might be serious. (I wouldn’t be

happy with it :-). A limitation of 2^32 bits is significantly less so

in practical terms.

Christophe

—

http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757

(set-pprint-dispatch ‘number (lambda (s o) (declare (special b)) (format s b)))

(defvar b “~&Just another Lisp hacker~%”) (pprint #36rJesusCollegeCambridge)

Scott g. mille2007-12-22 11:47:32

Yes. I think he misread. The maximum bignum in SISC would occupy about

270mb of memory (2.1 billion bits) in a single number, which would be

pretty impractical to use in real computations. The limitation, fwiw,

comes out of the Java BigInteger class, which has several methods which

operate on bits indexed by a Java int, which is a signed 32 bit integer.

That means the largest addressable bit by those operators is (-

(expt 2 31) 1)

Scott

Johan kullstam2007-12-22 11:47:33

Christophe Rhodes

D’oh. I totally misread that then. Sorry, my bad.

—

Johan KULLSTAM

## Leave a Reply

You must be logged in to post a comment.