CrazyEngineers
CrazyEngineers

  • Programming doubt: Mathematical Operations on Very Large Numbers

    mech_guy

    Member

    Updated: Oct 27, 2024
    Views: 997
    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 😀
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • sookie

    Member • Aug 30, 2009

    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 !
    Are you sure? This action cannot be undone.
    Cancel

  • Manish Goyal

    Member • Sep 27, 2009

    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
    Are you sure? This action cannot be undone.
    Cancel

  • vik001ind

    Member • Sep 28, 2009

    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.
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register