Re: ADA arithmetic

Re: ADA arithmetic

[Robert Dewar]

To put my 2c in on this issue, I thought the assignment in question was
pretty easy, well within reach of a first programming course if the 
algorithmic points are discussed a little in class.

Re: ADA arithmetic

[comp.vuw.ac.nz!canterbury.ac.nz!otago.ac.nz!piglet.otago.ac.nz!pgorman]

is20115@otago.ac.nz wrote:
> In article <CAvptp.B5F@inmet.camb.inmet.com>, stt@spock.camb.inmet.com (Tucke
r Taft) writes:
> > In article <1993Jul26.134358.1@otago.ac.nz> is20115@otago.ac.nz writes:
> > 
> >>I am currently working on a program which requires arithmetic to be perform
ed
> >>on numbers of up to 16 digits long.  Has anyone out ther written a package
> >>which will do this?  Add & Subtract would suffice but * & divide and MOD wo
uld
> >>be a big help.  If anyone has one of these could they please mail to source
> >>code to COSC214.OTAGO.AC.NZ  this would be much appreciated.
> > 
> > Every Ada compiler includes within it an "infinite" precision
> > arithmetic package.  The GNAT compiler is no exception, so
> > if you want to do infinite precision arithmetic (both integral
> > and rational), you can snarf the "july9-release" of GNAT and
> > extract the following files:
> > 
> >     uintp-.ada   -- Universal Integer package spec
> >     uintp.ada    -- Univ int package body
> >     rat-.ada     -- Rational numbers package spec
> >     rat.ada      -- Rational numbers package body
> > 
> > GNAT is available by anonymous ftp from cs.nyu.edu
> > in directory pub/gnat/july9-release.  All of the Ada sources
> > are in the file gnat-src.tar.z (don't forget to use binary/image mode
> > to transfer it, and you will need gunzip and tar to extract
> > individual source files).
> >
> Are you sure that address is right?  seems a little short and it doesn't work
> when I try it.  This tar.z thing is a real pain, I have unzip and VMStar whic
h
> I hope will work.  Though I still haven't figured out to run them using run
> with parameters.  The VAX is about as userfriendly as a wet paper bag full of
> wet paper bags.  Thanks for you help, it is much appreciated.
> By the way, if anyone is really bored this Friday night and is looking for
> something to do, they could always do my whole assignment, that would be much
> appreciated also.  Gee I hope Paul doesn't read this one too!

>   

There is no point in FTPing the Ada9X files as we are in the process of
installing the compiler here so we already have the 9X source code.
Also since the point of the assignment is that you should learn something
by doing it yourself I don't know if Chris will give you a grade for the
'work' you are doing.
Finally, this sort of communication should be via e-mail and not posted
world-wide.

Paul
--
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Dr. Paul Gorman                  tel   : +64 -3 479 8366              |
| Lecturer                         fax   : +64 -3 479 8529              |
| Department of Computer Science   e-mail: pgorman@gandalf.otago.ac.nz  |
| University of Otago                                                   |  
| PO Box 56, Dunedin, NZ           "OK...So...She's a dog."             |

Re: ADA arithmetic

[waikato.ac.nz!canterbury.ac.nz!otago.ac.nz!is20115]

In article <CAvptp.B5F@inmet.camb.inmet.com>, stt@spock.camb.inmet.com (Tucker 
Taft) writes:
> In article <1993Jul26.134358.1@otago.ac.nz> is20115@otago.ac.nz writes:
> 
>>I am currently working on a program which requires arithmetic to be performed
>>on numbers of up to 16 digits long.  Has anyone out ther written a package
>>which will do this?  Add & Subtract would suffice but * & divide and MOD woul
d
>>be a big help.  If anyone has one of these could they please mail to source
>>code to COSC214.OTAGO.AC.NZ  this would be much appreciated.
> 
> Every Ada compiler includes within it an "infinite" precision
> arithmetic package.  The GNAT compiler is no exception, so
> if you want to do infinite precision arithmetic (both integral
> and rational), you can snarf the "july9-release" of GNAT and
> extract the following files:
> 
>     uintp-.ada   -- Universal Integer package spec
>     uintp.ada    -- Univ int package body
>     rat-.ada     -- Rational numbers package spec
>     rat.ada      -- Rational numbers package body
> 
> GNAT is available by anonymous ftp from cs.nyu.edu
> in directory pub/gnat/july9-release.  All of the Ada sources
> are in the file gnat-src.tar.z (don't forget to use binary/image mode
> to transfer it, and you will need gunzip and tar to extract
> individual source files).
>
Are you sure that address is right?  seems a little short and it doesn't work
when I try it.  This tar.z thing is a real pain, I have unzip and VMStar which
I hope will work.  Though I still haven't figured out to run them using run
with parameters.  The VAX is about as userfriendly as a wet paper bag full of
wet paper bags.  Thanks for you help, it is much appreciated.
By the way, if anyone is really bored this Friday night and is looking for
something to do, they could always do my whole assignment, that would be much
appreciated also.  Gee I hope Paul doesn't read this one too!

  

