Skip to content

Instantly share code, notes, and snippets.

@Brandon-Rozek
Created May 15, 2021 00:00
Show Gist options
  • Save Brandon-Rozek/6e98315faf52d31ef70503e0413934cc to your computer and use it in GitHub Desktop.
Save Brandon-Rozek/6e98315faf52d31ef70503e0413934cc to your computer and use it in GitHub Desktop.
Different arithmetic calculations represented as tail recursions
// Addition & subtraction are independent implementations
var add = function(x, y) {
if (y == 0) {
return x;
}
if (y < 0) {
return add(x - 1, y + 1);
}
return add(x + 1, y - 1);
}
var subtract = function(x, y) {
if (y == 0) {
return x;
}
if (y < 0) {
return subtract(x + 1, y + 1);
}
return subtract(x - 1, y - 1);
}
// Negate relies upon addition to work
var negate = function(x) {
return negate_helper(x, x);
}
var negate_helper = function(orig_x, x) {
if (add(orig_x, x) == 0) {
return x;
}
if (orig_x < 0) {
return negate_helper(orig_x, x + 1);
}
return negate_helper(orig_x, x - 1);
}
// Multiply relies on addition & subtraction to work
var multiply = function(x, y) {
if (y == 0) {
return 0;
}
if (y < 0) {
y = negate(y);
return negate(multiply_helper(x, x, y));
}
return multiply_helper(x, x, y);
}
var multiply_helper = function(x, orig_x, y) {
if (y == 1) {
return x;
}
return multiply_helper(add(x, orig_x), orig_x, y - 1);
}
var factorial = function(x) {
if (x < 0) {
return NaN;
}
if (x == 0 || x == 1) {
return 1;
}
return multiply(x, factorial(x - 1));
}
// Division depends on addition & negate to work
var divide = function(x, y) {
if (x < 0) {
x = negate(x);
y = negate(y);
}
if (y == 0) {
return NaN;
}
if (y == 1) {
return x;
}
if (y > x) {
return 0;
}
if (y < 0) {
y = negate(y);
return negate(divide_helper(x, y, y, 1));
}
return divide_helper(x, y, y, 1);
}
var divide_helper = function(x, y, orig_y, counter) {
if (y > x) {
return counter - 1;
}
if (y == x) {
return counter;
}
return divide_helper(x, add(y, orig_y), orig_y, counter + 1);
}
var exponentiate = function(x, y) {
if (y == 0) {
return 1;
}
if (y < 0) {
return 0;
}
return exponentiate_helper(x, x, y);
}
var exponentiate_helper = function(x, orig_x, y) {
if (y == 1) {
return x;
}
return exponentiate_helper(multiply(x, orig_x), orig_x, y - 1);
}
// Relies on multiplication
var logarithmic = function(num, base) {
if (base == 0) {
return 0;
}
if (base == 1) {
return NaN;
}
if (base < 0) {
return NaN;
}
return logarithmic_helper(num, base, base, 1);
}
var logarithmic_helper = function(x, y, y_old, counter) {
if (y > x) {
return counter - 1;
}
if (y == x) {
return counter;
}
return logarithmic_helper(x, multiply(y, y_old), y_old, counter + 1);
}
var absolute_value = function(x) {
if (x < 0) {
return negate(x);
}
return x;
}
var mod = function(x, y) {
if (y == 0) {
return NaN;
}
if (y < 0) {
y = negate(y);
}
return mod_helper(x, y, y);
}
/*
sqrt(16) == 4
What number multiplied by itself equals 16
*/
var root = function(number, r) {
// 1^(-1) == 1
if (number == 1 && r < 0) {
return 1;
}
// All other roots form fractions less than 1
if (r < 0) {
return 0;
}
if (r == 0) {
return NaN;
}
if (r == 1) {
return number;
}
return root_search(number, r, 2);
}
var root_search = function(num, r, try_num) {
if (exponentiate(try_num, r) > num) {
return try_num - 1;
}
if (exponentiate(try_num, r) == num) {
return try_num;
}
return root_search(num, r, try_num + 1);
}
var mod_helper = function(x, y, y_orig) {
if (x == y) {
return 0;
}
if (y > x) {
return subtract(x, subtract(y, y_orig));
}
return mod_helper(x, add(y, y_orig), y_orig);
}
var summation = function(from, to, func) {
if (from > to) {
return 0;
}
if (from == to) {
return func(from);
}
return add(func(from), summation(from + 1, to, func));
}
var prod = function(from, to, func) {
if (from > to) {
return 0;
}
if (from == to) {
return func(from);
}
return multiply(func(from), prod(from + 1, to, func));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment