[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

900 points!! Division Help

Posted on 2004-09-01
10
Medium Priority
?
461 Views
Last Modified: 2010-04-15
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;
      int col_add, carry=0;

      /* 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 */
            add_BigNum(temp1, c, temp2);
            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[])
{
    //ignore leading zeros
    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
                        add_BigNum(cur_line[i-1], cur_line[i], next_line[i]);

                  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
Comment
Question by:sonic2000
  • 3
  • 3
  • 2
  • +2
10 Comments
 
LVL 11

Expert Comment

by:avizit
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

by:avizit
ID: 11958979
sorry wqrong question
my apologies
0
 
LVL 11

Expert Comment

by:avizit
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 45

Expert Comment

by:sunnycoder
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

by:Sjef Bosman
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

by:Sjef Bosman
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

by:
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

by:jhshukla
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

by:Sjef Bosman
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

by:sonic2000
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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
Suggested Courses

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

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

Join & Ask a Question