palindromes (output stuffs here: https://gist.github.com/4219658 )

palindrome.cpp

/* palindrome.cpp
 * C++ implementation of palindrome.py
 * (https://gist.github.com/4081368)
 *
 * - Matthew Martz 2012
 */

#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <gmp.h>
#include <time.h>

// includes for testing only
#include <typeinfo>

using namespace std;

struct Factors {
    long long i;
    long long j;
};

Factors factorize(long long product){
    // square sieving to search for factors
    long long symmetry;
    symmetry = floor(sqrt(product) + 0.5);
    int mag;
    mag = floor(log10(product)) + 1;
    long long factor_ceiling, factor_floor;
    factor_ceiling = pow((double)10, (mag / 2)) - 1;
    factor_floor = symmetry - (factor_ceiling - symmetry);
    cout << "floor : " << factor_floor << " ceiling : " << factor_ceiling << endl;
    Factors results = { symmetry, symmetry  };
    long long low_high_product;
    if (pow((double)factor_ceiling, 2) < product){
        results.i = 0;
        results.j = 0;
    } else if ((factor_floor * factor_ceiling) == product){
        results.i = factor_floor;
        results.j = factor_ceiling;
    } else {
        while(1){
            cout << product << endl;
            cout << results.i << " , " << results.j << endl;
            low_high_product = results.i * results.j;
            if (low_high_product == product){
                cout << "match" << endl;
                break;
            } else if (results.j < factor_floor ||
                    results.i < factor_floor){
                cout << "too low" << endl;
                results.i  = 0;
                results.j = 0;
                break;
            } else if (results.j > factor_ceiling ||
                    results.i > factor_ceiling){
                cout << "too high" << endl;
                results.i  = 0;
                results.j = 0;
                break;
            } else if (low_high_product < product){
                cout << "up" << endl;
                results.j++;
            } else if (low_high_product > product){
                cout << "down" << endl;
                results.i--;
            }
        }
    }
    return results;
}

int get_digits(){
    // retrieve digits for factor size from user
    int number_digits;
    cout << " Enter number of digits: " << endl;
    cin >> number_digits;
    return number_digits;
}

string as_string(long long number){
    // convert integer to string
    stringstream ss;
    ss << number;
    return ss.str();
}

long long as_int(string number){
    // convert string number to int number
    return atoi(number.c_str());
}

int main(int argc, char * argv[]){
    clock_t start_time, end_time;
    // get number of digits for factor size
    int factor_size;
    if (argc > 1){
        factor_size = atoi(argv[1]);
    } else {
        factor_size = get_digits();
    }
    // product magnitude
    int magnitude = factor_size * 2;
    // maximum, or start iteration value
    long long start = pow((double)10, magnitude) - 1;
    // stop point for n by n digit factor products
    // we should not hit this else we have no 
    // palindromes
    long long stop = pow((double)10, (factor_size - 1));

    // Cut the number into symmetrical elements
    // we will then flip to make palindromes
    // convert number into string and take first half substring
    string number_string = as_string(start);
    string symmetry_string = number_string.substr(0, factor_size);
    long long symmetry = as_int(symmetry_string);

    // ------------------------------------------------------------
    // debugging things and making sure our conversions are working
    //cout << symmetry << " - symmetry" << endl;
    //cout << "start " << start << " - stop " << stop << endl;
    //long long test_int = 5;
    //string test_str = "5";
    //cout << typeid(symmetry).name() << typeid(test_int).name() << endl;
    //cout << typeid(symmetry_string).name() << typeid(test_str).name() << endl;
    // end debugging stuffs 
    // ------------------------------------------------------------
    
    start_time = clock();

    long long max_pali;
    long long num;
    Factors results;
    while (symmetry >= stop){
        symmetry_string = as_string(symmetry);
        num = as_int(symmetry_string + 
                string (symmetry_string.rbegin(), 
                    symmetry_string.rend()));
        // check this palindrome now
        results = factorize(num);
        if (results.i != 0 &&
                results.j != 0){
            cout << "found" << endl;
            break;
        }
        // finally, increment our counters down
        symmetry = as_int(symmetry_string);
        symmetry--;
    }
    
    end_time = clock();
    float seconds = float(end_time - start_time) / CLOCKS_PER_SEC;
    
    cout << results.i << " , " << results.j << " , " << num << endl;
    cout << seconds << " s to run" << endl;
    return 0;
}

palindrome.py

#########################################
# Find the maximum numerical palindrome
# product from multiplying together two
# factors of a certain magnitude
#
# e.g. What is the maximum palindromic
# product for 4digit x 4digit?
#
# >>> palindrome.get_pali(4)
# ((9999, 9901), '99000099')
#
# So the maximum palindromic product for
# 4digit*4digit is 99000099 yielded by
# 9999*9901.
#
#    - Matthew Martz 2012
#########################################

from math import sqrt, log10

def get_pali(digits, limit_digits=True, square_sieve=True):
    '''
    Finds the maximum numerical palindrome for
    n-digits*n-digits.
    '''
    max_pali = None
    mag = digits * 2 # magnitude of product
    start = 10**mag - 1
    counter = start
    # Cut the number into symmetrical elements
    # we will then flip to make palindromes
    symmetry = int(str(start)[:mag / 2])
    # We set limit_digits if we want to ensure
    # factors have to have no less than n digits
    if limit_digits:
        stop = 10**(mag - 1)
    else:
        stop = 0
    # assign our desired factorization function
    # sqrt is fastest and will find only n-digit factors
    # the other version is slower but can potentially
    # find all factors as well as any primes
    if square_sieve:
        factorization = factors_sqrt
    else:
        factorization = factors
    while counter >= stop:
        # If we have even magnitude our sequence
        # is symmetrical and we just flip
        if mag % 2 == 0:
            # make palindrome by flipping first half
            # and joining together with string slicing
            # and then convert back to integer
            num = int(str(symmetry)+str(symmetry)[::-1])
            # check to see if we can make this
            # from our possible factors of n digits
            to_make = factorization(num)
            if to_make != (0, 0):
                max_pali = (to_make, num)
                # we've found a possible palindrome
                # since we are working top down, we
                # know this is the maximum possible
                # so we break out of the loop
                break
        else:
            # since we are not symmetrical, we have a
            # digit in the middle that can change and
            # we need to iterate over it's 10 possible
            # values working down from 9 to 0 with each
            # part of the first half symmetry we test
            for i in range(9, -1, -1):
                num = int(str(symmetry)+str(i)+str(symmetry)[::-1])
                # check to see if we can make this
                # from our possible factors of n digits
                to_make = factorization(num)
                if to_make != (0, 0):
                    max_pali = (to_make, num)
                    # we've found a possible palindrome
                    # since we are working top down, we
                    # know this is the maximum possible
                    # so we break out of the loop
                    break
        # increment down the couter so that we can stop
        # when we hit our stop point we've set by digits
        counter -= 1
        # increment down the first half symmetry component
        # that we are generating the palindromes with
        # 9889 has symmetry of 98 and will now be 97 to
        # give us a palindrome next loop of 9779
        symmetry -= 1
    # return our palindrome if we have it in the form of
    # ((factor high, factor low), palindrome)
    return max_pali

def factors(target, full_range=False, inclusive=False):
    '''
    Uses a squeeze algorithm to find factors
    that may yield a given product. We are not
    identifying multiple possible factor sets, we
    only car if we can find at least one set to
    yield the target product.
    '''
    # set our max and minimum values
    # e.g. 3 digit factors would be
    # 999-100 based on mag=3
    # we can set full range to be all inclusive
    # from 0 to mag to use this as a more generic
    # factorization
    mag = len(str(target)) / 2
    if full_range:
        start_low = 0
        start_high = target
    else:
        start_low = 10**(mag - 1)
        start_high = 10**mag - 1
    # get symmetry (half way point) of our
    # target product
    symmetry = start_low * 2
    # set our squeeze factors to the
    # high and low start points
    high, low = start_high, start_low
    # setup a container for all the possible
    # factors if we want inclusivity
    if inclusive:
        factor_list = []
    while 1:
        # if our target is greater than the square
        # of the highest possible factor, we cannot
        # make this product and break
        if high**2 < target:
            high, low = 0, 0
            break
        # if high and low iterators hit the
        # symmetry point, we can't make product
        # and going further is operating on factors
        # we've already tried with opposite
        # symmetry so we break
        elif high <= symmetry and low >= symmetry:
            high, low = 0, 0
            break
        # if we are less than the product, we need
        # to increase the low squeeze factor
        elif high * low < target:
            low += 1
        # if we are greater than the product, we
        # need to decrease the high squeeze factor
        elif high * low > target:
            high -= 1
        # if we've hit the target, break
        elif high * low == target:
            if inclusive:
                factor_list.append((high, low))
                high -= 1
                low += 1
            else:
                break
    # return our squeeze factors
    if inclusive:
        return factor_list
    return (high, low)

def factors_sqrt(target):
    '''
    Uses sqrt sieving to find factors
    of target
    '''
    # find our sqrt symmetry point and
    # since we want integers we round and
    # use the integer form of this value
    symmetry = int(round(sqrt(target)))
    # get the number of digits of the product
    mag = int(log10(target) + 1)
    # calculate the maximum and minimum
    # n digit factor which is based on
    # mag / 2 since we want n-digit * n-digit
    # palindromes
    factor_ceiling = 10**(mag / 2) - 1
    #factor_floor = 10**(mag / 2 - 1)
    # make the floor based on our symmetry point
    # distance of maximum from this point
    factor_floor = symmetry - (factor_ceiling - symmetry)
    high, low = symmetry, symmetry
    # break and set to 0, 0 if we cannot
    # possibly make this product with n*n digits
    if factor_ceiling**2 < target:
        high, low = 0, 0
    else:
        while 1:
            # if either iterator goes below floor
            # we break
            if high < factor_floor or low < factor_floor:
                high, low = 0, 0
                break
            # if either iterator goes above ceiling
            # we break
            elif high > factor_ceiling or low > factor_ceiling:
                high, low = 0, 0
                break
            # if we are too low, increment up an iterator
            elif high * low < target:
                low += 1
            # if we are too high, increment down an iterator
            elif high * low > target:
                high -= 1
            # if we've hit our target, we break with iterators
            # resting at our factors
            elif high * low == target:
                break
    # return our fast sieve products
    return (high, low)

>>> profile.run('palindrome.get_pali(7)')
         17348 function calls in 39.876 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     4336    0.018    0.000    0.018    0.000 :0(log10)
     4336    0.046    0.000    0.046    0.000 :0(round)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
     4336    0.024    0.000    0.024    0.000 :0(sqrt)
        1    0.000    0.000   39.876   39.876 <string>:1(<module>)
     4336   39.702    0.009   39.790    0.009 palindrome.py:162(factors_sqrt)
        1    0.086    0.086   39.876   39.876 palindrome.py:21(get_pali)
        1    0.000    0.000   39.876   39.876 profile:0(palindrome.get_pali(7))
        0    0.000             0.000          profile:0(profiler)

No Changes:

>>> profile.run('palindrome.get_pali(8)')
         40004 function calls in 21.522 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    10000    0.029    0.000    0.029    0.000 :0(log10)
    10000    0.044    0.000    0.044    0.000 :0(round)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
    10000    0.029    0.000    0.029    0.000 :0(sqrt)
        1    0.000    0.000   21.521   21.521 <string>:1(<module>)
    10000   21.358    0.002   21.460    0.002 palindrome.py:162(factors_sqrt)
        1    0.062    0.062   21.521   21.521 palindrome.py:21(get_pali)
        1    0.000    0.000   21.522   21.522 profile:0(palindrome.get_pali(8))
        0    0.000             0.000          profile:0(profiler)

Changing round to trunc:

>>> profile.run('palindrome.get_pali(8)')
         40004 function calls in 21.378 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    10000    0.028    0.000    0.028    0.000 :0(log10)
        1    0.001    0.001    0.001    0.001 :0(setprofile)
    10000    0.028    0.000    0.028    0.000 :0(sqrt)
    10000    0.030    0.000    0.030    0.000 :0(trunc)
        1    0.000    0.000   21.377   21.377 <string>:1(<module>)
    10000   21.232    0.002   21.318    0.002 palindrome.py:162(factors_sqrt)
        1    0.059    0.059   21.377   21.377 palindrome.py:21(get_pali)
        1    0.000    0.000   21.378   21.378 profile:0(palindrome.get_pali(8))
        0    0.000             0.000          profile:0(profiler)

After dropping the cast to int on the truncation line (Since trunc returns an Int):

>>> profile.run('palindrome.get_pali(8)')
         40004 function calls in 22.277 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    10000    0.029    0.000    0.029    0.000 :0(log10)
        1    0.001    0.001    0.001    0.001 :0(setprofile)
    10000    0.029    0.000    0.029    0.000 :0(sqrt)
    10000    0.031    0.000    0.031    0.000 :0(trunc)
        1    0.000    0.000   22.276   22.276 <string>:1(<module>)
    10000   22.123    0.002   22.212    0.002 palindrome.py:162(factors_sqrt)
        1    0.064    0.064   22.276   22.276 palindrome.py:21(get_pali)
        1    0.000    0.000   22.277   22.277 profile:0(palindrome.get_pali(8))
        0    0.000             0.000          profile:0(profiler)

Code (test.py):

import time
import palindrome

t0 = time.clock()
print palindrome.get_pali(8)
t = time.clock() - t0
print t

Python:

DTSN-02947-Eriks-iMac ~  $ python test.py
((99990001, 99999999), 9999000000009999)
22.074752

PyPy:

DTSN-02947-Eriks-iMac ~  $ Downloads/pypy-1.9/bin/pypy test.py
((99990001, 99999999), 9999000000009999)
0.298731

Another datapoint (get_pali(10)):

((9999986701, 9999996699), 99999834000043899999L)
221.705623

Moved the calculation of max (factor_ceiling**2) outside of while statement since this won't change and we should only be doing it once, else go into the while loop:

    # break and set to 0, 0 if we cannot
    # possibly make this product with n*n digits
    if factor_ceiling**2 < target:
        high, low = 0, 0
    else:
        while 1:
            ...

compiling on freebsd:

g++ -o palindrome -I /usr/local/include -L /usr/local/lib palindrome.cpp -lgmp

Made an output stuffs gist:
https://gist.github.com/4219658

So we don't create scrolling mess here.

GMP switch: http://www.cs.colorado.edu/~srirams/classes/doku.php/gmp_usage_tutorial