• C

# 900 points!! Division Help

URGENT!!!

I have the below code at the moment.

As you all know, integers have got its limitations and the largest number is either 2^32 or 2^64. I am creating  a"Big Number" using 100 integer to form an array. Each element represent 1 digit. So to store number 1234, I actually store them as "432100000000000...00" in the array.

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

#define MAX 100

void string_to_BigNum(char[], int[]);
int compare_BigNum(int a[], int b[]);
void init_BigNum(int[]);
void print_BigNum(int[], char[]);
void subtract_BigNum(int[], int[], int[]);
void multiply_BigNum(int[], int[], int[]);
void divide_BigNum(int a[], int b[], int c[]);
void divide_BigNum1(int a[], int b[], int c[]);
void pascal_triangle(void);

int main()
{
int i=0;
int BigNum[MAX]={0};
char StringNum[MAX+1]="";
int BigNum1[MAX]={0}, BigNum2[MAX]={0};
char StringNum1[MAX+1]="", StringNum2[MAX+1]="";
int a[MAX]={0}, b[MAX]={0}, c[MAX]={0};
char a_string[MAX+1]="", b_string[MAX+1]="";

printf(">> divide_BigNum Test:\n");
printf("Enter first string: ");
fflush(stdin);
scanf("%100s", a_string);
printf("Enter second string: ");
fflush(stdin);
scanf("%100s", b_string);
string_to_BigNum(a_string, a);
string_to_BigNum(b_string, b);
divide_BigNum(a, b, c);
for ( i=0; i<MAX; i++)
printf("%d", c[i]);
printf("\nPress <ENTER> to continue ");
fflush(stdin);
getchar();
printf("\n\n");

/* return EXIT status */
return 0;
}

/* initialize big number to all 0 */
void init_BigNum(int a[])
{
int i;

/* loop through the array and initialize each element */
for ( i=0; i<MAX; i++ )
a[i] = 0;
}

/* b will contain a representation of the big number stored in string a */
void string_to_BigNum(char a[], int b[])
{
int i, j=0;

/* initialize big number */
init_BigNum(b);

/* loop through the array and set value of b from a */
for ( i=strlen(a)-1; i>=0; i-- )
b[j++] = a[i] - '0';
}

/*
*  returns 0 if a==b
*  returns 1 if a > b
*  returns -1 otherwise
*/
int compare_BigNum(int a[], int b[])
{
char a_string[MAX+1];
char b_string[MAX+1];

/* convert to string numbers */
print_BigNum(a, a_string);
print_BigNum(b, b_string);

/* length of a longer meaning a is larger */
if ( strlen(a_string) > strlen(b_string) )
return 1;
/* length of a shorter meaning a is smaller */
else if ( strlen(a_string) < strlen(b_string) )
return -1;
/* of same length so we compare them using strcmp */
else
return (strcmp(a_string, b_string) == 0 ? 0 : strcmp(a_string, b_string) / abs(strcmp(a_string, b_string)) );
}

/*
* c will contain the sum of a and b
*/
void add_BigNum(int a[], int b[], int c[])
{
int i;

/* initialize c to 0 */
init_BigNum(c);

/* loop thru all elements of both a and b */
for ( i=0; i<MAX; i++ )
{
/* add the corresponding element of a and b incl the carry */
col_add = carry + a[i] + b[i];

/* addition is more than 0 */
if ( col_add > 0 )
{
/* c[i] will be the remainder when divided by 10 */

/* if more than 9 implies there is a carry */
if ( col_add > 9 )
carry = 1;
/* no carry because less than 10 */
else
carry = 0;
}
/* addition is 0 so c[i] is 0 and no carry */
else
{
c[i] = 0;
carry = 0;
}
}

/* meaning overflow ie. addition results in >100 digits */
if ( carry == 1 )
{
printf("Overflow!!!\n");
exit(1);
}
}

