[simeesta]

The add() and add1() functions seem to be working correctly. The multiply function does not and i cant work out why not. It only works for n<=2

#include <stdio.h>
#define SIZE 1001
#define BASE 10

int add(int *c,int *d,int* e); //adds arrays c and d into e
int add1(int x, int y,int* z); //adds digits of the arrays
int multiply(int *f,int multiple,int* g); //multiplies f by multiple into g

int main()
{
    int a[SIZE],b[SIZE],test=0,i;
    for(i=0;i<SIZE;i++)//initialize a & b to 0
    {
        a[i]=0;
        b[i]=0;
    }

    a[1000]=9;
    a[999]=1;   //a=19
    int n=3;        //only works where n<=2
    multiply(a,n,B)/>; //b=n*a btw b is not capitalized in my code 

    for(i=0;i<SIZE;i++) //prints b
    {                                       /* /removes leading zero's */
        if(test==0 && b[i]==0) continue; // ie 1 instead of 00000001
        test=1;
        printf("%d",b [i]);
    }
    if(!test)printf("0");


    return 0;
}



int add1(int x,int y,int* z)  //adds digits - and takes care of the carry into z
{
    int p;
    p=z[x]+y;
    if(p<BASE)   //this recursively tests whether there is a carry
    {
        z[x]+=y;
        return 0;
    }
    else
    {
        add1(x-1,p/BASE,z); //carry
        z[x]=(p%BASE);
        return 0;
    }
}


int add(int *c,int *d,int* e)  //adds two arrays c and dtogether into and puts answer into array e
{
    int i,sum;
    for(i=SIZE-1;i>=0;i--)
    {
        sum=c[i]+d[i];
        if(e[i]+sum<BASE)       //no carry if true
        {
            e[i]+=sum;
        }
        else
        {
            add1(i,sum,e);     //adds the digits and takes care of the carry
        }
    }
    return 0;
}

int multiply(int *f,int multiple, int* g)  // times array f by multiple - into array g
{                                          // using 5*a = a+a+a+a+a
    int i;
    if(multiple==2)
    {
        add(f,f,g);
        return 0;
    }
    else
    for(i=0;i<multiple;i++)
    {
        add(f,g,g); //g+=f ??
    }
    return 0;
}

This post has been edited by simeesta: 03 May 2010 - 10:46 AM

[r.stiltskin]

What is the purpose of your constant BASE and what is the purpose of the "carry" code in add and add1? What sort of numbers and what sort of arrays are you dealing with?

[simeesta]

r.stiltskin, on 03 May 2010 - 05:30 PM, said:

What is the purpose of your constant BASE and what is the purpose of the "carry" code in add and add1? What sort of numbers and what sort of arrays are you dealing with?

dealing with very large numbers e.g. 2^1000.
but using small numbers to test and get the function correct,

e.g

__ 9 9
__ 9 9+
_ 1 9 8
_1 1 carry

base 10 means digits 0 to 9 ie decimal so you cant have 10 or 11 or A (hexadecimal)as a digit

This post has been edited by simeesta: 03 May 2010 - 11:44 AM

[r.stiltskin]

Are you trying to implement simple assignment
g = f*multiple
or
g = g + (f*multiple) (i.e. g += f*multiple)

This post has been edited by r.stiltskin: 03 May 2010 - 11:49 AM

[simeesta]

r.stiltskin, on 03 May 2010 - 05:49 PM, said:

Are you trying to implement simple assignment
g = f*multiple
or
g = g + (f*multiple) (i.e. g += f*multiple)

g = f * multiple

using addition though e.g. 5*f = f+f+f+f+f etc

[Oler1s]

Interesting, rather than outright multiplying digit by digit, you rely on repeated addition....

[r.stiltskin]

Your add and add1 seem to implement +=, so why can't multiply be

int multiply(int *f,int multiple, int* g)
{
    int i;
    for(i=0;i<SIZE;i++)
    {
        g[i]=f[i];
    }
    
    for(i=0;i<multiple-1;i++)
    {
        add(f,g,g);
    }
    return 0;
}

This post has been edited by r.stiltskin: 03 May 2010 - 12:23 PM

[simeesta]

r.stiltskin, on 03 May 2010 - 06:12 PM, said:

Your add and add1 seem to implement +=, so why can't multiply be

int multiply(int *f,int multiple, int* g)
{
    int i;
    for(i=0;i<SIZE;i++)
    {
        g[i]=0;
    }
    for(i=0;i<multiple-1;i++)
    {
        add(f,f,g);
    }
    return 0;
}

isnt that the same as writing:

g=f+f;
g=f+f;
g=f+f;
... or g=2f which is doubling
multiple times etc???

whereas i want
g=g+f;
g=g+f;
...
etc.

also g is an external variable ( b[] ) so does not have to be zeroed.

This post has been edited by simeesta: 03 May 2010 - 12:19 PM

[r.stiltskin]

Sorry, while you were writing I was editing. See my revised post above.

[simeesta]

r.stiltskin, on 03 May 2010 - 06:22 PM, said:

Sorry, while you were writing I was editing. See my revised post above.

Thanks for the help anyway.

My origninal code was to sum to the digits of the number of 2^1000 for project euler no. 16. which gives the correct answer

here it is :

/* Program to find the sum of the digits of the number 2^1000 */

#include <stdio.h>
#define SIZE 1001
#define BASE 10

int* add(int *c,int *d,int* e); //adds arrays c and d into e
int* add1(int x, int y,int* z); //adds digits of the arrays
int twice(int *c,int* d);       //doubles c into d

int main()
{
    int i,j,sum,value[SIZE];
    int a[SIZE];
    int test=0;
    for(i=0;i<SIZE;i++)//zero the arrays ready for addition
    {
        value[i]=0;
        a[i]=0;
    }

    //calculate 2^1000
    a[1000]=1;
    for(i=0;i<1000;i++)
    {
        twice(a,value);
        for(j=0;j<=1000;j++)
        {
            a[j]=value[j];
            value[j]=0;
        }
    }

    printf("2 ^ 1000 is :\n");
    for(i=0;i<SIZE;i++)//print 2^1000
    {
        if(test==0 && a[i]==0) continue;
        test=1;
        printf("%d",a [i]);
    }
    if(!test)printf("0");
    sum=0;

for(i=0;i<SIZE;i++)//sum up the digits
{
    sum+=a[i];
}
printf("\n\nthe sum of its digits is %d\n\n",sum);
return 0;
}

int* add1(int x,int y,int* z)  //adds digits - and takes care of the carry into z
{
    if(z[x]+y<BASE)   //this recursively tests whether there is a carry
    {
        z[x]+=y;
        return z;
    }
    else
    {
        add1(x-1,(z[x]+y)/BASE,z); //carry
        z[x]=((z[x]+y)%BASE);
    }
}


int* add(int *c,int *d,int* e)  //adds two arrays c and dtogether into and puts answer into array e
{
    int i,sum;
    for(i=SIZE-1;i>=0;i--)
    {
        sum=c[i]+d[i];
        if(e[i]+sum<BASE)       //no carry if true
        {
            e[i]+=sum;
        }
        else
        {
            add1(i,sum,e);     //adds the digits and takes care of the carry
        }
    }
    return e;
}

int twice(int *f, int* g)  // times array f by 2 - into array g. g=(f+f)
{
    add(f,f,g);

}

i've just change the twice function to multiply a number by something else instead of just two. perhaps this may help?


Thanks to everyone trying to help as well, in case I forget

[r.stiltskin]

???

Is there something wrong with this:

int multiply(int *f,int multiple, int* g)
{
    int i;
    for(i=0;i<SIZE;i++)
    {
        g[i]=f[i];
    }
    
    for(i=0;i<multiple-1;i++)
    {
        add(f,g,g);
    }
    return 0;
}

[simeesta]

r.stiltskin, on 03 May 2010 - 06:36 PM, said:

???

Is there something wrong with this:

int multiply(int *f,int multiple, int* g)
{
    int i;
    for(i=0;i<SIZE;i++)
    {
        g[i]=f[i];
    }
    
    for(i=0;i<multiple-1;i++)
    {
        add(f,g,g);
    }
    return 0;
}

just copied that into my code and gives the same answer as the original
however 3*19 is not 293.

i've got a feeling it's something to do with variable scope of g and f but they're pointer so it should not matter. right?

[r.stiltskin]

