Revisions to Project Euler Problem #4 - Palindromic number

Davislor is unstoppable

Source Link

edited Apr 21, 2017 at 12:43

pgs

932
8
24

[Benchmark]
public static string LargestPalindromeDavislor() {=> 
    return LargestPalindromeDavislorImpl().First(HasFactors).ToString();
}
private static IEnumerable<Int32> LargestPalindromeDavislorImpl() {
    for (Int32 a = 9; a >= 1; --a)
        for (Int32 b = 9; b >= 0; --b)
            for (Int32 c = 9; c >= 0; --c)
                yield return a * 100001 + b * 10010 + c * 1100;
}
private static bool HasFactors(Int32 p) {
    Int32 lower1 = (p / 999 + 10) / 11,
        lower = Math.Max(10, lower1);
    Int32 upper1 = p / 1100,
          upper = Math.Min(90, upper1);
    Int32 count = Math.Max(upper - lower + 1, 0);
    return Enumerable.Range(lower, count).Any(x => p % x == 0);
}

And here are the results@Divislor (Fastest)

[Benchmark]
public static string LargestPalindromeDavislor2() =>  
    LargestPalindromeDavislorImpl().First(p => XCandidates(p).Any(x => p % x == 0)).ToString();
   Method |
private static IEnumerable<int> XCandidates(int p) {
    int q Mean= |p / 11;
    int lower StdDev= |Math.Max(10, (q + (999 - 1)) / 999);
  Median | int upper = Math.Min(90, q / 100);
-------------------------- |--------------- |-------------- |-------------- int k = q % 6;
    
    if (k == 1 || k == 5) {
        int r = lower % 6;
        bool mod1 = r <= 1;
        int i = lower - |r + (mod1 ? 1 : 5);
 LargestPalindromeOriginal | 33,922.0879 us |   388.5217 
 us | 33,977.7592 us |   while (i <= upper) {
    LargestPalindromeDenis |  3,573.3143 us |   yield 56.9470return usi;
 |           i += mod1 ? 4 : 2;
            mod1 = !mod1;
        }
    } else if (k == 2 || k == 4) {
        int r = lower % 6;
        int m = (r == 3,561.6188 us|| |r == 0) ? r + 1 : r;
     LargestPalindromeEric | 81,791.4122 usint |i = lower - r + m;
        while (i <= upper) {
            yield return i;
            if (m == 5) {
                i += 2;
                m = 1;
            } else if (m == 2) {
                i += 2;
                m = 4;
            } else {
                ++i;
                ++m;
            }
        }
    } else if (k == 3) {
        int i = lower + 1,028.3498 us- |lower 81,635.8259% us2;
 |       while (i <= upper) {
      LargestPalindromePgs |     34.4525yield usreturn |i;
     0.4323 us |     34.3658i us+= |2;
 LargestPalindromeDavislor |      7.2958}
 us |  } else {
 0.0600 us |     for 7.3064(int usi |= lower; i <= upper; ++i)
            yield return i;
    }
}

                     Method |           Mean |        StdDev |         Median |
--------------------------- |--------------- |-------------- |--------------- |
  LargestPalindromeOriginal | 33,322.0311 us |   271.1871 us | 33,298.1558 us |
     LargestPalindromeDenis |  3,547.6625 us |    59.1731 us |  3,538.8128 us |
      LargestPalindromeEric | 79,636.8086 us | 1,029.9705 us | 79,615.3664 us |
       LargestPalindromePgs |     34.9557 us |     0.6435 us |     34.8254 us |
  LargestPalindromeDavislor |      7.3468 us |     0.1378 us |      7.3217 us |
 LargestPalindromeDavislor2 |      5.2548 us |     0.0622 us |      5.2729 us |

[Benchmark]
public static string LargestPalindromeDavislor() {
    return LargestPalindromeDavislorImpl().First(HasFactors).ToString();
}
private static IEnumerable<Int32> LargestPalindromeDavislorImpl() {
    for (Int32 a = 9; a >= 1; --a)
        for (Int32 b = 9; b >= 0; --b)
            for (Int32 c = 9; c >= 0; --c)
                yield return a * 100001 + b * 10010 + c * 1100;
}
private static bool HasFactors(Int32 p) {
    Int32 lower1 = (p / 999 + 10) / 11,
        lower = Math.Max(10, lower1);
    Int32 upper1 = p / 1100,
          upper = Math.Min(90, upper1);
    Int32 count = Math.Max(upper - lower + 1, 0);
    return Enumerable.Range(lower, count).Any(x => p % x == 0);
}

