[2 days left] Whatâ€™s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
Solved

# 900 points!! Division Help

Posted on 2004-09-01
Medium Priority
456 Views
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.

I am left with the divide function and am very stuck with it! PLEASE HELP.

#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 add_BigNum(int[], int[], int[]);
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 */
c[i] = col_add % 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];
}
}
}
0
Question by:sonic2000
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions
• 3
• 3
• 2
• +2

LVL 11

Expert Comment

ID: 11958977
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

LVL 11

Expert Comment

ID: 11958979
sorry wqrong question
my apologies
0

LVL 11

Expert Comment

ID: 11959854
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

LVL 45

Expert Comment

ID: 11960787
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

LVL 46

Expert Comment

ID: 11961295
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

LVL 46

Expert Comment

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

LVL 9

Accepted Solution

jhshukla earned 1500 total points
ID: 11975566
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

LVL 9

Expert Comment

ID: 11975662
>> /* 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

LVL 46

Expert Comment

ID: 11976436
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 Comment

ID: 11978526
Problem is solved and the deadline is up.
But I think I will still award points here and of course not 900.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: Iâ€™ve never triâ€¦
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
###### Suggested Courses
Course of the Month14 days, 5 hours left to enroll

#### 656 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.