Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to work with 100+digit numbers

  1. Jan 27, 2014 #1

    Edi

    User Avatar

    I am studying programming for the first year so I dont have whole lot of experience. I am interested in how to work with super-large numbers, numbers that are much, much larger then the included Int or _int64. I mean some 100, 1000 .. 17 million (largest prime) digit numbers. How do they do that? I understand that my home pc has no chance at calculating some of the monster primes (unless I come up with a genius, simple way to find primes :tongue: ), but I might do some other manipulations with monster numbers. Cryptography and what not.
    I figure one way might be to use an array (or a string) where each iteration is a single digit along with a custom made function to do maths digit by digit (kinda like on-paper multiplication)..
    That might be one way, but then each element of the array would consume 4 bytes (2 if I define it as short int ) and I only need .. half a byte to represent a digit from 0 to 9.A lot of memory wasted. I might resolve that problem by working in a higher base (2 byte max value base) ..
    Maybe, but how do professionals do it? Even ms calculator can do calculations with larger numbers...
     
  2. jcsd
  3. Jan 27, 2014 #2
    There are two basic approaches. One uses whatever machine instructions available on the given platform to perform arithmetic operations with "carry". Another emulates "carry" in software. For example, you can represent your big number using a sequence of 64 bit "limbs", and each limb uses only 63 bits to store data. When you add two limbs, you then check that the 64-th bit in the result is set or not. If set, that's your "carry" flag. The second approach is generally slower and uses more memory, but it is portable.
     
  4. Jan 27, 2014 #3

    jedishrfu

    Staff: Mentor

  5. Jan 27, 2014 #4
    // Using voko's numbers (see post #2)
    // Each input array specifies an integer with nWords*63 bits. The words are grouped in big endian form.
    // Integer at pnB is added to the integer at pnA.
    AddBigNums(int nWords, __int64 *pnA, const __int64 *pnB)
    {
    int n, nCarry;
    __int64 nSum;

    nCarry = 0;
    for(n=0;n<nWords;n++) {
    nSum = pnB[n] + pnA[n] +nCarry;
    if(nSum<0) {
    nSum &= 0x7FFFFFFFFFFFFFFF;
    nCarry = 1;
    } else {
    nCarry = 0;
    }
    pnA[n] = nSum;
    }
     
  6. Jan 27, 2014 #5
    .Scott, I would use unsigned arithmetic and shifts to get the carry bit. That eliminates conditional statements.
     
  7. Jan 27, 2014 #6
    I was trying to be explicit. If I was actually implementing something, I would have created a "BigNumber" class; I would have used all 64 bits; and I would have used operator overloading for "+".

    Actually, I would have search for some existing implementation of this class.
     
  8. Jan 27, 2014 #7

    Borek

    User Avatar

    Staff: Mentor

    :thumbs:
     
  9. Jan 31, 2014 #8

    rcgldr

    User Avatar
    Homework Helper

    It's a complicated combination of algorithms like Karatsuba's binary splitting for doing large multiplies, and performing the math modulo some prime number (less than 32 bits or 64 bits depending on the word size), and FFT like methods. Example description from apfloat (a downloadable source code library for large number math):

    http://www.apfloat.org/ntt.html

    Another link: (look for the FFT stuff):

    http://numbers.computation.free.fr/Constants/constants.html

    These methods are overkill for 100 to 1000 digits, but for large numbers (1 million + digits) they are fast.
     
    Last edited: Feb 1, 2014
  10. Feb 1, 2014 #9

    SixNein

    User Avatar
    Gold Member

    Well if your want to look at a good existing library, GMP is probably the best. And it's written in C++.

    just do a search for it in google.
     
  11. Feb 7, 2014 #10

    chiro

    User Avatar
    Science Advisor

    If it is for non-commercial use, then MIRACL is a good library to use (it's free for non-commercial use).

    I've used it in the past and it had good performance.

    Other suggestions include looking at cryptography libraries which often contain big number libraries out of necessity.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How to work with 100+digit numbers
  1. Number of digits in n! (Replies: 8)

  2. Number of digit (Replies: 2)

Loading...