/*
* c will contain the difference of a and b (a-b)
*/
void subtract_BigNum(int a[], int b[], int c[])
{
int i, j;
int diff;
int temp[MAX];

/* check and compare the difference */
diff = compare_BigNum(a, b);

init_BigNum(c);

/* a > b so we can subtract */
if ( diff == 1 )
{
/* copy contents of a onto temp */
for ( i=0; i<MAX; i++ )
temp[i] = a[i];

/* loop thru array temp and b to perform subtraction */
for ( i=0; i<MAX; i++ )
{
/* temp[i] >= b[i] so need not bring carry */
if ( temp[i] >= b[i] )
c[i] = temp[i] - b[i];
/* temp[i] < b[i] so need to carry */
else
{
temp[i] = 10 + temp[i];
c[i] = temp[i] - b[i];
j = 1;

/* carry all the way to the left until top is > bottom */
while ( 1 )
{
if ( temp[i+j] > c[i+j] )
{
temp[i+j]--;
break;
}
else
{
if ( temp[i+j] == 0 )
temp[i+j] = 9;
else
temp[i+j] = 9 + temp[i+j];
}

j++;
}
}
}
}
/* a == b so we can initialize c to all zeros */
else if ( diff == 0 )
init_BigNum(c);
/* a < b so we cannot continue */
else
{
printf("Subtraction results in negative value!!!\n");
exit(1);
}
}

/*
* c will contain the product of a and b
*/
void multiply_BigNum(int a[], int b[], int c[])
{
int i, j, carry=0;
int col_mul=1;
int temp1[MAX], temp2[MAX];

/* initilize c */
init_BigNum(c);

/* loop through the array b */
for ( i=0; i<MAX; i++ )
{
/* initilize temp */
init_BigNum(temp1);
/* initialize carry to 0 */
carry = 0;

/* loop through array a */
for ( j=0; j<MAX; j++ )
{
/* do multiplication of respective digit of a and b */
/* then add that with the carry */
col_mul = a[j] * b[i] + carry;

if ( j + i < MAX )
temp1[j+i] = col_mul % 10;
else
{
if ( (col_mul % 10) > 0 )
{
printf("Overflow!!!\n");
exit(1);
}
}
carry = col_mul / 10;
}

/* add up the row obtained from each multiplication */
for ( j=0; j<MAX; j++ )
c[j] = temp2[j];
}
}

/*
* c will contain the integer division of a and b
* i.e. 10/3 = 3
*/
void divide_BigNum(int a[], int b[], int c[])
{
}

void print_BigNum(int num[], char num_string[])
{
int i,j;

for(i=MAX-1; i>0; i--)
{
if(num[i]>0) break;
}
for (j=0; i>=0; i--)
{
num_string[j]='0'+num[i];
j++;
}
num_string[j]='\0';
}

/*
generate a pascal triangle and stop printing when the first line
with a term > 10^n is encountered.
*/
void pascal_triangle(void)
{
int i=0, j;
int tocontinue=1;
int zero[MAX]={0};
int limit[MAX];
int cur_line[MAX*3][MAX], next_line[MAX*3][MAX];
char to_print[MAX+1];

init_BigNum(limit);
limit[70] = 1;

for ( i=0; i<MAX*3; i++ )
{
init_BigNum(cur_line[i]);
init_BigNum(next_line[i]);
}

cur_line[0][0] = 1;

while ( 1 )
{
i = 0;

while ( compare_BigNum(cur_line[i], zero) != 0 )
{
print_BigNum(cur_line[i], to_print);
printf("%s ", to_print);
i++;
}
printf("\n");

if ( !tocontinue )
break;

for ( i=0; i<MAX*3; i++ )
init_BigNum(next_line[i]);

i = 0;
while ( compare_BigNum(cur_line[i], zero) != 0 )
{
if ( i == 0 )
next_line[i][0] = 1;
else

if ( compare_BigNum(next_line[i], limit) == 1 )
tocontinue = 0;

i++;
}
next_line[i][0] = 1;

for ( ; i>=0; i-- )
{
init_BigNum(cur_line[i]);
for ( j=0; j<MAX; j++ )
cur_line[i][j] = next_line[i][j];
}
}
}
###### Who is Participating?

