On Apr 30, 2:43 am, tarcisio praciano-pereira
<[email protected]> wrote:
> Eras, Pedro! explica o código - put some comments! Não entendi nada, e
> sou matemático.
>
> Aparentemente fazes alguma seleção entre par e impar, mas não entendi
> porque.
> > (defun ! (n)
> > (let ((shift 0))
> > (labels ((fact1 (n m)
> > (cond
> > ((and (evenp n) (> m 1))
> > (incf shift (ash n -1))
> > (fact1 (ash n -1) (ash m -1)))
> > ((<= n m) n)
> > (t (* (fact1 n (ash m 1)) (fact1 (- n m)(ash m 1)))))))
> > (ash (fact1 n 1) shift))))
>
> > pedro
Ele usou otimização com bitshifting, uma operação a nível de máquina.
Não é pra ser compreendido para não iniciados. ;)
Fatorial é aquela definição recursiva e simples (e não otimizada) de
sempre:
(defun fatorial (n)
(if (< n 2) 1
(* n (fatorial (- n 1)))))
Exceto que uma implementação puramente recursiva desse tipo
rapidamente chega a um limite de execução: a pilha estoura por haver
muitas chamadas para ns muito grandes. A solução simples em
programação funcional é usar o estilo de tail calls (que a maioria das
implementações suporta).
Nesse estilo, elimina-se a necessidade de se manter várias chamadas em
aberto na pilha ao se eliminar a espera pelo termino de uma
computação: a última chamada (tail call) é realmente uma chamada, não
uma expressão esperando pelo resultado de uma chamada. Como nada
exceto a chamada original da função espera pelo seu resultado final,
por baixo dos panos pode-se simplesmente, a grosso modo, eliminar todo
o artefato de chamadas reais de função e compilá-la como se fosse uma
simples iteração ou um goto nomeado. Não se gasta pilha de chamadas.
Ilustrando:
(if (< n 2) 1 ; <- expressão final
(* n (fatorial (- n 1))))) ; <- expressão final esperando pelo
resultado da chamada recursiva
a troca é simples e o benefício é imenso:
(if (< n 2) 1
(fatorial (- n 1) (* n)))) ; trazemos a expressão final como um
parâmetro para a própria chamada
mas está incompleto, pois o resultado de (fatorial (- n 1)) ainda não
foi calculado e não podemos portanto multiplicá-lo a n, certo? Bem,
digamos que possamos e chamemos a ele de resultado:
(if (< n 2) resultado ; <- aqui
(fatorial (- n 1) (* n resultado)))) ; <- e aqui
agora vamos dar um valor inicial a resultado, que por acaso vai ser o
mesmo para a condição de parada original: 1
(defun fatorial (n &optional (resultado 1))
(if (< n 2) resultado
(fatorial (- n 1) (* n resultado))))
Bem, devo dizer que esse SBCL realmente é um bicho parrudo. Executou
(and (fatorial 100000) t) em 9,8 segundos. Gambit, uma das mais
potentes implementações para Scheme, ficou na marca de 32 segundos
para uma implementação similar:
(define (fatorial n)
(define (! n r) (if (< n 2) r (! (- n 1) (* r n))))
(! n 1))
3 x mais lento... por outro lado, gera C portável. :)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Lisp-br" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/lisp-br?hl=en
-~----------~----~----~----~------~----~------~--~---
