Performance Comparison of Project Euler Problem 12: Optimization Strategies in C, Python, Erlang, and Haskell

Experimental Design for Performance Comparison

Project Euler Problem 12 requires finding the first triangle number with over 500 divisors. To accentuate execution time differences, the threshold was increased to 1000 divisors. Implementations in all four languages follow the same algorithmic logic: iteratively generating triangle numbers and computing divisor counts for each. The core factorCount function employs an optimization strategy, iterating only up to the square root to determine the total number of divisors.

Analysis of Initial Performance Results

Without optimizations, execution times vary significantly: C serves as the baseline at 11.074 seconds (100%), Python at 692%, Erlang at 436%, and Haskell at 1421%. These differences stem from language characteristics and runtime environments. C uses long integers directly without runtime loading, while other languages default to arbitrary-precision integers, adding computational overhead. Additionally, interpreted languages like Python require interpreter execution, further affecting performance.

In-Depth Analysis of Haskell Performance Optimization

Based on the best answer's optimization practices, Haskell achieves a performance leap from 1421% to surpassing C through multiple technical improvements. First, using GHC compiler options -O2 -fllvm enables advanced optimizations, reducing execution time from 2 minutes 37 seconds to 36 seconds. Second, explicit type annotations are crucial: the default Integer type supports arbitrary precision but is less efficient; switching to Int reduces time to 11.1 seconds. This leverages hardware support on 64-bit machines, avoiding unnecessary overflow checks.

Choice of arithmetic operations also impacts performance: replacing mod with rem (remainder operation) reduces extra computations, further shortening time to 8.5 seconds. Most importantly, tail recursion optimization (worker/wrapper transformation) restructures the factorCount' function to eliminate repeated passing of constant parameters:

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate + 1) (count + 2)
    | otherwise = go (candidate + 1) count

This optimization reduces execution time to 7.95 seconds, 0.5 seconds faster than C. It demonstrates that Haskell, when fully optimized, can utilize pure functional and lazy evaluation features for efficient numerical computations.

Supplementary Erlang Optimization Practices

Referencing other answers, Erlang optimization involves compiler options and code adjustments. Using the +native compilation flag generates native code, but -compile(export_all) causes conservative compiler optimizations. Changing to -export([solve/0]) reduces execution time from 47.6 seconds to 31.5 seconds. Algorithmically, the original implementation's per-iteration check Candidate == Sqrt adds overhead; adjusting to logic similar to C further reduces time to 19.468 seconds. Although Erlang is not designed for numerical computing, optimizations enable performance within 50% of C.

Answers to Core Questions

Impact of Arbitrary-Precision Integers: Even when values are below MAXINT, Erlang, Python, and Haskell may incur performance penalties due to runtime checks. For example, Erlang must verify whether operations fit into a tagged word or require heap-allocated bignums, introducing overhead even if bignums are never used. In Haskell, using Int instead of Integer avoids this issue.

Tail Recursion Optimization (LCO): All functional implementations support tail recursion optimization, preventing call stack frame accumulation. Performance issues in the experiment stem from algorithm and type choices, not stack overflow.

Cross-Language Optimization Principles: 1) Utilize compiler optimization flags (e.g., -O2, +native); 2) Select appropriate data types (e.g., fixed-width integers); 3) Use efficient arithmetic operations (e.g., rem over mod); 4) Apply tail recursion and worker/wrapper transformations to reduce parameter passing.

Conclusions and Implications

This experiment shows that language performance is not absolute; optimization strategies are decisive. C maintains advantages through low-level control and direct hardware access, but Haskell can surpass it with advanced optimizations. Python and Erlang can also significantly improve performance via JIT (e.g., PyPy) and compilation optimizations in specific scenarios. Developers should deeply understand language features, combining type systems, compiler tools, and algorithmic optimizations to fully realize each language's potential. Future work could explore more languages (e.g., Rust, Julia) in numerical computing and investigate applications of automatic optimization tools.