Created
November 8, 2017 05:48
-
-
Save PythonJedi/63283d8baa96219d8d1bfdf61c895762 to your computer and use it in GitHub Desktop.
Much faster implementation of Kaprekar's function
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
/* | |
* Attempt to find fixed points of a particularly interesting function. | |
* | |
* Kaprekar's function sorts the digits of n ascending and descending, then | |
* returns the descending minus the ascending. The fixed points of this | |
* function, as well as the attractor classes are very interesting. | |
*/ | |
#include<stdio.h> | |
#include<limits.h> | |
void kaprekar(unsigned int, unsigned int *); | |
void reverse(unsigned int, unsigned int *); | |
void sort_digits(unsigned int, unsigned int *); | |
int main(int argc, char *argv[]) { | |
for (unsigned int i = 0; i <= UINT_MAX/10; i++) { | |
printf("%d", i); | |
unsigned int k; | |
kaprekar(i, &k); | |
if (i == k) | |
printf("\n"); // Newline to leave fixedpoint in console output | |
else | |
printf("\x1B[G"); // Return to beginning of line to overwrite | |
} | |
return 0; | |
} | |
void kaprekar(unsigned int x, unsigned int *result) { | |
unsigned int ascending, descending; | |
sort_digits(x, &descending); | |
reverse(descending, &ascending); | |
*result = descending-ascending; | |
} | |
void reverse(unsigned int x, unsigned int *result) { | |
*result = 0; | |
while (x > 0) { | |
*result = *result*10 + x%10; | |
x /= 10; | |
} | |
} | |
void sort_digits(unsigned int x, unsigned int *result) { | |
unsigned int mask[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; | |
*result = 0; | |
while (x > 0) { | |
unsigned int d = x%10; | |
unsigned int rem = *result % mask[d]; | |
*result = (*result - rem) * 10 + d*mask[d] + rem; | |
x /= 10; // Pop digit | |
for (int i = d+1; i < 10; i++) { // increment masks after inserted digit | |
mask[i] *= 10; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment