## A cool way to find out whether a number is palindromic

In this blog entry I proposed a solution to Problem 4 at Project Euler, a crucial element of the problem is to find out whether a number is a palindrome (909 is, 809 isn't), a bit out of laziness and a bit in order to reuse existing methods, I decided to verify the palindrome by converting the number into a char array and then comparing this array with its mirror version, it works but it's not really that mathematical... Dustin Campbell proposed a solution kind of similar to mine (alas, more elegant and, above that, in F#) and using the same trick of converting the number to chars, as he didn't like this part of the solution, in this new blog entry he proposes the detection of a palindrome by mirroring the number one digit at a time. A translation of his F# code to C# 3.0 could be:

1     Func<int, int, int> TailReverseNumber = null;

2     TailReverseNumber = (n, res) => n == 0 ? res : TailReverseNumber(n / 10, 10 * res + n % 10);

3

4     Func<int, bool> IsPalindrome = n => n == TailReverseNumber(n, 0);

TailReverseNumber takes a number n and "mirrors" it, one digit at a time, for example: TailReverseNumber(237, 0) -> TailReverseNumber(23, 7) -> TailReverseNumber(2, 73) -> TailReverseNumber(0, 732), the big trick is that res works as an accumulator that is multiplied by 10, therefore moving its value to the left, and putting in the "hole" that appears at the right the least significant digit of n. As it names implies, TailReverseNumber() uses tail recursion, so that no extra call stack space is used to save any intermediate results, which makes the process pretty efficient. Actually, in my PC it's four times faster than the initial solution. More efficient and more elegant, a smart guy Dustin.

Published Tuesday, May 06, 2008 1:40 AM by Edgar Sánchez

#### # re: A cool way to find out whether a number is palindromic

Tuesday, May 06, 2008 2:22 PM by Dustin Campbell

Very nicely done Edgar!

#### # re: A cool way to find out whether a number is palindromic

Tuesday, May 06, 2008 9:44 PM by rajbk

AFAIK and seen, even though the CLR supports tail recursion, the C# compiler has not implemented it yet.

connect.microsoft.com/.../ViewFeedback.aspx

Raj

#### # re: A cool way to find out whether a number is palindromic

Friday, May 16, 2008 3:48 AM by Jay

The F# version is almost identical:

let rec tailReverseNumber n res =

match n with

| 0 -> res

| _ -> tailReverseNumber (n/10) (10*res+n%10)

let isPalindrome n =

n = tailReverseNumber n 0

#### # projecteuler

Saturday, May 24, 2008 4:49 PM by projecteuler

Pingback from  projecteuler