1

I have an assignment due the following week that requires me to multiply two thousand digit binary numbers. The numbers are read from 2 txt files.

Some of the solutions I tried:

1) Used int, long int, and long long int but none of them can hold a thousand digits

2) Read each text file into an array of 1000 units, then into a smaller array of 100 units, each unit holding 10 digits. Unfortunately, this would mean the multiplication wouldn't work properly. And I can't do something like array1*array2.

What I haven't tried, mainly because I don't think that would work anyway, is converting the binary number to a decimal number, as the value is still too large to fit in any variation of int.

Anyone have any ideas on how to deal with this? I can write the rest of the program no problem, but I'm struggling with figuring out a way to do the multiplication. I've even done multiple Google Searches and also checked the "similar topics" suggestions that pop up, but nothing that fits my description specifically. Thanks in advance for any help provided, even just pointers that may lead to the solution. If more details are needed, do let me know and I'll get back to it immediately.

Jass5991
  • 31
  • 3
  • I'm feel like the professor wants you to implement the multiplication yourself. If the assignment is to find a library that can do it, then that's an odd assignment. Think about how you performed multiplication in elementary school. There are tonnes of algorithms for doing multiplication which I'm sure you can turn into code if you think long enough about it. – flakes Jul 15 '18 at 10:41
  • @flakes that's probably what he wants, true, however I'm having difficulty around the implementation of school grade "by hand" multiplication. Can't quite wrap my head around it. I'll refer to the link that was provided when this question was marked as a duplicate. Also, considering it's binary multiplication, I'd have to ensure there are only ones and zeros in the final answer, but I reckon I can sort that out without much issue. As I said, it's the multiplication giving me problems right now. Thanks again! – Jass5991 Jul 15 '18 at 10:46
  • Yeah, there are a lot of moving parts in multiplication; it's not exactly a trivial problem. Just a hint; It might be easier if you work with an array of chars containing `'0'`, or `'1'` and perform the calculation on the arrays without ever converting the number to the decimal domain. It wont be the most efficient way, but I believe It will reduce the amount of work you have do. – flakes Jul 15 '18 at 10:53
  • @Jass5991 The easiest way to wrap your head around it, is to recall how you do multiplication manually with pencil and paper and digit by digit. If you use `char`'s to represent each digit of the large numbers, it's merely the same. – πάντα ῥεῖ Jul 15 '18 at 10:55
  • Thank you, @flakes and @πάντα ῥεῖ, I'll look into both of those, but for now, what I'm trying to do is create a 2-dimensional array called `ans` of length 1000000 by 1000000 and create a separate 1-dimensional array to capture the final answer after summing down the `ans` array. I've no idea if this would work, but it's the only thing I can think of. Should this fail, especially considering I haven't done anything like this before, and my skill is beginner at best, I'll definitely revisit the comments and try your methods. Thank you both once again. – Jass5991 Jul 15 '18 at 11:03
  • Start with that and start small. Maybe 10 digit numbers first. That's n^2 space complexity. You should be able to do it with 3 or 4 arrays if you sum as you go. End target should be n space complexity. Good luck! :) – flakes Jul 15 '18 at 11:10

0 Answers0