C++ BigInt multiplication conceptual problem
- by Kapo
I'm building a small BigInt library in C++ for use in my programming language.
The structure is like the following:
short digits[ 1000 ];
int len;
I have a function that converts a string into a bigint by splitting it up into single chars and putting them into digits.
The numbers in digits are all reversed, so the number 123 would look like the following:
digits[0]=3 digits[1]=3 digits[2]=1
I have already managed to code the adding function, which works perfectly.
It works somewhat like this:
overflow = 0
for i ++ until length of both numbers exceeded:
add numberA[ i ] to numberB[ i ]
add overflow to the result
set overflow to 0
if the result is bigger than 10:
substract 10 from the result
overflow = 1
put the result into numberReturn[ i ]
(Overflow is in this case what happens when I add 1 to 9: Substract 10 from 10, add 1 to overflow, overflow gets added to the next digit)
So think of how two numbers are stored, like those:
0 | 1 | 2
---------
A 2 - -
B 0 0 1
The above represents the digits of the bigints 2 (A) and 100 (B).
- means uninitialized digits, they aren't accessed.
So adding the above number works fine: start at 0, add 2 + 0, go to 1, add 0, go to 2, add 1
But:
When I want to do multiplication with the above structure, my program ends up doing the following:
Start at 0, multiply 2 with 0 (eek), go to 1, ...
So it is obvious that, for multiplication, I have to get an order like this:
0 | 1 | 2
---------
A - - 2
B 0 0 1
Then, everything would be clear: Start at 0, multiply 0 with 0, go to 1, multiply 0 with 0, go to 2, multiply 1 with 2
How can I manage to get digits into the correct form for multiplication?
I don't want to do any array moving/flipping - I need performance!
