ratioanl number type

ratioanl number type

[Clifford J. Nelson]

Are there any Ada95 examples in books or on the web that implement the
exact rational number data type with overloading of all appropriate
arithmetic operations and conversion to and from other number types, all
in Ada95 without anything relating to the platform it will run on? It
goes without saying that it is too difficult to predict the number of
digits that the numerator and denominator need to have, so, available
memory should be the only limit to their size.

  Cliff Nelson

Re: ratioanl number type

[Gautier]

> Are there any Ada95 examples in books or on the web that implement the
> exact rational number data type with overloading of all appropriate
> arithmetic operations and conversion to and from other number types, all
> in Ada95 without anything relating to the platform it will run on? It
> goes without saying that it is too difficult to predict the number of
> digits that the numerator and denominator need to have, so, available
> memory should be the only limit to their size.

A thing to do is to combine a generic code to obtain the fraction
field of an (euclidean) ring, with multi-precision integers,
so you can choose the two component independently.

All ingredients are there

  http://lglwww.epfl.ch/Team/MW/mw_components.html

You can also take my generic code (frac) in mathpaqs.zip

  http://members.xoom.com/gdemont/gsoft.htm

and use one of the multi-precision packs from there

  http://members.xoom.com/gnatlist/

NB: no bug-free warranty in any I think ... ;-)

HTH

-- 
Gautier

Re: ratioanl number type

[Tucker Taft]

"Clifford J. Nelson" wrote:
> 
> Are there any Ada95 examples in books or on the web that implement the
> exact rational number data type with overloading of all appropriate
> arithmetic operations and conversion to and from other number types, all
> in Ada95 without anything relating to the platform it will run on? It
> goes without saying that it is too difficult to predict the number of
> digits that the numerator and denominator need to have, so, available
> memory should be the only limit to their size.

We created this for our Ada 83 compiler long ago.  It is written in
Ada 83.  Here is a link to it.  It worked for years, but we are
not in a position to provide a warranty on it...

    http://www.averstar.com/~stt/_adasource/

Post a reply if you find an obvious stupidity in it somewhere.
Enjoy...

>   Cliff Nelson

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: ratioanl number type

[Dmitriy Anisimkov]

"Clifford J. Nelson" wrote:

> Are there any Ada95 examples in books or on the web that implement the
> exact rational number data type,

.......

> available
> memory should be the only limit to their size.

Try  http://www.chat.ru/~vagul/Unlimit7.zip

Re: ratioanl number type

[Clifford J. Nelson]

Dmitriy Anisimkov wrote:

> "Clifford J. Nelson" wrote:
>
> > Are there any Ada95 examples in books or on the web that implement the
> > exact rational number data type,
>
> .......
>
> > available
> > memory should be the only limit to their size.
>
> Try  http://www.chat.ru/~vagul/Unlimit7.zip

A timing test of GNAT Ada95 CodeBuilder 1.1 exact rational numbers with
unlimited size integers using http://www.chat.ru/~vagul/Unlimit7.zip
compared to Mathematica 3.01.

Ada95 took 4861.733319000 seconds. Mma took 15.2667 seconds.

First[Timing[vtt = tt[t]-a]]
15.2667 Second

4861.733319000/15.2667
318.453

Mathematica unlimited exact rational arithmetic is 318 times faster in this
test.

Here is the Mathematica code. Translate it into other languages or use
other packages in Ada and see how long it takes. vtt should be all zeros
(97 of them). Other odd primes instead of 97 should work too. So, test it
for 5 first to see if it works.

See:
http://forum.swarthmore.edu/epigone/geometry-research/brydilyum

tt[x_] := timesbnum[x,divperm[x]]

eigen[x_,n_] :=Append[x[[Mod[Range[Length[x]-1]*n, Length[x]] ]],Last[x]]

conjugate[x_] :=
  Module[{xx = eigen[x,2]},
    Do[xx = timesbnum[xx,eigen[x,i]],{i,3,Length[x]-1}];xx]

procal[x_,y_] :=y/((-y.Reverse[x])/Length[x])

divperm[x_] :=procal[x,conjugate[x]]

timesbnum[x_, y_] := dt[-Reverse[x], y, Length[x]]

dt[x_, y_, n_] := Table[RotateRight[x, i] . y, {i, 0, n - 1}]/n

makezero[x_] := Join[x, {-Plus @@ x}]

a = makezero[Table[1,{96}]]

t = makezero[Range[96]]

First[Timing[vtt = tt[t]-a]]
15.2667 Second

4861.733319000/15.2667
318.453

   Cliff Nelson

Re: ratioanl number type

[Robert Dewar]

In article <385252FF.BB4C7A5@gte.net>,
  cnelson9@gte.net wrote:
>
>
> Dmitriy Anisimkov wrote:
>
> > "Clifford J. Nelson" wrote:
> >
> > > Are there any Ada95 examples in books or on the web that
implement the
> > > exact rational number data type,
> >
> > .......
> >
> > > available
> > > memory should be the only limit to their size.
> >
> > Try  http://www.chat.ru/~vagul/Unlimit7.zip
>
> A timing test of GNAT Ada95 CodeBuilder 1.1 exact rational
numbers with
> unlimited size integers using
http://www.chat.ru/~vagul/Unlimit7.zip
> compared to Mathematica 3.01.
>
> Ada95 took 4861.733319000 seconds. Mma took 15.2667 seconds.


That's not too surprising. It is very easy to write inefficient
exact rational handling, and a naive approach is indeed likely
to be far slower than the carefully crafted routines inside
Mma, where these operations are of course central to the
mission, so a lot of effort has gone into doing things right.

Another reminder that choosing the proper algorithms and data
structures is usually FAR more important from an efficiency
point of view than choice of language!

Actually in the case of multiple precision, high level languages
are often at a disadvantage compared to machine language for two
reasons:

1. They do not give easy access to the carry flag, and
operations like add-carry.

2. They do not give easy access to the multiply and divide
operations that mix single and double length results.

It wouldn't surprise me if Mma used some assembly language
insertions at this point, or at the very least, very low level
code designed to interface to the machine very carefully.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: ratioanl number type

[Clifford J. Nelson]

Pascal Obry wrote:

> Clifford J. Nelson <cnelson9@gte.net> a �crit dans l'article
> <385252FF.BB4C7A5@gte.net>...
> >
> > A timing test of GNAT Ada95 CodeBuilder 1.1 exact rational numbers with
> > unlimited size integers using http://www.chat.ru/~vagul/Unlimit7.zip
> > compared to Mathematica 3.01.
> >
> > Ada95 took 4861.733319000 seconds. Mma took 15.2667 seconds.
> >
>
> Well, you did not tell us what option you did use to build the Unlimit7
> package!
>
> You should definitly use gnatmake's "-gnatpn -O3" options.
>
> Anyway this is expected as Robert said in a previous mail. Mma is tuned
> for this kind of computation.
>
> Pascal.
>
> --
>
> --|------------------------------------------------------
> --| Pascal Obry                           Team-Ada Member
> --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
> --|------------------------------------------------------
> --| http://ourworld.compuserve.com/homepages/pascal_obry
> --|
> --| "The best way to travel is by means of imagination"

Well then, am I wasting my time trying to beat Mma with a compiled high
level language?

   Cliff Nelson

Re: ratioanl number type

[Vladimir Olensky]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 984 bytes --]


Pascal Obry wrote in message <01bf43f3$3aadb600$022a6282@dieppe>...

>Clifford J. Nelson <cnelson9@gte.net> a �crit dans l'article
><38527A46.B4833D6A@gte.net>...
>>
>> Well then, am I wasting my time trying to beat Mma with a compiled high
>> level language?
>>
>>    Cliff Nelson
>
>If your goal is to beat Mma you'll certainly are about to wast some time.
>To beat it  you'll certainly have to produce some (maybe lot of :) assembly
code...


Maybe only some core  assembler routines  that make use of  processor
SIMD extensions. That would allow  drastically improve efficiency.

I suspect that Mathematica  is using SIMD already.


>If your goal is to build a portable set of packages to do some mathematical
>computation then you are far from beeing wasting your time. And if you plan
>to release these libraries under GPL or let us have the sources then
definitly
>go ahead :)


