What language are you using? In most languages a bool is either 1 byte
or 4 bytes long. So you'd be wasting a tremendous amount of time and
space if you're doing the additions one bit at a time.
Here's roughly how it work work in C, but you'll get a faster result
with GNU mp on most machines because inner loops use assembly language
inserted to get access to the carry register. My code is untested,
but ought to be at least very close.
typedef unsigned long long LIMB;
#define N_BITS 100000
#define L sizeof(LIMB)
#define LIMB_SIZE ((N_BITS + L - 1) / L)
typedef struct big_num {
LIMB bits[LIMB_SIZE]; // 12,500 long longs hold bits
} BIG_NUM;
// Add a and b. Put result in r. Return the carry out.
LIMB add(BIG_NUM *r, BIG_NUM *a, BIG_NUM *b)
{
int i;
LIMB c = 0;
for (i = 0; i < LIMB_SIZE; i++) {
LIMB ia = a->bits[i];
LIMB ib = b->bits[i];
LIMB it = ia + ib;
LIMB ir = it + c;
r->bits[i] = ir;
c = (ir < it) || (it < ia);
}
return c;
}
On Feb 13, 2:12 am, rspr <ravishanker....@gmail.com> wrote:
> I have two binary sequences x and y (100000 bits long)...I am taking a
> bool array to store it.....I have to implement the summation
> operation( at most 400000 summation operation)...while the bits patter
> in changing in x and y....in my approach before performing a sum I am
> taking care of a. to check is sequence A or B is changed b. is the sum
> operations are continuous....so i have not to sum up it again bcz in
> between there is no change in A and B
>
> But the output is killing....what could be the better approach to
> implement the sum operation.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
