SICP Exercise 2.5 - селектор работает нестабильно

Я читаю SICP и делаю упражнение 2.5:

Упражнение 2.5. Покажите, что мы можем представить пары неотрицательных целых чисел, используя только числа и арифметические операции, если мы представим пару a и b как целое число, являющееся произведением 2^a*3^b. Дайте соответствующие определения процедур cons, car и cdr.

Вот мое решение:

;;; Exercise 2.5
;;; ============

(define (cons x y)
  (* (expt 2 x)
     (expt 3 y)))

(define (car z)
  ; n is a power of 2, which is greater than z
  (let ((n (expt 2 (ceiling (/ (log z) (log 2))))))
   (/ (log (gcd z n)) (log 2))))

(define (cdr z)
  ; n is a power of 3, which is greater than z
  (let ((n (expt 3 (ceiling (/ (log z) (log 2))))))
   (/ (log (gcd z n)) (log 3))))

Мой код хорошо работает с относительно небольшими тестовыми примерами:

(define x 12)
(define y 13)
(define z (cons x y))

(car z)
;Value: 12.
(cdr z)
;Value: 12.999999999999998

Однако при увеличении числа он дает неверные результаты:

(define x 12)
(define y 14)
(define z (cons x y))

(car z)
;Value: 12.
(cdr z)
;Value: 2.8927892607143724 <-- Expected 14

Я хочу знать, что не так с моей реализацией. Что-то не так с алгоритмом? Идея состоит в том, что наибольший общий разработчик z = 2 ^ x * 3 ^ y и n (степень двойки, которая больше z) - это ровно 2 ^ x.

Если мой алгоритм верен, вызвано ли это несоответствие ошибкой округления и / или переполнением?


algorithm floating-point numerical-methods scheme sicp
person nalzok    schedule 17.01.2017    source источник
comment
В ваших определениях есть асимметрия, которая выглядит неверной. Я подозреваю, что вы написали cdr методом копирования и вставки.   -  person molbdnilo    schedule 18.01.2017
comment
@molbdnilo Да, я видел, потому что я думаю, что они аналогичны. И car, и cdr используют (ceiling (/ (log z) (log 2))), потому что для z=2^x*3^y log_2(z) будет больше, чем x и y, а log_3(z) только гарантированно будет больше y.   -  person nalzok    schedule 18.01.2017
comment
@SunQingyao Я только что изменил 2 на 3 в определении cdr, и на самом деле я получаю 14.0 вместо 2.89, так что, похоже, это имеет эффект.   -  person Sylwester    schedule 19.01.2017
comment
@Sylwester IOW, вы обнаружили опечатку, которая повлияла на случаи некопростых полномочий (а не на случаи больших чисел :)); тем не менее, (car (cons 31 37)) не возвращает 31.0.   -  person Will Ness    schedule 20.01.2017

Ответы (1)


arrow_upward
2
arrow_downward

Одно из решений - избегать чисел с плавающей запятой.

Рассмотрим max-power-dividing, который находит максимальный показатель k такой, что p^k делит n:

(define (max-power-dividing p n)
  (if (zero? (remainder n p))
      (+ 1 (max-power-dividing p (/ n p)))
      0))

Тогда мы можем написать:

(define (car z) (max-power-dividing 2 z))
(define (cdr z) (max-power-dividing 3 z))

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

person soegaard    schedule 17.01.2017
comment
Спасибо за другое решение этого вопроса. Однако я хотел бы улучшить свое решение, а не просто использовать чужое решение. В любом случае, отладка - это половина удовольствия от кодирования. Итак, расскажите мне, как заставить MIT-Scheme не использовать вычисления с плавающей запятой. (Кроме того, мой алгоритм, похоже, имеет порядок роста тета-журнала (n), а ваш - порядок тета-из-n. роста ...) - person nalzok; 18.01.2017
comment
@SunQingyao Я ожидаю, что log обязательно будет с плавающей запятой, но вы можете проверить документацию. Что касается эффективности, вы можете улучшить приведенный здесь код с помощью стандартного приема удвоения на каждом этапе итерации. - person Will Ness; 20.01.2017