how to add two no. of 100 digits or more?

Discussion in 'C Programming' started by Umesh, May 30, 2007.

  1. Umesh

    Umesh Guest

    Is there any way by which i can do it? Thanks.
    Umesh, May 30, 2007
    #1
    1. Advertising

  2. Umesh

    Ian Collins Guest

    Umesh wrote:
    > Is there any way by which i can do it? Thanks.
    >

    Yes

    --
    Ian Collins.
    Ian Collins, May 30, 2007
    #2
    1. Advertising

  3. On May 30, 3:53 am, Umesh <> wrote:
    > Is there any way by which i can do it? Thanks.


    Link with a library which does that.
    Quentin Godfroy, May 30, 2007
    #3
  4. Umesh

    Sanchit Guest

    On May 30, 1:00 pm, Ian Collins <> wrote:
    > Umesh wrote:
    > > Is there any way by which i can do it? Thanks.

    >
    > Yes
    >
    > --
    > Ian Collins.


    But howwwwwwwwwwwwwwwwwww?????????????????????????????????
    Sanchit, May 30, 2007
    #4
  5. Sanchit said:

    > On May 30, 1:00 pm, Ian Collins <> wrote:
    >> Umesh wrote:
    >> > Is there any way by which i can do it? Thanks.

    >>
    >> Yes
    >>
    >> --
    >> Ian Collins.

    >
    > But howwwwwwwwwwwwwwwwwww?????????????????????????????????


    Well, he says he's Sanchit, but he's acting like Umesh.

    Into the killfile with him.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
    Richard Heathfield, May 30, 2007
    #5
  6. Umesh

    Sanchit Guest

    On May 30, 3:32 pm, Richard Heathfield <> wrote:
    > Sanchit said:
    >
    > > On May 30, 1:00 pm, Ian Collins <> wrote:
    > >> Umesh wrote:
    > >> > Is there any way by which i can do it? Thanks.

    >
    > >> Yes

    >
    > >> --
    > >> Ian Collins.

    >
    > > But howwwwwwwwwwwwwwwwwww?????????????????????????????????

    >
    > Well, he says he's Sanchit, but he's acting like Umesh.
    >
    > Into the killfile with him.
    >
    > --
    > Richard Heathfield
    > "Usenet is a strange place" - dmr 29/7/1999http://www.cpax.org.uk
    > email: rjh at the above domain, - www.


    I am Sanchit only..... not umesh..... So I want to know how can i do
    this.... can anyone tell me this
    Sanchit, May 30, 2007
    #6
  7. Umesh

    Ian Collins Guest

    Sanchit wrote:
    > On May 30, 3:32 pm, Richard Heathfield <> wrote:
    >> Sanchit said:
    >>
    >>> On May 30, 1:00 pm, Ian Collins <> wrote:
    >>>> Umesh wrote:
    >>>>> Is there any way by which i can do it? Thanks.
    >>>> Yes
    >>>> --
    >>>> Ian Collins.
    >>> But howwwwwwwwwwwwwwwwwww?????????????????????????????????

    >> Well, he says he's Sanchit, but he's acting like Umesh.
    >>
    >> Into the killfile with him.
    >>

    *Please* don't quote people's signatures.
    >
    > I am Sanchit only..... not umesh..... So I want to know how can i do
    > this.... can anyone tell me this
    >

    Use an arbitrary precision library.

    --
    Ian Collins.
    Ian Collins, May 30, 2007
    #7
  8. "Umesh" <> wrote:

    > Is there any way by which i can do it?


    Is there any way you can do *WHAT*?

    Oh, I see you put most of your message body in the
    "Subject" header again. Tsk, tsk.

    I just got through writing functions to add, subtract, and
    multiply integers of up to two billion digits. (The greatest
    expressible number is well over 10^2000000000, which, in case
    you don't realize, is so big it's no longer "astronomical".
    Astronomy doesn't use numbers anywhere near that large.
    Combinatorial analysis, however, does.)

    Alas, though, my functions are in C++, not C.

    Basically, use strings of digits to represent the decimal
    expansions of integers. Do arithmetic manually on the
    individual digits, just like you do when adding numbers
    with pencil and paper. Don't forget to carry when the
    sum of any two digits (plus previous carry) is > 9.

    For what it's worth, the following may give you an idea of
    the algorithm you need. I'm afraid you'll have to translate
    it to C and intuit the unresolved references yourself.
    (If it doesn't make any sense to you, google "addition algorithm".)

    rhmath::BigNum rhmath::eek:perator+(const BigNum& a, const BigNum& b)
    {
    if ( a.neg() && !b.neg()) {return (( b)-(-a));} // could go either way
    if (!a.neg() && b.neg()) {return (( a)-(-b));} // could go either way
    if ( a.neg() && b.neg()) {return -((-a)+(-b));} // always negative

    // If we get to here, a and b are both non-negative integers.

    // Get sizes of a and b:
    long a_size = a.str().size();
    long b_size = b.str().size();

    // Get necessary size for C:
    long C_size = 1;
    if (a_size > C_size) {C_size = a_size;}
    if (b_size > C_size) {C_size = b_size;}
    C_size += 1;

    // Make a string of 0s of length C_size:
    std::string C (C_size, '0');

    register long i = 1;
    register int accum = 0;
    register int carry = 0;

    while ( i <= C_size )
    {
    // Reset Accumulator:
    accum = 0;

    if (i <= a_size) accum += ctoi(a.str()[a_size - i]);
    if (i <= b_size) accum += ctoi(b.str()[b_size - i]);
    if (carry > 0)
    {
    accum += carry;
    carry = 0;
    }

    // If overflow occured, transfer overflow to carry:
    while (accum > 9) {carry += 1; accum -= 10;}

    // Insert character representation of accumulator in C:
    C[C_size - i] = itoc(accum);

    // Move on to next-higher place value:
    ++i;
    }
    return BigNum (C);
    }

    --
    Cheers,
    Robbie Hatley
    lonewolf aatt well dott com
    triple-dubya dott tustinfreezone dott org
    Robbie Hatley, May 30, 2007
    #8
  9. Umesh

    Guest

    On May 30, 3:53 pm, Umesh <> wrote:
    > Is there any way by which i can do it? Thanks.


    I think you can reference the book << Numerical Recipes in C:The Art
    of Scientific Computing,Second Edition>>.
    , May 30, 2007
    #9
  10. Umesh

    user923005 Guest

    On May 30, 12:53 am, Umesh <> wrote:
    > Is there any way by which i can do it? Thanks.


    Use one of these thingies:
    http://www.medicis.polytechnique.fr/~pphd/mpfr/timings-220.html

    A web search will turn up stuff like this in just a few keystrokes and
    hey -- no waiting. Better yet, no punching bag duty for off-topic
    questions.

    IMO-YMMV.
    user923005, May 30, 2007
    #10
  11. Umesh

    Tim Smith Guest

    In article <>,
    Umesh <> wrote:

    > Is there any way by which i can do it? Thanks.


    Yes. You do it the same way you would do it by hand on paper. The main
    difference is that it might be more convenient to work in something
    other than base 10, depending on exactly how you have the numbers
    represented.

    If *all* you need to do is add numbers, this is sufficient. It will be
    easy to implement, and the time complexity will be O(N), where N is the
    number of digits in the larger number, and that is the best you can do,
    so no need to use an arbitrary precision library.

    However, if you need to multiple or divide numbers with 100 digits or
    more, then do as others have said, and find an arbitrary precision
    library that looks good to you and use it. While you can reasonably
    implement multiplication on your own following the common by-hand
    algorithm, that's O(N^2) to multiply two N digit numbers, and that is
    considerably slower than what you can do, but getting better involves
    things not for the feint of heart. (I left subtraction out...it's not
    really much different from addition, but you can blow it, so it can go
    either way as to whether doing it yourself or using a library is best if
    all you need is addition and subtraction).

    See Knuth volume 2 for the details. (If possible, see all editions of
    Knuth volume 2, because there were major changes to that part of the
    book between the first edition, the second edition, and the third
    edition. I think the second edition is the best if you want to
    understand this area, rather than just copy an algorithm out of the
    book).

    --
    --Tim Smith
    Tim Smith, May 31, 2007
    #11
  12. Umesh

    Tak Guest

    On 5ÔÂ30ÈÕ, ÏÂÎç3ʱ53·Ö, Umesh <> wrote:
    > Is there any way by which i can do it? Thanks.


    #include<iostream>
    #include<string>
    #include<iomanip>
    #include<algorithm>
    using namespace std;

    #define MAXN 9999
    #define DLEN 4

    class BigNum
    {
    private:
    int a[500];//¿ÉÒÔ¿ØÖÆ´óÊýµÄλÊý
    int len; //´óÊý³¤¶È
    public:
    BigNum(){len = 1;memset(a,0,sizeof(a));}
    BigNum(const int);
    BigNum(const char*);
    BigNum(const BigNum &);
    BigNum &operator=(const BigNum &);
    BigNum operator+(const BigNum &) const;
    BigNum operator-(const BigNum &) const;
    BigNum operator*(const BigNum &) const;
    BigNum operator/(const int &) const;
    BigNum operator^(const int &) const;
    int operator%(const int &) const;
    bool operator>(const BigNum & T)const;
    void print();
    };

    BigNum::BigNum(const int b)
    {
    int c,d = b;
    len = 0;
    memset(a,0,sizeof(a));
    while(d > MAXN)
    {
    c = d - (d / (MAXN + 1)) * (MAXN + 1);
    d = d / (MAXN + 1);
    a[len++] = c;
    }
    a[len++] = d;
    }

    BigNum::BigNum(const char*s)
    {
    int t,k,index,l;
    memset(a,0,sizeof(a));
    l = strlen(s);
    len = l / DLEN;
    if(l % DLEN)len++;
    index = 0;
    for(int i = l-1; i >= 0; i -= DLEN)
    {
    t = 0; k = i - DLEN + 1;
    if(k < 0) k = 0;
    for(int j = k; j <= i; j++)
    t = t * 10 + s[j] - '0';
    a[index++] = t;
    }
    }
    BigNum::BigNum(const BigNum & T) : len(T.len)
    {
    int i;
    memset(a,0,sizeof(a));
    for(i = 0; i < len; i++)a = T.a;
    }
    BigNum & BigNum::eek:perator=(const BigNum & n)
    {
    len = n.len;
    memset(a,0,sizeof(a));
    for(int i = 0; i < len; i++)
    a = n.a;
    return *this;
    }
    BigNum BigNum::eek:perator+(const BigNum & T) const
    {
    BigNum t(*this);
    int i,big;//λÊý
    big = T.len > len ? T.len : len;
    for(i = 0; i < big; i++)
    {
    t.a +=T.a;
    if(t.a > MAXN)
    {
    t.a[i+1]++;
    t.a -= MAXN+1;
    }
    }
    if(t.a[big] != 0)
    t.len = big + 1;
    else
    t.len = big;
    return t;
    }
    BigNum BigNum::eek:perator-(const BigNum & T) const
    {
    int i,j,big;
    bool flag;
    BigNum t1,t2;
    if(*this>T)
    {
    t1 = *this;
    t2 = T;
    flag = 0;
    }
    else
    {
    t1 = T;
    t2 = *this;
    flag = 1;
    }
    big = t1.len;
    for(i = 0; i < big; i++)
    {
    if(t1.a < t2.a)
    {
    j = i + 1;
    while(t1.a[j] == 0) j++;
    t1.a[j--]--;
    while(j > i) t1.a[j--] += MAXN;
    t1.a += MAXN + 1 - t2.a;
    }
    else
    t1.a -= t2.a;
    }
    t1.len = big;
    while(t1.a[len - 1] == 0 && t1.len > 1)
    {
    t1.len--;
    big--;
    }
    if(flag)
    t1.a[big-1] = 0 - t1.a[big-1];
    return t1;
    }
    BigNum BigNum::eek:perator*(const BigNum & T) const
    {
    BigNum ret;
    int i,j,up;
    int temp,temp1;
    for(i = 0 ; i < len ; i++)
    {
    up = 0;
    for(j = 0 ; j < T.len ; j++)
    {
    temp = a * T.a[j] + ret.a[i+j] + up;
    if(temp > MAXN)
    {
    temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
    up = temp / (MAXN + 1);
    ret.a[i + j] = temp1;
    }
    else
    {
    up = 0;
    ret.a[i + j] = temp;
    }
    }
    if(up != 0)
    ret.a[i + j] = up;
    }
    ret.len = i + j;
    while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
    return ret;
    }
    BigNum BigNum::eek:perator/(const int & b) const
    {
    BigNum ret;
    int i,down = 0;
    for(i = len-1; i >= 0; i--)
    {
    ret.a = (a + down * (MAXN + 1)) / b;
    down = a + down * (MAXN + 1) - ret.a * b;
    }
    ret.len = len;
    while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
    return ret;
    }
    int BigNum::eek:perator %(const int & b) const
    {
    int i,d = 0;
    for (i = len-1; i >= 0; i--)
    {
    d = ((d * (MAXN+1)) % b + a) % b;
    }
    return d;
    }
    BigNum BigNum::eek:perator^(const int & n) const
    {
    BigNum t,ret(1);
    if(n < 0) exit(-1);
    if(n == 0) return 1;
    if(n == 1) return *this;
    int m = n;
    while(m > 1)
    {
    t = *this;
    for(int i=1;i<<1<=m;i<<=1)
    t=t*t;
    m -= i;
    ret = ret*t;
    if(m == 1)ret = ret * (*this);
    }
    return ret;
    }
    bool BigNum::eek:perator>(const BigNum & T) const
    {
    int ln;
    if(len > T.len)
    return true;
    else if(len == T.len)
    {
    ln = len - 1;
    while(a[ln] == T.a[ln] && ln >= 0) ln--;
    if(ln >= 0 && a[ln] > T.a[ln])
    return true;
    else
    return false;
    }
    else
    return false;
    }
    void BigNum::print()
    {
    int i;
    cout << a[len-1];
    for(i = len-2; i >= 0; i--)
    {
    cout.width(DLEN);
    cout.fill('0');
    cout << a[i];
    }
    cout << endl;
    }[/i]
    Tak, Jun 1, 2007
    #12
  13. Umesh

    Flash Gordon Guest

    Tak wrote, On 01/06/07 05:50:
    > On 5ÔÂ30ÈÕ, ÏÂÎç3ʱ53·Ö, Umesh <> wrote:
    >> Is there any way by which i can do it? Thanks.

    >
    > #include<iostream>


    <snip>

    Please read the name of the group again. This group is for C, there is a
    separate group for C++.
    --
    Flash Gordon
    Flash Gordon, Jun 1, 2007
    #13
  14. Tak <> writes:
    > On 5ÔÂ30ÈÕ, ÏÂÎç3ʱ53·Ö, Umesh <> wrote:
    >> Is there any way by which i can do it? Thanks.

    >
    > #include<iostream>
    > #include<string>
    > #include<iomanip>
    > #include<algorithm>
    > using namespace std;

    [snip]

    This is comp.lang.c. comp.lang.c++ is down the hall, just past the
    water cooler, second door on the left.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Jun 1, 2007
    #14
  15. On May 29, 11:06 pm, "Robbie Hatley" <> wrote:
    > I just got through writing functions to add,
    > subtract, and multiply integers ...
    > (The greatest expressible number is well over
    > 10^2000000000, which, in case
    > you don't realize, is so big it's no
    > longer "astronomical".


    Here's a program at Robert Munafo's site:
    http://home.earthlink.net/~mrob/pub/perl/hypercalc.txt
    which operates on *much* bigger numbers than the
    tiny ones you mention :) It's written in perl;
    sorry if that makes it off-topic here.

    For a good time, browse around at Mr. Munafo's
    site. He has some interesting pages, including
    mention of some integers which are too
    large even for his hypercalc program.

    James Dow Allen
    James Dow Allen, Jun 1, 2007
    #15
  16. Umesh

    Tak Guest

    On 6ÔÂ1ÈÕ, ÏÂÎç2ʱ30·Ö, Flash Gordon <> wrote:
    > Tak wrote, On 01/06/07 05:50:
    >
    > > On 5ÔÂ30ÈÕ, ÏÂÎç3ʱ53·Ö, Umesh <> wrote:
    > >> Is there any way by which i can do it? Thanks.

    >
    > > #include<iostream>

    >
    > <snip>
    >
    > Please read the name of the group again. This group is for C, there is a
    > separate group for C++.
    > --
    > Flash Gordon


    The key is maybe I could help to solve the asker's puzzle.
    It's more important than whether it is a group for c or c++,I think.
    Tak, Jun 1, 2007
    #16
  17. Tak said:

    > On 6?1?, ??2?30?, Flash Gordon <> wrote:
    >> Tak wrote, On 01/06/07 05:50:
    >>
    >> > On 5?30?, ??3?53?, Umesh <> wrote:
    >> >> Is there any way by which i can do it? Thanks.

    >>
    >> > #include<iostream>

    >>
    >> <snip>
    >>
    >> Please read the name of the group again. This group is for C, there
    >> is a separate group for C++.

    >
    > The key is maybe I could help to solve the asker's puzzle.


    Here are some other puzzles you might be able to solve: How come a
    guitar capo knows all the easy chords? Why are meteorologists so lousy
    at their job? What does "prime number" mean. Who was Nelson? Who is
    Christine Perfect? What type is 'x'? If four and a half chickens take
    four and a half days to lay four and a half eggs, how many eggs can
    half a dozen chickens lay in half a dozen days? What is the difference
    between a dwarf and a gnome? What's the average rainfall of the Amazon
    basin?

    > It's more important than whether it is a group for c or c++,I think.


    You might think that, but lots of us disagree with you, and for
    excellent reasons. Please note that the answer to at least one of the
    questions above depends on what programming language you are using.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
    Richard Heathfield, Jun 1, 2007
    #17
  18. Umesh

    Tak Guest

    On 6ÔÂ1ÈÕ, ÏÂÎç6ʱ09·Ö, Richard Heathfield <> wrote:

    > Here are some other puzzles you might be able to solve: How come a
    > guitar capo knows all the easy chords? Why are meteorologists so lousy
    > at their job? What does "prime number" mean. Who was Nelson? Who is
    > Christine Perfect? What type is 'x'? If four and a half chickens take
    > four and a half days to lay four and a half eggs, how many eggs can
    > half a dozen chickens lay in half a dozen days? What is the difference
    > between a dwarf and a gnome? What's the average rainfall of the Amazon
    > basin?


    haha...I really want to know the answers to these questions.
    tell me please, thank you.
    Tak, Jun 1, 2007
    #18
  19. Tak said:

    > On 6?1?, ??6?09?, Richard Heathfield <> wrote:
    >
    >> Here are some other puzzles you might be able to solve: How come a
    >> guitar capo knows all the easy chords? Why are meteorologists so
    >> lousy at their job? What does "prime number" mean. Who was Nelson?
    >> Who is Christine Perfect? What type is 'x'? If four and a half
    >> chickens take four and a half days to lay four and a half eggs, how
    >> many eggs can half a dozen chickens lay in half a dozen days? What is
    >> the difference between a dwarf and a gnome? What's the average
    >> rainfall of the Amazon basin?

    >
    > haha...I really want to know the answers to these questions.
    > tell me please, thank you.


    The point, I hope, is clear. The sum of human knowledge, whilst
    remaining pathetically finite, is nevertheless so astoundingly large
    that the only way we can hope to make sense of it is to categorise.

    It is for that reason that we have multiple newsgroups, rather than just
    one. People seek out newsgroups that deal with the topics in which they
    are interested. If those newsgroups get choked up with all kinds of
    other stuff, they become less useful.

    *This* newsgroup is for discussing C. If you want to discuss C++, that's
    fine, but comp.lang.c++ is the newsgroup in which to do it.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
    Richard Heathfield, Jun 1, 2007
    #19
  20. Umesh

    Tak Guest

    On 6ÔÂ1ÈÕ, ÏÂÎç7ʱ41·Ö, Richard Heathfield <> wrote:
    > Tak said:
    >
    > > On 6?1?, ??6?09?, Richard Heathfield <> wrote:

    >
    > >> Here are some other puzzles you might be able to solve: How come a
    > >> guitar capo knows all the easy chords? Why are meteorologists so
    > >> lousy at their job? What does "prime number" mean. Who was Nelson?
    > >> Who is Christine Perfect? What type is 'x'? If four and a half
    > >> chickens take four and a half days to lay four and a half eggs, how
    > >> many eggs can half a dozen chickens lay in half a dozen days? What is
    > >> the difference between a dwarf and a gnome? What's the average
    > >> rainfall of the Amazon basin?

    >
    > > haha...I really want to know the answers to these questions.
    > > tell me please, thank you.

    >
    > The point, I hope, is clear. The sum of human knowledge, whilst
    > remaining pathetically finite, is nevertheless so astoundingly large
    > that the only way we can hope to make sense of it is to categorise.
    >
    > It is for that reason that we have multiple newsgroups, rather than just
    > one. People seek out newsgroups that deal with the topics in which they
    > are interested. If those newsgroups get choked up with all kinds of
    > other stuff, they become less useful.
    >
    > *This* newsgroup is for discussing C. If you want to discuss C++, that's
    > fine, but comp.lang.c++ is the newsgroup in which to do it.


    I confess you are right.
    but should we say "sorry , we can't help you, please goto comp.lang.c+
    + where may help you"?
    Tak, Jun 1, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. anand_ps
    Replies:
    3
    Views:
    1,578
    Ryan Stewart
    Jan 19, 2005
  2. Replies:
    2
    Views:
    323
    Ryan Stewart
    Jan 20, 2005
  3. Replies:
    8
    Views:
    6,687
    Neredbojias
    Dec 9, 2005
  4. fred
    Replies:
    3
    Views:
    273
    Zifud
    Mar 17, 2005
  5. Replies:
    5
    Views:
    880
Loading...

Share This Page