Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #4690
| From | Kaz Kylheku <kaz@kylheku.com> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: large integer |
| Date | 2014-08-12 00:47 +0000 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <20140811172432.527@kylheku.com> (permalink) |
| References | <9e5d6662-d967-4ff0-9089-33004e916323@googlegroups.com> |
On 2014-08-11, b <mike7411@gmail.com> wrote: > What is the best way to store a large integer? > > Let's say it can be of theoretically unlimited size (assuming adequate memory). This depends entirely on what kinds of operations you want to do on the integer easily. For most "run of the mill" operations, you can use a dynamic vector of digits, with a size (count of digits) and a sign. A digit of the large integer is some convenient unit for the machine, like a 32 or 64 bit unsigned word. These digits represent the number in straightforward binary code. Little-endian storage order for the digits will somewhat simplify many operations, which have to process the digits of two numbers in parallel. For instance, when adding two numbers, a index can be used into both arrays: you add the [0] digits, then the [1] (plus any necessary carry) and so on. When one of the numbers runs out of digits, you keep propagating the carry through the other. In the TXR project I used Michael Fromberger's MPI library. I fixed a few portability bugs in it, and gave it some new operations, such as a full complement (pun intended) of bit operations which simulate infinite-bit two's complement; a faster square root and a few other optimizations, and more conversions, like bignum to double precision floating point. The patches are all here: http://www.kylheku.com/cgit/txr/tree/mpi-patches
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
large integer b <mike7411@gmail.com> - 2014-08-11 16:55 -0700
Re: large integer Kaz Kylheku <kaz@kylheku.com> - 2014-08-12 00:47 +0000
Re: large integer "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2014-08-12 12:17 +0100
Re: large integer Richard Heathfield <invalid@see.sig.invalid> - 2014-08-14 12:29 +0100
Re: large integer "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2014-08-15 09:31 +0100
Re: large integer Sjouke Burry <burrynulnulfour@ppllaanneett.nnll> - 2014-08-12 03:39 +0200
Re: large integer "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2014-08-12 12:23 +0100
Re: large integer Mark Storkamp <mstorkamp@yahoo.com> - 2014-08-12 09:36 -0500
csiph-web