0

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

Attachments mesh.PNG 8.59 KB
4
Contributors
6
Replies
8
Views
9 Years
Discussion Span
Last Post by iamthwee
0

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.

0

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?

0

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.

0

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.

0
#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)
Votes + Comments
Indeed it is
impressive
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.