Synthetic Division Heavylifter

Synthetic Division Heavylifter is a tool available in JavaScript, Python, Ruby, and Common Lisp that performs synthetic division. Synthetic division is a process that is used to speed up the factoring of polynomials. However, it is still a hassle to utilize when the first term or the last term of the polynomial has a large number of factors, since the possible number factor candidates would increase. Enter Synthetic Division Heavylifter, which would do synthetic division for you. Below is the original JavaScript code that it was written in. It works nicely as a Rhino shell script.

var syntheticDivision = function(polynomial, divisor) {
  var result   = polynomial[0];
  var quotient = [result];  
  for (i = 1; i < polynomial.length; i++) {
    result *= divisor;
    result += polynomial[i];
    quotient.push(result);
  }
  var remainder = quotient.pop();
  return {'quotient': quotient, 'remainder': remainder};
};

var polynomial = arguments.map(Number);
var divisor    = polynomial.shift();
var result = syntheticDivision(polynomial, divisor);

print('Divisor: ' + divisor);
print('Polynomial: ' + polynomial.join(' '));
print('Quotient: ' + result.quotient.join(' '));
print('Remainder: ' + result.remainder);

It is also available in Python for those who don't want to mess around with Java, since Rhino is a Java implementation of JavaScript. The pitfall for the Python version is that if a decimal number shows up anywhere, whether in the divisor or in the polynomial coefficients, it will be converted into an integer. To fix this, change the two instances of int to float.

#!/usr/bin/python
import sys

def synthetic_division(polynomial, divisor):
  result = polynomial[0]
  quotient = [result]
  for i in range(1, len(polynomial)):
    result *= divisor
    result += polynomial[i]
    quotient.append(result)
  remainder = quotient.pop()
  return {"quotient": quotient, "remainder": remainder}

polynomial = map(int, sys.argv[2:])
divisor = int(sys.argv[1])
result = synthetic_division(polynomial, divisor)

print "Divisor: " + str(divisor)
print "Polynomial: " + " ".join(map(str, polynomial))
print "Quotient: " + " ".join(map(str, result["quotient"]))
print "Remainder: " + str(result["remainder"])

And in Ruby as well. It suffers the same problem as the Python version does. To fix this, change n.to_i to n.to_f. Only JavaScript doesn't suffer from this problem, because there's only one kind of number, which is Number.

#!/usr/bin/ruby
def synthetic_division(polynomial, divisor)
  result = polynomial.first
  quotient = [result]
  polynomial[1, polynomial.size - 1].each do |coefficient|
    result *= divisor
    result += coefficient
    quotient << result
  end
  remainder = quotient.pop
  { :quotient => quotient, :remainder => remainder }
end

polynomial = $*.map { |n| n.to_i }
divisor = polynomial.shift
result = synthetic_division polynomial, divisor

puts "Divisor: #{divisor}"
puts "Polynomial: #{polynomial * " "}"
puts "Quotient: #{result[:quotient] * " "}"
puts "Remainder: #{result[:remainder]}"

Also, in Common Lisp. This only has the function, as the way to handle command line parameters vary between different implementations. I'm very sure this isn't considered "Lispy" and would surely seem like an awkward port from an extremely Algol-like mindset in the eyes of a seasoned Lisper.

(defun synthetic-division (polynomial divisor)
  (setf result (car polynomial)) 
  (setf quotient (list result))
  (dolist (coefficient (cdr polynomial))
    (setf result (* result divisor))
    (setf result (+ result coefficient))
    (push result quotient))
  (setf remainder (pop quotient)) 
  (list 'quotient (nreverse quotient) 'remainder remainder))