-
-
Save seyfer/109bafa8d92c37facd43612f6ec8bc9c to your computer and use it in GitHub Desktop.
PHP: Negative Base Conversion from Base 10 Decimal
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?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