Commented:
C = A/B
just do the division as you would on paper

123456 / 123

count digits(B).
(**)
take that many digits from A [from the significant end]
if (part of A < B) get one more digit from A and append to the part of A
tmp1 = part of A
tmp2 = 0
while(tmp1 > B){
tmp1 -= B
tmp2++;
}
/* tmp2 is the first digit of C */
A -= b*tmp2;
repeat from (**) until A<B
0

Commented:
and btw in your program in the for loop

for(i=2;i<=n;i++)

you reallly need to do only till  i < = int(sqrt(n))

so you can just have

int k;
k = (int) sqrt(n);

for(i=2;i<=k;i++)

cos for values k > sqrt(n)    , the n/k  is less than k and hence must have already been found if k is a factor

for example

for 100

you need do that only till 10 cos  say for 20 , you have 100/20 = 5 , but 5 must have alreday been found when you had i = 5
0

Commented:
sorry wqrong question
my apologies
0

Commented:
okay since i bumped into here anyway ...

you need to have one more function

int number_of_digits (int a[] );

which returns the number of digits in a[]

so for 5631432100000000000000  it should return 8
(basically you read the array from MAX_SIZE  down to 0  and return the i +1 where i = first non zero number you reach

void divide_BigNum(int a[], int b[], int c[]){  /** i take this to men you want c = a/b ****/

if ( a < b ) {
return 0   ;  /*** we are talking of integer division right  , you can use your compare function to check if a < b * /
}

done = 0;

i = 0;

while(!done){
k = number_of_digits(b[]);
int  temp[MAX] = a[i]--[ k+i-1]  ;    /*** you have tofind a way to do it **/
if (temp < b ) {
temp[MAX] = a[i] ......a[k+i];
}

int ctr = 0;
int tempREM[MAX];
do{
subtract_BigNum( temp, a , temREM);
ctr++;
}while(tempREM > b )  /**this while loop will run for at most 9 times , here iam divinding by repeatedly substracting**/
c[i] = ctr ;
i++;
if( i+  number_of_digits (a)  >  number_of_digits (b) ){
done = 1;  /** no more  digits of b left *//
}

}

========================================

the above is what i just wrote off hand , I am sure there are mistakes , but i think you can build on it

0

Commented:
Long division is one way ... It might be difficult to incorporate but looks like a good way out ... search web for implementing long division using bitwise operators

Yet another way might be to break down your numerator and if required, the denominator ...

Assume that an int can hold only 3 digits for you and you need to calculate

123456 / 345

is same as

123X1000 + 456
---------------------
345

123   * 1000  +        456
-----                     ---------
345                          345

yet another and probably the best way out is to use one of the free open source big number libraries like gmp
http://www.swox.com/gmp/

At the very least, check their source code for finding out some better methods

Two side notes, Since you are storing only a digit per element of arra, you could have used unsigned chars ... That way you will require only 1/4th memory for storing your numbers

Second, EE allows max 500 points per question ... so you will not be able to award another 400 ;o)

cheers
0

Groupware ConsultantCommented:
Hi sonic2000,

You must be pretty desperate to leave behind your old question (http:Q_21110603). It IS the same question, isn't it?

Anyway, I will look through your code if I get the time today.

Cheers!
Sjef
0

Groupware ConsultantCommented:
I hoped you had something here, but you don't have any division-algorithm yet! Until then, I'll be off.
0

Commented:
>> /* tmp2 is the first digit of C */
better stated as: tmp2 is the most significant digit of C

and next iteration would make it next to the most significant and so on.

one more mistake:
A -= B*tmp2 is wrong
A -= B*tmp2 * 10^(dig(A) - dig(B)) or in a easier to understand format A -= B*tmp2*10^(log(A) - log(B))
0

Groupware ConsultantCommented:
Hi sonic2000,

For an urgent question, you don't show very much interest in the help you get here. Jhshukla even did half the thinking for you, in this homework-like question. Your opinion please ...

Sjef
0

Author Commented:
Problem is solved and the deadline is up.
But I think I will still award points here and of course not 900.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.