CrazyEngineers Logo

Programming doubt: Mathematical Operations on Very Large Numbers

Hi All,

A programming doubt:-

We need to multiply (or add) very large numbers. By very large i mean that there might be an overflow problem i.e.

If c = a*b then c will not fit into 32 bit or 64 bit memory storage meant for integers or long long integers.

How do we go about this?

I know few methods (for Product):-
1. Long Hand Multiplication (School method)
2. Karatsuba algorithm
3. Fast Fourier Transform and Inverse Transform method.

I tried 1st method and it worked out pretty well (speed efficiency not at all good for very large numbers!!).
Karatsuba does well for "astronomically big" numbers.

Never tried Fourier method. Any ideas on this??

Apart from these can we do something using "Bitwise operations"??

Can't we store product in separate 32 bits (or 64 bits) (separate bytes) and also keep track of each bit??

I would like to participate in discussions (with my stupid doubts) if someone gives a right kick to this topic.

Thanks in advance 😀

Replies

  • sookie
    sookie
    Hi mech_guy,

    Very good topic 😁. Man, I also face similar type of problem. Let me take an example- I want to write a program that calculates the factorial of 100(or any number 'n' such that n>20) but prints the output in pure integer form (not in exponential form) ? How should I go for it in Java? Any ideas ? 😕 ? Just only give the idea of how to print long integer type values(like 100!). I am not asking for full program.


    Thanks !
  • Manish Goyal
    Manish Goyal
    sookie
    Hi mech_guy,

    Very good topic 😁. Man, I also face similar type of problem. Let me take an example- I want to write a program that calculates the factorial of 100(or any number 'n' such that n>20) but prints the output in pure integer form (not in exponential form) ? How should I go for it in Java? Any ideas ? 😕 ? Just only give the idea of how to print long integer type values(like 100!). I am not asking for full program.


    Thanks !
    helloo sookie
    i am not sure bt if you use concept of union in c++
    you will get what you want
    try it if you can
  • vik001ind
    vik001ind
    Solution of this problem lies in linked list of data structures.
    For example you wanna add two very large numbers say 100 digits each, what you can do here is create a linked list for 1st no. having 5 digits in each node starting from right end of digit. Similarly for 2nd no., add both & put the result in another similar linked list, if addition leads to 6 digits, store only 5 digits in a node & add leftmost digit to next node & proceed further in similar fashion. You can develop a C/C++ program using pointers for linked list.
    Eg. 232222323112121 in linked list form
    node3(23222)<--node2(23231)<--node1(12121)
    Refer "Data Stuctures by Tenonbaum" for detail usage.
    You can do similar work for 100! calculation.

You are reading an archived discussion.

Related Posts

Your enemy's (GOOGLE) enemy(APPLE) is your(MS) friend

You , you read it right. Google is emerging as a very silent super power in the world of computers. First though the concentration was only on web, it has...

Anyone try out these new mobile projectors?

I was reading in a commercial real estate forum about these new mobile projectors. I haven't seen one myself - figured this would be a better forum to ask. Anyone...

sixth sense technology ?

have u ever tried to inter face your brain to some thing, well here is the first step. Pattie Maes demos the Sixth Sense | Video on TED.com well its...

SCJA is compulsory or not before SCJA.....

can anyone tell me that pass the SCJA(sun certified java asso.) is compulsory before SCJP..... cause SCJA is only theory n i don't want to give that exam...

Oersted's birthday

hi Lets all wish Hans Christian Oersted a happy birthday he discovered electriccurrents,magnetic fields both form an important part of electromagnetism.