Making a palindrome

[48T7M4Gy]

Good one gunnerfunner. The answer is correct as you probably know.

I haven't compared timings but there is a way using the method @Meden proposes (but not unique to it) that's fast and takes 94 iterations.

906609 913 993
Number of iterations: 94
Program ended with exit code: 0

[gunnerfunner]

... compare(d) timings ...

0.07s at this end: http://coliru.stacked-crooked.com/a/2e3d3085109a397c

full disclosure: struct Timer (above link) is not my artwork, got it off this forum

[48T7M4Gy]

@gunnerfunner, double full disclosure, I can't tell a lie. I pinched the timing stuff you pinched and the results on using coliru are:

906609 = 913 x 993
Number of iterations: 94
time taken 0.000631795

On my machine:

906609 = 913 x 993
Number of iterations: 94
time taken 0.00040605
Program ended with exit code: 0

I'm not trying to be cute by not showing you the code but I'm happy to show it once @Meden has had a go. Keep in touch.

[48T7M4Gy]

PS You'll be pleased to know when I solved this problem a couple of years ago using arrays of numbers the timings using the 'stolen' system are:

[output]913	993	906609
That's it ...Time taken 0.189716
Program ended with exit code: 0

It shows how powerful string/stream/algorithm manipulation is.

[gunnerfunner]

wow! that's a very high (low?) bar indeed to beat, let's see what OP comes back with. well done

[48T7M4Gy]

Here's a challenge - I am confident from the information in the thread you'll be able to get your timing down, whether it's enough I don't know - it doesn't compromise @Meden's first call or the Project Euler spirit ;)

[lastchance]

#include <iostream>
#include <algorithm>
#include <chrono>
using namespace std;

// The official timer, apparently
struct Timer
{
    Timer() : beg_(clock_::now()) {}
    void reset() { beg_ = clock_::now(); }
    double elapsed() const { return std::chrono::duration_cast<second_> (clock_::now() - beg_).count(); }
    using clock_= std::chrono::high_resolution_clock;
    using second_= std::chrono::duration<double, std::ratio<1>>;
    std::chrono::time_point<clock_> beg_;
};


int main()
{
   Timer tmr;
   int left = 999, right = 999;
   while ( left > 0 )
   {
      int test = 1000 * left + right;
      for ( int small = max( test / 999, 100 ); small <= 999; small++ )
      {
         int large = small;
         while ( large <= 999 )
         {
            int n = small * large;
            if ( n == test )
            {
               double t = tmr.elapsed();
               cout << small << " x " << large << " = " << test << '\n';
               cout << "Processor time taken = " << t;
               return 0;
            }
            else if ( n > test ) break;
            large++;
         }
      }
      left--;
      if      ( right < 10  ) right += 989;
      else if ( right < 100 ) right += 890;
      else                    right -= 100;
   }
}

http://coliru.stacked-crooked.com/a/aeb55f2bd5d17c3c

g++ -std=c++14 -O2 -Wall -pedantic -pthread main.cpp && ./a.out
913 x 993 = 906609
Processor time taken = 0.000253517

You gave too many clues away, @kemort. Counting down from 999, 906 is the 94th trial, corresponding to palindrome 906609.

Timer testing suggests that stringstreaming is about 2-3 times slower producing each palindrome test than raw integer arithmetic.

[48T7M4Gy]

Congratulations. You've lowered the bar again @lastchance. FWIW if I remove the use of streams but still use strings the timing on my machine is:

906609 = 913 x 993
Time taken 0.000399855 (vs @lastchance  .000186537)
Program ended with exit code: 0

[lastchance]

Timing the code with stringstream-generated palindromes, plus my bloopers earlier on in this thread are enough to make me very cautious using stringstream in future.

Just using strings (with to_string() and reverse iterators) was a little faster, but didn't match integer arithmetic alone.

[JLBorges]

> Timing the code with stringstream-generated palindromes, plus my bloopers earlier on in this
> thread are enough to make me very cautious using stringstream in future.

If performance is the primary concern (say, performance better than C, on par with boost spirit), and the locale in effect is not significant (always use the default classic locale), C++17 has std::from_chars and std::to_chars.
http://en.cppreference.com/w/cpp/utility/from_chars
http://en.cppreference.com/w/cpp/utility/to_chars

[48T7M4Gy]

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
# include <chrono>


struct Timer
{
    Timer() : beg_(clock_::now()) {}
    void reset() { beg_ = clock_::now(); }
    double elapsed() const {
        return std::chrono::duration_cast<second_>
        (clock_::now() - beg_).count(); }
    
    using clock_= std::chrono::high_resolution_clock;
    using second_= std::chrono::duration<double, std::ratio<1>>;
    std::chrono::time_point<clock_> beg_;
};

int main()
{
    Timer tmr;
    
    bool found = false;
    int no_iterations = 0;
    
    std::stringstream stream;
    std::string tempStr;
    int tempInt = 0;
    
    for(int i = 999; i > 99 and !found; --i)
    {
        no_iterations++;
        tempStr = std::to_string(i);
        
        stream.str(std::string());
        stream << tempStr;
        std::reverse(tempStr.begin(), tempStr.end());
        stream << tempStr;
        
        tempInt = stoi(stream.str());
        
        for(int j = 999; j > 99; --j)
        {
            if( tempInt % j == 0 and tempInt/j < 999 and tempInt/j  > j)
            {
                std::cout << tempInt << " = " << j << " x " << tempInt/j << '\n';
                found = true;
            }
        }
    }
    std::cout << "Number of iterations: " << no_iterations << '\n';
    
    double t = tmr.elapsed();
    std::cout << "Time taken " << t << '\n';
    
    return 0;
}

906609 = 913 x 993
Number of iterations: 94
Time taken 0.000341255
Program ended with exit code: 0