Crystal vs Rust: A Comparison

3

Someone in the Rust forum did a version to numerically form the palindromes to eliminate the number<->string conversions, and I did the equivalent for Crystal. The times are literally the same now, and almost 2.5x faster (from ~25.5s to ~9.3s for Crystal). Here’s the code.

Crystal:

def palindromicgapfuls(digit, count, keep)
  skipped = 0                       # initial count of skipped values
  to_skip = count - keep            # count of unwanted values to skip
  gapfuls = [] of UInt64            # array of palindromic gapfuls
  nn, base = digit * 11, 1_u64      # digit gapful divisor: 11, 22,...88, 99
  (2..).select do |power|
    base   *= 10 if power.even?     # value of middle digit position: 10..
    base11  = base * 11             # value of middle two digits positions: 110..
    this_lo = base * digit          # starting half for this digit: 10.. to  90..
    next_lo = base * (digit + 1)    # starting half for next digit: 20.. to 100..
    this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
      basep = power.odd? ? base11 : base 
      palindrome = make_palindrome(front_half, power)
      10.times do
        (gapfuls << palindrome if (skipped += 1) > to_skip) if palindrome.divisible_by?(nn)
        palindrome += basep
      end
      return gapfuls[0...keep] unless gapfuls.size < keep
    end
  end
end

def make_palindrome(front_half, power) 
  result = front_half
  result //= 10 if power.even?
  while front_half > 0
    result *= 10
    result += front_half.remainder(10)
    front_half //= 10
  end
  result
end

t = Time.monotonic

count, keep = 20, 20
puts "First 20 palindromic gapful numbers ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 100, 15
puts "\nLast 15 of first 100 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 1_000, 10
puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 100_000, 1
puts "\n100,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 1_000_000, 1
puts "\n1,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

count, keep = 10_000_000, 1
puts "\n10,000,000th palindromic gapful number ending with:"
1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }

puts (Time.monotonic - t).total_seconds

Here’s the Rust code:

fn palindromicgapfuls(digit: u64, count: u64, keep: usize) -> Vec<u64> {
    let mut skipped = 0u64;               // initial count of skipped values
    let to_skip = count - keep as u64;    // count of unwanted values to skip
    let mut gapfuls: Vec<u64> = Vec::with_capacity(keep);
    let nn = digit * 11;                  // digit gapful divisor: 11, 22,...88, 99
    let (mut power, mut base) = (1, 1u64);
    loop {
        power += 1;
        if power & 1 == 0 { base *= 10 }  // value of middle digit position: 10..
        let base11 = base * 11;           // value of middle two digits positions: 110..
        let this_lo = base * digit;       // starting half for this digit: 10.. to  90..
        let next_lo = base * (digit + 1); // starting half for next digit: 20.. to 100..
        for front_half in (this_lo..next_lo).step_by(10) { // d_00; d_10; d_20; ...
            let basep = if power & 1 == 1 { base11 } else { base };
            let mut palindrome = make_palindrome(front_half, power);
            for _ in 0..10 {
                if palindrome % nn == 0 {
                    skipped += 1;
                    if skipped > to_skip {
                        gapfuls.push(palindrome);
                        if gapfuls.len() >= keep { return gapfuls; }
                    }
                };
                palindrome += basep;
            }
        }
    }
}

fn make_palindrome(mut front_half: u64, power: u64) -> u64 {
    let mut result = front_half;
    if power & 1 == 0 { result /= 10; }
    while front_half > 0 {
        result *= 10;
        result += front_half % 10;
        front_half /= 10;
    }
    result
}

fn main() {
    let t = std::time::Instant::now();

    let (count, keep) = (20, 20);
    println!("First 20 palindromic gapful numbers ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (100, 15);
    println!("\nLast 15 of first 100 palindromic gapful numbers ending in:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (1_000, 10);
    println!("\nLast 10 of first 1000 palindromic gapful numbers ending in:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (100_000, 1);
    println!("\n100,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (1_000_000, 1);
    println!("\n1,000,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    let (count, keep) = (10_000_000, 1);
    println!("\n10,000,000th palindromic gapful number ending with:");
    for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }

    println!("{:?}", t.elapsed())
  }
8 Likes