LINUX.ORG.RU

Ткните носом, что я пропустил

 ,


0

6

Вот тут есть реализация теста Миллера-Рабина, и меня смущает одна строка:

(define (miller-rabin-test n) 
   (define (try-it a) 
     (define (check-it x) 
       (and (not (= x 0)) (= x 1)))  ;;вот это что?
     (check-it (miller-rabin-expmod a (- n 1) n))) 
   (try-it (+ 1 (random (- n 1))))) 
Если я правильно понимаю, это проверка ((x != 0) AND (x = 1)). Почему не просто проверка х на равенство с единицей? Синтаксис: The <test> expressions are evaluated from left to right, and the value of the first expression that evaluates to a false value (see section 6.3.1) is returned. Any remaining expressions are not evaluated. [...] То есть сначала происходит сравнение с нулем, и если х = 0, сразу возвращается #f? Это не то же самое, что и просто
(define (check-it x)  (= x 1))
?

★★★★★

Последнее исправление: cdshines (всего исправлений: 3)

5 подписавшихся и ни одного ответа. :)

Все ждут, когда придет кто-то умнее их и все разложит по полочкам?

Давайте я первым сделаю предположение.

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

1. Автор банально перетрудился (ну с кем не бывает?) и сделал опечатку. Двойная проверка не нужна.
2. Так как на вход функции check-it передается функция, а не просто значение, то двойная проверка может иметь смысл, если значение функции расчитывается каждый раз, однако, насколько я знаю, в схеме это не так и значение x в обоих сравнениях будет одинаковым, а потому смысла в лишних действиях я опять не вижу.

delete83 ★★
()
Ответ на: комментарий от delete83

Нет, я же вон скопипастил из стандарта вроде. Только если все #t, то возвращается последнее знаечение, а если, идя слева направо, встречается #f, оно сразу возвращается.

Если кто-то может подсказать по самому тесту - у меня есть подозрение, что это and относится и к первому, и ко второму условиям.

cdshines ★★★★★
() автор топика
Ответ на: комментарий от cdshines

Не, ты не понял.

Предположим, что (not (= x 0)) вернуло #t. Тогда нам придется сделать второе сравнение. При этом x нова будет вычисляться или нет?

Дело в том, что x тут тождественна (+ 1 (random (- n 1)))

Понимаешь, о чем я говорю?

delete83 ★★
()
Ответ на: комментарий от delete83

А, понял. Нет, в этой области х - заранее известная величина, это параметр функции. С любым порядком вычислений. А иначе и смысла бы не было.

cdshines ★★★★★
() автор топика
Ответ на: комментарий от cdshines

Я уже увидел. miller-rabin-expmod возвращает либо 0, либо 1, причем при одинаковых аргументах всегда возвращает одинаковый результат. Смысла делать проверку дважды нет никакого.

delete83 ★★
()
Ответ на: комментарий от delete83

точно второй раз x не будет вычисляться

Точно.

buddhist ★★★★★
()
Ответ на: комментарий от delete83

expmod возвращает не только 0 или 1, а, собственно, то, для чего предназначена - степень числа по модулю.

cdshines ★★★★★
() автор топика

Вот вам доказательство эквивалентности:

(define (proof N)
  (let ((test-list (map (lambda (x) (- x (quotient N 2))) (iota N)))
	(simple (lambda (x) (= x 1)))
	(complicated (lambda (x) (and (not (= x 0)) (= x 1)))))
    (equal? (map simple test-list)
	    (map complicated test-list))))      

Найдете контрпример?

По сему, предположу, что либо автор заработался, либо здесь какие-то низкоуровневые причины.

buddhist ★★★★★
()
Ответ на: комментарий от buddhist

Во-первых, я немного пока такой код не понимаю, во-вторых, я, хоть и мало кода на ским видел, но ни в одном авторы не заморачивались низкоуровневыми оптимизациями) попробую поискать аналоги от других авторов - интересно, что там.

