1
\$\begingroup\$

I'm working to implement some simple bigint functions for addition, multiplication and powers. They work correctly but the larger the numbers the longer the time it takes. For example 210000 takes a very long time. Here are all the functions I'm using.

char    *ft_strnew(size_t size)
    {
    char    *temp;
    size_t  i;

    if (!(temp = (char*)malloc(sizeof(char) * (size + 1))))
        return (NULL);
    i = 0;
    while (i < size)
    {
        temp[i] = '\0';
        i++;
    }
    temp[i] = '\0';
    return (temp);
}

char    *ft_strjoin(char const *s1, char const *s2)
{
    char    *temp;
    int     i;
    int     j;

    if (!(temp = (char*)malloc(sizeof(char) *
        (ft_strlen(s1) + ft_strlen(s2) + 1))))
        return (NULL);
    i = 0;
    j = 0;
    while (s1[i])
    {
        temp[j] = s1[i];
        i++;
        j++;
    }
    i = 0;
    while (s2[i])
    {
        temp[j] = s2[i];
        i++;
        j++;
    }
    temp[j] = '\0';
    return (temp);
}

int         left_one(int *i, char c)
{
    if (--(*i) < 0)
        return (0);
    else
        return (c - '0');
}

char        *add_char(char *nbr1, char *nbr2)
{
    int     i;
    int     j;
    int     left[4];
    char    *temp;

    left[0] = 0;
    temp = ft_strnew(0);
    i = ft_strlen(nbr1);
    j = ft_strlen(nbr2);
    if (i > j)
        left[3] = i;
    else
        left[3] = j;
    while (--left[3] >= 0)
    {
        left[1] = left_one(&i, nbr1[i - 1]);
        left[2] = left_one(&j, nbr2[j - 1]);
        left[0] += left[1] + left[2];
        temp = ft_charjoin((left[0] % 10) + '0', temp, 'l');
        left[0] /= 10;
    }
    if (left[0] > 0)
        temp = ft_charjoin((left[0] % 10) + '0', temp, 'l');
    return (temp);
}

char        *multi1_char(char *nbr1, int nbr2)
{
    int     i;
    char    *temp;

    if (nbr1[0] == '0' || nbr2 == 0)
        return ("0");
    i = -1;
    temp = ft_strdup(nbr1);
    while (++i < nbr2 - 1)
        temp = add_char(temp, nbr1);
    return (temp);
}

char        *multi_char(char *nbr1, char *nbr2)
{
    int         i;
    char        *temp;
    int         j;
    char        *temp1;
    int         t;
    char        *mul;

    mul = ft_strnew(0);
    temp = ft_strnew(1);
    j = 0;
    i = ft_strlen(nbr2);
    while (--i >= 0)
    {
        t = -1;
        temp1 = multi1_char(nbr1, nbr2[i] - '0');
        //temp1 = multi1_char(temp1, 10*j);
        /*while (++t < j)
            temp1 = ft_strjoin(temp1, "0");*/
        temp1 = ft_strjoin(temp1, mul);
        temp = add_char(temp, temp1);
        mul = ft_strjoin("0", mul);
        j++;
    }
    return (temp);
}

char    *power_char(int nbr1, int nbr2)
{
    char        *temp;

    temp = ft_strnew(0);
    if (nbr2 == 1)
        return (ft_itoa(nbr1));
    if (nbr2 % 2 == 0)
    {
        temp = power_char(nbr1, nbr2 / 2);
        return (multi_char(temp, temp));
    }
    else
    {
        nbr2 -= 1;
        temp = power_char(nbr1, nbr2 / 2);
        return(multi_char(ft_itoa(nbr1), multi_char(temp, temp)));
    }
}

I came up with a way to make the function that handles powers work faster but still the multiplication function is slow for big numbers.

Is there any way of improving my functions or are they bad from the start and I should start all over?

\$\endgroup\$
5
\$\begingroup\$

It seems you're allergic to for loops for some reason; for example, in ft_strnew:

for (size_t i = 0; i < size; i++)

There are examples elsewhere.

Don't predeclare your variables, e.g.

int     i;
int     j;

This hasn't been needed for 20 years. Declare them where they're used.

Replace this entire loop:

size_t  i;
i = 0;
while (i < size)
{
    temp[i] = '\0';
    i++;
}
temp[i] = '\0';

With this:

memset(temp, '\0', size+1);

Otherwise, your entire approach to arbitrary-size integer math is a quite slow one. (Other libraries have solved this, but it's nice that you're trying to learn.) You can't be doing this character by character; rather you need to do it integer by integer. Do some googling about arbitrary-precision integer arithmetic on 64-bit architectures.

A comment on something you said:

They work correctly but the larger the numbers the longer the time it takes.

No arbitrary-precision library can escape this. The execution time of even the best libraries will scale according to the size of the input when it exceeds the size of the machine word.

\$\endgroup\$
  • \$\begingroup\$ Thank you, about the "for loop " is something that i am not allowed to use only the "While loop" and for the predeclared variables its also something thats im forced to because of the norm You are correct my approach is very slow thank you for you informations i will look for what you suggested right away Again thank you very much \$\endgroup\$ – Hamza El Bouazizi Dec 13 '18 at 23:01
  • 2
    \$\begingroup\$ Not "being allowed" to use a for loop is ridiculous. \$\endgroup\$ – Reinderien Dec 13 '18 at 23:02
  • \$\begingroup\$ Yes i know but because using while while takes a bigger space and im not allowed to have more than 25lines in any function so i need to make the best out of my space \$\endgroup\$ – Hamza El Bouazizi Dec 13 '18 at 23:17
  • \$\begingroup\$ @HamzaElBouazizi Commenting about restrictions to code after a review is ineffective. Far better to post coding restrictions in the initial question. \$\endgroup\$ – chux Dec 15 '18 at 21:54
