Thread: My bigints are overcomplicated.

I just finished writing an adder for a bigint struct I made. It seems as if it works. The thing is is that I have ended up with about 80 lines of code just to add 2 numbers together. I'm guessing that there may be an easier way to do this, as this is pretty much just something I invented off the top of my head. If anyone has any suggestions on how to make it simpler/faster/better, or can spot a bug in it let us know.

Cheers.

Bignum.c:

Code:

#include "bignum.h"

bigint make_int(Uint8 size)
{
    bigint new_int;
    new_int.byte = (Uint8*)calloc(size, 1); 
    new_int.size = size;
    return new_int;
}
void reset_int(bigint i)
{
    memset(i.byte, 0, i.size);
}
void set_int(bigint num, Uint32 set_to)
{
    int i;
    Uint8 *byte = num.byte;
    for(i=0; i<4; i++, byte++)
    {
        *byte = set_to & 255;
        set_to >>= 8; 
    }
}
bigint resize_bigint(bigint old, Uint8 size)
{
    bigint result = make_int(size);

    Uint8 *src = old.byte;
    Uint8 *dst = result.byte;
    Uint8 i;

    for(i=0; i<old.size; i++, src++, dst++)
        *dst = *src;
    free(old.byte);
    return result;
}
//******************** ADDER ********************************//
bigint add_bigint(bigint a, bigint b)
{   
    Uint8 big = MAX(a.size, b.size);
    Uint8 sml = MIN(a.size, b.size); 

    bigint result = make_int(big);
    
    Uint8 *a_ptr = (a.size > b.size)? a.byte: b.byte;
    Uint8 *b_ptr = (a.size > b.size)? b.byte: a.byte;
    Uint8 *r_ptr = result.byte;
    Uint8 carry=0;
    Uint8 count=0; 

    // Add bytes up until the smallest bignum's size
    for(; count<sml; count++)
    {
        carry = add_byte(a_ptr, b_ptr, r_ptr, carry);
        a_ptr++; b_ptr++; r_ptr++;
    }  
    // If one number was bigger continue adding carry, or copying bytes
    for(; count<big; count++)
    {
        if(carry)
            carry = add_carry(a_ptr, r_ptr);
        else
            *r_ptr = *a_ptr;
        r_ptr++; a_ptr++;
    }
    // If there was a carry on the last byte, then resize result and add carry
    if(carry)
    {
        result = resize_bigint(result, big+1);
        r_ptr = result.byte + big;
        *r_ptr = 1;   
    }
    return result;      
} 

Uint8 add_byte(Uint8 *a, Uint8 *b, Uint8 *r, Uint8 carry)
{
    Uint8 i, num = 0;
    Uint8 bit = 1;

    for(i=0; i<CHAR_BIT; i++)
    {        
        num = 0;
        if(*a & bit) num++;
        if(*b & bit) num++;
        if( carry )  num++;    
        if(num & 1) *r |= bit;
        carry = (num & 2);
        bit <<= 1;
    }  
    return carry; //returns 2 NOT 1!  
}

Uint8 add_carry(Uint8 *a, Uint8 *r)
{
    Uint8 carry = 1;
    Uint8 bit = 1,i;

    for(i=0; i<CHAR_BIT; i++)
    {
        if(carry)
            if(*a & bit)
                *r &= ~bit;
            else
            {
                *r |= bit;
                carry = 0;
            }
        else
            if(*a & bit)
                *r |= bit;                        
    }
    return carry;
}

//************************************************************//
void print_int_bin(bigint num)
{
    int x, y, bit;
    Uint8 *byte = num.byte+(num.size-1);
    for(y=0; y<num.size; y++)
    {
        bit = 128;
        for(x=0; x<CHAR_BIT; x++, bit>>=1)
            putchar((*byte & bit)?'1':'0');
        putchar(' ');
        byte--;
    }           
}

Bignum.h:

Code:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

#ifndef Uint8
    #define Uint8 unsigned char
#endif
#ifndef Uint16
    #define Uint16 unsigned short
#endif 
#ifndef Uint32
    #define Uint32 unsigned long
#endif 

#define MIN(x,y)  ((x<y) ? (x) : (y))
#define MAX(x,y)  ((x>y) ? (x) : (y))