cdshines ★★★★★
() автор топика
Ответ на: комментарий от cdshines

Вероятно, автор когда-то активно писал на каком-нибудь асме :)

buddhist ★★★★★
()
Ответ на: комментарий от buddhist

Вот вам доказательство эквивалентности

Только это тест а не доказательство. Доказывать тут нечего, так как это аксиома (conjunction elimination).

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

Всё равно для обоих выражений в лучшем случае будет cmp 1 r1; sete r2. При сравнении с нулём - test r1, r1; sete r2, но тут сравнение с нулём не нужно.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Только это тест а не доказательство

По Лакатосу — это доказательство :)

buddhist ★★★★★
()
Ответ на: комментарий от buddhist

Вы это серьезно?? Asm и Scheme в одном треде? У меня разрыв шаблона!

delete83 ★★
()
Ответ на: комментарий от quasimoto

Ну я имел в виду, что первый и единственный аргумент функции в данном случае хранится в аккумуляторе.

buddhist ★★★★★
()
Ответ на: комментарий от cdshines

Вообще, интересно получается. Рассуждают о какой-то оптимизации лишнего сравнения с нулем, а забывают при этом, что каждое замыкание обычно сопровождается созданием нового объекта на куче, в данном случае функции :)

dave ★★★★★
()
Ответ на: комментарий от dave