And here are the results

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 33,922.0879 us |   388.5217 us | 33,977.7592 us |
    LargestPalindromeDenis |  3,573.3143 us |    56.9470 us |  3,561.6188 us |
     LargestPalindromeEric | 81,791.4122 us | 1,028.3498 us | 81,635.8259 us |
      LargestPalindromePgs |     34.4525 us |     0.4323 us |     34.3658 us |
 LargestPalindromeDavislor |      7.2958 us |     0.0600 us |      7.3064 us |

[Benchmark]
public static string LargestPalindromeDavislor() => 
    LargestPalindromeDavislorImpl().First(HasFactors).ToString();
private static IEnumerable<Int32> LargestPalindromeDavislorImpl() {
    for (Int32 a = 9; a >= 1; --a)
        for (Int32 b = 9; b >= 0; --b)
            for (Int32 c = 9; c >= 0; --c)
                yield return a * 100001 + b * 10010 + c * 1100;
}
private static bool HasFactors(Int32 p) {
    Int32 lower1 = (p / 999 + 10) / 11,
        lower = Math.Max(10, lower1);
    Int32 upper1 = p / 1100,
          upper = Math.Min(90, upper1);
    Int32 count = Math.Max(upper - lower + 1, 0);
    return Enumerable.Range(lower, count).Any(x => p % x == 0);
}

@Divislor (Fastest)

[Benchmark]
public static string LargestPalindromeDavislor2() =>  
    LargestPalindromeDavislorImpl().First(p => XCandidates(p).Any(x => p % x == 0)).ToString();
    
private static IEnumerable<int> XCandidates(int p) {
    int q = p / 11;
    int lower = Math.Max(10, (q + (999 - 1)) / 999);
    int upper = Math.Min(90, q / 100);
    int k = q % 6;
    
    if (k == 1 || k == 5) {
        int r = lower % 6;
        bool mod1 = r <= 1;
        int i = lower - r + (mod1 ? 1 : 5);
         
        while (i <= upper) {
            yield return i;
            i += mod1 ? 4 : 2;
            mod1 = !mod1;
        }
    } else if (k == 2 || k == 4) {
        int r = lower % 6;
        int m = (r == 3 || r == 0) ? r + 1 : r;
        int i = lower - r + m;
        while (i <= upper) {
            yield return i;
            if (m == 5) {
                i += 2;
                m = 1;
            } else if (m == 2) {
                i += 2;
                m = 4;
            } else {
                ++i;
                ++m;
            }
        }
    } else if (k == 3) {
        int i = lower + 1 - lower % 2;
        while (i <= upper) {
            yield return i;
            i += 2;
        }
    } else {
        for (int i = lower; i <= upper; ++i)
            yield return i;
    }
}

                     Method |           Mean |        StdDev |         Median |
--------------------------- |--------------- |-------------- |--------------- |
  LargestPalindromeOriginal | 33,322.0311 us |   271.1871 us | 33,298.1558 us |
     LargestPalindromeDenis |  3,547.6625 us |    59.1731 us |  3,538.8128 us |
      LargestPalindromeEric | 79,636.8086 us | 1,029.9705 us | 79,615.3664 us |
       LargestPalindromePgs |     34.9557 us |     0.6435 us |     34.8254 us |
  LargestPalindromeDavislor |      7.3468 us |     0.1378 us |      7.3217 us |
 LargestPalindromeDavislor2 |      5.2548 us |     0.0622 us |      5.2729 us |

Divislor' nice optimisation

Source Link

edited Apr 20, 2017 at 9:34

pgs

932
8
24

@Divislor

[Benchmark]
public static string LargestPalindromeDavislor() {
    return LargestPalindromeDavislorImpl().First(HasFactors).ToString();
}
private static IEnumerable<Int32> LargestPalindromeDavislorImpl() {
    for (Int32 a = 9; a >= 1; --a)
        for (Int32 b = 9; b >= 0; --b)
            for (Int32 c = 9; c >= 0; --c)
                yield return a * 100001 + b * 10010 + c * 1100;
}
private static bool HasFactors(Int32 p) {
    Int32 lower1 = (p / 999 + 10) / 11,
        lower = Math.Max(10, lower1);
    Int32 upper1 = p / 1100,
          upper = Math.Min(90, upper1);
    Int32 count = Math.Max(upper - lower + 1, 0);
    return Enumerable.Range(lower, count).Any(x => p % x == 0);
}

