From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,245c84afd1e393ce X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news4.google.com!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!newscon06.news.prodigy.com!prodigy.net!newsfeed-00.mathworks.com!nntp.TheWorld.com!not-for-mail From: Robert A Duff Newsgroups: comp.lang.ada Subject: Re: What about big integers in Ada 2005? Date: 04 Oct 2005 15:44:53 -0400 Organization: The World Public Access UNIX, Brookline, MA Message-ID: References: <1581461.uQ1jN63t33@linux1.krischik.com> <5mo0f.529$B14.97@newssvr11.news.prodigy.com> <1x4pe4pv41qsn$.m5c5jawjqcpq.dlg@40tude.net> NNTP-Posting-Host: shell01.theworld.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: pcls4.std.com 1128455094 14131 192.74.137.71 (4 Oct 2005 19:44:54 GMT) X-Complaints-To: abuse@TheWorld.com NNTP-Posting-Date: Tue, 4 Oct 2005 19:44:54 +0000 (UTC) User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 Xref: g2news1.google.com comp.lang.ada:5386 Date: 2005-10-04T15:44:53-04:00 List-Id: clubley@remove_me.eisner.decus.org-Earth.UFP (Simon Clubley) writes: > > I think the only reason to use BCD these days (instead of binary) is to > > interface to something that uses BCD. In the old days, another reason > > was to avoid the cost of converting strings to binary integers and > > vice-versa, but that seems like an obsolete reason at this > > > > Am I right? > > How would you choose to implement big number packages ? I have implemented such a thing, and I used all manner of low-level trickery to make it efficient. Of course what's "efficient" depends on typical usage patterns, such as: 1. Almost all numbers are small (fit comfortably in one machine word). 2. Extremely large numbers are common. Lots of arithmetic, comparisons, etc. 3. Not so much arithmetic, etc. Lots of conversions back and forth to human-readable text strings. My scanario was number 1. I won't go into all the details, but basically a big int is a word, containing a small number, plus some flag bits, or a pointer to a big number, plus some flag bits. The pointer points to a heap-allocated array of "super digits". Each super digit is half a 32-bit word. In other words, we're using base 2**16. It would be more efficient to use base 2**32, but that would have required non-portable machine code inserts or something, because Ada doesn't give access to the necessary machine instructions (double-length multiply, for example). For scenario 2, I suppose the small-int hack would be a waste -- just make it a pointer to the array. For scenario 3, base 1_000_000_000 would be more efficient. Or base 10_000, if you're doing the half-word thing. I still don't see a really good reason to use base 10. - Bob