I am working on a program in C as a part of Homework in which I have to get the product of two long numbers which are taken as character string. eg: 123456789021 and 132456789098. Since it is taken as a string, I converted them to long long int for the multiplication. But the resulting product will be very large(larger than long long int I guess). Can anyone please suggest me a method to perform this multiplication?
+11
A:
Here's one approach: Consider how you would multiply these numbers by hand, on paper. Implement this method in C. You will have to discover:
- how to break up an integer (represented as a string) into digits
- how to convert each digit back to an integer
0 <= d < 10 - how to manage arrays of digits (ie. how big should you make the arrays?)
- how to write the loop(s) you might need to implement multiplication
- how to manage carrying products from one digit to the next
- how to convert those digits back to characters for output
Greg Hewgill
2009-12-06 19:13:26
And if it weren't for the fact that your input and output were in base 10, you could do all this more efficiently by using base 2^32 (digits held in a 64 bit type) or base 2^16 (in a 32 bit type) instead of base 10.
Steve Jessop
2009-12-06 23:10:48
A:
You can use a library for large integer arithmetik, Wikipedia has a list here.
Doc Brown
2009-12-06 19:19:48
Although large number libraries are often helpful, I believe it would go against the thought and purpose behind the problem.
JTA
2009-12-06 19:24:55
+1
A:
usually big integers represented as byte arrays. You can look at Microsoft's BigInteger implementation in DLR. I think they've used algorithms developed by Knuth
Trickster
2009-12-06 19:20:43
A:
Another approach would be to multiply the numbers as float/double and stip off the decimal when displaying the results.
Pratik Bhatt
2009-12-06 19:28:35
That won't give an exact answer if there are too many digits though. It may be good enough depending on the use case, but I don't think that's the point of the assignment.
Matthew Crumley
2009-12-06 19:41:23
+1
A:
Check this BigInteger library and a very basic sample code from World of Seven.
If you are interested in some of my home cooked codes in C (only multiplication) :
////////////////////////////////////////////////////////////////////////////////
Code removed after I checked the home-work tag ;)
///////////////////////////////////////////////////////////////////////////////////////
This works in some of the earlier programming contests I had participated ;)But if you are looking for even faster multiplication algorithm you can Implement Karatsuba algorithm,I personally use this now in real time contest.
nthrgeek
2009-12-07 04:12:22