Member Avatar for wellibedamned

Okay, so i have an idea...that looks like it should work. I'm supposed to be able to multiply for example: 1234567812345678912345678*1234562345673456.
My idea was to put each number into a string, and then make a matrix to store the values of each digit multiplied by each digit... i'll put an image down there so you could see what i mean. I've done all of that, but the tricky part comes now.. i gotta sum the diagonals of that table (red ones on the pic)... put the sums into another array, and then work with fixing numbers larger than 9 in them. Hope someone got what i was thinking... Just tell me if it's a stupid idea!

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAX 505

using namespace std;

int fix(char a[MAX], char b[MAX]){while(strlen(a) != strlen(b))
                                                    if(strlen(a) < strlen(b))
                                                                 {strrev(a); strcat(a, "0"); strrev(a);}
                                                    else {strrev(b); strcat(b, "0"); strrev(b);}
                                                                 }
int main(void)
{
    char n1[MAX], n2[MAX];
    scanf("%s%s", n1, n2);
    fix(n1, n2);
    //printf("%s %s", n1, n2);
    int mat[MAX][MAX], bigarr[2*MAX];
    
    for(int i = 0; i < strlen(n1); i++)   
            for(int j = 0; j < strlen(n2); j++){
                    mat[i][j] = (int(n1[i])-48)*(int(n2[j])-48);
                    //printf("%d", mat[i][j]);
                    }
    
    
    scanf("\n");
    return 0;
}

ow, and also, if someone could tell me an easier way to concatenate a string to add some zeros to it, i would be really thankful. <--- this is the image

mesh.PNG 8.59 KB
  • 4 Contributors
  • 6 Replies
  • 399 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by iamthwee

Recommended Answers

All 6 Replies

Member Avatar for selvaganapathy

HI
I heard about Number Theory algorithm for long number addition, subtration, multiplication and division. It was found in a book [Cryptography in C]. I hope, It may help to u.

Member Avatar for wellibedamned

Hmm, can't use that. Kinda can't use non standard cpp libs... I'll check it out anyways. What do you mean by reinventing the wheel?

Member Avatar for jephthah

its an expression.

as in, don't waste your time "inventing" something that's already been done.

GMP may not be "Standard C++" but it is one of the industry standards.

Member Avatar for wellibedamned

i get it. i'm not trying to reinvent something that has been invented. I just think i should know how it works. Also, i'm not in the industry (no waaaaii), i'm in school. And i guess my teacher would go like "Waaat?! Wat is dat GMP?" and my school standards are iostream, cstdio, string, cstring, cstdlib, vector, algorithm, functional and that's it i think. can't even use conio.h i think.

Member Avatar for iamthwee 
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_DIGITS 1024

void  gradeSchool ( int *a, int *b, int *ret, int d );
void  doCarry ( int *a, int d );
void  getNum ( int *a, int *d_a );
void  printNum ( int *a, int d );

int main()
{
  int             a[MAX_DIGITS];
  int             b[MAX_DIGITS];
  int             r[6 * MAX_DIGITS];
  int             d_a;
  int             d_b;
  int             d;
  int             i;
  clock_t         start;
  clock_t         stop;

  getNum ( a, &d_a );
  getNum ( b, &d_b );

  if ( d_a < 0 || d_b < 0 )
  {
    printf ( "0\n" );
    exit ( 0 );
    return 0;
  } 

  i = ( d_a > d_b ) ? d_a : d_b;
  for ( d = 1; d < i; d *= 2 );
  for ( i = d_a; i < d; i++ ) a[i] = 0;
  for ( i = d_b; i < d; i++ ) b[i] = 0; 

  start = clock();
  stop = start + CLOCKS_PER_SEC;
  for ( i = 0; clock() < stop; i++ )
  {
    gradeSchool ( a, b, r, d );
    doCarry ( r, 2 * d );
  }
  start = clock() - start;
  printNum ( r, 2 * d );
  printf ( " %f ms (%d trials)\n", 1000 * ( double ) start / CLOCKS_PER_SEC / i, i );

  system ( "pause" );
} 
void gradeSchool ( int *a, int *b, int *ret, int d )
{
  int i, j;

  for ( i = 0; i < 2 * d; i++ ) ret[i] = 0;
  for ( i = 0; i < d; i++ )
  {
    for ( j = 0; j < d; j++ ) ret[i + j] += a[i] * b[j];
  }
}

void doCarry ( int *a, int d )
{
  int             c;
  int             i;

  c = 0;
  for ( i = 0; i < d; i++ )
  {
    a[i] += c;
    if ( a[i] < 0 )
    {
      c = - ( - ( a[i] + 1 ) / 10 + 1 );
    }
    else
    {
      c = a[i] / 10;
    }
    a[i] -= c * 10;
  }
  if ( c != 0 ) fprintf ( stderr, "Overflow %d\n", c );
}

void getNum ( int *a, int *d_a )
{
  int c;
  int i;

  *d_a = 0;
  while ( true )
  {
    c = getchar();
    if ( c == '\n' || c == EOF ) break;
    if ( *d_a >= MAX_DIGITS )
    {
      fprintf ( stderr, "using only first %d digits\n", MAX_DIGITS );
      while ( c != '\n' && c != EOF ) c = getchar();
    }
    a[*d_a] = c - '0';
    ++ ( *d_a );
  }

  for ( i = 0; i * 2 < *d_a - 1; i++ )
  {
    c = a[i], a[i] = a[*d_a - i - 1], a[*d_a - i - 1] = c;
  }
}

void printNum ( int *a, int d )
{
  int i;
  for ( i = d - 1; i > 0; i-- ) if ( a[i] != 0 ) break;
  for ( ; i >= 0; i-- ) printf ( "%d", a[i] );
}

Input

1234567812345678912345678
1234562345673456

Output

1524150934302428409273601219887580923168 0.015843 ms (63120 trials)
commented: impressive +3
commented: Indeed it is +5
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.