Skip to content

Instantly share code, notes, and snippets.

@rtobar rtobar/capicuas.cpp
Last active Feb 11, 2020

Embed
What would you like to do?
//
// Compilacion: Como el usuario lo estime conveniente.
// Si se define HAVE_GMP entonces hay que linkear contra libgmp y libgmpxx, e.g.:
//
// $> CXXFLAGS="-Wall -O3 -DHAVE_GMP" LDLIBS="-lgmp -lgmpxx" make capicuas
//
// Uso: ./capicuas
// ./capicuas <primer-numero> <ultimo-numero>
// ./capicuas <primer-numero> <ultimo-numero> <precision>
// ./capicuas <primer-numero> <ultimo-numero> <precision> <max-iteraciones>
//
// Precision es "i", "l" o "ll", representando "int", "long" y "long long", y es el tipo de dato que
// se usa para hacer los calculos y guardar los resultados. Si se compila usando GMP tambien se puede
// usar la precision "gmp". La unica forma de llegar a un millon de iteraciones de forma correcta es
// usando gmp; los tipos de datos nativos hace overflow despues de no mas de ~30-40 iteraciones, por
// lo que las respuestas que entregarian pasadas ese numero de iteraciones serian incorrectas.
//
// El codigo es relativamente largo por la flexibilidad que se da en la precision a usar, y el chequeo
// de overflow; si esa funcionalidad no estuviera presente el codigo seria bastante mas simple.
//
// Resultados para precision "int" y "long" en Linux x86_64. Usando "gmp" con 1000 iteraciones no se converge
// a nuevos resultados, y usando mas de 10000 iteraciones ya toma demasiado tiempo.
//
// $> time ./capicuas 100 1000 i
// n=167, capicua=88555588, iteraciones=11
// n=266, capicua=88555588, iteraciones=11
// n=365, capicua=88555588, iteraciones=11
// n=464, capicua=88555588, iteraciones=11
// n=563, capicua=88555588, iteraciones=11
// n=662, capicua=88555588, iteraciones=11
// n=761, capicua=88555588, iteraciones=11
// n=860, capicua=88555588, iteraciones=11
// n=829, capicua=88555588, iteraciones=10
// n=928, capicua=88555588, iteraciones=10
// n=193, capicua=233332, iteraciones=8
// n=292, capicua=233332, iteraciones=8
// n=391, capicua=233332, iteraciones=8
// n=490, capicua=233332, iteraciones=8
// n=589, capicua=1136311, iteraciones=8
// n=688, capicua=1136311, iteraciones=8
// n=787, capicua=1136311, iteraciones=8
// n=886, capicua=1136311, iteraciones=8
// n=949, capicua=2322232, iteraciones=8
// n=985, capicua=1136311, iteraciones=8
//
// real 0m0.006s
// user 0m0.001s
// sys 0m0.006s
// $> time ./capicuas 100 1000 l
// n=187, capicua=8813200023188, iteraciones=23
// n=286, capicua=8813200023188, iteraciones=23
// n=385, capicua=8813200023188, iteraciones=23
// n=484, capicua=8813200023188, iteraciones=23
// n=583, capicua=8813200023188, iteraciones=23
// n=682, capicua=8813200023188, iteraciones=23
// n=781, capicua=8813200023188, iteraciones=23
// n=880, capicua=8813200023188, iteraciones=23
// n=869, capicua=8813200023188, iteraciones=22
// n=968, capicua=8813200023188, iteraciones=22
// n=989, capicua=89540004598, iteraciones=19
// n=739, capicua=5233333325, iteraciones=17
// n=838, capicua=5233333325, iteraciones=17
// n=899, capicua=133697796331, iteraciones=17
// n=937, capicua=5233333325, iteraciones=17
// n=998, capicua=133697796331, iteraciones=17
// n=999, capicua=8939779398, iteraciones=16
// n=177, capicua=8836886388, iteraciones=15
// n=276, capicua=8836886388, iteraciones=15
// n=375, capicua=8836886388, iteraciones=15
//
// real 0m0.008s
// user 0m0.001s
// sys 0m0.008s
// $> time ./capicuas 100 1000 ll
// n=187, capicua=8813200023188, iteraciones=23
// n=286, capicua=8813200023188, iteraciones=23
// n=385, capicua=8813200023188, iteraciones=23
// n=484, capicua=8813200023188, iteraciones=23
// n=583, capicua=8813200023188, iteraciones=23
// n=682, capicua=8813200023188, iteraciones=23
// n=781, capicua=8813200023188, iteraciones=23
// n=880, capicua=8813200023188, iteraciones=23
// n=869, capicua=8813200023188, iteraciones=22
// n=968, capicua=8813200023188, iteraciones=22
// n=989, capicua=89540004598, iteraciones=19
// n=739, capicua=5233333325, iteraciones=17
// n=838, capicua=5233333325, iteraciones=17
// n=899, capicua=133697796331, iteraciones=17
// n=937, capicua=5233333325, iteraciones=17
// n=998, capicua=133697796331, iteraciones=17
// n=999, capicua=8939779398, iteraciones=16
// n=177, capicua=8836886388, iteraciones=15
// n=276, capicua=8836886388, iteraciones=15
// n=375, capicua=8836886388, iteraciones=15
//
// real 0m0.008s
// user 0m0.001s
// sys 0m0.007s
#include <algorithm>
#include <cstdlib>
#include <limits>
#include <iostream>
#include <vector>
#ifdef HAVE_GMP
#include <gmpxx.h>
#endif // HAVE_GMP
template <typename Integer>
struct CapicuaInfo
{
Integer n;
Integer capicua;
int iteraciones;
};
template <typename T, typename Char, typename Integer>
std::basic_ostream<T, Char> &operator<<(std::basic_ostream<T, Char> &stream, const CapicuaInfo<Integer> &info)
{
stream << "n=" << info.n << ", capicua=" << info.capicua << ", iteraciones=" << info.iteraciones;
return stream;
}
template <typename Integer>
Integer reverso(Integer numero)
{
Integer reverso = 0;
while (numero) {
auto digito = numero % 10;
reverso = reverso * 10 + digito;
numero /= 10;
}
return reverso;
}
template <typename Integer>
inline
bool suma_es_posible(Integer numero, Integer numero_reverso)
{
return std::numeric_limits<Integer>::max() - numero >= numero_reverso;
}
#ifdef HAVE_GMP
template <>
bool suma_es_posible<mpz_class>(mpz_class numero, mpz_class numero_reverso)
{
return true;
}
#endif // HAVE_GMP
template <typename Integer>
CapicuaInfo<Integer> capicua_info(Integer numero, int max_iteraciones)
{
int iteracion = 1;
Integer numero_original = numero;
numero = numero + reverso(numero);
while (iteracion < max_iteraciones) {
auto numero_reverso = reverso(numero);
if (numero_reverso == numero) {
return {numero_original, numero, iteracion};
}
if (!suma_es_posible(numero, numero_reverso)) {
return {numero_original, -1, iteracion};
}
numero = numero + numero_reverso;
iteracion++;
}
return {numero_original, -1, iteracion};
}
template <typename Integer>
void imprimir_info_capicuas(Integer primer_numero, int n, int max_iteraciones, int max_resultados)
{
// Obtenemos primero todos los resultados, luego imprimimos,
// para aprovechar al maximo el cache de instrucciones de la CPU
using resultado_t = CapicuaInfo<Integer>;
std::vector<resultado_t> resultados;
resultados.reserve(n);
for (auto numero = primer_numero; numero < primer_numero + n; numero++) {
auto resultado = capicua_info(numero, max_iteraciones);
if (resultado.capicua != -1) {
resultados.emplace_back(resultado);
}
}
std::stable_sort(resultados.begin(), resultados.end(), [](const resultado_t &a, const resultado_t &b) {
return a.iteraciones > b.iteraciones;
});
// Imprimimos los top-20
for (int i = 0; i != std::min(max_resultados, int(resultados.size())); i++) {
std::cout << resultados[i] << '\n';
}
}
int main(int args, char *argv[])
{
int primer_numero = 100;
int ultimo_numero = 1000;
std::string precision = "i";
int max_iteraciones = 1000000;
int max_resultados = 20;
if (args >= 3) {
primer_numero = std::atoi(argv[1]);
ultimo_numero = std::atoi(argv[2]);
}
if (args >= 4) {
precision = argv[3];
}
if (args >= 5) {
max_iteraciones = std::atoi(argv[4]);
}
if (args >= 6) {
max_resultados = std::atoi(argv[5]);
}
int n = ultimo_numero - primer_numero + 1;
if (precision == "l") {
imprimir_info_capicuas<long>(primer_numero, n, max_iteraciones, max_resultados);
}
else if (precision == "ll") {
imprimir_info_capicuas<long long>(primer_numero, n, max_iteraciones, max_resultados);
}
#ifdef HAVE_GMP
else if (precision == "gmp") {
imprimir_info_capicuas<mpz_class>(primer_numero, n, max_iteraciones, max_resultados);
}
#endif // HAVE_GMP
else if (precision == "i") {
imprimir_info_capicuas<int>(primer_numero, n, max_iteraciones, max_resultados);
}
else {
std::cerr << "precision deconocida: " << precision << '\n';
return 1;
}
return 0;
}
@rtobar

This comment has been minimized.

Copy link
Owner Author

rtobar commented Jan 27, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.