C++ BigInt multiplication conceptual problem
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 followi开发者_StackOverflow中文版ng:
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
digitsinto the correct form for multiplication? - I don't want to do any array moving/flipping - I need performance!
- Why are you using
shortto store digits in the[0..9]acharwould suffice - You're thinking incorrectly about the multiplication. In the case of multiplication you need a double for loop that multiplies
Bwith each digit inAand sums them up shifted with the correct power of ten.
EDIT: Since some anonymous downvoted this without a comment this is basically the multiplication algorithm:
bigint prod = 0
for i in A
prod += B * A[i] * (10 ^ i)
The multiplication of B with A[i] is done by an extra for loop where you also keep track of the carry. The (10 ^ i) is achieved by offseting the destination indices since bigint is in base 10.
Your example in the question is over-engineering at its best in my opinion. Your approach will end up even slower than normal long multiplication, because of the shear number of multiplications and additions involved. Don't limit yourself to working at one base digit at a time when you can multiply approximately 9 at a time!. Convert the base10 string to a hugeval, and then do operations on it. Don't do operations directly on the string. You will go crazy. Here is some code which demonstrates addition and multiplication. Change M to use a bigger type. You could also use std::vector, but then you miss out on some optimizations.
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <iomanip>
#ifdef _DEBUG
#include <assert.h>
#define ASSERT(x) assert(x)
#else
#define ASSERT(x)
#endif
namespace Arithmetic
{
const int M = 64;
const int B = (M-1)*32;
struct Flags
{
Flags() : C(false),Z(false),V(false),N(false){}
void Clear()
{
C = false;
Z = false;
V = false;
N = false;
}
bool C,Z,V,N;
};
static unsigned int hvAdd(unsigned int a, unsigned int b, Flags& f)
{
unsigned int c;
f.Clear();
//b = -(signed)b;
c = a + b;
f.N = (c >> 31UL) & 0x1;
f.C = (c < a) && (c < b);
f.Z = !c;
f.V = (((signed)a < (signed)b) != f.N);
return c;
}
static unsigned int hvSub(unsigned int a, unsigned int b, Flags& f)
{
unsigned int c;
f.Clear();
c = a - b;
//f.N = ((signed)c < 0);
f.N = (c >> 31UL) & 0x1;
f.C = (c < a) && (c < b);
f.Z = !c;
f.V = (((signed)a < (signed)b) != f.N);
return c;
}
struct HugeVal
{
HugeVal()
{
std::fill(part, part + M, 0);
}
HugeVal(const HugeVal& h)
{
std::copy(h.part, h.part + M, part);
}
HugeVal(const std::string& str)
{
Flags f;
unsigned int tmp = 0;
std::fill(part, part + M, 0);
for(unsigned int i=0; i < str.length(); ++i){
unsigned int digit = (unsigned int)str[i] - 48UL;
unsigned int carry_last = 0;
unsigned int carry_next = 0;
for(int i=0; i<M; ++i){
tmp = part[i]; //the value *before* the carry add
part[i] = hvAdd(part[i], carry_last, f);
carry_last = 0;
if(f.C)
++carry_last;
for(int j=1; j<10; ++j){
part[i] = hvAdd(part[i], tmp, f);
if(f.C)
++carry_last;
}
}
part[0] = hvAdd(part[0], digit, f);
int index = 1;
while(f.C && index < M){
part[index] = hvAdd(part[index], 1, f);
++index;
}
}
}
/*
HugeVal operator= (const HugeVal& h)
{
*this = HugeVal(h);
}
*/
HugeVal operator+ (const HugeVal& h) const
{
HugeVal tmp;
Flags f;
int index = 0;
unsigned int carry_last = 0;
for(int j=0; j<M; ++j){
if(carry_last){
tmp.part[j] = hvAdd(tmp.part[j], carry_last, f);
carry_last = 0;
}
tmp.part[j] = hvAdd(tmp.part[j], part[j], f);
if(f.C)
++carry_last;
tmp.part[j] = hvAdd(tmp.part[j], h.part[j], f);
if(f.C)
++carry_last;
}
return tmp;
}
HugeVal operator* (const HugeVal& h) const
{
HugeVal tmp;
for(int j=0; j<M; ++j){
unsigned int carry_next = 0;
for(int i=0;i<M; ++i){
Flags f;
unsigned int accum1 = 0;
unsigned int accum2 = 0;
unsigned int accum3 = 0;
unsigned int accum4 = 0;
/* Split into 16-bit values */
unsigned int j_LO = part[j]&0xFFFF;
unsigned int j_HI = part[j]>>16;
unsigned int i_LO = h.part[i]&0xFFFF;
unsigned int i_HI = h.part[i]>>16;
size_t index = i+j;
size_t index2 = index+1;
/* These multiplications are safe now. Can't overflow */
accum1 = j_LO * i_LO;
accum2 = j_LO * i_HI;
accum3 = j_HI * i_LO;
accum4 = j_HI * i_HI;
if(carry_next){ //carry from last iteration
accum1 = hvAdd(accum1, carry_next, f); //add to LSB
carry_next = 0;
if(f.C) //LSB produced carry
++carry_next;
}
/* Add the lower 16-bit parts of accum2 and accum3 to accum1 */
accum1 = hvAdd(accum1, (accum2 << 16), f);
if(f.C)
++carry_next;
accum1 = hvAdd(accum1, (accum3 << 16), f);
if(f.C)
++carry_next;
if(carry_next){ //carry from LSB
accum4 = hvAdd(accum4, carry_next, f); //add to MSB
carry_next = 0;
ASSERT(f.C == false);
}
/* Add the higher 16-bit parts of accum2 and accum3 to accum4 */
/* Can't overflow */
accum4 = hvAdd(accum4, (accum2 >> 16), f);
ASSERT(f.C == false);
accum4 = hvAdd(accum4, (accum3 >> 16), f);
ASSERT(f.C == false);
if(index < M){
tmp.part[index] = hvAdd(tmp.part[index], accum1, f);
if(f.C)
++carry_next;
}
carry_next += accum4;
}
}
return tmp;
}
void Print() const
{
for(int i=(M-1); i>=0; --i){
printf("%.8X", part[i]);
}
printf("\n");
}
unsigned int part[M];
};
}
int main(int argc, char* argv[])
{
std::string a1("273847238974823947823941");
std::string a2("324230432432895745949");
Arithmetic::HugeVal a = a1;
Arithmetic::HugeVal b = a2;
Arithmetic::HugeVal d = a + b;
Arithmetic::HugeVal e = a * b;
a.Print();
b.Print();
d.Print();
e.Print();
system("pause");
}
Andreas is right, that you have to multiply one number by each digit of the other and sum the results accordingly. It is better to multiply a longer number by digits of the shorter one I think. If You store decimal digits in Your array char would indeed suffice, but if you want performance, maybe you should consider bigger type. I don't know what Your platform is, but in case of x86 for example You can use 32 bit ints and hardware support for giving 64 bit result of 32 bit multiplication.
Alright seeing that this question is answered almost 11 years ago, I figure I'll provide some pointers for the one who is writing their own BigInt library.
First off, if what you want is purely performance instead of studying how to actually write performant code, please just learn how to use GMP or OpenSSL. There is a really really steep learning curve to reach the level of GMP's performance.
Ok, let's get right into it.
- Don't use base 10 when you can use a bigger base. CPUs are god-level good at addition, subtraction, multiplication, and division, so take advantage of them.
Suppose you have two BigInt
a = {9,7,4,2,6,1,6,8} // length 8
b = {3,6,7,2,4,6,7,8} // length 8
// Frustrating writing for-loops to calculate a*b
Don't make them do 50 calculations in base 10 when they could do 1 calculations of base 2^32:
a = {97426168}
b = {36724678}
// Literally only need to type a*b
If the biggest number your computer can represent is 2^64-1, use 2^32-1 as the base for your BigInt, as it will solve the problem of actually overflowing when doing multiplication.
Use a structure that supports dynamic memory. Scaling your program to handle the multiplication of two 1-million digits numbers would probably break you program since it doesn't have enough memory on the stack. Use a std::vector instead of std::array or raw int[] in C to make use of your memory.
Learn about SIMD to give your calculation a boost in performance. Typical loops in noobs' codes can't process multiple data at the same time. Learning this should speed things up from 3 to 12 times.
Learn how to write your own memory allocators. If you use std::vector to store your unsigned integers, chances are, later on, you'll suffer performance problems as std::vector is only for general purposes only. Try to tailor your allocator to your own need to avoid allocating and reallocating every time a calculation is performed.
Learn about your computer's architecture and memory layout. Writing your own assembly code to fit certain CPU architecture would certainly boost your performance. This helps with writing your own memory allocator and SIMD too.
Algorithms. For small BigInt you can rely on your grade school multiplication but as the input grows, certainly take a good look at Karatsuba, Toom-Cook, and finally FFT to implement in your library.
If you're stuck, please visit my BigInt library. It doesn't have custom allocator, SIMD code or custom assembly code, but for starters of BigInteger it should be enough.
I'm building a small BigInt library in C++ for use in my programming language.
Why? There are some excellent existing bigint libraries out there (e.g., gmp, tommath) that you can just use without having to write your own from scratch. Making your own is a lot of work, and the result is unlikely to be as good in performance terms. (In particular, writing fast code to perform multiplies and divides is quite a lot trickier than it appears at first glance.)
加载中,请稍侯......
精彩评论