✍ diale.org

Webpage of Tiago Charters de Azevedo

Início/Start Arquivo/Archive AdNauseum Notas/Notes Contact me RSS


0's e 1's Stern-Brocot

... outra implementação

2016/01/27-19:45:06

Depois da a implementação da árvore de Stern-Brocot em LISP, uma conversa com um colega revelou outra forma de a construir. A saber, usar símbolos. A sugestão incluía usar L e R e uma ordenação lexicográfica: L<R, mas 0's e 1's servem perfeitamente para o efeito. Construir qualquer coisa do género

0: (0,1)
1: (0,01,1)
2: (0,010,01,011,1)
...
onde o nível (k+1) obtém-se intercalando, entre cada duas sequências de (k), a concatenação das mesmas, começando pela maior com 0 inicial.

A ideia é a mesma da implementação anterior. Começa-se pela construção do mediante

(defun mediant (lst1 lst2)
  (cond ((and (= 0 (car lst2))
              (> (length lst2) (length lst1)))
         (append lst2 lst1))
        (t
         (append lst1 lst2))))

;; Example
> (mediant '(0) '(1))
(0 1)
Depois,
(defun mediant-list (01-lst)
  (cond ((cadr 01-lst)
         (append (list (car 01-lst)
                       (mediant (car 01-lst) (cadr 01-lst)))
                 (mediant-list (cdr 01-lst))))
        (t
         01-lst)))