Re: ADA arithmetic

[cis.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!spool.mu.ed]

In article <1993Jul29.133129.1@otago.ac.nz>, is20115@otago.ac.nz writes:
|> In article <EACHUS.93Jul26135137@spectre.mitre.org>, eachus@spectre.mitre.or
g (Robert I. Eachus) writes:
|> > 
|> >      Mike, if a teacher is handing out assignments like this, I want
|> > to know what the class is!  I've now done two portable packages for
|> > extended arithmetic in Ada, and it is not something taught in any
|> > undergraduate or graduate curriculum that I am aware of.  If it were,
|> > the SPARC architecture would show up much better in most benchmarks.
|> > (In particular on most SPARC chips, the algorithms recommended in the
|> > SPARC architecture manual are much slower than simpler shorter
|> > routines that DO set the condition codes correctly.)
|> > 
|> > --
|> > 
|> Would you be able to give me the address of an FTP site which has the packag
e
|> ADAR?   I haven't been able to find it yet and am not sure how to go about
|> Craig.
|> finding it, it would be much appreciated thanx.
|> 
|> 
ADAR is on ajpo.sei.cmu.edu under public/atip/adar ... it is also on the Ada
CDROM under ajpo/atip/adar

Rick Conn

Re: ADA arithmetic

[Robert I. Eachus]

In article <1993Jul28.165516.1@otago.ac.nz> simon@otago.ac.nz (The Arch-Deviant
) writes:

   > It's worth 7% of Otago's core 2nd-year programming course (just
   > my luck - all the possible Comp. Sci. lecturers and I have to get
   > a software engineer! (sorry Paul, just kidding :-) ). Alas we're
   > only allowed to use VAXen so performance isn't really a concept
   > we're familiar with.

In article <235qd1$52u@schonberg.cs.nyu.edu> dewar@cs.nyu.edu (Robert Dewar) wr
ites:

   > To put my 2c in on this issue, I thought the assignment in
   > question was pretty easy, well within reach of a first
   > programming course if the algorithmic points are discussed a
   > little in class.

   Actually, on a VAX it is very easy.  I may have a lot of complaints
about the VAX but the arithmetic support is not one of them.  Not only
will the ADAR stuff give you beaucoup digits on the VAX, but the
instruction set will allow you to do lots of high/multiprecision
things easily.


--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: ADA arithmetic

[agate!spool.mu.edu!uwm.edu!wupost!waikato.ac.nz!canterbury.ac.nz!news!ota]

In article <1993Jul28.170334.1@otago.ac.nz>, simon@otago.ac.nz (The Arch-Devian
t) writes:
> In article <gmacmanus.2.743824190@gandalf.otago.ac.nz>, gmacmanus@gandalf.ota
go.ac.nz (Greg MacManus) writes:
>> How do you implement the numbers then?
>> 
>> 	- Just curious.
> 
> Easy - treat them as variable-length arrays (ie in a record with a default
> discriminant) of 0..9 then treat each term as a coefficient in an polynomial
> evaluated at x=10. As Paul observes, the literature is bulging with nifty
> ways for performing operations on polynomials, and since we don't have to
> generate keys we can get away with defining only three operations - square
> the number, halve it and test for a remainder, and MOD.
> 
Well of course....  now I know why I can't do it....    I don't speak the lingo
I still recon my idea of FTP'ing a package is the best idea.  Is that legal
the fact that we didn't write the arithmetic package shouldn't matter should
it????????
	////
  \\\\ ////   ******   Long live the Amiga!!!    *******  
    \\////    

Paul?  I mean the idea of the assignment is to implement an RSA key thingie so

Re: ADA arithmetic

[Michael Feldman]

