Project Euler 14: производительность по сравнению с C и мемоизацией

В настоящее время я работаю над проблемой Эйлера проекта 14.

Я решил это с помощью плохо закодированной программы без мемоизации, которая заняла 3865 секунд (см. редактирование).

Вот оно:

step :: (Integer, Int) -> Integer -> (Integer, Int)
step (i, m) n   | nextValue > m         = (n, nextValue)
                | otherwise             = (i, m)
                where nextValue = syr n 1

syr :: Integer -> Int -> Int
syr 1 acc   = acc
syr x acc   | even x    = syr (x `div` 2) (acc + 1)
            | otherwise = syr (3 * x + 1) (acc + 1)

p14 = foldl step (0, 0) [500000..999999]

Мой вопрос касается нескольких комментариев в ветке, связанных с этой проблемой, где упоминалось время выполнения ixдля кода -- примечание: я не проверял, действительно ли время выполнения соответствует упомянутому):

#include 


int main(int argc, char **argv) {
    int longest = 0;
    int terms = 0;
    int i;
    unsigned long j;
    for (i = 1; i <= 1000000; i++) {
        j = i;
        int this_terms = 1;
        while (j != 1) {
            this_terms++;
            if (this_terms > terms) {
                terms = this_terms;
                longest = i;
            }
            if (j % 2 == 0) {
                j = j / 2;
            } else {
                j = 3 * j + 1;
            }
        }
    }
    printf("longest: %d (%d)\n", longest, terms);
    return 0;
}

Для меня эти программы в чем-то похожи, если говорить об алгоритме.

Интересно, почему такая большая разница? Или есть какая-то фундаментальная разница между нашими двумя алгоритмами, которая может оправдать коэффициент x6 в производительности?

Кстати, в настоящее время я пытаюсь реализовать этот алгоритм с помощью мемоизации, но я немного запутался, его намного проще реализовать на императивном языке (и я еще не манипулирую монадами, поэтому я не могу использовать эта парадигма). Так что, если у вас есть хороший учебник, который подойдет новичку для изучения мемоизации, я буду рад (те, с которыми я столкнулся, были недостаточно подробными или не в моей лиге).

Примечание: я пришел к декларативной парадигме через Пролог и все еще нахожусь в самом начале процесса открытия Haskell, так что я могу пропустить важные вещи.

Note2: приветствуются любые общие советы по поводу моего кода.

РЕДАКТИРОВАТЬ:благодаря помощи delnan я скомпилировал программу, и теперь она запускается за 5 секунд, поэтому сейчас я в основном ищу подсказки по мемоизации (даже если идеи о существующем разрыве x6 все еще приветствуются).