And here are the results

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 3433,142922.43090879 us |   140388.02195217 us | 3433,137977.47667592 us |
    LargestPalindromeDenis |  3,477573.56503143 us |    2556.33619470 us |  3,472561.77476188 us |
     LargestPalindromeEric | 7981,561791.32174122 us | 21,772028.41053498 us | 7881,526635.18138259 us |
      LargestPalindromePgs |     3634.00294525 us |     0.13244323 us |     3634.05013658 us |
 LargestPalindromeDavislor |      7.2958 us |     0.0600 us |      7.3064 us |

And here are the results

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 34,142.4309 us |   140.0219 us | 34,137.4766 us |
    LargestPalindromeDenis |  3,477.5650 us |    25.3361 us |  3,472.7747 us |
     LargestPalindromeEric | 79,561.3217 us | 2,772.4105 us | 78,526.1813 us |
      LargestPalindromePgs |     36.0029 us |     0.1324 us |     36.0501 us |

@Divislor

[Benchmark]
public static string LargestPalindromeDavislor() {
    return LargestPalindromeDavislorImpl().First(HasFactors).ToString();
}
private static IEnumerable<Int32> LargestPalindromeDavislorImpl() {
    for (Int32 a = 9; a >= 1; --a)
        for (Int32 b = 9; b >= 0; --b)
            for (Int32 c = 9; c >= 0; --c)
                yield return a * 100001 + b * 10010 + c * 1100;
}
private static bool HasFactors(Int32 p) {
    Int32 lower1 = (p / 999 + 10) / 11,
        lower = Math.Max(10, lower1);
    Int32 upper1 = p / 1100,
          upper = Math.Min(90, upper1);
    Int32 count = Math.Max(upper - lower + 1, 0);
    return Enumerable.Range(lower, count).Any(x => p % x == 0);
}

And here are the results

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 33,922.0879 us |   388.5217 us | 33,977.7592 us |
    LargestPalindromeDenis |  3,573.3143 us |    56.9470 us |  3,561.6188 us |
     LargestPalindromeEric | 81,791.4122 us | 1,028.3498 us | 81,635.8259 us |
      LargestPalindromePgs |     34.4525 us |     0.4323 us |     34.3658 us |
 LargestPalindromeDavislor |      7.2958 us |     0.0600 us |      7.3064 us |

edited body

Source Link

edited Apr 19, 2017 at 21:44

pgs

932
8
24

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 3534,069142.85384309 us |   199140.98240219 us | 3534,040137.98724766 us |
    LargestPalindromeDenis |  3,539477.89035650 us |    3525.60923361 us |  3,542472.88017747 us |
     LargestPalindromeEric | 8179,938561.63453217 us | 12,338772.10574105 us | 8178,773526.23511813 us |
      LargestPalindromePgs |     36.82680029 us |     0.38901324 us |     36.72230501 us |

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 35,069.8538 us |   199.9824 us | 35,040.9872 us |
    LargestPalindromeDenis |  3,539.8903 us |    35.6092 us |  3,542.8801 us |
     LargestPalindromeEric | 81,938.6345 us | 1,338.1057 us | 81,773.2351 us |
      LargestPalindromePgs |     36.8268 us |     0.3890 us |     36.7223 us |

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 34,142.4309 us |   140.0219 us | 34,137.4766 us |
    LargestPalindromeDenis |  3,477.5650 us |    25.3361 us |  3,472.7747 us |
     LargestPalindromeEric | 79,561.3217 us | 2,772.4105 us | 78,526.1813 us |
      LargestPalindromePgs |     36.0029 us |     0.1324 us |     36.0501 us |

Reverse

Source Link

edited Apr 19, 2017 at 21:32

pgs

932
8
24

Loading

added 109 characters in body

Source Link

edited Apr 19, 2017 at 21:02

pgs

932
8
24

Loading

Add benchmarks

Source Link

edited Apr 19, 2017 at 20:33

pgs

932
8
24

Loading

deleted 10 characters in body

Source Link

edited Apr 19, 2017 at 19:28

pgs

932
8
24

Loading

Add comment

Source Link

edited Apr 19, 2017 at 19:21

pgs

932
8
24

Loading

Source Link

answered Apr 19, 2017 at 19:09

pgs

932
8
24

Loading

Stack Exchange Network

Return to Answer