It would be nice. This could be very good contribution to Ada.

Regards,
Vladimir Olensky

Re: ratioanl number type

[Robert Dewar]

In article <s5513sek53119@corp.supernews.com>,
  "Vladimir Olensky" <vladimir_olensky@yahoo.com> wrote:
> Maybe only some core  assembler routines  that make use of
> processor SIMD extensions. That would allow  drastically
> improve efficiency.

Well we know Vladimir likes the SIMD extensions, but knowing
them well, and having written many high efficiency assembly
language packages for multi-precision arithmetic, my opinion
is that they won't be any help at all in this particular
task. Vladimir, have you actually done assembly coding using
these instructions? And have you looked at their specs in
detail?


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: ratioanl number type

[Vladimir Olensky]

Robert Dewar wrote in message <82upl4$dra$1@nnrp1.deja.com>...
>In article <s5513sek53119@corp.supernews.com>,
>  "Vladimir Olensky" <vladimir_olensky@yahoo.com> wrote:
>> Maybe only some core  assembler routines  that make use of
>> processor SIMD extensions. That would allow  drastically
>> improve efficiency.
>
>Well we know Vladimir likes the SIMD extensions,

Yes I like them.
This technique was used for more than 20 years in Russian
supercomputers "Elbrus". So no wonder that one of the
leading scientists from "Elbrus" team (Pentkovsky) was invited
to the Intel and he lead the development of SIMD extensions
for Intel chips.

>Vladimir, have you actually done assembly coding using
>these instructions?

Not too much myself but there are a lot of SIMD code around
(MMX and SSE). I have  copies of almost all most interesting
examples of code  on this topic (in different domains)  from Intel.

>And have you looked at their specs in
>detail?


Yes of course. I have all Intel's  manuals at hand.

All that is very interesting.
Operations  on vectors of data are significantly faster using
MMX or SSE.

With MMX you have eight 64 bit integer registers with a set of
operations for them (including saturated arithmetic !!!).
Each MMX register can be represented as  vector of 8X8bit,
or 4x16bit or 2x32bit or 1x64bit of elements (sub-registers).
One can use one instruction to apply the same operation
to all of them.
SSE use eight 128 bits floating point registers with that same
approach.

MMX allows for instance to use directly  64bit integer arithmetic
on IA32+ platform.  Is that useless ?

As far as for data processing there are so many exiting things
with SIMD that they go far beyond the scope of this discussion.

Going back to multi-precision arithmetic I think that it is obvious
that if one is able to use directly longer registers (64bit
registes instead of 32 bit) than one  could obtain better
efficiency.

From another point of view any rational number could be
considered as vector of elements (digits) and in some
circumstances vector operations could be applied to it
to obtain some particular results.

So I think (but not insist)  that SIMD could be useful in doing
multi-precision arithmetic.

In data processing I doubt that anyone would object that
SIMD extensions (MMX and SSE) are useless.
Also I suspect that one of the Ada design goals was
also data processing. If something new has emerged
recently that can significantly improve Ada performance
in this area why not to use it ?

Regards,
Vladimir Olensky

MMX (was Re: ratioanl number type)

[Vladimir Olensky]

Vladimir Olensky wrote in message ...
>
>Robert Dewar wrote in message <82upl4$dra$1@nnrp1.deja.com>...
>>
>>Well we know Vladimir likes the SIMD extensions,
>
>Yes I like them.


Below  is a reference  to  MMX Technology Technical Overview:
http://developer.intel.com/drg/mmx/Manuals/overview/

Hope this will be interesting.

Regards,
Vladimir Olensky

Re: ratioanl number type

[Robert Dewar]

In article <s57e138d53112@corp.supernews.com>,
  "Vladimir Olensky" <vladimir_olensky@yahoo.com> wrote:

> This technique was used for more than 20 years in Russian
> supercomputers "Elbrus". So no wonder that one of the
> leading scientists from "Elbrus" team (Pentkovsky) was invited
> to the Intel and he lead the development of SIMD extensions
> for Intel chips.

