My bigints are overcomplicated.

This is a discussion on My bigints are overcomplicated. within the C Programming forums, part of the General Programming Boards category; I just finished writing an adder for a bigint struct I made. It seems as if it works. The thing ...

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    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;
    }
    Last edited by mike_g; 03-20-2008 at 08:22 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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
    Last edited by mike_g; 03-20-2008 at 08:39 AM.

  4. #4
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Ok, I that worked and I managed to get rid of the add byte and add carry functions.
    Code:
    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; 
        Uint16 part_sum;    
    
        // Add bytes up until the smallest bignum's size
        for(; count<sml; count++)
        {
            part_sum = *a_ptr + *b_ptr + carry;
            carry = (part_sum > 255)? 1: 0;
            *r_ptr = part_sum & 255;
            a_ptr++; b_ptr++; r_ptr++;
        }  
        // If one number was bigger continue adding carry, or copying bytes
        for(; count<big; count++)
        {   
            if(carry)
            {
                part_sum = *a_ptr + 1;
                carry = (part_sum > 255)? 1: 0;
                *r_ptr = part_sum & 255;
            }
            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;      
    }

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah, good idea. Memory is usually the least of my worries. Might event be worth using Uint32 instead and Uint64 to test overflows.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by mike_g View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    I think I found the thread you were talking about:
    generic add with carry
    I'm pretty sure used that method sometime before actually...

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by mike_g View Post
    I think I found the thread you were talking about:
    generic add with carry
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Thanks, but the adding bits part was basic stuff I learnt in electronics. If I were clever enough to figure it out for myself I'd take full credit for it

    Anyway, i got my prog checking overflows if the result < something that went in, and its using 32bit blocks now too, which is nice.

    Tbh I'm not sure if the extensible size thing is really worth it as theres going to be a lot of overhead when the numbers have to keep resizing themselves. But if it works....

  11. #11
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.
    I hate real numbers.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21