Number: 696
Date: 13-Apr-84 13':59':56
Submitter: Sannella.PA
Source: Masinter.pa
Subject: Want BIGNUMs in Interlisp
Lisp Version:
Description: '
Date': 12 Apr 84 17':42 PST'
From': Masinter.pa'
Subject': getting into BIGNUMS'
To': JonL, LispSupport'
'
One way to do this is to separate out the issue of integration from that of the implementation of the bignum algorithms themselves.'
'
I''d be willing to work on integration (since it touches some undocumented fragile code), if you get the algorithms going.'
'
Here''s my spec for what I think is involved':'
'
datatype BIGNUM (your implementation)'
Lisp code will just use (type? BIGNUM X)'
'
Here''s my first cut at an interface. If you don''t like it, propose another interface (preferably a simpler one, but in general I''d like most of the special casing to go on OUTSIDE of the BIGNUM kernel and into the interface to the rest of the system.)'
'
Functions':'
'
(BIGNUM.PLUS bn1 n)'
takes a bignums and another number (either bignum, fixp, smallp), and returns sum as bignum, fixnum, or smallp'
(BIGNUM.MINUS bn1 n)'
similar, does subtract'
'
(BIGNUM.MINUS2 n bn)'
First arg is not a bignum'
'
(BIGNUM.TIMES bn1 n)'
similar, does multiply'
'
(BIGNUM.DIVIDE bn1 n remflg)'
returns quotient or remainder if remflg=T'
'
(BIGNUM.MINUSP bn)'
returns T if negative, NIL if positive'
'
(BIGNUM.GREATERP bn1 bn2)'
can assume both args are bignums'
'
(BIGNUM.FROM.FLOATP fn)'
takes floating point number, returns bignum.'
Can assume that arg is outside of MIN.FIXP to MAX.FIXP'
range.'
'
(BIGNUM.TO.FLOATP bn)'
convert bignum to a floating point number, give'
overflow error if out of range.'
'
(BIGNUM.TO.STRING bn radix)'
returns a string with the bignum converted to appropriate radix. It should create a new string.'
'
(BIGNUM.FROM.STRING string radix)'
string is a string of digits too large to read in as a FIXP.'
'
We may actually have to change our read algorithm to read in bignums bigger than 128 characters.'
'
-----'
'
Date': 5 MAY 84 00':56 PDT'
From': MASINTER.PA'
Subject': under AR, want bignums...'
To': lispsupport'
'
note that on [phyhlum]misc> there are versions of BIGTEST.LSP and DIVTST.LISP which are rutgers diagnostics for ELisp bignums.'
'
-----'
'
Date': 5 MAY 84 00':57 PDT'
From': MASINTER.PA'
Subject': more on bignums'
To': lispsupport'
'
22 - *******************************************'
Return-Path': HEDRICK@RUTGERS.ARPA'
Received': from RUTGERS.ARPA by Xerox.ARPA ; 30 APR 84 11':17':38 PDT'
Date': 30 Apr 84 14':05':12 EDT'
From': Charles Hedrick '
Subject': Re': new ELISP': bignums and DREVERSE'
To': masinter.pa'
In-Reply-To': Message from "masinter.pa@XEROX.ARPA" of 30 Apr 84 03':27':28 EDT'
'
It is in t':, as bigtest.lsp and divtst.lsp. Note that this'
tries to test boundary cases. To do so, we obviously use information'
about our representation. We store bignum''s in 70-bit chunks. '
Presumably whatever you want to test will not do so, so you will'
have to modify it to use the right size chunks. DIVTST is the'
one that tests a million cases. It actually tests division,'
multiplication, addition, and comparison for equality. BIGTEST'
was an attempt to test everything, but does not test as many cases.'
It should run very quickly. It wouldn''t be hard to make BIGTEST'
test all the cases from DIVTST. However, the result might only be'
acceptable for testing Lisp on a Cray.'
'
-------'
Date': 5 Apr 84 13':14 PST'
From': Masinter.pa'
Subject': Another batch of ARs'
'
System':language'
Subsystem':arithmetic'
Impact':moderate'
Problem type':wish'
Priority':perhaps'
Difficulty':hard'
Subject':want bignums'
Description':this is a desire for a smoothly integrated BIGNUM package in '
Interlisp-D.'
Smooth integration means that it fits well into the current way of Interlisp-D doing arithmetic. Interlisp puts few if any constraints on the way arithmetic is done or the word size (since we have both 32 and 36 bit implementations with a variety of SMALLP ranges). However, the current Interlisp-D implementation in places confuses INTEGER (arbitrary precision) with 32-bit arithmetic. Thus, one of the preconditions may require running with OVERFLOW(T) and weeding out those places tht are relying on implicit arithmetic modulus. '
'
Design A': 16-bit smalls, 32-bit mediums, arbitrary bignums.'
All numbers are NUMBERP and FIXP (must change macro for FIXP, NUMBERP or maybe new opcode or bit in DTD). All arithmetic operations PLUS, TIMES, IPLUS, ITIMES etc work on bigs. TYPENAME is the proper way to distinguish between the three datatypes tht distinguished numbers. This involves minor changes to microcode, '
but massive rewrite of tha arithmetic UFNs, with some care exhibited. At the '
same time, we can add rational arithmetic. Rationals are NUMBERP not FIXP not '
FLOATP. '
'
Design B is just to get rid of the intermediate 32-bit quanta. This is probably undesirable only because of the number of places in the system that use 32-bit boxes for things like clocks and timers.'
'
It is imperative that "FIXP" be retained as a generic "INTEGERP".'
'
It is reasonable when adding bignums to also add positive infinity and negative infinity. These special quantities which are also FIXP are the value of MAX.FIXP and MIN.FIXP.'
'
JonL has had a confusion between Interlisp FIXP and MacLisp FIXNUM and '
introduced some distinctions between FIXP and INTEGER. While MACLISP made that cut, it would be more reasonable for backward compatibility to say that ALL integers are FIXP.'
'
This distinction probably will need to be elaborated in the manual.'
'
Workaround:
Test Case:
Edit-By: Sannella.PA
Edit-Date: 14-Jun-84 14':57':09
Attn: jonl,masinter,lisp
Assigned To:
In/By:
Disposition:
System: Language Support
Subsystem: Arithmetic
Machine:
Disk:
Microcode Version:
Memory Size:
File Server:
Server Software Version:
Difficulty:
Frequency: Everytime
Impact: Annoying
Priority: Perhaps
Status: Open
Problem Type: Design - Impl
Source Files: