Was wondering if I could enlist your expertise to help me with this problem.
Basically, I have to write a program)that is capable of performing basic arithmetic with very large numbers (the exact range we were given was -9*10^100 to 9*10^100).
What is supposed to happen is that the user enters string representation of these numbers, then the program converts them to a workable data type, and performs a user defined operation on them (addition, subtraction, multiplication).
My solution has been so far to convert each number into an integer array with each element being a digit in the in the actual large number. (I should probably mention now that I have to do this in C#.)
After both numbers are entered and converted to arrays I basically do the arithmetic digit by digit, elementary-school style.
Obviously, with this method, I would need code that allows the program to "carry the one" when the sum would be more than 1 digit. I already have code that does this.
My problem is with the subtraction. I can't think of a way to make the program "borrow" from another digit in the number, if it needs to. This is what I truly need help with. If you can suggest a way I can implement this OR suggest an entirely different method of subtraction that would work, I would be so, so grateful.
Note that if a class already exists that does this, I'm not allowed to use it. I basically have to re-invent the wheel on this one. I can provide any sample code if you wish.
And I apologize if I wrote way too much. I'm just trying to be as clear as possible,
Thanks.
Name:
Anonymous2012-02-16 0:11
My problem is with the subtraction. I can't think of a way to make the program "borrow" from another digit in the number, if it needs to.
Just use the N's complement to negate the subtrahend and then add them together. sub(a,b) == add(a,neg(b)) Note that if a class already exists that does this, I'm not allowed to use it.
For reference, it's the BigInteger class.
And yeah I was thinking of BigInteger when I said that, but I decided not to be specific in case someone suggested one I wasn't aware of
Name:
Anonymous2012-02-16 0:18
My solution has been so far to convert each number into an integer array with each element being a digit in the in the actual large number.
That's stupid for several reasons.
Name:
Anonymous2012-02-16 0:22
>>4
If there is a better way to do it, I'm all ears. Please enlighten me.
>>4
Or at least tell me the reasons why it's stupid so I have something to consider
Name:
Anonymous2012-02-16 0:37
>>5,6
You're using (what I'm going to presume is 32 or 64 bits, whatever the size of an integer is in C#) to store just a single character. (Binary) Computers are good at doing binary shit, you should store it in binary using just a couple of integers so that you don't waste a shit ton of memory.
Name:
Anonymous2012-02-16 1:30
>>7
I see your point but for someone of my skill level, it will be harder to manage in binary. Besides, it's a just a stupid assignment for college, it's gonna get graded and discarded.
Name:
Anonymous2012-02-16 2:15
Use all 32 bits.
What's your decimal print algorithm? I imagine it would be easy with only a single digit; it's a bit more complex (but not by much) with integers represnting a variable amount of digits
>>8
assuming you work on 64 bit architecture, i guarantee that doing it in base 18446744073709551616 will be much faster, easier and memory efficient than in base 10.
in other words, let your number be represented as array of uint64_t, every element of your array represents a digit of your number.
>>10
You can use 8-bit variables to store the digits, idiot.
Name:
Anonymous2012-02-18 9:56
You are supposed to implement 'bcd' arithmetic, exactly the way you do it by hand.
It will be stupidly slow and not worth using but if that is an assignment it will suffice.
Name:
Anonymous2012-02-18 11:12
C# runs in a managed GC-ed environment. It really does NOT matter if he is using int.
Hey >>1-chan, if you wanna look a little cooler, you can use a short array. They use a little less bytes than a regular int and probably won't mess up your code.
As for the subtraction, make a routine that thinks on something like this:
240
-45
I am assuming you are using 2 arrays, and the answer will be in the first one, where is the number that is being subtracted on.
"well, 2 minus 0 is two. next!
4 minus 4 is 0. next!
0 minus 5? oops. I am going to borrow from the house directly above.
There is 0? I can't take from 0. Oops. I am going to borrow from the house directly above.
There is 2? Great. Subtract one from this, add 10 to the inferior house, then go back to the inferior house //use recursion to achieve this.
There is 10? Great. Subtract one from this, add 10 to the inferior house, then go back to the inferior house.
10 minus 5 is 5.
No nexts? Print the result.
>>15
I'm not him, but that's easy. Just check if n2 is bigger than n1, and if true, do the reverse order subtraction and switch the + to a - (a signature bit or whatever you are using).
Name:
Anonymous2012-02-18 19:44
>>1
Jew all of the code from GMP, and then fix the multiplication algorithm so it isn't a piece of shit.
>>14,16
Are you seriously too retarded to think up a subtraction algorithm that works without special cases?
Name:
Anonymous2012-02-18 21:37
>>18
maybe you should try to produce a subtraction algorithm that operates without a special case, when the numbers are represented in (sign,magnitude).
I wrote myself a small BigInt library in C once, and it worked.
It shouldn't be hard. Follow your instincts.
Name:
Anonymous2012-02-20 5:04
>>1
... why don't you just read in the strings with the long numbers, then start another program with the numbers and the operation as parameters.
Said program should be written in a language that normally works with large numbers like this, like any sort of LISP, Haskell or Erlang. That program should return the number again through stdout, which you read with your C# program.
... if the whole purpose of the program is to calculate with big numbers (read: it's not something that the program also needs to do), then maybe using C# for this is stupid in the first place. "The right tool for the right job."
Oh, and if this is a programming assignment from a teacher: go do your fucking homework yourself, faggot.