42_EXT_05_computorv1

todo

• arg limit ?
• change order is_number_int and is_number_double
• remove double limit in lexer
• check why number stored in int or double
• get rid of lib math (check in libft)
• use ft_abs() instead of abs() -> actually abs() is in stdlib
• solve expressions without '=' ?
• solve when max exponent is 0
• check reduced form in subject

ressources

• project intra : https://projects.intra.42.fr/projects/42cursus-computorv1
• project luke : https://github.com/LuckyLaszlo/computorv1

install

this project uses submodules (maybe recursively), so either :

• git clone --recurse-submodules <repo-url>
• or, after cloning : git submodule update --init --recursive

---

sqrt implementation

finding the square root of x

dichotomy method

the dichotomie method, or binary search, consist on dividing the range of research by 2 each time, and choosing the right one for the next iteration.

Ex :

     solution
        ↓
|------------------------------ 1. define range bound_1 : 0
|-----------------------------| 2. define range bound_2 : x
|--------------+--------------| 3. take mid : (bound_1 + bound_2) / 2
|--------------|-------ø------| 4. choose range bound : bound_1 or bound_2

---------------|--------------- 1. range bound_1 = mid
|--------------|--------------- 2. range bound_2 = chosen previous bound
|------+-------|--------------- 3. mid
|--ø---|-------|--------------- 4. choose range

-------|----------------------- 1. range bound_1 = mid
-------|-------|--------------- 2. range bound_2 = chosen previous bound
-------|---+---|--------------- 3. mid
-------|---|-ø-|--------------- 4. choose range

-----------|------------------- 1. range bound_1 = mid
-------|---|------------------- 2. range bound_2 = chosen previous bound
-------|-+-|------------------- 3. mid
-------|-|ø|------------------- 4. choose range

---------|--------------------- 1. range bound_1 = mid
-------|-|--------------------- 2. range bound_2 = chosen previous bound
-------|+|--------------------- 3. mid
-------ø|---------------------- 4. choose range

--------|---------------------- --> solution

Newton–Raphson method

it's like a self-correcting binary search, we get rid of the step "choose range", we use the formulae x/v to find the next range, with x being the number we are trying to get the sqaure root from, and v the value found at the previous step.

Ex :

     solution
        ↓
------------------------------| 1. define range bound_1 : v
--|---------------------------| 2. choose range bound_2 : x/v
--|-------------+-------------| 3. take mid : (v + x/v) / 2

----------------|-------------- 1. range bound_1 : v = mid
------|---------|-------------- 2. range bound_2 : x/v
------|----+----|-------------- 3. mid

-----------|------------------- 1. range bound_1 : v = mid
-|---------|------------------- 2. range bound_2 : x/v
-|----+----|------------------- 3. mid

------|------------------------ 1. range bound_1 : v = mid
------|-------|---------------- 2. range bound_2 : x/v
------|---+---|---------------- 3. mid

----------|-------------------- 1. range bound_1 : v = mid
------|---|-------------------- 2. range bound_2 : x/v
------|-+-|-------------------- 3. mid

--------|---------------------- --> solution

mathematical proof that each range is automatically in the right range :

• if the value was higher than the answer, then new value is below old value, and vice versa
• how ? :
  • define x, solution s = √x, and value v = (old_value + x / old_value) / 2
  • supposition : if v < s , then new_v > v, else new_v < v :
  • demonstration :
    1. if v < s : v < s <=> v < √x <=> v² < x (that's actually how we know that v < s) <=> v²/v < x/v <=> v < x/v -> and is s < x/v ? : v < s <=> v < √x <=> v² < x (as previously) <=> v² < x²/x <=> v² _ x < x² <=> (v _ √x)² < x² <=> v _ √x < x <=> v _ √x < v * x/v <=> √x < x/v -> so indeed : if v < √x, then v < √x < x/v == v < s < x/v -> conclusion, the new range < v , x/v > contains the solution
    2. the same demonstration works for v > s

here is a more intuitive demonstration, with x = 20 :

1. show that if v² > x (== v > s) then v > s > x/v, and if v² < x (== v < s) then v < s < x/v : 1.1. for value too high v > s : 1.1.1 why v > x/v : - let's take initial value v = 5 : - is 5² the solution ? 5² == 25 -> so no, 5 is not the sqrt, it's too high v v² 0 (5) 10 15 20 25 v : |----|----|----|----|----| x/v: |---|---|---|---|---| <----- squiz it, so the previous 5 portions fit the x = 20 size 0 (4) 8 12 16 20 x/v x - the value of the new portion is 4, and we can visually see that it's lower than the previous portion 5 - so : v > x/v 1.1.2 why s > x/v : - let's take the value v = 5 : - we already showed that it's too high, now we will see that x/v == 20/5 is too low : v 0 (5) 10 15 20 25 v : |----|----|----|----|----| x/v: |---|---|---|---|---| <----- squizz 0 *1 *2 *3 *4 *5 -> number of portions 01234 -> portion size (x/v)²: |---|---|---|---| 0 4 8 12 16 - the portion size is smaller than the number of portions, so it's too small to be the sqrt, indeed we visually see that this portion size x/v is a root of a smaller number : (x/v)² == 16 - so : s > x/v 1.1.3. conclusion : - v > s - and v > x/v (<- this proof is not essential) - and s > x/v (<- we actually only need this proof) - so v > s > x/v

   1.2. for value too high v < s :

   • this is the same demonstration but in other direction, let's just summarize it :
   • let's take initial value v = 4 :

                     v           v²
                 0  (4)  8   12  16
     (1) v  :    |---|---|---|---|
     (2) x/v:    |----|----|----|----|   -----> stretch
     (3)         0   (5)   10   15   20
                     x/v             x
     (4)         0   *1   *2   *3   *4       -> number of portions
                 012345                      -> portion size
     (5) (x/v)²: |----|----|----|----|----|
                 0    5    10   15   20   25
     

   • (1) : 4 is not the sqrt of x == 20, it's too smalle : (4² == 16) < 20
   • (2) : stretch it, so the previous 4 portions fit the x = 20 size
   • (3) : the new portion x/v == 5, is more than v == 4, so v < x/v
   • (4) : portion size is bigger than number of portions, so it's too big to be the root
   • (5) : indeed, we see that the portion² == (x/v)² is bigger than x, so √x < x/v == s < x/v
   • so v < s < x/v