HugeMotherFuckingInt

I'm trying to write a HugeMotherFuckingInt processing library in C.

My first try, I stored the numbers as a char[] and computed them using basic arithmetic.

My second try, I stored the numbers as unsigned long char[]. This proved to be a faster, easier and clearer approach.

Still though, it seems to be a bit too slow.

What other data structures might result in faster execution of basic arithmetic +/*-?

Also, are there any algorithms to speed up the arithmetic operations themselves?

...Here's a kind of fast multiply



Darn backseat Coders, Get your own text editor =)







void FSMultiply(int xa[], int xb[], int xc[]){
int mCount[52], VAdd[52], VCount[52], FStore[52], FCount[52], OldStore[52];

One(mCount);
//Zero(OldCount);
Zero(OldStore);
Zero(FCount);
Zero(FStore);

if(isLarger(xa, xb)>=0){
    Set(VCount, xb);
    Set(VAdd, xa);
    } else{
    Set(VAdd, xb);
    Set(VCount, xa);
    }

while(isLarger(VCount, aZero)==1){
    One(mCount);

    //printf("ONED m:");
    //Printout(mCount);
    //printf("Remainder V:");
    //Printout(VCount);
    //printf("VADD:");
    //Printout(VAdd);   
    //Pause();

    Set(FStore, VAdd);
    if(isLarger(VCount, mCount)==0){
        Add(xc, VAdd, xc);
        Sub(VCount, mCount, VCount);

        //printf("plus 1\nDone!");
        Printout(xc);
        return;
        }

    while(isLarger(VCount, mCount)>=0){
        Set(FCount, mCount);
        Set(OldStore, FStore);
        Add(mCount, mCount, mCount);
        Add(FStore, FStore, FStore);

        //printf("FC:");
        //Printout(FCount);
        //printf("OS:");
        //Printout(OldStore);
        //Pause();
   
        Sub(VCount, FCount, VCount);
        Add(xc, OldStore, xc);
        }   
   
   
    //printf("\nVC:");
    //Printout(VCount);
    //printf("\nxc:");
    //Printout(xc);
    //Pause();

    }
}

//====================================

>>39,41
_IHBT

450 Digit is not too shabby....

5760 Digit.... blam =)
...too bad it's hell slow

>>1

Do it using unsigned chars first, and limit the number to two limbs. Implement your algorithms that way. This way you can simply compare your results with the same operation done straightforward. You can make a unit test for that.

Addition and subtraction are trivial to implement.

For multiplication, use Karatsuba's or Toom-Cook's.

For division, there's nothing really cool that I know of.

For module, use Montgomery's transformations.

>>42
Nu-uh, this guy's legit.

https://gitorious.org/factorialofnumber/factorialofnumber/blobs/master/factorial.c

>>47
This is unreal.

>>Full code [Quartz3.c]
Loop in main Will Square result until it is larger than bMax( which is set to 1*10e4500) .... Largest number i have seen?!
//Mod'ed multiply a bit [should be a little faster again =) ]

...Not coming up with your own solutions....
*Shame on you /prog*

You'll never find a better solution to anything if you just use what's already on the table...


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

const RRay = 1000;       //      Max array Size //
const CutOff = 1000000000;   //      Base

int aa[1020], ab[1020], ac[1020], aCount[1020], aZero[1020], aOne[1020], bCount[1020], bMax[1020];


//----------------------------------------------------

void Set(int xa[], int xb[]){
int i;
for(i=0;i<=RRay;i++) xa[i] = xb[i];
}

//----------------------------------

void Zero(int xa[]){
int i;
for(i=0;i<=RRay;i++) xa[i] = 0;
}

//----------------------------------

void One(int xa[]){
Zero(xa);
xa[0]=1;
//xa[RRay]=1;
}
 
//----------------------------------

int GOWFish(int a, int b){
int Ret=0;
if(a!=b){
    if(a>b) Ret= 1;
    if(a<b) Ret=-1;
    }
return Ret;
}

//---------------------

int isLarger(int xa[], int xb[]){
int a, b, i, ret=0;
a = xa[RRay];
b = xb[RRay];
i =a+1;
ret = GOWFish(a, b);
while((ret==0) + (i>0)==2){
    i--;
    a = xa[i];
    b = xb[i];
    ret = GOWFish(a, b);
    }
return ret;
}

//----------------------------------------------   
   
void Add(int xa[], int xb[], int xc[]){
int i, iCarry=0, raymax=0;
raymax = xa[RRay];
if(xb[RRay]>raymax) raymax = xb[RRay]; 
xc[RRay] = raymax;
for(i=0;i<=xc[RRay];i++){
    xc[i] = xa[i] + xb[i] + iCarry;
    iCarry=0;
    if(xc[i]>=CutOff){
        iCarry++;
        xc[i]-=CutOff;
        }
    if((i==xc[RRay])+(iCarry==1)+(xc[RRay]<RRay-1)==3) xc[RRay]++;
    }
}
//----------------------------------

void CheckRRay(int xa[]){
int i, iTop=0;
for(i=0;i<RRay;i++){
    if(xa[i]>0) iTop=i;
    }
if(xa[RRay]!=iTop){ printf("Fixed RRay"); xa[RRay]=iTop;}
}

//-------------------------------------
   
void Sub(int xa[], int xb[], int xc[]){
int i, iCarry=0, raymax=0;
raymax = xa[RRay];
if(xb[RRay]>raymax){ printf("Problem!"); raymax = xb[RRay];  }
xc[RRay] = raymax;   
for(i=0;i<=raymax;i++){
    xc[i] = xa[i] - (xb[i] + iCarry);
    iCarry=0;
    if(xc[i]<0){
        iCarry++;
        xc[i]+=CutOff;
        }
    if((i==xc[RRay])+(iCarry==1)==2){ printf("Negative!"); xc[RRay]++; }
    }
CheckRRay(xc);
}

//------------------------------------

void Printout(int xX[]){
    int i;
    for(i=xX[RRay];i>=1;i--) printf("%9i,", xX[i]);
    printf("%9i\n", xX[0]);
   
}

//-----------------------------------
   
void Pause(void){
char i3;
printf("Enter to continue");
scanf("%c",&i3);    
}    
//-----------------------------------
   
void Entry(int x[]){
int i, i2, i3;
printf("Enter Base size");
scanf("%i",&i3);         
if(i3>RRay) i3 = RRay;
for(i=i3;i>=0;i--){
    printf("Enter No %i", i);
    scanf("%i",&i2);
    printf("Entered %i\n", i2);
    x[i]=i2;   
        }
x[RRay] = i3;         
//for(i=i3;i>=0;i--) printf("%9i,", x[i]);   
Printout(x);
}

//---------------------------------------------------

void SlowMultiply(int xa[], int xb[], int xc[]){
int mCount[52];
One(mCount);


while(isLarger(xb, mCount)==1){   
   
    Printout(mCount);
    Printout(xc);

    Add(xc, xa, xc);
    Add(mCount, aOne, mCount);
    }
}

//---------------------------------------------------

void FSMultiply(int xa[], int xb[], int xc[]){
int mCount[1020], VAdd[1020], VCount[1020], FStore[1020], FCount[1020], OldStore[1020], JumpStore[1020], JumpCount[1020];

int maxLoop=0, halfLoop=0, OnOff=0;

One(mCount);
//Zero(OldCount);
Zero(OldStore);
Zero(FCount);
Zero(FStore);


if(isLarger(xa, xb)>=0){
    Set(VCount, xb);
    Set(VAdd, xa);
    } else{
    Set(VAdd, xb);
    Set(VCount, xa);
    }

while(isLarger(VCount, aZero)==1){
    One(mCount);

    //printf("ONED m:");
    //Printout(mCount);
    //printf("Remainder V:");
    //Printout(VCount);
    //printf("VADD:");
    //Printout(VAdd);   
    //Pause();

    Set(FStore, VAdd);
    if(OnOff==1){
        OnOff=0;
        //maxLoop=0;
        }
    if(halfLoop!=0){
        if(isLarger(VCount, JumpCount)==1){
            Set(mCount, JumpCount);
            Set(FStore, JumpStore);
            } else{
            printf("Klunk=)");
            maxLoop=halfLoop;
            }
        halfLoop=0;
        //BumpScan
        }
    if(maxLoop!=0){
        halfLoop=3*maxLoop/4;
        OnOff=1;
        //maxLoop=0;
        }
    maxLoop=0;
    while(isLarger(VCount, mCount)>=0){
        if(OnOff==1){
            if(maxLoop==halfLoop){
                Set(JumpCount, mCount);
                Set(JumpStore, FStore);
                }
            }
       
        Set(FCount, mCount);
        Set(OldStore, FStore);
        Add(mCount, mCount, mCount);
        Add(FStore, FStore, FStore);

        //printf("FC:");
        //Printout(FCount);
        //printf("OS:");
        //Printout(OldStore);
        //Pause();
   
        Sub(VCount, FCount, VCount);
        Add(xc, OldStore, xc);
        maxLoop++;
        }   
   
   
    //printf("\nVC:");
    //Printout(VCount);
    //printf("\nxc:");
    //Printout(xc);
    //Pause();

    }
}

//====================================

int main(){
int i=0;
Zero(aZero);
One(aOne);
Zero(aa);
Zero(ab);
Zero(bMax);
bMax[500]=1;
bMax[RRay]=500;


One(aCount);
//One(bCount);


Entry(aa);
Entry(ab);

//Set(ac, aa);

printf("\n----------------------------------\n");

/*while(isLarger(aa, aCount)==1){   
   
    //Printout(aCount);
    //Printout(ac);

    Add(ac, aa, ac);
    Add(aCount, aOne, aCount);
    }
*/

FSMultiply(aa, ab, ac);

//Printout(aCount);
Printout(ac);

while(isLarger(bMax, ac)==1){
    FSMultiply(ac, ac, ac);
    printf("\nAC:");
    Printout(ac);
    }

return;
}