;; Example
> (mediant-list '((0) (1)))
((0) (0 1) (1))
> (mediant-list '((0) (0 1) (1)))
((0) (0 1 0) (0 1) (0 1 1) (1))
ou mais completamente
> (mediant-list
 (mediant-list
  (mediant-list '((0) (1)))))
((0) (0 1 0 0) (0 1 0) (0 1 0 0 1) (0 1) (0 1 1 0 1) (0 1 1) (0 1 1 1) (1))

E finalmente

(defun stern-brocot (01-list n)
  (nest #'mediant-list 01-list n))

;; Example
> (stern-brocot '((0) (1)) 5)
((0) (0 1 0 0 0 0) (0 1 0 0 0) (0 1 0 0 0 0 1 0 0) (0 1 0 0)
 (0 1 0 0 0 1 0 0 1 0 0) (0 1 0 0 0 1 0) (0 1 0 0 0 1 0 0 1 0) (0 1 0)
 (0 1 0 0 1 0 1 0 0 1 0) (0 1 0 0 1 0 1 0) (0 1 0 0 1 0 1 0 0 1 0 0 1)
 (0 1 0 0 1) (0 1 0 0 1 0 1 0 1 0 0 1) (0 1 0 0 1 0 1) (0 1 0 0 1 0 1 0 1)
 (0 1) (0 1 1 0 1 0 1 0 1) (0 1 1 0 1 0 1) (0 1 1 0 1 0 1 0 1 1 0 1)
 (0 1 1 0 1) (0 1 1 0 1 0 1 1 0 1 1 0 1) (0 1 1 0 1 0 1 1)
 (0 1 1 0 1 0 1 1 0 1 1) (0 1 1) (0 1 1 1 0 1 1 0 1 1) (0 1 1 1 0 1 1)
 (0 1 1 1 0 1 1 0 1 1 1) (0 1 1 1) (0 1 1 1 1 0 1 1 1) (0 1 1 1 1)
 (0 1 1 1 1 1) (1))
usando para a composição
(defun nest (function arg n)
  (cond ((= n 0)
         arg)
        (t 
         (nest function (funcall function arg) (- n 1)))))

Claro que posso sempre voltar aos racionais ;)

(defun back-to-rationals (01-lst)
  (mapcar (lambda (x)(/ (sum x)
                        (length x))) 01-lst))

;; Example
(back-to-rationals (stern-brocot '((0) (1)) 5))
(0 1/6 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 5/13 2/5 5/12 3/7 4/9 1/2 5/9 4/7
 7/12 3/5 8/13 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 5/6 1)
usando a função auxiliar
(defun sum (lst)
  (cond (lst
         (+ (car lst)
            (sum (cdr lst))))
        (t
         0)))

;; ore using reduce

(defun sum(lst)
  (reduce #'+ lst))

Etiquetas/Tags: Stern-Brocot, LISP, hack

Implementação do LISP de John McCarthy, de 1960

Implementação do LISP de JMC de 1960 em LTK

2016/01/25-15:38:28

Hoje tive tempo para acabar a implementação do LISP de 1960 de John McCarthy (Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Communications of the ACM 3:4, April 1960, pp. 184-195) em LTK. O código está aqui.

A imagem mostra uma das funções descrita no artigo.

(provide :1960-lisp)
(load "/home/tca/lisp_packages/ltk/ltk.lisp")
(defpackage :1960-lisp
  (:use :common-lisp :ltk)
  (:export lisp)
  (:documentation "1960-lisp is a CL implementation of John McCarthy's  LISP from the paper
    Recursive Functions of Symbolic Expressions and Their Computation by Machine, higly inspired in Paul Graham's
    The Roots of Lisp"))

(in-package :1960-lisp)

(setf tutorial "Examples: 

 1. ((eq 'a 'a) '()) => t

 2. ((eq 'a 'b) '()) => nil

 3. ((cons x '(b c))'((x a ) (y b))) => (a b c)

 4. (((label firstatom (lambda (x)
                                  (cond ((atom x) x)
                                        ('t (firstatom (car x))))))
               y)
             '((y ((a b) (c d))))) => a

 5. ((cons x (cdr y))
             '((x a) (y (b c d)))) => (a b c)

 6.  (((lambda (x) (cons 'a x)) '(b c))
       '((f (lambda (x) (cons 'a x))))) => (a b c)
 
 7. (((label ident (lambda (x) x))
         y)
         '((y ident))) => indent

 8. (((lambda (x) x) '((lambda (x) x))) '()) => (lambda (x) x)

 9. (((label diag (lambda (x) (list x (list 'quote x))))
          y)
        '((y list))) => (list (quote list))

 10. (((label diag (lambda (x) (list x (list 'quote x))))
         y)
       '((y diag))) => (diag (quote diag))

 11. From the original paper og JMC

     (((label ff (lambda (x)
                     (cond ((atom x) x)
                           ('t (ff (car x))))))
         y)
       '((y ((a b) (c d))))) => a
")

(defun not. (x)
  (cond (x '())
        ('t 't)))

(defun null. (x)
  (eq x '()))

(defun and. (x y)
  (cond (x (cond (y't) ('t '())))
        ('t '())))

(defun pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom x)) (not. (atom y)))
         (cons (list (car x) (car y))
               (pair. (cdr x) (cdr y))))))

(defun append. (x y)
  (cond ((null. x) y)
        ('t (cons (car x) (append. (cdr x) y)))))

(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
        ('t (assoc. x (cdr y)))))

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ((eq (car e) 'list) (evlis. (cdr e) a))
       ((eq (car e) 'list) (evlis. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))


(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval. (car m) a)
            (evlis. (cdr m) a)))))

(defun apply. (f a)
  (eval. (cons f (appq. a)) '()))


(defun appq. (m)
  (cond ((null m) '())
        (t
         (cons (list 'quote (car m)) (appq. (cdr m))))))

(defun lisp ()
    (with-ltk ()
      (wm-title *tk* "LISP")
      (let* ((frame-menus (make-menubar))
             (menu-help (make-menu frame-menus "Help"))
             (f-1 (make-instance 'frame))
             (f-2 (make-instance 'frame))
             (f-3 (make-instance 'frame))
             (f-tutorial (make-instance 'frame))
             (f-eval (make-instance 'frame))
             (f-t-1 (make-instance 'frame))
             (f-t-2 (make-instance 'frame))
             (title-f-1 (make-instance 'label :master f-1 :text "Input box: "))
             (title-f-2 (make-instance 'label :master f-2 :text "Output box: "))

             (input-text (make-instance 'text 
                              :master f-1))
             (output-text (make-instance 'text 
                                         :master f-2))
             (b-clear-in (make-instance 'button
                                     :text "Clear Input"
                                     :master f-3
                                     :width 7
                                     :command (lambda () (clear-text input-text))))
             (b-clear-out (make-instance 'button
                                     :text "Clear Output"
                                     :master f-3
                                     :width 8
                                     :command (lambda () (clear-text output-text))))
                                                         
             (b-eval (make-instance 'button
                                    :text "Eval"
                                    :master f-eval
                                    :width 4
                                    :command (lambda ()
                                               (setf (text output-text) 
                                                     (eval-input-text (read-from-string (text input-text))))))))
        (make-menubutton menu-help "Tutorial" (lambda ()
                                                (let* ((w-about (make-instance 'toplevel  :takefocus nil))
                                                       (txt (make-instance 'scrolled-text :master w-about)))
                                                  (wm-title w-about "Examples")
                                                  (pack txt)
                                                  (setf (text txt) tutorial))))
        (make-menubutton menu-help "About" (lambda ()
                                             (let* ((w-about (make-instance 'toplevel  :takefocus nil))
                                                    (txt (make-instance 'text :master w-about :width 60 )))
                                               (wm-title w-about "About")
                                               (pack txt)
                                               (setf (text txt) "GPLv3 - (c) Tiago Charters de Azevedo <tca@diale.org>"))))

        (pack f-1 :side :top :expand t :fill :both)

        (pack title-f-1 :side :top :expand t :fill :both)               
        (pack input-text)

        (pack f-2 :side :top :expand t :fill :both)      
        (pack title-f-2 :side :top :expand t :fill :both)
        (pack output-text)
        
        (pack f-3 :side :left :expand nil :fill :none)      
        (pack b-clear-in :side :left)
        (pack b-clear-out :side :left)

        (pack f-eval :side :right :expand t :fill :both)
        (pack b-eval :side :right)
        )))

(defun eval-input-text (txt)
  (eval. (car txt) (cadadr txt)))

(lisp)

P.S. 160125: Código LTK actualizado.

Etiquetas/Tags: LISP, John McCarthy, original paper, LTK

Diagonal de Cantor

... quando estou para paródias, dá nisto.

2016/01/21-22:54:21

O argumento da diagonal de Cantor pode ser formulado da seguinte forma. Considere-se T o conjunto de todas as sequências de 0 e 1. Se s1, s2, ..., sn ... é uma enumeração dos elementos de T então existe um elemento de T que não corresponde a nenhuma sequência, i=1,2,... Estranho não?

Estranhamente, repito, o resultado obtém-se de uma forma construtiva. Podemos começar por fazer uma lista (note-se que a ordenação escolhida é totalmente arbitrária e qualquer outra podia ser escolhida sem perda de generalidade)

((0 0 0 0 0 0 0 ...) 
 (1 1 1 1 1 1 1 ...) 
 (0 1 0 1 0 1 0 ...)
 (1 1 0 1 0 1 1 ...)
 (0 0 1 1 0 1 1 ...)
 (1 0 0 0 1 0 0 ...))

Posso assim construir um elemento s de T que não está nessa lista. Como? Tomando o primeiro elemento de s diferente do primeiro elemento de s1, i.e. 1, de seguida o segundo elemento s diferente do segundo elemento de s2, e assim por diante. Viajo pela diagonal e retiro para s um elemento diferente daquele que encontro. s tem então a forma

(1 0 1 1 0 1 ...)

É fácil ver que s não está contido na enumeração inicial que construímos para os elementos de T. E logo que não é possível enumerar todas as sequências de zeros e uns. Falta pelo menos um elemento dessa proposta lista completa.

Não é possível deixar de sentir um certo desconforto que se tem na explicação acima. Admitimos que conseguiríamos enumerar, fazer uma lista de todos as sequências de zeros e uns e depois, de uma foram construtiva, obtemos uma lista extra que não estava contida na lista inicial que nos propusemos construir. A contradição surge de uma forma escandalosa e perturbante e é um sinal de que tomamos uma hipótese que de alguma forma contradiz a nossa habitual forma de ver o mundo e em particular como construímos listas.

Para os matemáticos profissionais (e para mim também, quando não estou para paródias) tal resultado é tomado com muita naturalidade e é uma técnica usada em muitas outras áreas de aplicação.

O facto de T não ser numerável, não conseguirmos fazer uma lista completa, apenas mostra que é sem sentido a afirmação ``consideremos todas as sequências de zeros e uns''. A expressão lista é e si mesma uma variável e não uma coisa com significado primitivo

O paradoxo é sempre o mesmo, em muitas formas surge e reaparece. Mostra bem a nossa confusão sobre tudo isto.

Volte-se então há nossa lista de zeros e uns. Enumerei essa lista na forma s1, s2, ... sn, ... A lista s onde o n-ésimo elemento é dado por

s(n)=1-sn(n)
não está na lista inicial.

Pergunta: é isto uma lei natural? Ou é simplesmente um problema de notação que se revela quando escrevo estas listas de 0's e 1's?

Deve a minha notação prevenir encontrar-me na situação em que me encontro? Que significa pensar que está tudo escrito? A lista foi construída propositadamente para se encontrar o que não lá está. Deve ser isso.

Etiquetas/Tags: Cantor, diagonal

New audio monitors

... build from scracth from two auto speakers

2016/01/14-13:25:36

Etiquetas/Tags: DIY, audio, monitors

Escolher, não escolher, escrever, não escrever...

Notas sobre o princípio de Buridan e o livre arbítrio e o teorema do valor intermédio

2016/01/13-09:30:22

O paradoxo do burro de Buridan afirma que um burro colocado num ponto equidistante entre dois fardos de palha morre de fome porque não consegue escolher para que lado se deve deslocar (admitindo que se desloca sempre para o que está mais perto). Não tem nenhuma razão para escolher um ou o outro fardo, qualquer uma das escolhas é igualmente boa para satisfazer as suas necessidades alimentares. Não sabendo ou conseguindo escolher, definha onde está. Morre à fome antes de chegar a um fardo de palha. Posso formular este mesmo problema usando o teorema do Valor Intermédio. (Resultado ensinado a qualquer aluno de um primeiro ano numa cadeira de Análise Matemática de um curso de ciências.) A referência para o que se segue é um texto de Leslie Lamport intitulado "Buridan's Principle" (1984)1.

Admitamos que num instante inicial t=0 o burro está colocado numa posição x numa linha que liga os dois fardos de palha, um dos fardos está na posição 0 e o outro em 1. Assim as posições em que o burro se pode encontrar inicialmente são tais que 0<= x<= 1. A posição de burro num instante posterior é assim uma função de dois argumentos: o tempo t e a posição inicial x. Denote-se por l(t,x) essa posição. Admitamos que quando o burro chega a um fardo de palha se mantém nessa posição para sempre, e ainda que o burro pode estar em qualquer ponto entre dois fardos de palha enquanto decide para que lado se quer deslocar: ou para a esquerda ou para a direita (uma escolha discreta). Assim a posição do burro num instante t obedece a: 0<= l(t,x)<= 1 onde 0<= x <= 1.

É fácil ver para um dado instante, pela continuidade das sucessivas posições do burro (estou a usar o teorema do Valor Intermédio), que existe uma posição estritamente compreendida entre os dois fardos de palha para uma escolha da posição inicial do burro. I.e. existe um L entre 0 e 1 tal que L(a)=l(t,a) onde 0<a<1 para qualquer t. Esse instante poderá ser tarde demais, o burro terá morrido à fome entretanto. Existe uma infinidade de instantes compatíveis com L(a) e logo instantes onde o burro morreu antes de chegar a um dos fardos.

Lamport enuncia o Princípio de Buridan na seguinte forma:

Não é possível concretizar uma escolha num tempo finito baseada num input com variação contínua.

Ao ler este enunciado qualquer cabeça fervilha na construção de exemplos e contra exemplos na economia, nas decisões políticas, enfim, na vida de todos os dias. Primeiro, antes de qualquer outra interpretação mais cosmológica mais fundamental, uma nota.

O que este princípio mostra é que a continuidade da função l(t,x) na condição inicial x não é suficiente para que saibamos, e o burro também, como fazer a escolha num tempo suficientemente curto, i.e. antes de morrer. A forma como o princípio está enunciado, não detalhando todas as propriedades da função l(t,x), faz com que qualquer leitura do princípio nos leve a pensar que é um princípio importante e de aplicabilidade geral. Mas falta quase tudo. Por exemplo, se se admitir que o burro se desloca sempre para a direita a partir de qualquer posição inicial (l(t,x) é uma função crescente na variável t, monótona), como se o burro sofresse de uma certa tendência de translação para direita, o princípio deixa de ter qualquer aura de relevância. O facto de o princípio ter como desfecho final a morte do burro dá ao enunciado uma característica de relevância e de necessidade de resolução, afinal trata-se da morte de um animal, e é importante saber-se como evitar uma tal tragédia.

Do ponto de vista mais geral é óbvia a tentação para se discutir o livre arbítrio individual. Não vou discutir isso em grande profundidade recorrendo a citações passadas, a literatura deste tema é extensa e corro o risco de fazer uma análise incompleta. A minha ideia é apenas fazer uma discussão com o que escrevi atrás. Como se verá qualquer introdução de argumentos extras revelar-se-á completamente desnecessária.

Pode usar-se o Princípio de Buridan para tecer algumas considerações sobre o livre arbítrio. A ideia é a de que uma pessoa sujeita à escolha de duas opções igualmente válidas não tem, de uma forma racional, razões para escolher uma delas. Mas será a escolha entre duas opções racionalmente equivalentes uma opção racional? Não devo fazer as coisas de modo a não ser apanhado desta forma? A minha racionalidade deve precaver-me de ser apanhado numa situação destas.

O que fazer então para sair deste dilema? Escolher aquela que corresponde ao maior bem? Ou aquela que mais me beneficia? Ou a outro? Mas não tenho razões para escolher, como? Não as consigo enumerar? Enumero-as mas são irrelevantes para a minha decisão? Não ter razões é o mesmo que dizer que não sei quais são? Uso um princípio de extremo: escolher o bem maior, que maximiza a utilidade?

Um passeio de bicicleta. A mesma situação ocorre quando ando de bicicleta e tenho que me desviar de uma árvore que se encontra no meu caminho. Desvio-me para a direita ou para a esquerda? Tenho duas opções de escolha enquanto continuamente me aproximo da fatídica árvore. É um problema semelhante cuja não solução tem como consequência uma ida à urgência do hospital. Travo e paro a bicicleta. E agora escolho com calma para que lado vou, circundo a árvore pela esquerda ou pela direita. Neste caso a escolha recai sobre um bem maior a minha integridade física.

Mas porque me coloco numa posição em que tenho de resolver e explicar situações como estas? Ou devo ficar calado.

Porquê este desconforto?

Volto ao início, "uma pessoa não tem razões para escolher". Isto é, não há nenhuma razão para me desviar para a esquerda ou para a direita e, mesmo assim, tenho de fazer uma escolha. Tenho de me desviar. Mas a escolha entre esquerda ou direita não é de facto a escolha que me interessa. O que me preocupa é a colisão com a árvore, se a circundo pela esquerda ou pela direita é totalmente irrelevante para mim. E é exactamente isto que o princípio nos diz, que sem hipóteses extra, uma preferência não expressa, a escolha não fica determinada. Virar para a esquerda ou para a direita é irrelevante, qualquer uma serve.

Se repararmos bem, o princípio foi formulado propositadamente para que este desconforto se revele. A aparente ingenuidade e simplicidade na formulação do princípio sobre a escolha de um dos fardos de palha tem um resultado final que não foi expressamente incluído desde o início: a morte do burro. Ninguém acredita que o burro morrerá nas condições do enunciado se a escolha fosse uma decisão sobre a vida e a morte. O dilema da escolhas dos dois fardos não é a escolha entre a vida e a morte do burro, porque se fosse, a escolha não se colocava neste caso, e o princípio eventualmente necessitaria de uma nova formulação. De uma certa maneira se fosse uma escolha de vida ou morte, não haveria escolha. E aí desaparece o desconforto.

Não é por acaso que a questão sobre uma escolha determinada entre duas opções seja exactamente formulada pelo caso em cada uma das escolhas são exactamente iguais. Em todos os outros casos não há dúvidas e no caso em que há, não há.

1. Buridan's Principle, Leslie Lamport, Digital Equipment Corporation Systems Research Center 31 October 1984 revised: 24 February 2012

Etiquetas/Tags: Buridan, burro, lógica, paradoxo

A terceira sonata para piano de Pierre Boulez

Notas sobre a terceira sonata para piano de Pierre Boulez

2016/01/06-14:10:00

A terceira sonata para piano de Pierre Boulez (1957-58) surge da literatura, em particular do livro-projecto de Mallarmé, e representa uma das primeiras formulações de uma obra aberta. O plano da terceira sonata consiste em cinco movimentos que Boulez, usando uma terminologia acústica, designou por formandos. Estes cinco formandos são:

A - Antophonie B - Trope C - Constellation / Constellation-miroir D - Strophe E - Séquence

Apenas os formandos B e C estão publicados e gravados. A terceira sonata, embora inacabada, tem as suas regras fundamentais de construção: é possível trocar A com B e por outro lado trocar D e E, C fica sempre ao meio. O primeiro par (A,B) pode ser trocado com o segundo (D,E), o que justifica C como sendo constelação espelho.

Boulez evoca três imagens ou ideias que dirigem a obra:

  1. A ideia de obra aberta, que cabe ao executante resumir/acabar, a de work in progress e a ideia de infinitude e permutatividade;
  2. A ideia de labirinto;
  3. E, por último, a ideia de um universo em expansão.

As equações de Einstein em Relatividade Geral (RG) são escritas fazendo uso de um tensor denominado tensor de Ricci que por seu lado se obtém por contração do tensor de Riemann com a métrica. Se não veja-se: latex2png equation

e

latex2png equation

O que é relevante é que o tensor de Riemann, que é designado por latex2png equation onde a, b, c, d = 1, 2, 3, 4, tem exactamente as simetrias que Boulez impôs à sua terceira sonata para piano e cuja ideia, a de um universo em expansão, tem nas equações de Einstein uma das soluções mais relevantes para a compreensão da evolução do universo.

Etiquetas/Tags: Boulez, Mallarmé, Riemann

Árvore Stern-Brocot

... uma implementação em LISP

2016/01/06-00:14:58

Para a construção da árvore de Stern-Brocot precisamos dos mediantes de dois números racionais a/b e c/d. Uma implementação simples dá:

(defun mediant. (a b c d)
  (list (/ a b)
        (/ (+ a c) (+ b d))
        (/ c d)))

;; Example
> (mediant. 0 1 1 1)
(0 1/2 1)

Claro que dá mais jeito ter uma versão para o cálculo do mediante que usa directamente números racionais em vez da sua decomposição, ou seja,

(defun mediant (p q)
  (/ (+ (numerator p) (numerator q))
     (+ (denominator p) (denominator q))))

;; Example
> (mediant 1/2 3/5)
4/7

A ideia agora é ir introduzindo os mediantes entre cada dois números de uma lista de números racionais:

(defun mediant-list (pq-list)
  (cond ((not (cdr pq-list))
         pq-list)
        (pq-list
         (append (list (car pq-list)
                       (mediant (car pq-list) (cadr pq-list)))
                 (mediant-list (cdr pq-list))))))

;; Example
> (mediant-list '(0/1 1/1))
(0 1/2 1)

> (mediant-list '(0/1 1/2 1/1))
(0 1/3 1/2 2/3 1)

fazendo a composição sucessiva partindo de uma lista inicial com dois números (0 1)

> (mediant-list
   (mediant-list
    (mediant-list
     (mediant-list
      (mediant-list '(0 1))))))

(0 1/6 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 5/13 2/5 5/12 3/7 4/9 1/2 5/9 4/7
 7/12 3/5 8/13 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 5/6 1)

Para isso precisamos de uma função que trate da composição sucessiva (em geral, para se poder aproveitar para outras coisas no futuro)

(defun nest (function arg n)
  (cond ((= n 0)
         arg)
        (t 
         (nest function (funcall function arg) (- n 1)))))

;; Example
> (nest 'cos .5 10)
0.73500633

> ((lambda (x) (+ 1 x)) 1)
2

> (nest (lambda (x) (+ 1 x)) 2 10)
12

> (nest #'mediant-list '(0/1 1/1) 7)
(0 1/8 1/7 2/13 1/6 3/17 2/11 3/16 1/5 4/19 3/14 5/23 2/9 5/22 3/13 4/17 1/4
 5/19 4/15 7/26 3/11 8/29 5/18 7/25 2/7 7/24 5/17 8/27 3/10 7/23 4/13 5/16 1/3
 6/17 5/14 9/25 4/11 11/30 7/19 10/27 3/8 11/29 8/21 13/34 5/13 12/31 7/18 9/23
 2/5 9/22 7/17 12/29 5/12 13/31 8/19 11/26 3/7 10/23 7/16 11/25 4/9 9/20 5/11
 6/13 1/2 7/13 6/11 11/20 5/9 14/25 9/16 13/23 4/7 15/26 11/19 18/31 7/12 17/29
 10/17 13/22 3/5 14/23 11/18 19/31 8/13 21/34 13/21 18/29 5/8 17/27 12/19 19/30
 7/11 16/25 9/14 11/17 2/3 11/16 9/13 16/23 7/10 19/27 12/17 17/24 5/7 18/25
 13/18 21/29 8/11 19/26 11/15 14/19 3/4 13/17 10/13 17/22 7/9 18/23 11/14 15/19
 4/5 13/16 9/11 14/17 5/6 11/13 6/7 7/8 1)

Agora é fácil escrever a versão final ;)

(defun stern-brocot (pq-list n)
  (nest #'mediant-list pq-list n))

;;
> (stern-brocot '(0 1) 6)
(0 1/7 1/6 2/11 1/5 3/14 2/9 3/13 1/4 4/15 3/11 5/18 2/7 5/17 3/10 4/13 1/3
 5/14 4/11 7/19 3/8 8/21 5/13 7/18 2/5 7/17 5/12 8/19 3/7 7/16 4/9 5/11 1/2
 6/11 5/9 9/16 4/7 11/19 7/12 10/17 3/5 11/18 8/13 13/21 5/8 12/19 7/11 9/14
 2/3 9/13 7/10 12/17 5/7 13/18 8/11 11/15 3/4 10/13 7/9 11/14 4/5 9/11 5/6 6/7
 1)

Se quisermos converter os números acima nas suas expansões decimais basta fazer

> (mapcar (lambda (x) (float x)) (stern-brocot '(0 1) 6))
(0.0 0.14285715 0.16666667 0.18181819 0.2 0.21428572 0.22222222 0.23076923 0.25
 0.26666668 0.27272728 0.2777778 0.2857143 0.29411766 0.3 0.30769232 0.33333334
 0.35714287 0.36363637 0.36842105 0.375 0.3809524 0.3846154 0.3888889 0.4
 0.4117647 0.41666666 0.42105263 0.42857143 0.4375 0.44444445 0.45454547 0.5
 0.54545456 0.5555556 0.5625 0.5714286 0.57894737 0.5833333 0.5882353 0.6
 0.6111111 0.61538464 0.61904764 0.625 0.6315789 0.6363636 0.64285713 0.6666667
 0.6923077 0.7 0.7058824 0.71428573 0.7222222 0.72727275 0.73333335 0.75
 0.7692308 0.7777778 0.78571427 0.8 0.8181818 0.8333333 0.85714287 1.0)

Para futura utilização preciso de mais dígitos. Em vez de

> *read-default-float-format*
single-float
ponho
(setf *read-default-float-format* single-float)
Em vez de
> (/ 1 3.0)
0.33333334
obtém-se
> (/ 1 3.0)
0.3333333333333333

Happy hacking!

P.S.

(defun stern-brocot-f (pq-list n)
  (mapcar (lambda (x) (float x)) (stern-brocot pq-list n)))

(defun frac-to-list (p)
  (cddr (map 'list #'digit-char-p (prin1-to-string p))))

Etiquetas/Tags: LISP, Stern-Brocot

Grey Walter's Tortoises - ELSIE

Some notes

2015/12/19-10:30:37

Grey Walter's Tortoises

"Why did you call him tortoise if he wasn't one?" Alice asked. "We called him tortoise because he taught us" said the Mock Turtle angrily: "really you are very dull!" (Alice's Adventures in Wonderland, Lewis Carroll)

And a 1957-60 – Transistorized Tortoise ;)

Etiquetas/Tags: tortoise, robot, DIY, ai, neuron, electronics

Some notes on a V-Bot

... math and physics

2015/12/16-11:03:36

A V-Bot is a simple drawing machine based on two-center bipolar coordinates. Here's some web references:

The layout of a V-Bot is quite simple, two motors at the upper vertices at a distance d, with two strings attached with lengths l1 and l2. The drawing pen rests at (x,y).

Problems to solve

The typical math problems associated with robots are two: direct and inverse kinematics. In this particular case the inverse kinematics is easy to obtain, given the pen position obtain the lengths of the strings:

latex2png equation

I'm using GNU/Octave, so here's some auxiliary functions:

function retval=l1c(x,y,d)
  retval= sqrt(y.^2+(x+d/2).^2);
end
function retval=l2c(x,y,d)
  retval= sqrt(y.^2+(x-d/2).^2);
end

These equations define a map from the cartesian coordinates (x,y) to (l1,l2).

For the direct kinematics one has, with some simple algebra, latex2png equation

Drawing resolution

One can tackle the problem of finding the resolution in two ways. Using the Jacobian and the arc length of a curve.

The Jacobian

The Jacobian latex2png equation defines the ratio of a unit area in both coordinates. That is, it controls what happens (direct kinematics) when a unit area in (l1,l2) coordinates is transformed in to (x,y) coordinates, it expands, contracts or stays the same. Values for J greater than one gives an area expansion, lower than one the area is reduced. The Jacobian controls the resolution of the drawing region.

What happens when the Jacobian is zero? In simple terms it simply means that the transformation breaks, i.e. one can not use the transformation between (x,y) and (l1,l2) to control the robot, and so at the points or at the lines where Jacobian is zero the robot can not be controlled (you can guess by simple inspection, with no math, what these lines/points are ;) ).

The Jacobian latex2png equation is given by latex2png equation

The next image shows the value of this Jacobian as a function of (x,y)

The code for the Jacobian J(x,y,l1,l2) is given by

function retval=jac(x,y,d)
  retval=l1c(x,y,d).*l2c(x,y,d)./(d*y);
end

For the inverse kinematics the Jacobian is the reciprocal of J(x,y,l1,l2), that is 1/J(x,y,l1,l2). In this case one gets

As expected (see pics) the problematic lines are l1+l2=d or simply the line y=0 for any x.

The previous plots shows the "good" areas for drawing, somewhere below the y=0 line (10cm?). Will see the same result when considering the tension on the strings (see below).

The arc length of a curve

The the arc length of a curve can be used to determine the "good" plotting region for the robot. This is done by taking the first order Taylor expansion of the direct and inverse kinematics equations. This however requires some prior considerations.

Because the relation between (x,y) and (l1,l2) is non-linear any variation (x,y) will produce a non-linear variation in (l1,l2) this variation is path dependent, the propagation of the variations depends if, for example, the pen goes right and then up or by the hypotenuse to the same point on the drawing board.

latex2png equation and latex2png equation

Here goes:

function retval=lenghtl(x,y,dx,dy,d)
  dl1=(y.*dy+(x+d/2).*dx)./l1c(x,y,d);
  dl2=(y.*dy+(x-d/2).*dx)./l2c(x,y,d);
  retval=sqrt((dl1.^2+dl2.^2)/(dx.^2+dy.^2));
end
function retval=lenghtxy(x,y,dl1,dl2,d)
  dx=l1c(x,y,d)./d.*dl1 - l2c(x,y,d)./d.*dl2;
  dy=l1c(x,y,d).*(1-2*x/d)./(2*y).*dl1 + l2c(x,y,d).*(1+2*x/d)./(2*y).*dl2;
  retval=sqrt((dx.^2+dy.^2)/(dl1.^2+dl2.^2));
end

The next plot shows the ratio of unit lengths in the direct kinematics plotted in the (x,y) plane by taking the average on the 4 movements of the pen (right,0), (left,0), (0,up) and (0,down)1.

The next plot takes the average length on 4 movements of the pen (left,up), (right,up), (left,down) and (right,down)2.

This last plot is similar to the final plot obtained by Bill Rasmussen. My point is that in this way we only account for the variation of the length of a straight segment in this coordinate transformation. Obviously the length changes after the transformation due to the non-linearity of the transformation and reflects the loss of resolution but the right way to determine the resolution is using the Jacobian.

The ends of the control lines in the above picture seem to be further away from the plotting surface than V plotters commonly seen on the internet.

That's just because the important tool to measure resolution is the Jacobian, even thought many of the V-Bot builders do not know about it ;)

What about the tension on the strings?

One should also take into account the tension on each string. With some trigonometry one gets

latex2png equation

There's only one singular configuration that one should take note, the case latex2png equation which yields latex2png equation

function retval=tension(x,y,d)
  m=1;
  g=1;
  l1=sqrt(y.^2+(d/2-x).^2);
  l2=sqrt(y.^2+(d/2+x).^2);       
  cosa1=(d/2+x)./l1;
  cosa2=(d/2-x)./l2;
  sina1=y./l1;
  sina2=y./l2;
  
  T1=m*g*cosa2./(cosa1.*sina2+cosa2.*sina1);
  T2=m*g*cosa1./(cosa1.*sina2+cosa2.*sina1);
  retval=sqrt(T1.^2+T2.^2);
end

This is shown in the following plot:

Also the cases of null tension on one of the strings latex2png equation, latex2png equation or latex2png equation, latex2png equation yields, respectivly, latex2png equation and latex2png equation or latex2png equation and latex2png equation.

1. Vertical displacements: (right,0), (left,0), (0,up) and (0,down)

2. Oblique displacements: (left,up), (right,up), (left,down) and (right,down)

Etiquetas/Tags: v-bot, dc motor, math, physics, polargraph

Resistência de uma lâmpada

para amplificador de áudio.

2015/12/09-22:08:16

O meu pequeno amplificador classe A com uma lâmpada de carro ficou assim (aliás já o tinha mostrado em entradas a anteriores).

Em vez de uma resistência de potência usa uma lâmpada de carro para o mesmo efeito, i.e. como carga para o único dispositivo activo do amplificador: um mosfet.

É muito fácil medir a resistência de uma lâmpada em função da tensão aplicada aos seus terminais:

A curva vermelha corresponde a uma lâmpada de 12V âmbar de 21W (lâmpada de pisca), a curva a preto a uma lâmpada de 12V de 21W branca (lâmpada de stop), a curva a azul corresponde a um lâmpada de 24V de 25W oferecida por um aluno ;) e a finalmente a curva verde de 12V/10W.

A primeira coisa que se vê nestas curvas é que uma lâmpada não se comporta como um elemento puramente resistivo. Não são proporcionais a corrente que a atravessa e a tensão aplicada. Não é válida a lei de Ohm V=R.I . A resistência neste caso depende da temperatura do filamento, quanto mais quente maior a resistência aos seus terminais.

Como estou a usar uma lâmpada de 21W de 12V e defini o ponto de funcionamento do mosfet de modo a que se tenha 12V aos terminais da lâmpada, obtém-se uma estimativa para a resistência dada por R=P^2/V=12^2/21~6.9 . Este valor não está muito longe do que se mede para R (ver figura anterior).

A potência dissipada no mosfet é assim dada por P=V.I= (18-12)*1.7~10W1 o que nos dias de frio é muito útil.

1. Estou a usar uma fonte de tensão de 18V para alimentar o amplificador.

Etiquetas/Tags: áudiom zen amp, car, light bulb

Palavras chave/keywords: página pessoal, blog

Criado/Created: NaN

Última actualização/Last updated: 27-01-2016 [19:45]


GNU/Emacs

1999-2016 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.