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

Groups > comp.programming > #4689 > unrolled thread

large integer

Back to article view | Back to comp.programming

Contents

  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

#4689 — large integer

What is the best way to store a large integer?

Let's say it can be of theoretically unlimited size (assuming adequate memory).

[toc] | [next] | [standalone]

#4690

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

[toc] | [prev] | [next] | [standalone]

#4692

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 

[toc] | [prev] | [next] | [standalone]

#4698

Chris Uppal wrote:

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

I find the term "bigit" irresistible.

I coined it myself, but I doubt very much whether I was the first to do so.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#4699

Richard Heathfield wrote:

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

:)

    -- chris 

[toc] | [prev] | [next] | [standalone]

#4691

On 12.08.14 1:55, b wrote:
> What is the best way to store a large integer?
>
> Let's say it can be of theoretically unlimited size (assuming adequate memory).
>
In a large enough block of memory. Where else?

[toc] | [prev] | [next] | [standalone]

#4693

Sjouke Burry wrote:

> > What is the best way to store a large integer?
> >
> > Let's say it can be of theoretically unlimited size (assuming adequate
> > memory).
> In a large enough block of memory. Where else?

Linked list ?   /Very/ fast right and left shifts.

Also suitable if the underlying language implementation handles linked list 
better than large blocks of memory -- I think that some Lisp systems have used 
that representation (can't remember for sure, though).

Also /necessary/ if you want to handle numbers larger than will fit into main 
memory, and so the "digits" (or groups of 'em) are mapped out to file (there is 
at least one bignum package that does this).

    -- chris 

[toc] | [prev] | [next] | [standalone]

#4694

In article <9e5d6662-d967-4ff0-9089-33004e916323@googlegroups.com>,
 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).

The method used in MIDI files is to break the number into 7 bit chunks. 
If bit 7 is 0, then you have the entire number. If bit 7 is 1, then the 
number continues in the next byte.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web