Mombu 2007-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:
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
3) Are there packages for this kind of symbolic/numerical work in GNU
Maxima (maxima.sf.net)? Or in other environments?
Rahul jain 2007-12-19 20:03:08
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
Common Lisp requires support for rationals as well as floats and complex
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
Professional Software Developer, Amateur Quantum Mechanicist
Rlewis 2007-12-20 09:00:16
Look into the computer algebra system Fermat, for Windows, Mac,
Unix, and Linux. It’s shareware.
Robert H. Lewis
Department of Mathematics
New York City
Mombu 2007-12-20 09:00:28
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:
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?
Joe marshall 2007-12-20 09:00:28
MIT Scheme: yes
Scott g. mille 2007-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.
Cstacy 2007-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.
Mombu 2007-12-20 09:00:33
firstname.lastname@example.org (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?
Scott g. mille 2007-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
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.
Mombu 2007-12-20 20:20:47
I made a mistake: Bigloo does not support rationals:
Unbound variable — rationalize
Unbound variable — numerator
Unbound variable — denominator
1:=> (/ 10 3)
1:=> (/ 1111111111111111111 999999999999999999999999)
not a number — #l1111111111111111111
Devore 2007-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 antoniot 2007-12-20 20:20:52
But any CL implementation does. A piece of advice: bite the bullet!
Switch to CL 🙂
Mombu 2007-12-20 20:21:20
email@example.com (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 fatema 2007-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”
Dscheers 2007-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
All functions are for big numbers (theoreticly no limit except RAM)
they are all based on rational number calculation.
Johan kullstam 2007-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.
Christophe rho 2007-12-22 11:47:27
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.
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. mille 2007-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)
Johan kullstam 2007-12-22 11:47:33
D’oh. I totally misread that then. Sorry, my bad.