2
\$\begingroup\$

Drip, drip, drip

The is the sound a leak makes. This code also "drips" and leaks memory. The various allocations are lost. Instead code should

ptr = function_that_allocates(...);

// use ptr;

free(ptr);  // free memory when done.

Much too inefficient

Example: multi1_char(char *nbr1, int nbr2) performs O(nbr1 * nbr2) allocations and O(nbr1 * nbr1) runtime.

Consider the following which does 1 allocation and O(nbr1) run time. The below is untested, so consider it advanced pseudo code. This is much like grade school math.

char *multi1_char(const char *nbr1, int nbr2) {
  assert(nbr2 >= 0 && nbr2 < 10);
  size_t len = strlen(nbr1);  // If you cannot use strlen(), write your own

  // Make space for potential overflow, len, and \0
  char *product = malloc(1 + len + 1); 
  char *p = product + 1 + len;
  *p = '\0';

  int carry = 0;
  const char *n1 = nbr1 + len; // start at the \0
  while (n1 > nbr1) {
    n1--;
    int sum = (*n1 - '0')*nbr2 + carry;
    p--;
    *p = (sum%10) + '0';
    carry = sum/10;
  }
  if (carry) {
    p--;
    *p = carry + '0';
  } else {
    // Shift left
    for (size_t i = 0; i<len+1; i++) {  // Use a while loop is you must
      p[i] = p[i+1]; 
    }
  }
  return product;
}

Many other functions can similarly be improved. Allocate once for the result and avoid O(N to some power) solutions when a O(N to some smaller power) solution exists.

Deeper: multi1_char() is not even needed as multi_char(a,b) can be re-written with the above idea: allocate strlen(a) + strlen(b) + 1) memory and perform long multiplication.

\$\endgroup\$
1
\$\begingroup\$

You seem to be missing some required headers; at least <stdlib.h>, and also whatever defines ft_strlen, ft_strdup, ft_itoa and ft_charjoin.


Let's start with the first function, ft_strnew():

This allocation is very long-winded:

temp = (char*)malloc(sizeof(char) * (size + 1))

Firstly, it's not necessary or desirable to cast the result of malloc() - that's usually a symptom of not including <stdlib.h>. Secondly sizeof (char) is always 1, because sizeof measures in units of char. Thirdly, that's followed by a loop that zeroes out the storage; that's more efficiently achieved by using calloc() instead of malloc():

char *ft_strnew(size_t size)
{
    return calloc(size + 1, 1);
}

Next up, ft_strjoin(). This appears to be simply an allocating version of strcat(), so let's use that instead of hand-rolled loops:

#include <string.h>

char *ft_strjoin(char const *s1, char const *s2)
{
    char *result = malloc(strlen(s1) + strlen(s1) + 1);
    if (result) {
        strcpy(result, s1);
        strcat(result, s2);
    }
    return result;
}

Or a little more efficiently:

#include <string.h>

char *ft_strjoin(char const *s1, char const *s2)
{
    const size_t len1 = strlen(s1);
    const size_t len2 = strlen(s2);

    char *result = malloc(len1 + len2 + 1);
    if (result) {
        strcpy(result, s1);
        strcpy(result + len1, s2);
    }
    return result;
}

Either of those is much clearer and easier to read, IMO.


  int left_one(int *i, char c)

This function signature is very uninformative. What are i and c meant to represent? What's the result mean?

Perhaps this is intended to be internal (in which case it should be declared with static linkage), but even in that case, it still needs at least some guidance for the unfortunate maintenance engineer (which may well be Future You, so worth the investment!).

Even with the body, the intent is still mysterious:

if (--*i < 0)
    return 0;
else
    return c - '0';

(I've removed the extraneous parentheses for clarity). I would certainly expect at least one comment here.


Now on to add_char:

I don't understand what the array left[] is for - it seems to be used as four independent int variables rather than as an array. It's hard to give the function a full review due to the lack of its dependencies, particularly ft_charjoin() - does that function realloc() the passed temp? It's hard to reason about allocation and deallocation when they are so separated.


I'm going to abandon function-by-function review at this point, where it becomes clear that there's problems with the data representation - big-endian variable-length decimal strings are an unwieldy format, and we really need to improve on that first.

Little-endian strings are more suitable, as they don't need shuffling when overflow adds an extra digit, and we can store more than one decimal digit in an unsigned char (at least 2 decimal digits, or CHAR_BIT binary ones).

We should be able to reduce the number of memory allocations by implementing more in-place algorithms, rather than copying to new memory as much as we do.


A final general comment: this would have been much easier to review if the code were complete, and particularly if a sample main() had been included (perhaps the 2^10000 calculation mentioned in the text would be apposite?). Then I would have been able to run the code and perhaps even benchmark any suggestions.

\$\endgroup\$
  • \$\begingroup\$ First off, Thank you sir for the time, the thing about casting malloc and using sizeof is because i have to...its something i agreed on, and for the way you made ft_strjoin using strcpy what can i say i feel stupid especialy since i implemented strcpy myself, the function left_one is used to make sure i dont go in a place in mystring that doesnt exist (exemple : nbr1[-1]) instead it takes it as a 0, for the way im approaching the problem is bad as it seems so i will have to do some research. Overall you are right i should make my code more understandable using comments and provide a main \$\endgroup\$ – Hamza El Bouazizi Dec 13 '18 at 23:12
  • \$\begingroup\$ If your team style guide insists on writing sizeof (char) and useless/harmful casts, there's an argument that it needs to be reconsidered. Unfortunately, you probably have to gain your experience under these crazy constraints to get into a position where you can correct them! Good luck! \$\endgroup\$ – Toby Speight Dec 14 '18 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.