True, 3*19 is not 293. But neither is 19+19==331 nor 19+0==350.

I think you'll find that the problem is in add or add1, not multiply.

I modified your main to this:

int main()
{
    int a[SIZE],b[SIZE],test=0,i;
    for(i=0;i<SIZE;i++)//initialize a & b to 0
    {
        a[i]=0;
        b[i]=0;
    }

    int z[SIZE] = {0};
    a[1000]=9;
    a[999]=1;   //a=19
    int n=3;        //only works where n<=2
    
    multiply(a,n,B)/>; //b=n*a btw b is not capitalized in my code 
    for(i=0;i<SIZE;i++) //prints b
    {                                       /* /removes leading zero's */
        if(test==0 && b[i]==0) continue; // ie 1 instead of 00000001
        test=1;
        printf("%d",b [i]);
    }
    if(!test)printf("0");
    printf("\n\n");
    test = 0;


    add(a,a,B)/>; //b=n*a btw b is not capitalized in my code 
    for(i=0;i<SIZE;i++) //prints b
    {                                       /* /removes leading zero's */
        if(test==0 && b[i]==0) continue; // ie 1 instead of 00000001
        test=1;
        printf("%d",b [i]);
    }
    if(!test)printf("0");
    printf("\n\n");
    test = 0;

    
    add(a,z,B)/>; //b=n*a btw b is not capitalized in my code 
    for(i=0;i<SIZE;i++) //prints b
    {                                       /* /removes leading zero's */
        if(test==0 && b[i]==0) continue; // ie 1 instead of 00000001
        test=1;
        printf("%d",b [i]);
    }
    if(!test)printf("0");
    printf("\n\n");
    test = 0;

    return 0;
}

ed: damn smileys -- watch out for those uppercase B's.

Supposedly if you turn off emoticons that shouldn't happen. Not sure if that works, but I keep forgetting to do it anyway.

This post has been edited by r.stiltskin: 03 May 2010 - 12:59 PM

[simeesta]

#include <stdio.h>
#define SIZE 1001
#define BASE 10

int add(int *c,int *d,int* e); //adds arrays c and d into e
int add1(int x, int y,int* z); //adds digits of the arrays
int multiply(int *f,int multiple,int* g); //multiplies f by multiple into g

int main()
{
    int a[SIZE],b[SIZE],c[SIZE],test=0,i;
    for(i=0;i<SIZE;i++)//initialize a & b to 0
    {
        a[i]=0;
        b[i]=0;
        c[i]=0;
    }

    a[1000]=9; //a=19
    a[999]=1;
    b[1000]=9;
    b[999]=1; //b=19
    add(a,b,c); //c=a+b



    for(i=0;i<SIZE;i++) //prints b
    {                                       /* /removes leading zero's */
        if(test==0 && c[i]==0) continue; // ie 1 instead of 00000001
        test=1;
        printf("%d",c [i]); //prints 38???
    }
    if(!test)printf("0");


    return 0;
}



int add1(int x,int y,int* z)  //adds digits - and takes care of the carry into z
{
    int p;
    p=z[x]+y;
    if(p<BASE)   //this recursively tests whether there is a carry
    {
        z[x]+=y;
        return 0;
    }
    else
    {
        add1(x-1,p/BASE,z); //carry
        z[x]=(p%BASE);
        return 0;
    }
}


int add(int *c,int *d,int* e)  //adds two arrays c and dtogether into and puts answer into array e
{
    int i,sum;
    for(i=SIZE-1;i>=0;i--)
    {
        sum=c[i]+d[i];
        if(e[i]+sum<BASE)       //no carry if true
        {
            e[i]+=sum;
        }
        else
        {
            add1(i,sum,e);     //adds the digits and takes care of the carry
        }
    }
    return 0;
}
int multiply(int *f,int multiple, int* g)  // times array f by multiple - into array g
{                                          // using 5*a = a+a+a+a+a
    int i;
    if(multiple==2)
    {
        add(f,f,g);
        return 0;
    }
    else
    for(i=0;i<multiple;i++)
    {
        add(f,g,g); //g+=f ??
    }
    return 0;
}

which is correct

This post has been edited by simeesta: 03 May 2010 - 01:04 PM

[r.stiltskin]

Right. Sorry, I forgot to zero b in between.