Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4692

Re: large integer

Show all headers | View raw

Kaz Kylheku wrote:
> 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.

Agreed.  Just want to add that another viable choice can be to store "digits" 
which are some power of 10.  That is suitable in the case where the primary 
purpose of the numbers is for display to users or storage as text, and 
non-trivial arithmetic (stuff more complicated that addition or multiplication 
by small constants) is either rare or not required at all.  The point is that 
converting between binary representation and decimal can be more expensive than 
everything else put together (depending on the application of course), so 
representing the number as decimal "internally" can /sometimes/ be a big win. 
I've used that representation in one "financial" application.

BTW: an often-used term for the "digits" in this context is "limb" -- which 
might help the OP when searching for further information.

And, just for interest (perhaps), another representation I've used (only once!) 
is as a "bag of primes": some sort of mapping from prime numbers to counts 
representing the prime factorisation of the number.  Upside -- multiplication 
and division are /fast/.  Downsides -- don't even /think/ about addition; also 
numbers beyond a certain point cannot be represented using, say, 32-bit 
counters.  The application was one where I wanted to manipulate numbers created 
by multiplying and dividing millions of small primes.

    -- chris 

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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