Krdytkyu

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 2^10000 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] = '';

        i++;

    }

    temp[i] = '';

    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] = '';

    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?

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] = '';

    i++;

}

temp[i] = '';

With this:

memset(temp, '', 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.

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 (either 2+ digits, or the full range of UCHAR_MAX).

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.