In article <CAt7yr.HoH@news.otago.ac.nz> pgorman@piglet.otago.ac.nz (Paul Gorma
n) writes:
>Michael Feldman (mfeldman@seas.gwu.edu) wrote:
>> In article <1993Jul26.134358.1@otago.ac.nz> is20115@otago.ac.nz writes:
>> >I am currently working on a program which requires arithmetic to be perform
ed
>> >on numbers of up to 16 digits long.  Has anyone out ther written a package
>> >which will do this?  Add & Subtract would suffice but * & divide and MOD wo
uld
>> >be a big help.  If anyone has one of these could they please mail to source
>> >code to COSC214.OTAGO.AC.NZ  this would be much appreciated.
>> >
>> Ummm - is this a class problem? If so, does your teacher know you're out
>> on the net instead of working on it?
>
>> Mike Feldman
>
>The teacher knows now, he is one of my colleagues and I noticed the posting
>the other day. The assignment is to implement the RSA Public Key cryptography
>system. I think they have been given a reference in a book for algorithms to
>use for the operations on the type.
>
As I said before, I think I'd give the kid at least partial credit for
resourcefulness. Reuse principle, y'know :-)

Mike

Re: ADA arithmetic

[Tucker Taft]

In article <1993Jul26.134358.1@otago.ac.nz> is20115@otago.ac.nz writes:

>I am currently working on a program which requires arithmetic to be performed
>on numbers of up to 16 digits long.  Has anyone out ther written a package
>which will do this?  Add & Subtract would suffice but * & divide and MOD would
>be a big help.  If anyone has one of these could they please mail to source
>code to COSC214.OTAGO.AC.NZ  this would be much appreciated.

Every Ada compiler includes within it an "infinite" precision
arithmetic package.  The GNAT compiler is no exception, so
if you want to do infinite precision arithmetic (both integral
and rational), you can snarf the "july9-release" of GNAT and
extract the following files:

    uintp-.ada   -- Universal Integer package spec
    uintp.ada    -- Univ int package body
    rat-.ada     -- Rational numbers package spec
    rat.ada      -- Rational numbers package body

GNAT is available by anonymous ftp from cs.nyu.edu
in directory pub/gnat/july9-release.  All of the Ada sources
are in the file gnat-src.tar.z (don't forget to use binary/image mode
to transfer it, and you will need gunzip and tar to extract
individual source files).

As do all such infinite precision packages, these packages
uses a sequence of "digits" in some convenient base
(e.g. 10_000 or 2**15) that can safely be manipulated
without overflowing the hardware integer.
In GNAT, these digits are stored in a somewhat obscure way,
since they are using arrays to represent everything.
The algorithms, however, can readily be adapted to other
representations for the sequence of digits.
They are based on the ones given in Knuth's "The Art of 
Computer Programming" Volume 2 (section 4.3.1).

If you are doing a lot of multiplication, rather than addition,
representations based on the "Chinese Remainder Theorem"
are more efficient, but the approach is somewhat more complicated.
(Unfortunately, I don't have a reference on the Chinese Remainder
Theorem.)

Hope this helps.

S. Tucker Taft   stt@inmet.com
Intermetrics, Inc.
Cambridge, MA  02138

Re: ADA arithmetic

[Robert Dewar]

Of course Simon's suggestion of how to program multi-precision numbers in
Ada is reasonable as a crude approach for beginning students, but is
ludicrously inefficient. Probably it is likely that a well written routine
(I believe brother Eachus is hard at work on a portable efficient 64-bit
integer package) will be an order of magnitude faster.

Of course in assembler one can do much better. This is one of the very few
times that assembler is not only more efficient but much easier to program
than typical high level languages like Ada. Why: because these languages
don't give access to the crucial primitives such as unsigned add with a
carry indication.

Re: ADA arithmetic

[Th e Arch-Deviant]

In article <gmacmanus.2.743824190@gandalf.otago.ac.nz>, gmacmanus@gandalf.otago
.ac.nz (Greg MacManus) writes:
> How do you implement the numbers then?
> 
> 	- Just curious.

Easy - treat them as variable-length arrays (ie in a record with a default
discriminant) of 0..9 then treat each term as a coefficient in an polynomial
evaluated at x=10. As Paul observes, the literature is bulging with nifty
ways for performing operations on polynomials, and since we don't have to
generate keys we can get away with defining only three operations - square
the number, halve it and test for a remainder, and MOD.