Well there is absolutely nothing new conceptually in the SIMD
extensions (or in the Elbrus), these techniques are very old
and very well known and have been for 30 years. Indeed the jury
is still out on whether such extensions are worthwhile. The ia64
should help to answer that question. Remember that the Elbrus
team as well as similar contemporary architectures were very
much under the CISC philosophy (and of course Intel still is,
indeed I would really call the ia64 a CISC design, full of
crufty stuff [e.g. long offset arithmetic available only in
4 of the 128 registers].

So the point is not the general approach, but rather,
specificaly for the ia32 extensions:

a) whether it is useful in the context of an optimizing Ada
compiler. Answer: very dubious, almost certainly there is a
long list of better optimization opportunities for any existing
compiler. Obviously you can find some test cases where pattern
matching will do nice things, but I doubt as a general
optimization it will have a noticable affect on applications
in general.

b) Whether it would help a hand written multi-precision integer
package. Again I think dubious. Vladimir, assuming you have some
experience with multi-precision arithmetic packages, why not
try writing some critical inner loops, and timing them both
ways. Vague conjecture here is not very convincing :-)



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: ratioanl number type

[Gisle S�lensminde]

In article <s57e138d53112@corp.supernews.com>, Vladimir Olensky wrote:
>
>Robert Dewar wrote in message <82upl4$dra$1@nnrp1.deja.com>...
>>In article <s5513sek53119@corp.supernews.com>,
>>  "Vladimir Olensky" <vladimir_olensky@yahoo.com> wrote:
>>> Maybe only some core  assembler routines  that make use of
>>> processor SIMD extensions. That would allow  drastically
>>> improve efficiency.
>>
>>Well we know Vladimir likes the SIMD extensions,
>
>Yes I like them.
>This technique was used for more than 20 years in Russian
>supercomputers "Elbrus". So no wonder that one of the
>leading scientists from "Elbrus" team (Pentkovsky) was invited
>to the Intel and he lead the development of SIMD extensions
>for Intel chips.
>
>>Vladimir, have you actually done assembly coding using
>>these instructions?
>
>Not too much myself but there are a lot of SIMD code around
>(MMX and SSE). I have  copies of almost all most interesting
>examples of code  on this topic (in different domains)  from Intel.


I have in fact tried the MMX instructions, and found it 
remarkable difficult to use them.

- They do not introduce full 64-bit aritmetrics.

- The parallelism is difficult to use. You can't add in the
  upper half and multiply in the lower half of the register, 
  it's also difficult to order you data to use the parellelism 
  in the instruction set efficiently.

- MMX adds more registers, and that's nice, but there are 
  latencies when moving data from 32-bit registrers to MMX
  registers, which in many cases removes the benefits from
  the MMX registers.

- The MMX instruction set has no FP instructions, and blocks
  the FP stack if you use them. You must use the emms instruction 
  first. The MMX instructions is not very general, which makes
  it necesary to use 32-bit instructions anyway in most cases. 
  Since 32-bit to MMX registers include latencies, this often 
  eat up the speed benefits of MMX.

- There use will often intoduce the need for a '32-bit version'
  of the code, since many computers not have MMX instructions 
  available.

In some cases the MMX instructions can make your code more
eficient, but it's in practice hard to write faster programs
using MMX instructions. 

--
Gisle S�lensminde ( gisle@ii.uib.no )   

ln -s /dev/null ~/.netscape/cookies

Re: ratioanl number type

[Robert Dewar]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 371 bytes --]

In article <slrn85kqa4.qrv.gisle@struts.ii.uib.no>,
  gisle@struts.ii.uib.no (Gisle S�lensminde) wrote:
> I have in fact tried the MMX instructions, and found it
> remarkable difficult to use them.

Thanks for a "real" report, this corresponds much more closely
with my knowledge of the MMX instructions :-)



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: ratioanl number type

[Robert Dewar]

In article <38527A46.B4833D6A@gte.net>,
  cnelson9@gte.net wrote:
> Well then, am I wasting my time trying to beat Mma with a
> compiled high level language?

You are not wasting your time, just tackling a very difficult
problem. Doing this efficiently without asm inserts requires
very careful tuning against the particular compiler you are
using.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: rational number type

[Wes Groleau]

The Ada 95 Rationale has some examples, though I don't think they are
"complete."