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 rtobar commented Jan 27, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment