Skip to content

Instantly share code, notes, and snippets.

@CMCDragonkai
Last active March 9, 2017 04:18
Show Gist options
  • Save CMCDragonkai/841bdc56b568c9068a5d to your computer and use it in GitHub Desktop.
Save CMCDragonkai/841bdc56b568c9068a5d to your computer and use it in GitHub Desktop.
PHP: Negative Base Conversion from Base 10 Decimal
<?php
/**
* Negabase
* To convert a decimal to negative base.
* Divide the number by the negative base.
* Acquire the whole number quotient and remainder.
* If the remainder is negative, add 1 to the quotient and add the absolute value of the base to the remainder.
* Divide the quotient by the negative base... rinse and repeat until the quotient is 0.
* Aggregate the remainders in reverse (as a stack), and you have your negative base representation.
*/
function negative_base ($decimal, $base) {
// initialise a digit stack
$digits = [];
// divide the decimal by the base repeatedly until the quotient is 0
while ($decimal != 0) {
// how many of the base exist in the quotient?
$quotient = intval($decimal / $base);
// modulus can return negative numbers
$remainder = $decimal % $base;
// negative base numbers do not have negative digits
// if we get a negative remainder from the modulus
// all we have to do is increment the quotient
// and add the absolute value of the base to the remainder
// This works because:
// (a/b = q r) -> (b*q + r = a) where
// a => numerator,
// b => denominator,
// q => quotient,
// r => remainder
// If we get a negative remainder, we can just increment the quotient multiplying the denominator
// giving us a number greater than the numerator
// Subtracting this number from the numerator gives us a positive remainder
// For example: (-5 / -2) => (2 r:-1) => (3 r:1) because [3 * -2 = -6 -> -6 + 1 -5 -> r:1]
if ($remainder < 0) {
$quotient += 1;
$remainder += (-1 * $base);
}
// repeat the division using the new quotient
$decimal = $quotient;
// push the current number onto the stack
array_unshift($digits, $remainder);
}
return $digits;
}
$number = 42;
$base = -2;
$negative_base_number = negative_base($number, $base);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment