Solved

900 points!! Division Help

Posted on 2004-09-01
10
400 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
 
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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 500 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

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Suggested Solutions

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…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops 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.

743 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now