typedef struct
{
    Uint8*byte;
    Uint8 size;
}bigint;

bigint make_int(Uint8 size);
void reset_int(bigint i);
void set_int(bigint num, Uint32 set_to);
bigint resize_bigint(bigint old);
bigint add_bigint(bigint a, bigint b);
Uint8 add_byte(Uint8 *a, Uint8 *b, Uint8 *r, Uint8 carry);
Uint8 add_carry(Uint8 *a, Uint8 *r);
void print_int_bin(bigint num);

Test Prog:

Code:

#include <stdio.h>
#include "bignum.h"

int main(int argc, char *argv[])
{
    bigint a = make_int(2);
    set_int(a, 10);
    print_int_bin(a);
    putchar('\n'); 

    bigint b = make_int(4);
    set_int(b, 0xFFFFFFFF);
    print_int_bin(b);
    putchar('\n');

    bigint c = add_bigint(a, b);
    print_int_bin(c);
    putchar('\n');
    
    getchar();
    return 0;
}

Adding a byte (or even a long int) should be possible in one operation, and detecting the carry can be done with a simple compare operation. There was a discussion on that some time ago, where iMalc posted the right answer.

That should reduce the actual addition by some amount.

--
Mats

Yeah that would pretty much chop the amount of code in half. I'll have a go at it.

Edit: I guess having a short to hold the result of 2 bytes should work and if its over 255 then theres a carry

And you could immediately almost double the execution speed by using Uint16 instead of Uint8 for the number itself, and then use Uint32 where you are currently using Uint16. The only drawback is that odd-sized numbers require one extra byte to make it line up for Uint16 - but I think that's a sacrifice worth having.

--
Mats

Originally Posted by mike_g

Yeah, good idea. Memory is usually the least of my worries. Might event be worth using Uint32 instead and Uint64 to test overflows.

Sure.

As I suggested earlier, there is a post somewhere that describes how to tell if there was a carry from two unsigned number added together, without using a larger type.

--
Mats

Originally Posted by mike_g

I think I found the thread you were talking about:
http://cboard.cprogramming.com/showt...=test+overflow
I'm pretty sure used that method sometime before actually...

Yeah, that's the one. Well done for working it out the adding at the bit level in the first place though!
I might hurry up and write a variable-length bigint class myself, finally.

I think this is one of the situation where assembly language can be handy, since it offers instructions that you can't normally access in C (like the "add with carry" instruction from the x86 instruction set). This is one of the rare case where the assembly version of one function can actually looks simpler than the high level version.

Of course, you'll have portability issue if you write some code in assembly. But if you don't need your code to be portable and only want to target one computer family, well, you might want to take a look. There is pros and cons.

Here's a little example on how would looks an add function (i'm assuming you are targeting x86-32 CPU and assuming sizeof(unsigned int) == 32 bits on the compiler). This isn't related with your work, and it's not meant to be useful.

Code:

#include <stdio.h>

#define BIGINT_SIZE 4

typedef unsigned int BigInt[BIGINT_SIZE];

void addBigInt(BigInt n1, BigInt n2)
//  Add n1 and n2 and put the result in n1
{
    _asm
    {
        push eax
        push ebx
        push ecx
        push edx
        push esi

        mov ebx, n1
        mov esi, n2
        mov ecx, BIGINT_SIZE
        xor edx, edx

add_1:
        lodsd
        adc [ebx][edx * 4], eax
        inc edx
        loop add_1

        pop esi
        pop edx
        pop ecx
        pop ebx
        pop eax
    }
}

void displayBigInt(BigInt n1)
{
    unsigned int i = BIGINT_SIZE;
    while (i > 0)
    {
        printf("%08X ", n1[--i]);
    }
    putchar('\n');
}

int main()
{
    BigInt n1 = {0x01234567, 0x89ABCDEF};
    BigInt n2 = {0xFEDCBA98, 0x86543210};

    addBigInt(n1, n2);
    displayBigInt(n1);

    return 0;
}

I must admit it doesn't look that clear. But what's interesting is that the "real" treatment is only 4 instructions long. But of course, except if you are working with exceptionally large numbers, you won't see the difference between a version written in assembly and one in plain C.