How to Differentiate a Polynomial in Java

1
2

Equation.differenatiate("12x+2", 3)      ==>   12
Equation.differenatiate("x^2+3x+2", 3)   ==>   9

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import java.math.BigInteger;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class Equation {
    private static final Pattern TERM = Pattern.compile("(.*?)x(\\^\\d+)?");

    public static BigInteger differentiate(String equation, long x) {
        BigInteger xb = BigInteger.valueOf(x);
        BigInteger result = BigInteger.ZERO;
        Matcher m = TERM.matcher(equation);
        while (m.find()) {
            long k = 1;
            String ks = m.group(1);
            if (!ks.isEmpty() && !ks.equals("+"))
                k = ks.equals("-") ? -1 : Long.parseLong(ks);
            int p = 1;
            String ps = m.group(2);
            if (ps != null)
                p = Integer.parseInt(ps.substring(1));
            result = result.add(BigInteger.valueOf(k).multiply(BigInteger.valueOf(p)).multiply(xb.pow(p - 1)));
        }
        return result;
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

import java.math.BigInteger;
import java.util.ArrayList;

public class Equation {
    
    public static BigInteger differentiate(String equation, long x) {
        if(equation.equals("")) {
            return new BigInteger("0");
        }

        ArrayList<String> list = new ArrayList<>();
        char[] charEquation = equation.toCharArray();
        String temp = "" + charEquation[0];
        for (int i = 1; i < charEquation.length; i++) {
            if (charEquation[i] == '-' || charEquation[i] == '+') {
                list.add(temp);
                temp = "" + charEquation[i];
            }
            else temp += charEquation[i];
        }
        list.add(temp);

        BigInteger sum = new BigInteger("0");
        for (String el : list) {
            if(el.contains("^")) {
                sum = sum.add(pow(el, x));
            } else if (el.contains("x")){
                sum = sum.add(noPow(el));
            }
        }

        BigInteger bi = new BigInteger(String.valueOf(sum));
        return bi;
    }

    public static BigInteger noPow (String equation) {
        if (equation.toCharArray()[0] == '-' || equation.toCharArray()[0] == '+') {
            String coef = "";
            for (int i = 1; i < equation.toCharArray().length; i++) {
                if(equation.toCharArray()[i] == 'x') {
                    break;
                } else {
                    coef += equation.toCharArray()[i];
                }
            }
            if (coef.equals("")) coef = "1";
            if (equation.toCharArray()[0] == '-') {
                return new BigInteger(coef).multiply(new BigInteger("-1")) ;
            }
            return new BigInteger(coef) ;
        } else {
            String coef = "";
            for (int i = 0; i < equation.toCharArray().length; i++) {
                if(equation.toCharArray()[i] == 'x') {
                    break;
                } else {
                    coef += equation.toCharArray()[i];
                }
            }
            if(coef.equals("")) coef = "1";
            return new BigInteger(coef);
        }

    }

    public static BigInteger pow(String equation, long x) {
        if(equation.toCharArray()[0] == '-' || equation.toCharArray()[0] == '+') {
            String coef = "";
            int counter = 0;
            for (int i = 1; i < equation.toCharArray().length; i++) {
                if(equation.toCharArray()[i] == 'x') {
                    counter = i;
                    break;
                } else {
                    coef += equation.toCharArray()[i];
                }
            }

            if(coef.equals("")) coef = "1";
            String powCoef = "";
            for (int i = counter + 2; i < equation.toCharArray().length; i++) {
                powCoef += equation.toCharArray()[i];
            }
            BigInteger biCoef = new BigInteger(coef);
            BigInteger biPowCoef = new BigInteger(powCoef);

            biCoef = biCoef.multiply(biPowCoef);
            biPowCoef = biPowCoef.add(new BigInteger("-1"));

            BigInteger result = biCoef.multiply(new BigInteger(String.valueOf(x)).pow(Integer.valueOf(biPowCoef.toString())));
            if(equation.toCharArray()[0] == '-') {
                return result.multiply(new BigInteger("-1"));
            }
            return result;
        } else {
            String coef = "";
            int counter = 0;
            for (int i = 0; i < equation.toCharArray().length; i++) {
                if(equation.toCharArray()[i] == 'x') {
                    counter = i;
                    break;
                } else {
                    coef += equation.toCharArray()[i];
                }
            }

            if(coef.equals("")) coef = "1";
            String powCoef = "";
            for (int i = counter + 2; i < equation.toCharArray().length; i++) {
                powCoef += equation.toCharArray()[i];
            }
            BigInteger biCoef = new BigInteger(coef);
            BigInteger biPowCoef = new BigInteger(powCoef);

            biCoef = biCoef.multiply(biPowCoef);
            biPowCoef = biPowCoef.add(new BigInteger("-1"));

            BigInteger result = biCoef.multiply(new BigInteger(String.valueOf(x)).pow(Integer.valueOf(biPowCoef.toString())));
            return result;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import java.util.*;
import java.math.BigInteger;

public class Equation {
    
  public static BigInteger differentiate(String equation, long x) {
    BigInteger res = BigInteger.ZERO,
                 X = BigInteger.valueOf(x);
    
    equation += "+";    
    Map <Integer, Integer> copt = new HashMap <> ();
    char[]                token = equation.toCharArray();
    int     coeff = 1,
            power = 1,
             leng = token.length;
    boolean isPow = false;
    
    for (int i = 0; i < leng; i++) {
      if (token[i] == '+' || token[i] == '-') {
        if (isPow) copt.put(power, coeff);
        isPow = false;
        power = 1;
        coeff = token[i] == '+' ? 1 : -1;
      }
      if (token[i] == 'x') isPow = true;
      if (Character.isDigit(token[i])) {
        StringBuilder sb = new StringBuilder();
                      sb.append(token[i]);
        while (i < leng - 1 && Character.isDigit(token[i+1])) sb.append(token[++i]);
        int value = Integer.parseInt(sb.toString());
        if (isPow) power *= value; 
        else coeff *= value;
      }
    }
    
    for (int p : copt.keySet()) {
      BigInteger mul = BigInteger.valueOf(p * copt.get(p));
      res = res.add(X.pow(p - 1).multiply(mul));
    }
    return res;  
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.math.BigInteger;

public class SolutionTest {
    @Test
    public void sampleTests() {
        assertEquals(new BigInteger("12"),  Equation.differentiate("12x+2", 3));
        assertEquals(new BigInteger("5"),   Equation.differentiate("x^2-x", 3));
        assertEquals(new BigInteger("-20"), Equation.differentiate("-5x^2+10x+4", 3));
    }
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.*;
import java.util.stream.*;


// TODO: Replace examples and use TDD development by writing your own tests

public class SolutionTest {

    @Test
    public void sampleTests() {
        assertEquals(new BigInteger("12"),  Equation.differentiate("12x+2", 3));
        assertEquals(new BigInteger("5"),   Equation.differentiate("x^2-x", 3));
        assertEquals(new BigInteger("-20"), Equation.differentiate("-5x^2+10x+4", 3));
    }
    
    @Test
    public void moreTests() {
        assertEquals(new BigInteger("9"),                    Equation.differentiate("x^2+3x+3",3) );
        assertEquals(new BigInteger("1062300"),              Equation.differentiate("1000x^2+300x+200",531) );
        assertEquals(new BigInteger("87017"),                Equation.differentiate("21x^2+35x+3",2071) );
        assertEquals(new BigInteger("38509884"),             Equation.differentiate("66x^3+3x^2+3",441) );
        assertEquals(new BigInteger("5962009860"),           Equation.differentiate("21x^4+3x^3",414) );
        assertEquals(new BigInteger("-2480823269890144044"), Equation.differentiate("-21x^5+3x^3",12398) );
        assertEquals(new BigInteger("-2469135813"),          Equation.differentiate("-x^2+3x-3",1234567908) );
        assertEquals(new BigInteger("-6045"),                Equation.differentiate("-7x^5+22x^4-55x^3-94x^2+87x-56",-3) );
        assertEquals(new BigInteger("-3300404885229567012"), Equation.differentiate("-123x^5+3x",8559) );
        assertEquals(new BigInteger("119769696967118"),      Equation.differentiate("x^2",59884848483559L) );
    }
    
    
    
    private static class RefSolver {
    
        final static private Pattern    PATTERN = Pattern.compile("\\+?(?<coef>-?\\d*)(?<var>x?\\^?)(?<exp>\\d*)");
        final static private BigInteger ZERO    = BigInteger.ZERO;
        
        
        private static BigInteger differentiate(String s, long x) {
            
            BigInteger              bigX     = new BigInteger(""+x);
            Map<Integer,BigInteger> derivate = new HashMap<>();
            Matcher                 m        = PATTERN.matcher(s);
            
            while (m.find()) {
                BigInteger coef  = new BigInteger( "-".equals(m.group("coef")) ? "-1"
                                                 : m.group("coef").isEmpty()   ?  "1": m.group("coef") ),
                                                 
                           exp   = new BigInteger(!m.group("exp").isEmpty() ? m.group("exp")
                                                 : m.group("var").isEmpty() ?  "0" : "1");
                                                 
                int exp_1 = exp.intValue()-1;
                if (exp_1!=-1 && !exp.equals(ZERO) && !coef.equals(ZERO)) {
                    derivate.put(exp_1, derivate.getOrDefault(exp_1, ZERO)
                                                .add(exp.multiply(coef)) );
                }
            }
            return derivate.entrySet()
                           .stream()
                           .map( me -> me.getValue().multiply( bigX.pow(me.getKey()) ) )
                           .reduce(BigInteger.ZERO, (a,b) -> a.add(b));
        }
    }
    
    private static final Random rnd = new Random();
    
    private static int rand(int x)        { return rnd.nextInt(x+1); }
    private static int rand(int a, int b) { return a + rnd.nextInt(b-a+1); }
    
    
    @Test
    public void randomTests() {
        
        for (int i=0 ; i<100 ; i++) {
            long   x = rand(1,10000);
            String s = "";
            while (s.isEmpty()) {
                List<String> eq = IntStream.range(0,rand(2,7))
                                           .mapToObj(SolutionTest::getRndTerm)
                                           .collect(Collectors.toList());
                Collections.reverse(eq);
                s = String.join("+",eq).replaceAll("^\\+|\\+(?=[+-]|$)|\\b1(?=x)", "");
            }
            BigInteger exp = RefSolver.differentiate(s,x);
            //System.out.println(s + " => "+exp);
            
            assertEquals(exp, Equation.differentiate(s,x));
        }
    }
    
    private static String getRndTerm(int exp) {
        int coef = rand(9)==0 ? 0 : rand(-100,100);
        if (coef==0) return "";
        if (exp==0)  return coef+"";
        if (exp==1)  return coef+"x";
        return String.format("%dx^%d", coef, exp);
    }
}