2

I am trying to represent a string that holds any number to infinity. This number must be an integer and return its value as a result. Right now, my goal is to do this representation but for division only. So lets say we have 125 as our numerator, and 5 as our denominator. The answer should be 25 right? However, I need to represent this number as a linked list of strings. Currently the way to approach this problem is doing "division by subtracting" because I can iterate the number over and over without worrying its remainder and the size of the number. The iteration must be with a base number of 10, meaning it has to read '0' to '9'.

My division consists with operands A and B, and incrementing counter (which will be end result), and subtraction these operands. Here is the logic/pseudocode that I found from Wikipedia and my partner:

while N >= D do
    then  N := N - D
    counter++
end
return N

In our previous example, the 125/5 will result a counter of 25 because we are iterating our N every time and subtracting it with 5. Once N is not greater or equal to D, then we can finally finish and return our result according to the counter. This counter will be placed in a new list and added to our current list to return its final value.

I had to make separate functions to come with the logic, but I think something is not right structured.

Linked lists

typedef struct      s_list
{
    void            *content;
    size_t          content_size;
    struct s_list   *next;
}                   t_list;

typedef struct  s_BigNumber
{
    char        *base;
    int         base_size;
    char        *exp;
    int         exp_size;
}               t_BigNumber;

List add function

void    lstadd(t_list **alst, t_list *new)
{
    if (new)
    {
        new->next = *alst;
        *alst = new;
    }
}

Incrementor

t_list  *increment(t_bistro *bistro, t_list *oper)
{
    t_list  *incr;
    t_list  *counter;

    incr = NULL;
    lstadd(&incr, ft_lstnew(&(bistro->base[1]), 1));
    counter = addition(bistro, oper, incr);
    del_num(oper);
    free(incr->content);
    free(incr);
    return (counter);
}

My subtraction function is pretty big and requires other functions to works, so I will skip the code of it.

This is my actual code with everything mentioned from above:

Division

t_list      *division(t_list *big, t_list *oper1, t_list *oper2)
{
    t_list  *result;
    t_list  *tmp;

    result = NULL;
    lstadd(&result, lstnew(&(big->base[0]), 1)); //Creates a new list with the result to the first index of the new list
    while (oper2->content >= oper1->content)
    {
        tmp = result;
        result = subtract(big, result, oper1);
        del_num(tmp);
        oper2 = increment(big, oper2);
    }
    return (result);
}

Printing the value

void    digit_printer(char *num)
{
    char c;

    c = *num;
    putchar(c);
}

void    digitizer(t_list *num)
{
    if (num->next)
        digitizer(num->next);
    digit_printer(num->content);
}

Main

int main()
{
    t_list  *op1;
    t_list  *op2;
    t_list  *result;
    t_BigNumber *big;
    char *str = "125";
    char *str1 = "5";

    op1 = NULL;
    op2 = NULL;
    while (*str)
    {
        lstadd(&op1, lstnew(str, 1));
        str++;
    }
    while (*str1)
    {
        lstadd(&op2, lstnew(str1, 1));
        str1++;
    }

    big = malloc(sizeof(t_BigNumber));
    big->base = "0123456789";
    big->base_size = 10;

    result = division(big, op1, op2);
    digitizer(result);
    printf("\n");
}

Expected output: 25

I'm looking for a open discussion and willing to give suggestions. It is up to you to come with a solution. Some guidance and examples will help me :). Sorry for my English overall.

Community
  • 1
  • 1
Zeid Tisnes
  • 396
  • 5
  • 22
  • 3
    Division by subtraction is not a good idea, even with simple 32-bit numbers. You need [long division](https://en.wikipedia.org/wiki/Long_division#Example_with_multi-digit_divisor). – user3386109 Jan 14 '18 at 05:23
  • 3
    and storing digits in a linked list is an even worse idea – phuclv Jan 14 '18 at 05:34
  • @user3386109 That is what I was thinking, but my partner disagreed because it will be more complicating to build the algorithm for it. What would you suggest? – Zeid Tisnes Jan 14 '18 at 05:51
  • @Lưu Vĩnh Phúc They are dynamically allocated too, plus they are in a different linked lists after the arithmetic is done. – Zeid Tisnes Jan 14 '18 at 05:52
  • 1
    Yes it is more complicated. But simple subtraction will never finish. Simple example `60000000000000000000 / 2`. Assuming you have a 3GHz processor, come back in 1000 years to see if your program is finished. – user3386109 Jan 14 '18 at 05:58
  • @user3386109 oh wow lol, that is actually slow. Okay then, if i want to perform long division algorithm with links, what would be ideal for the average O-notation? – Zeid Tisnes Jan 14 '18 at 06:08
  • 1
    It's `O(N*D)` where `N` is the number of digits in the numerator, and `D` is the number of digits in the denominator. So basically instantaneous for my previous example. You need to get into thousands of digits in the numerator and denominator before long division gets slow. – user3386109 Jan 14 '18 at 06:14
  • Remember, with a proper long division algorithm you will get within 1 of the correct quotient digit (and always above if you miss) simply by comparing the leading digits. TAOCP vol. 2 has a very good treatment of the four basic math operations. I also agree with the statement that a list is a terrible structure for this, a simple array (or broken array such as a eque) is a much better choice. – SoronelHaetir Jan 14 '18 at 07:34
  • 1
    there's no problem if this is a homework, but [in real life](https://stackoverflow.com/q/34170566/995714) people generally [don't use linked lists](https://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/), and [never use base 10 but base 2^32 or 10^9 in 32-bit computers and base 2^64 or 10^19 in 64-bit ones](https://stackoverflow.com/q/10178055/995714) – phuclv Jan 14 '18 at 07:54

0 Answers0