SICP: малая теорема Ферма

Кусочек кода с распознаванием простых чисел по Малой Теореме Ферма.

; Разное встроенное
(define (even? x) (= (% x 2)))
(define (square x) (* x x))
(define (prime? p) (= (first (factor p)) p))

; Вычисляет (% (pow a b) p)
(define (expmod a b p)
  (cond ((= b) 1)
        ((even? b) (% (square (expmod a (/ b 2) p)) p))
        (true (% (* a (expmod a (dec b) p)) p))))

; Проверяет число на простоту 1 раз
(define (fermat-test p)
  (let (n (+ (rand (- p 1)) 1))
    (= (expmod n p p) n)))

; Проверяет число на простоту много раз
(define (fast-prime p (n 1))
  (local (f)
    (while (and (set 'f (fermat-test p)) (!= (dec n))))
    f))

; Проверяет число на принадлежность к Кармайкловым Числам.
(define (carmaicl? x)
  (and (not (prime? x))
       (apply and (map (fn (n) (= (expmod n x x) n)) (sequence 1 (- x 1))))))

Функция carmaicl? работает довольно медленно. Чтобы прогнать её на числах от 2 до 5 000 потребовалось несколько минут. При этом на проверку 2х функция затрачивает примерно в 2 раза больше времени, чем на проверку х. То есть, если я правильно понимаю, на проверку диапазона 5k-10k уйдёт в три раза больше времени, чем на проверку диапазона 0k-5k.

SICP 1.19: Фибоначчи по логарифму

Вот эта гнусная функция:

(define (even? x) (if (= (% x 2))))

(define (fib n (a 1) (b 0) (p 0) (q 1))
  (cond ((= n) b)
        ((even? n) (fib (/ n 2)
                        a
                        b
                        (+ (* p p) (* q q))
                        (+ (* 2 p q) (* q q))))
        (true (fib (dec n)
                   (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q))))

Программирования, тут, на мой взгляд, гораздо меньше, чем математики. Думаю, это неправильно.

SICP: итеративное возведение в степень

Долго думал, как сделать итеративный процесс возведения в степень (SICP, упражнение 1.16). Я сразу догадался, что брать за основу надо число в двоичной системе счисления, но мне было непонятно, как переводить это число в алгоритм.

Вот например, как выглядели алгоритмы и двоичная запись для некоторых чисел:

7 *+*+ 111
8 *** 1000
9 ***+ 1001
10 **+* 1010

В итоге оказалось всё просто. Надо отбрасывать самый первый знак, а дальше трактовать единицу как "возвести в квадрат и умножить", а ноль — как "просто возвести в квадрат".

Также я впервые использовал здесь функцию cons, которая объединяет first и rest.

; Возвести число b в степень p (p должно быть больше 1)
(define (pow-hm b p)
  (apply (fn (x y) (if (= y) (* x x) (* x x b)))
         (cons b (map int (1 (explode (bits p)))))
         2))

А вот то же самое, только по "итеративному алгоритму" предложенному в SICP:

; Возвести b в степень n
(define (pow-sicp-1 b n)
  (cond ((= n 1) b)
        ((= (% n 2)) (pow-sicp-1 (* b b) (/ n 2)))
        (true (* (pow-sicp-1 (* b b) (/ n 2)) b))))

Вроде бы как, ошибиться тут просто негде. Однако… цитирую SICP:

«Храните, помимо значения степени n и основания b, дополнительную переменную состояния a, и определите переход между состояниями так, чтобы произведение abⁿ от шага к шагу не менялось».

Спрашивается, зачем козе баян? Разве что, перехерачить алгоритм вот так:

; То же самое, но с инвариантом
(define (pow-sicp-2 b n (a 1))
  (if (= n 1)
    (* b a)
    (* a (pow-sicp-2 (* b b) (/ n 2) (if (= (% n 2)) 1 b)))))

Согласно тестам, кстати, самый быстрый алгоритм — это рекурсия без инварианта. Алгоритмы с инвариантом и с разложением на биты немного медленнее. Впрочем, скорости там одного порядка, существенной разницы нет.

Дополнение.

Блджад. Только перейдя к упражнению 1.17 я понял, в чём была соль. По условиям задачи, у нас есть вот такие функции:

(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (even? x) (if (= (% x 2))))

Из них надо склепать умножение. Вот труе итеративный вариант:

; Умножить а на b
(define (mul-sicp-i a b (p 0))
  (let (p 0)
    (until (= b 1)
      (set 'p (+ p (if (even? b) 0 a)))
      (set 'a (double a))
      (set 'b (halve b)))
    (+ a p)))

А вот то же самое, но через жопу концевую рекурсию:

; Умножить a на b
(define (mul-sicp-t a b (p 0))
  (if (= b 1)
    (+ a p)
    (mul-sicp-t (double a) (halve b) (+ p (if (even? b) 0 a)))))

Способы разменять монеты

Хитроумный алгоритм по размену монет из первой главы SICP. Мне потребовалось значительное время, чтобы понять как он работает и воспроизвести его:

#
# Число способов разменять n центов монетами по 1, 5, 10, 25 и 50 центов.
# 

; Доступные монеты
(set 'монеты '(1 5 10 25 50))

; Число разменов n центов с помощью c монет.
(define (размены n (c 5))
  (cond ((< n) 0)
        ((= n) 1)
        ((= c 1) 1)
        (true (+ (размены n (- c 1))
                 (размены (- n (монеты (- c 1))) c)))))

Это воссозданный мной алгоритм из книжки. Вначале же я сделал иначе: считал все возможные методы размена, потом через unique отбирал уникальные, потом через memoize добивался терпимой скорости. Тоже работало, плюс кроме числа способов размена я видел в списке ещё и сами способы.

Но решение из книжки, конечно, красивее.

Кстати, в самой книжке алгоритм реализован, на первый взгляд, примерно так же, но там есть слова: «на то, чтобы получить ответ 292 уйдёт какое-то время». В реальности время выполнения процедуры на моём компьютере — 0,3 миллисекунды.

То ли эта фраза писалась в семидесятые года, то ли newLISP гораздо круче чем Scheme.

PS: Разменять доллар можно 292 способами. Способов разменять 10 долларов уже 800 тысяч.

PPS: Те же яйца, но с печатью дерева.

(define (размены n (c 5))
  (print "Р" n " (" c "): ")
  (cond ((< n) (println 0) 0)
        ((= n) (println 1) 1)
        ((= c 1) (println 1) 1)
        (true (println "Р" n " (" (- c 1) ") + Р" (- n (монеты (- c 1))) " (" c ")")
              (+ (размены n (- c 1)) (размены (- n (монеты (- c 1))) c)))))

Хвостовая рекурсия

Немного доброты по ссылке с форума newLISP (Ссылка)

Подводя итог, эта точка зрения на хвостовую рекурсию основана на следующих идеях:

* Она предназначена для избегания циклов, которые по какой-то причине полагаются пуристами "плохими". Эти извращенцы думают в циклах, потом переводят свой код в хвостовую рекурсию, а потом ожидают от компилятора обратного перевода в циклы. Это чисто академическая ментальная гимнастика безо всякой практической цели.

* Люди, которым нравится хвостовая рекурсия, целенаправленно обмеменяют свой когд во имя "математической" или "теоретической" чистоты, ожидая при этом, что имлементатор языка сделает за них всю грязную работу.

* Любой код, который зависит от хвостовой рекурсии, легко может быть переписан в циклах. Такая перепись является тривиальной местной трансформацией.

* Межпроцедурная хвостовая рекурсия может привести к некоторому увеличению производительности, но это увеличение будет крайне мало, и за это увеличение придётся заплатить потерей ценной отладочной информации.

Фриддл, ДКА и НКА

Закончил читать книгу Фриддла про регулярные выражения.

Фриддл, конечно, молодец, сказать нечего. Но про автоматы и про разницу между ними он написал крайне непонятно. Гораздо понятнее вот здесь:

http://www.rsdn.ru/article/alg/nka.xml

Если бы я сначала потратил 10 минут на чтение этого текста, а только потом принялся бы за Фриддла, полагаю, я бы вынес из книги Фриддла гораздо больше пользы.

Три добродетели программиста

Источник: http://en.wikipedia.org/wiki/Larry_Wall

Во время работы над второй редакцией книги "Программируем на Перл" Ларри Волл, вместе с Рэндаллом Л. Шварцем и Томом Христиансеном, сформулировал три добродетели программиста. Вот они.

1. Лень — качество, которое заставляет тебя прикладывать большие усилия, чтобы уменьшить общие затраты энергии. Оно заставляет тебя писать трудосберегающие программы, которые другие люди находят полезными, и документировать эти программы, чтобы тебе не приходилось отвечать на кучу вопросов пользователей.

2. Нетерпеливость — гнев, который ты испытываешь, когда компьютер ленится. Этот гнев заставляет тебя писать программы, которые не только выполняют твои команды, но и предвидят их. Или, по меньшей мере, притязают на это.

3. Высокомерие — непомерная гордость, что-то из разряда тех пороков, за которые Зевс поражает молнией. Также это качество, которое заставляет тебя писать (и поддерживать) программы, которыми другие люди будут восхщаться.