Large number stored as vector, increase performance

Question

I made a code to initialize char vectors with random numbers representing very large numbers with more than 20.000 digits. The additions and multiplications are correct but my code is too slow (1 minute). I know that I can change char by 64 int to make operations with 19 numbers at a time, instead of 1 digit at a time, but I don't know how to do that without changing my current output that is correct.

Thanks for your help

#include <stdio.h>
#include <stdlib.h>

unsigned int seed;

int newrandom() {
  seed = (214013*seed+2531011);
  return (seed>>13);
}


void LongNumInit( char *L, unsigned N )
{
  for ( int i=0; i< N; i++ ) 
  {
    L[i] = newrandom() % 10;
  }
}

void PrintNumber( char *L, unsigned N, char *Name )
{
  printf("%s:", Name);
  for ( int i=N; i>0; i-- ) 
  {
    printf("%d", L[i-1]);
  }
  printf("\n");
}


void ValueSet( char *L, unsigned N, char digit )
{
  for ( int i=0; i< N; i++ ) 
  {
    L[i] = digit;
  }
}


void CPNumber( char *Vin, char *Vout, unsigned N )
{
  for ( int i=0; i< N; i++ ) 
  {
    Vout[i] = Vin[i];
  }
}

char Add( char *Vin1, char *Vin2, char *Vout, unsigned N )
{
  char CARRY = 0;
  for ( int i=0; i< N; i++ ) 
  {
    char R = Vin1[i] + Vin2[i] + CARRY;
    if ( R <= 9 )
    {
      Vout[i] = R; CARRY = 0;
    }
    else
    {
      Vout[i] = R-10; CARRY = 1;
    }
  }
  return CARRY;
}


char DigitAddition( char *V, char digit, unsigned N )
{
  int i=0;
  char R = V[0] + digit;
  if (R < 10)
  {
    V[0] = R; return 0;
  }

  V[0] = R-10;
  char CARRY = 1;
  i = 1;
  while ( CARRY && i < N ) 
  {
    if ( V[i] < 9 )
    {
      V[i] = V[i] + 1; CARRY = 0;
    }
    else 
    {
      V[i] = 0; i++;
    }
  }
  return CARRY;
}


char AddInHorizontal( char *Vin, char *Vout, unsigned N )
{
  char CARRY = 0;
  ValueSet ( Vout, N, 0 );
  for ( int i=0; i< N; i++ ) 
  {
    DigitAddition ( Vout, Vin[i], N );
  }
  return 0;
}

char MultiplyConst( char *V, unsigned N, char digit )
{
  char CARRY = 0;
  for ( int i=0; i< N; i++ ) 
  {
    char R = V[i] * digit + CARRY;
    CARRY = R / 10;
    R = R - CARRY*10;
    V[i] = R;
  }
  return CARRY; // may be from 0 to 9
}

void Mult( char *Vin1, char *Vin2, char *VoutH, char *VoutL,  unsigned N )
{ 

  unsigned char *TEMP= (unsigned char*) malloc( 2*N*sizeof(unsigned char) );
  unsigned char *RES = (unsigned char*) malloc( 2*N*sizeof(unsigned char) );

  ValueSet  ( RES, 2*N, 0 );    // Set RES to 0

  for ( int i=0; i<N; i++ ) 
  { 
    ValueSet  ( TEMP, 2*N, 0 );            
    CPNumber ( Vin1, TEMP+i, N );         
    MultiplyConst( TEMP, 2*N, Vin2[i] );
    Add ( TEMP, RES, RES, 2*N ); // TEMP + RES -> RES
  }

  CPNumber ( RES,   VoutL, N ); 
  CPNumber ( RES+N, VoutH, N ); 
}