Simon Brady                     "I'd join the Movement,
University of Otago              If there was one I could believe in"
Dunedin, New Zealand                  - U2, 'Acrobat'

Re: ADA arithmetic

[Th e Arch-Deviant]

In article <EACHUS.93Jul26135137@spectre.mitre.org>, eachus@spectre.mitre.org (
Robert I. Eachus) writes:
>      Mike, if a teacher is handing out assignments like this, I want
> to know what the class is!  I've now done two portable packages for
> extended arithmetic in Ada, and it is not something taught in any
> undergraduate or graduate curriculum that I am aware of.  If it were,
> the SPARC architecture would show up much better in most benchmarks.
> 
> 					Robert I. Eachus

It's worth 7% of Otago's core 2nd-year programming course (just my luck -
all the possible Comp. Sci. lecturers and I have to get a software
engineer! (sorry Paul, just kidding :-) ). Alas we're only allowed to use
VAXen so performance isn't really a concept we're familiar with.

Were I of an arrogant nature I could postulate some connection between the
rigour of our courses and our success in the ACM Programming Competition,
but that would be immature and contrary to the spirit of the net :-)

Simon Brady                     "I'd join the Movement,
University of Otago              If there was one I could believe in"
Dunedin, New Zealand                  - U2, 'Acrobat'

Re: ADA arithmetic

[agate!spool.mu.edu!wupost!waikato.ac.nz!canterbury.ac.nz!news!piglet.otag]

Michael Feldman (mfeldman@seas.gwu.edu) wrote:
> In article <1993Jul26.134358.1@otago.ac.nz> is20115@otago.ac.nz writes:
> >I am currently working on a program which requires arithmetic to be performe
d
> >on numbers of up to 16 digits long.  Has anyone out ther written a package
> >which will do this?  Add & Subtract would suffice but * & divide and MOD wou
ld
> >be a big help.  If anyone has one of these could they please mail to source
> >code to COSC214.OTAGO.AC.NZ  this would be much appreciated.
> >
> Ummm - is this a class problem? If so, does your teacher know you're out
> on the net instead of working on it?

> Mike Feldman

The teacher knows now, he is one of my colleagues and I noticed the posting
the other day. The assignment is to implement the RSA Public Key cryptography
system. I think they have been given a reference in a book for algorithms to
use for the operations on the type.

Paul Gorman.
--
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Dr. Paul Gorman                  tel   : +64 -3 479 8366              |
| Lecturer                         fax   : +64 -3 479 8529              |
| Department of Computer Science   e-mail: pgorman@gandalf.otago.ac.nz  |
| University of Otago                                                   |  
| PO Box 56, Dunedin, NZ           "OK...So...She's a dog."             |

Re: ADA arithmetic

[Robert I. Eachus]

     Mike, if a teacher is handing out assignments like this, I want
to know what the class is!  I've now done two portable packages for
extended arithmetic in Ada, and it is not something taught in any
undergraduate or graduate curriculum that I am aware of.  If it were,
the SPARC architecture would show up much better in most benchmarks.
(In particular on most SPARC chips, the algorithms recommended in the
SPARC architecture manual are much slower than simpler shorter
routines that DO set the condition codes correctly.)

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: ADA arithmetic

[Michael Feldman]

In article <1993Jul26.134358.1@otago.ac.nz> is20115@otago.ac.nz writes:
>I am currently working on a program which requires arithmetic to be performed
>on numbers of up to 16 digits long.  Has anyone out ther written a package
>which will do this?  Add & Subtract would suffice but * & divide and MOD would
>be a big help.  If anyone has one of these could they please mail to source
>code to COSC214.OTAGO.AC.NZ  this would be much appreciated.
>
Ummm - is this a class problem? If so, does your teacher know you're out
on the net instead of working on it?

Mike Feldman
------------------------------------------------------------------------
Michael B. Feldman -  co-chair, SIGAda Education Committee
Professor, Dept. of Electrical Engineering and Computer Science
The George Washington University -  Washington, DC 20052 USA
202-994-5253 (voice) - 202-994-0227 (fax) - mfeldman@seas.gwu.edu (Internet)
"We just changed our CONFIG.SYS, then pressed CTRL-ALT-DEL. It was easy."
-- Alexandre Giglavyi, director Lyceum of Information Technologies, Moscow.
------------------------------------------------------------------------