Ну у меня такого пока нет в сикпе, не дошел, наверное. Там написано просто - вложенные определения удобны с точки зрения целостности программы, понятно, что к чему и не нужно лишних параметров передавать. Все что-то скрывают, везде обман:(

cdshines ★★★★★
() автор топика
Ответ на: комментарий от cdshines

Да, ладно, не переживай. Языки ФП, вообще, очень прожорливы до кучи. Обнадеживает лишь то, что их сборщики мусора, как правило, заточены под частое выделение маленьких объектов, таких как эти вложенные функции.

dave ★★★★★
()
(define (miller-rabin-test n) 
   (define (try-it a) 
     (define (check-it x) 

Фигасе....

anonymous
()
Ответ на: комментарий от cdshines

Ну у меня такого пока нет в сикпе, не дошел, наверное.

И не надо. Преждевременная оптимизация - корень всех бед. (c)

anonymous
()
Ответ на: комментарий от dave

Здесь лишние замыкания (вложенные define)

Там почти нет замыканий, в основном вложенные функции, только m в miller-rabin-expmod и n в miller-rabin-test замыкаются - вряд ли это существенно повлияет на скорость обсчёта.

а они стоят дорого

При использовании очень тупого компилятора (или вообще при неиспользовании), нужно добавить :) В gcc, например, такой код:

int miller_test(int n) {
    int try_it(int a) {
        int check_it(int x) {
            return x == 1;
        };
        check_it(expmod(a, n - 1, n));
    };
    try_it(1 + random(n - 1));
}

при -O0 даёт

check_it.1593:
	pushq	%rbp
	movq	%rsp, %rbp
	movl	%edi, -4(%rbp)
	cmpl	$1, -4(%rbp)
	sete	%al
	movzbl	%al, %eax
	popq	%rbp
	ret
try_it.1590:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movl	%edi, -4(%rbp)
	movq	%r10, %rax
	movl	(%rax), %edx
	leal	-1(%rdx), %ecx
	movl	(%rax), %edx
	movl	-4(%rbp), %eax
	movl	%ecx, %esi
	movl	%eax, %edi
	movl	$0, %eax
	call	expmod
	movl	%eax, %edi
	call	check_it.1593
	leave
	ret
miller_test:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movl	%edi, %eax
	movl	%eax, -16(%rbp)
	movl	-16(%rbp), %eax
	subl	$1, %eax
	movl	%eax, %edi
	movl	$0, %eax
	call	random
	addl	$1, %eax
	leaq	-16(%rbp), %rdx
	movq	%rdx, %r10
	movl	%eax, %edi
	call	try_it.1590
	leave
	ret

функции не в куче, и даже не на стеке, а просто в CS, при том что n тут замыкается. При -O1 всё просто заинлайнится:

miller_test:
	movq	%rbx, -16(%rsp)
	movq	%rbp, -8(%rsp)
	subq	$24, %rsp
	movl	%edi, %ebx
	leal	-1(%rbx), %ebp
	movl	%ebp, %edi
	movl	$0, %eax
	call	random
	leal	1(%rax), %edi
	movl	%ebx, %edx
	movl	%ebp, %esi
	movl	$0, %eax
	call	expmod
	movq	8(%rsp), %rbx
	movq	16(%rsp), %rbp
	addq	$24, %rsp
	ret

С SBCL будет та же история:

(declaim (ftype (function (fixnum fixnum fixnum) fixnum) expmod)
         (ftype (function (fixnum) (or null boolean)) miller))

(defun miller (n)
  (flet ((try (a)
           (flet ((check (x) (= x 1)))
             (check (expmod a (- n 1) n)))))
    (try (+ 1 (random (- n 1))))))

; CL-USER> (disassemble #'miller)
; disassembly for MILLER
; 02F6F556:       488B55F8         MOV RDX, [RBP-8]           ; no-arg-parsing entry point
;      55A:       48C1FA03         SAR RDX, 3
;      55E:       4883EA01         SUB RDX, 1
;      562:       488D5C24F0       LEA RBX, [RSP-16]
;      567:       4883EC18         SUB RSP, 24
;      56B:       486BC208         IMUL RAX, RDX, 8
;      56F:       710E             JNO L0
;      571:       488BC2           MOV RAX, RDX
;      574:       4C8D1C2590050020 LEA R11, [#x20000590]      ; ALLOC-SIGNED-BIGNUM-IN-RAX
;      57C:       41FFD3           CALL R11
;      57F: L0:   488BD0           MOV RDX, RAX
;      582:       488B0567FFFFFF   MOV RAX, [RIP-153]         ; #<FDEFINITION object for RANDOM>
;      589:       B908000000       MOV ECX, 8
;      58E:       48892B           MOV [RBX], RBP
;      591:       488BEB           MOV RBP, RBX
;      594:       FF5009           CALL QWORD PTR [RAX+9]
;      597:       4883C208         ADD RDX, 8
;      59B:       488B45F8         MOV RAX, [RBP-8]
;      59F:       48C1F803         SAR RAX, 3
;      5A3:       4883E801         SUB RAX, 1
;      5A7:       488D5C24F0       LEA RBX, [RSP-16]
;      5AC:       4883EC18         SUB RSP, 24
;      5B0:       486BF808         IMUL RDI, RAX, 8
;      5B4:       710E             JNO L1
;      5B6:       488BF8           MOV RDI, RAX
;      5B9:       4C8D1C25C6060020 LEA R11, [#x200006C6]      ; ALLOC-SIGNED-BIGNUM-IN-RDI
;      5C1:       41FFD3           CALL R11
;      5C4: L1:   488B75F8         MOV RSI, [RBP-8]
;      5C8:       488B0529FFFFFF   MOV RAX, [RIP-215]         ; #<FDEFINITION object for EXPMOD>
;      5CF:       B918000000       MOV ECX, 24
;      5D4:       48892B           MOV [RBX], RBP
;      5D7:       488BEB           MOV RBP, RBX
;      5DA:       FF5009           CALL QWORD PTR [RAX+9]
;      5DD:       480F42E3         CMOVB RSP, RBX
;      5E1:       4883FA08         CMP RDX, 8
;      5E5:       BA17001020       MOV EDX, 537919511
;      5EA:       41BB4F001020     MOV R11D, 537919567
;      5F0:       490F44D3         CMOVEQ RDX, R11
;      5F4:       488BE5           MOV RSP, RBP
;      5F7:       F8               CLC
;      5F8:       5D               POP RBP
;      5F9:       C3               RET

Это при дефолтных оптимизациях. Функции из flet и labels активно раскрываются, функция в куче может аллоцироваться только при возвращении замыкающей лямбды или при возвращении flet/labels функции, так что она уже не будет локальной. Тут ещё можно видеть, что вывод типов работает (но не полностью - непонятно зачем ALLOC-SIGNED-BIGNUM). Правда, в CCL не будет никакого вывода типов и функция из flet будет аллоцироваться, но это проблемы CCL.

В GHC будет работать lambda lifting.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Я только на PDP-11 писал когда-то, поэтому твои примеры в полной мере оценить не могу :)

Ты пишешь, что CCL делает так, как я написал, а остальные хорошо оптимизируют. Допускаю, что в данном частном случае оптимизация возможна, но все же, есть другие случаи, и это не только возвращение функции, где происходит создание объекта на куче. А что если добавить в замыкание вычислимое поле? Как тогда? По-моему не останется других вариантов, как создавать объект.

Мой опыт здесь основан на изучении результатов компиляции F# с помощью рефлектора. Там есть необходимость вписаться в объектную модель дотнета. Предполагаю, что компилятор Scala создает примерно такой же код, как и F#. Возможно, что они более ограничены в выборе средств оптимизации, чем упомянутые тобою компиляторы gcc и sbcl. Поэтому о некоторых оптимизациях мог не знать.

dave ★★★★★
()
Ответ на: комментарий от dave

А что если добавить в замыкание вычислимое поле? Как тогда?

А что такое вычислимое поле?

Возьмём тот пример:

(define (miller-rabin-test n)
  (define (try-it a)
    (define (check-it x)
      (and (not (= x 0)) (= x 1)))
    (check-it (miller-rabin-expmod a (- n 1) n)))
  (try-it (+ 1 (random (- n 1)))))

тут есть вложенная функция check-it тело которой свободно от переменных окружения, то есть оно их не замыкает, так что, если такие функции остаются локальными, компилятор может их переписать как

(define (check-it x)
  (and (not (= x 0)) (= x 1)))

(define (miller-rabin-test n)
  (define (try-it a)
    (check-it (miller-rabin-expmod a (- n 1) n)))
  (try-it (+ 1 (random (- n 1)))))

вторая вложенная функция try-it уже замыкает n - в её теле используется переменная из окружающего скопа. Тем не менее, эта функция также локальна, поэтому её можно переписать явно передавая замыкаемые параметры:

(define (check-it x)
  (and (not (= x 0)) (= x 1)))

(define (try-it a n)
  (check-it (miller-rabin-expmod a (- n 1) n)))

(define (miller-rabin-test n)
  (try-it (+ 1 (random (- n 1))) n))

при -O0 gcc это и делает (там адрес n помещается в r10), если сделать readelf -s, то можно увидеть try_it и check_it помеченные как LOCAL. А дальше уже к функциям можно применить инлайнинг как к обычным функциям.

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

Проблемы могут быть с возвращаемыми замыканиями вместе с возможностью изменять замыкаемые переменные, это, буквально, нарушают линейность:

typedef int(bar)(int);

bar foo(int x) {
    int bar(int y) {
        x += y;
        printf("%i\n", x);
    };
    return bar;
}

теперь если сделать

    bar bar1 = foo(1);
    bar bar2 = foo(2);
    bar1(1); // -> 2
    bar2(1); // -> 3
    bar1(1); // -> 3
    bar2(1); // -> 4
    bar1(-2); // -> 1
    bar2(2); // -> 6

то каждый раз foo должна аллоцировать bar в куче. Также нужно решать проблему сборки функций в куче (в функциональном языке с активным созданием таких функций кроме GC мало вариантов).

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Проверил в студии для F#. Лишние объекты создаются только в режиме Debug. В режиме Release оптимизируется все хорошо. Прогресс.

dave ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.