int main (int argc, char **argv)
{
  int i, sum1, sum2, sum3, N=20000;

  seed = 12345;

  if (argc>1) { N    = atoi(argv[1]); }
  if (argc>2) { Rep  = atoi(argv[2]); }

  unsigned char *V1= (unsigned char*) malloc( N*sizeof(unsigned char) );
  unsigned char *V2= (unsigned char*) malloc( N*sizeof(unsigned char) );
  unsigned char *V3= (unsigned char*) malloc( N*sizeof(unsigned char) );
  unsigned char *V4= (unsigned char*) malloc( N*sizeof(unsigned char) );

  LongNumInit ( V1, N );
  LongNumInit ( V2, N );
  LongNumInit ( V3, N );

  Add ( V1, V2, V4, N );
  Mult ( V3, V4, V2, V1, N );
  AddInHorizontal ( V1, V2, N );
  DigitAddition ( V3, V2[0], N );

  PrintNumber( V1, 32, "V1" );
  PrintNumber( V2, 32, "V2" );
  PrintNumber( V3, 32, "V3" );
  PrintNumber( V4, 32, "V4" );

  free(V1);
  free(V2);
  free(V3);
  free(V4);
  return 0;
}

```

Answer 1

Congratulations on having code ready to review! Here are some thoughts on how you could improve this:

1. You have tagged this code as both C and C++. To me, this looks purely like C code. If so, please edit the tags. If this needs to work as both C and C++ code, you'll want to specify what other constraints apply.

2. C code is generally written using snake_case for function names. For a module of functions operating on a shared data type, a short prefix is often used. Since you are calling your objects "LongNum", I suggest you rename your functions to use a prefix of lnum_ or lngn_ or lnm_ or something.

   char Add( char *Vin1, char *Vin2, char *Vout, unsigned N ) {...}
   

   becomes

   char lnum_add(char * ln1, char *ln2, char *lnout, unsigned N) {...}
   

3. Creating a LongNum requires allocating memory. That operation can and should be part of the library by default. (You might want to code a function for "initialize longnum from user-supplied memory" but I doubt you'll need it.) So you should not be doing malloc() or free() calls directly, but instead you should be calling lnum_new_random() and lnum_delete().

4. I don't see a reason to avoid the C++ naming scheme, so I suggest calling your creation/allocation functions new and your free functions delete.

5. Related to (4), I believe a good library should be able to create objects in various ways. Particularly, a random value, a fixed value like zero or one, an arbitrary integer value, a value from a double, and possibly values from strings, and/or values from an input stream.

   lnum_new_random(unsigned max_digits)
   lnum_new_zero(unsigned max_digits)
   lnum_new_from_int(unsigned max_digits, long long init_val)
   lnum_new_from_unsigned(unsigned max_digits, unsigned long long init_val)
   lnum_new_from_double(unsigned max_digits, long double init_val)
   lnum_new_from_string(unsigned max_digits, const char * str)
   lnum_new_from_file(unsigned max_digits, FILE * input)
   lnum_new_from_lnum(LNUM original)
   

6. Instead of passing a parameter N around to specify the maximum length of the data type, why not build a struct to store the information.

   For starters, you could define a struct with your max_digits value and the pointer to the start of the digits buffer. A more advanced version would eliminate the pointer and allocate the digit buffer immediately after the max_digits value.

   struct LNUM {
       unsigned max_digits;
       char * digits;
   };
   

   By doing this, you could decide whether passing the objects as pointers or struct values made more sense. So you would want a named type that you control, rather than just letting the user pass around a char * pointer:

   typedef struct LNUM LNUM;     // if struct LNUM includes digits as pointer
   typedef struct LNUM * LNUM;   // if struct LNUM includes digits as array
   

7. Your PrintNumber function provides the only way to extract the number. And it hard-codes the radix, the output stream, and the format. I'd suggest writing a function to emit an LNUM onto a stream, and one to write an LNUM into a string buffer in a provided radix.

   size_t lnum_formatted_length(LNUM ln);
   void lnum_format_to_string(LNUM ln, char * buffer, size_t max_chars);
   

8. Instead of treating N as a constant, would it be so wrong to have N dynamically computed? Your multiplication function returns two numbers, "low" and "high", each of size N. Why not simply return a single number that has the correct size as determined by your multiply function? Maybe it needs more digits, maybe it doesn't.