* ratioanl number type @ 1999-12-03 0:00 Clifford J. Nelson 1999-12-03 0:00 ` Gautier ` (3 more replies) 0 siblings, 4 replies; 16+ messages in thread From: Clifford J. Nelson @ 1999-12-03 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-03 0:00 ratioanl number type Clifford J. Nelson @ 1999-12-03 0:00 ` Gautier 1999-12-03 0:00 ` Tucker Taft ` (2 subsequent siblings) 3 siblings, 0 replies; 16+ messages in thread From: Gautier @ 1999-12-03 0:00 UTC (permalink / raw) > 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-03 0:00 ratioanl number type Clifford J. Nelson 1999-12-03 0:00 ` Gautier @ 1999-12-03 0:00 ` Tucker Taft 1999-12-03 0:00 ` Dmitriy Anisimkov 1999-12-09 0:00 ` rational " Wes Groleau 3 siblings, 0 replies; 16+ messages in thread From: Tucker Taft @ 1999-12-03 0:00 UTC (permalink / raw) "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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-03 0:00 ratioanl number type Clifford J. Nelson 1999-12-03 0:00 ` Gautier 1999-12-03 0:00 ` Tucker Taft @ 1999-12-03 0:00 ` Dmitriy Anisimkov 1999-12-11 0:00 ` Clifford J. Nelson 1999-12-09 0:00 ` rational " Wes Groleau 3 siblings, 1 reply; 16+ messages in thread From: Dmitriy Anisimkov @ 1999-12-03 0:00 UTC (permalink / raw) "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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-03 0:00 ` Dmitriy Anisimkov @ 1999-12-11 0:00 ` Clifford J. Nelson [not found] ` <01bf43ea$646d5bc0$022a6282@dieppe> 1999-12-11 0:00 ` Robert Dewar 0 siblings, 2 replies; 16+ messages in thread From: Clifford J. Nelson @ 1999-12-11 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
[parent not found: <01bf43ea$646d5bc0$022a6282@dieppe>]
* Re: ratioanl number type [not found] ` <01bf43ea$646d5bc0$022a6282@dieppe> @ 1999-12-11 0:00 ` Clifford J. Nelson [not found] ` <01bf43f3$3aadb600$022a6282@dieppe> 1999-12-12 0:00 ` Robert Dewar 0 siblings, 2 replies; 16+ messages in thread From: Clifford J. Nelson @ 1999-12-11 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
[parent not found: <01bf43f3$3aadb600$022a6282@dieppe>]
* Re: ratioanl number type [not found] ` <01bf43f3$3aadb600$022a6282@dieppe> @ 1999-12-11 0:00 ` Vladimir Olensky 1999-12-12 0:00 ` Robert Dewar 0 siblings, 1 reply; 16+ messages in thread From: Vladimir Olensky @ 1999-12-11 0:00 UTC (permalink / raw) [-- 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-11 0:00 ` Vladimir Olensky @ 1999-12-12 0:00 ` Robert Dewar 1999-12-12 0:00 ` Vladimir Olensky 0 siblings, 1 reply; 16+ messages in thread From: Robert Dewar @ 1999-12-12 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-12 0:00 ` Robert Dewar @ 1999-12-12 0:00 ` Vladimir Olensky 1999-12-12 0:00 ` MMX (was Re: ratioanl number type) Vladimir Olensky ` (2 more replies) 0 siblings, 3 replies; 16+ messages in thread From: Vladimir Olensky @ 1999-12-12 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* MMX (was Re: ratioanl number type) 1999-12-12 0:00 ` Vladimir Olensky @ 1999-12-12 0:00 ` Vladimir Olensky 1999-12-14 0:00 ` ratioanl number type Robert Dewar 1999-12-17 0:00 ` Gisle S�lensminde 2 siblings, 0 replies; 16+ messages in thread From: Vladimir Olensky @ 1999-12-12 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-12 0:00 ` Vladimir Olensky 1999-12-12 0:00 ` MMX (was Re: ratioanl number type) Vladimir Olensky @ 1999-12-14 0:00 ` Robert Dewar 1999-12-17 0:00 ` Gisle S�lensminde 2 siblings, 0 replies; 16+ messages in thread From: Robert Dewar @ 1999-12-14 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-12 0:00 ` Vladimir Olensky 1999-12-12 0:00 ` MMX (was Re: ratioanl number type) Vladimir Olensky 1999-12-14 0:00 ` ratioanl number type Robert Dewar @ 1999-12-17 0:00 ` Gisle S�lensminde 1999-12-19 0:00 ` Robert Dewar 2 siblings, 1 reply; 16+ messages in thread From: Gisle S�lensminde @ 1999-12-17 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-17 0:00 ` Gisle S�lensminde @ 1999-12-19 0:00 ` Robert Dewar 0 siblings, 0 replies; 16+ messages in thread From: Robert Dewar @ 1999-12-19 0:00 UTC (permalink / raw) [-- 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. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-11 0:00 ` Clifford J. Nelson [not found] ` <01bf43f3$3aadb600$022a6282@dieppe> @ 1999-12-12 0:00 ` Robert Dewar 1 sibling, 0 replies; 16+ messages in thread From: Robert Dewar @ 1999-12-12 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: ratioanl number type 1999-12-11 0:00 ` Clifford J. Nelson [not found] ` <01bf43ea$646d5bc0$022a6282@dieppe> @ 1999-12-11 0:00 ` Robert Dewar 1 sibling, 0 replies; 16+ messages in thread From: Robert Dewar @ 1999-12-11 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: rational number type 1999-12-03 0:00 ratioanl number type Clifford J. Nelson ` (2 preceding siblings ...) 1999-12-03 0:00 ` Dmitriy Anisimkov @ 1999-12-09 0:00 ` Wes Groleau 3 siblings, 0 replies; 16+ messages in thread From: Wes Groleau @ 1999-12-09 0:00 UTC (permalink / raw) The Ada 95 Rationale has some examples, though I don't think they are "complete." ^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~1999-12-19 0:00 UTC | newest] Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1999-12-03 0:00 ratioanl number type Clifford J. Nelson 1999-12-03 0:00 ` Gautier 1999-12-03 0:00 ` Tucker Taft 1999-12-03 0:00 ` Dmitriy Anisimkov 1999-12-11 0:00 ` Clifford J. Nelson [not found] ` <01bf43ea$646d5bc0$022a6282@dieppe> 1999-12-11 0:00 ` Clifford J. Nelson [not found] ` <01bf43f3$3aadb600$022a6282@dieppe> 1999-12-11 0:00 ` Vladimir Olensky 1999-12-12 0:00 ` Robert Dewar 1999-12-12 0:00 ` Vladimir Olensky 1999-12-12 0:00 ` MMX (was Re: ratioanl number type) Vladimir Olensky 1999-12-14 0:00 ` ratioanl number type Robert Dewar 1999-12-17 0:00 ` Gisle S�lensminde 1999-12-19 0:00 ` Robert Dewar 1999-12-12 0:00 ` Robert Dewar 1999-12-11 0:00 ` Robert Dewar 1999-12-09 0:00 ` rational " Wes Groleau
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox