big integers

Discussion in 'C++' started by adrin, Jan 17, 2005.

  1. adrin

    adrin Guest

    hello,

    i have to write a simple class to represent big integer numbers and
    implement basic arithmetical operations such as + - * / modulo, etc.
    all will be written in c++ under linux OS on x86 architecture (however
    that's not that important)

    could you tell me what is an idea behind such construction?
    i think about creating an dynamic array in which single digits in 255 base
    will be stored(one byte). it is a common solution way when dealing with
    BigIntegers isnt it?

    adding would be implemented by adding digits, bit by bit, but how can i
    solve the problem with a carry? maybe writing accessing carry flag using
    asm code is a good solution? is there a better way?

    and what about multiplication? is it made by adding the number repeatedly?

    maybe you have a relevant tutorial or howto :)?


    --
    *a*
     
    adrin, Jan 17, 2005
    #1
    1. Advertising

  2. adrin

    Alex Vinokur Guest

    "adrin" <> wrote in message news:csh4av$ofh$...
    > hello,
    >
    > i have to write a simple class to represent big integer numbers and
    > implement basic arithmetical operations such as + - * / modulo, etc.
    > all will be written in c++ under linux OS on x86 architecture (however
    > that's not that important)
    >
    > could you tell me what is an idea behind such construction?
    > i think about creating an dynamic array in which single digits in 255 base
    > will be stored(one byte). it is a common solution way when dealing with
    > BigIntegers isnt it?
    >
    > adding would be implemented by adding digits, bit by bit, but how can i
    > solve the problem with a carry? maybe writing accessing carry flag using
    > asm code is a good solution? is there a better way?
    >
    > and what about multiplication? is it made by adding the number repeatedly?
    >
    > maybe you have a relevant tutorial or howto :)?
    >

    [snip]

    Look at C++ BigInt class at
    http://groups-beta.google.com/group/alt.sources/browse_frm/thread/e578379447411268/0761372dd0c1490c

    --
    Alex Vinokur
    email: alex DOT vinokur AT gmail DOT com
    http://mathforum.org/library/view/10978.html
    http://sourceforge.net/users/alexvn
     
    Alex Vinokur, Jan 17, 2005
    #2
    1. Advertising

  3. adrin wrote:
    > i have to write a simple class to represent big integer numbers and
    > implement basic arithmetical operations such as + - * / modulo, etc.
    > all will be written in c++ under linux OS on x86 architecture (however
    > that's not that important)
    >
    > could you tell me what is an idea behind such construction?


    The idea is to store numbers that your architecture doesn't allow to
    store using normal ways.

    > i think about creating an dynamic array in which single digits in 255 base
    > will be stored(one byte). it is a common solution way when dealing with
    > BigIntegers isnt it?


    To know about what's common, you need to set the sampling parameters.

    > adding would be implemented by adding digits, bit by bit,


    Why bit by bit? Couldn't you simply add two 255-base digits using normal
    [unsigned] octet rules? Especially if your platform has 8-bit bytes, it
    would be really simple, no?

    > but how can i
    > solve the problem with a carry?


    You keep the carry flag and add it to the next pair. Just like any other
    long addition/subtraction/multiplication/division...

    > maybe writing accessing carry flag using
    > asm code is a good solution? is there a better way?


    You don't need asm to write C++. If I were your instructor, I would
    fail you for using asm, actually.

    > and what about multiplication? is it made by adding the number repeatedly?


    Well, sort of. For every multidigit numbers A and B you can define the
    pairs of single-digit multiplications which need to be added to each other
    later.

    > maybe you have a relevant tutorial or howto :)?


    www.google.com

    And come back when you have a C++ language question.

    V
     
    Victor Bazarov, Jan 17, 2005
    #3
  4. adrin

    adrin Guest

    adrin, Jan 17, 2005
    #4
  5. adrin

    adrin Guest

    Victor Bazarov <> wrote in
    news:SHUGd.36146$01.us.to.verio.net:

    > Why bit by bit? Couldn't you simply add two 255-base digits using normal
    > [unsigned] octet rules? Especially if your platform has 8-bit bytes, it
    > would be really simple, no?


    maybe it'll sound stupid, but what do you mean by octet rules?


    thanks for help,
    --
    *a*
     
    adrin, Jan 17, 2005
    #5
  6. adrin wrote:
    > Victor Bazarov <> wrote in
    > news:SHUGd.36146$01.us.to.verio.net:
    >
    >
    >>Why bit by bit? Couldn't you simply add two 255-base digits using normal
    >>[unsigned] octet rules? Especially if your platform has 8-bit bytes, it
    >>would be really simple, no?

    >
    >
    > maybe it'll sound stupid, but what do you mean by octet rules?


    The rules your compiler is likely to follow.

    Your compiler is likely to have a type for unsigned char that has 8 bits.
    Those are octets. Add two together in an unsigned short or an unsigned
    int, or multiply them, or whatever, and your compiler will happily do it
    for you (using its own rules for those operations). If your compiler does
    not support 8-bit bytes, you can still use the 8 bits out of your [larger]
    char and perform those operations inside some larger types.

    Perhaps I used the wrong word to state the obvious :-/
     
    Victor Bazarov, Jan 17, 2005
    #6
  7. adrin

    Axel Guest

    adrin wrote:
    > hello,
    >
    > i have to write a simple class to represent big integer numbers and
    > implement basic arithmetical operations such as + - * / modulo, etc.
    > all will be written in c++ under linux OS on x86 architecture (however
    > that's not that important)
    >
    > could you tell me what is an idea behind such construction?
    > i think about creating an dynamic array in which single digits in 255 base
    > will be stored(one byte). it is a common solution way when dealing with
    > BigIntegers isnt it?
    >
    > adding would be implemented by adding digits, bit by bit, but how can i
    > solve the problem with a carry? maybe writing accessing carry flag using
    > asm code is a good solution? is there a better way?
    >
    > and what about multiplication? is it made by adding the number repeatedly?
    >
    > maybe you have a relevant tutorial or howto :)?
    >
    >

    Another advice: Use gmp
    (http://www.swox.com/gmp/), which is a
    big number library for c, coming along
    with comfortable c++ wrapper classes
    (i.e., overloaded operators etc.).

    Answering your question whether
    multiplication is done by adding numbers
    repeatedly: for large numbers there are
    much more clever ways of multiplication
    (karatsuba and fft-based algorithms).
    gmp also supports such fast arithmetic,
    which is a good reason not do implement
    things yourself - algorithms for fast
    arithmetic are _very_ complicated to
    implements.
     
    Axel, Jan 18, 2005
    #7
  8. Axel wrote:
    > [...]
    > Answering your question whether multiplication is done by adding numbers
    > repeatedly: for large numbers there are much more clever ways of
    > multiplication (karatsuba and fft-based algorithms). gmp also supports
    > such fast arithmetic, which is a good reason not do implement things
    > yourself - algorithms for fast arithmetic are _very_ complicated to
    > implements.


    Which may actually defeat the purpose. I think that the original query
    was because of the homework. Nobody has to (or would) "write a simple
    class" when there are industrial-strength libraries lying around on the
    'Net *unless* that was the actual task: to implement things yourself.

    V
     
    Victor Bazarov, Jan 18, 2005
    #8
  9. adrin

    Flzw Guest

    "adrin" <> wrote in message
    news:csh4av$ofh$...
    > hello,
    >
    > i have to write a simple class to represent big integer numbers and
    > implement basic arithmetical operations such as + - * / modulo, etc.
    > all will be written in c++ under linux OS on x86 architecture (however
    > that's not that important)
    >
    > could you tell me what is an idea behind such construction?
    > i think about creating an dynamic array in which single digits in 255 base
    > will be stored(one byte). it is a common solution way when dealing with
    > BigIntegers isnt it?
    >
    > adding would be implemented by adding digits, bit by bit, but how can i
    > solve the problem with a carry? maybe writing accessing carry flag using
    > asm code is a good solution? is there a better way?
    >
    > and what about multiplication? is it made by adding the number repeatedly?
    >
    > maybe you have a relevant tutorial or howto :)?
    >


    A better way of doing so is to use the fact that every integer can be
    decomposed in a factorial sum (don't know if that is the good english term)
    meaning any integer can be written like this : x1*y1! + x2*y2! + x3*y3! +
    .....xn*yn!

    You can then "'easily" (depends on your maths skills actually) do addition,
    multiplication can be a little trickier though
     
    Flzw, Jan 18, 2005
    #9
    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. hobbs

    Too big integers

    hobbs, Dec 25, 2003, in forum: C Programming
    Replies:
    39
    Views:
    1,014
    Joona I Palaste
    Dec 31, 2003
  2. Shaguf
    Replies:
    0
    Views:
    360
    Shaguf
    Dec 24, 2008
  3. Shaguf
    Replies:
    0
    Views:
    457
    Shaguf
    Dec 26, 2008
  4. Shaguf
    Replies:
    0
    Views:
    242
    Shaguf
    Dec 26, 2008
  5. Shaguf
    Replies:
    0
    Views:
    218
    Shaguf
    Dec 24, 2008
Loading...

Share This Page