## wellibedamned Light Poster

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

## selvaganapathy 31

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.

## jephthah 1,888

don't reinvent the wheel.

## 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?

## jephthah 1,888

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.

## 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.

## iamthwee 1,547

``````#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