Uma história alternativa e Microsoft-cêntrica do software livre

Embora muitas e muitas vezes tenha-se dito que "o software livre não é um movimento anti-Microsoft". Mas de certa forma é sim. E não necessariamente isto ilegitimiza o movimento. O software livre ganhou embalo na esteira das pisadas de bola da MS.

Em primeiro lugar, é curioso observar que em 1993, a MS tinha dois produtos bons que eram seus carros-chefes: Windows e Office. Hoje, em 2008, as vacas leiteiras da MS continuam sendo... Windows e Office. Tudo que aconteceu entre 1993 e 2008 não resultou em praticamente nada de terreno novo para a MS. Teria sido melhor poupar o dinheiro ou distribuir entre os acionistas. Aliás, é uma tremenda demonstração de como despejar dinheiro em cima de projetos, instituições ou regiões como os governos por aí gostam de fazer, não adianta nada; é preciso também um "estado de espírito" para transformar investimento em coisas novsa.

A MS fez tudo certo até 1995, quando lançou o Windows 95, um tremendo sucesso e um excelente produto para os padrões da época. Antes disso ela já tinha o Office, e dentro do Office um excelente produto chamado Access. Todo mundo queria desenvolver para Windows, muita gente sujeitou-se ao Win16 até a chegada do Windows 95.

Aí, alguma coisa aconteceu e a MS começou a querer dominar tudo e todos. Não bastava mais dominar os sistemas operacionais; ela queria dominar todos os nichos em volta disso. O início deste processo foi vergonhoso, quando a MS desdenhou a Internet em favor do Microsoft Network. Foi uma coisa tão amadora que ninguém botou fé.

A próxima vítima foi a Netscape, com o lançamento do Internet Explorer 3 integrado ao Windows. Neste caso a MS foi competente, pois lançou um browser melhor que o Netscape e incluído no Windows (quem hoje em dia imagina um SO sem browser incluído no pacote?). Apesar dos protestos, é discutível se a MS jogou sujo neste episódio. As maiores sujeiras vieram depois, com as tentativas de incompatibilizar-se com os padrões (HTML, Javascript) no intuito de forçar os Web designers a suportar apenas o IE. (Este esforço foi todo perdido quando a MS cometeu o mesmo erro que a Netscape -- deixou o IE 5.5 ou 6 sem atualizações por muito tempo, cimentando sua fama de bugado e inseguro).

Então veio a "guerra das linguagens" onde a MS jogou totalmente sujo. Primeiro, adquiriu o FoxPro com a clara intenção de descontinuá-lo (mas acabou não descontinuando tão cedo, talvez por medo das ações antitruste). Depois, começou uma guerra covarde contra a Borland e em particular contra o Delphi, que estava fazendo muito sucesso por volta de 96-97. Numa das propagandas sobre como o Visual Basic era melhor que o Delphi, a MS chegava a citar como desvantagem do Delphi o fato da Borland estar financeiramente mal das pernas. O ápice foi contratar o arquiteto-chefe do Delphi, que depois arquitetou o C#.

Uma coisa que já me intrigava na época: tanto o Delphi quanto o FoxPro rodavam exclusivamente em Windows. Qual o interesse da Microsoft em matar estes produtos? Já estava claro na época que vender Windows dava muito, muito mais dinheiro que vender Visual Basic.

Com estas ações que hoje sabemos que foram completamente idiotas, a Microsoft alienou seu principal ativo: os desenvolvedores da plataforma Windows. Na época, estava na moda a visão tecnocrática que o número de máquinas rodando Windows e o dinheiro na conta da Microsoft asseguravam sua hegemonia. Eram os frenéticos anos 90.

Hoje sabemos que a banda toca diferente. Uma plataforma é tão boa quanto os programas que existem para ela. E para haver programas, tem de haver desenvolvedores. Há 200 milhões de celulares Symbian e quase nenhum aplicativo para eles, porque o Symbian sempre maltratou os desenvolvedores.

Em paralelo a isso, os UNIXes comerciais caíram de qualidade, subiram de preço e amarraram-se ao hardware dos respectivos fabricantes, afundando junto com eles. Mas nem os UNIXes baseados em Intel escaparam do processo de apodrecimento, deixando seus desenvolvedores órfãos e aparentemente abrindo o caminho para o Windows NT, deixando todos entre a cruz e a espada.

Na esteira disso, cresceu o GNU/Linux, com uma plataforma relativamente amigável, gratuita, feita por desenvolvedores para desenvolvedores.

Na verdade, o problema das plataformas "pagas" e "fechadas" nunca foi o preço ou o fato de serem proprietárias. Elas afugentaram os desenvolvedores porque eram a) ruins; b) maltratavam o desenvolvedor. A ressurgência do Macintosh, que não é barato, não é livre e ainda por cima demanda hardware específico para rodar, prova anedoticamente este ponto.

First Cocoa App: CoCalc, beta 1

If anyone is interested, here goes the binary application package and the source code as a XCode project package. I couldn't care less about minority communities: binary application is Leopard && Intel only :)

IPv6 e 6to4

Das diversas técnicas de túnel para proporcionar conectividade IPv6 a quem não tem IPv6 nativo (ou seja, 99,9% da Internet), essa 6to4 parece realmente prometer.

A idéia é a seguinte: o IP do "servidor" do túnel é sempre 192.88.99.1. Embora este seja um IP privado, na verdade nada impede que IPs privados trafeguem na Internet pública. O problema é que cada provedor de Internet vai rotear IPs privados de um jeito diferente. No caso do 6to4, este problema vira solução: cada provedor roteia 192.88.99.1 para o servidor 6to4 mais próximo do seu usuário.

A faixa IPv6 atribuída ao usuário 6to4 é função do IPv4 público que ele possui. Assim, basta ter um IP público, aquele atribuído a qualquer conexão DSL ou 3G, para conseguir obter uma faixa IPv6 completa e distribuir IPv6 públicos por toda a rede. Quem tem IP fixo, terá uma faixa IPv6 também fixa. Quem ganha IP dinâmico (a maioria), também vai ganhar uma faixa IPv6 diferente a cada conexão. (Quem faz questão de uma faiva IPv6 fixa possuindo IP dinâmico, tem de adotar outro tipo de túnel IPv6).

Naturalmente, o provedor tem de colaborar ao menos com as rotas até o 192.88.99.1 mais próximo para o 6to4 funcionar, e aí mora uma dificuldade. Em se tratando de telecoms brasileiras, sabe Deus quando teremos 6to4. Mas qual não foi minha surpresa quando...

/Users/epx $ ping 192.88.99.1
PING 192.88.99.1 (192.88.99.1): 56 data bytes
64 bytes from 192.88.99.1: icmp_seq=0 ttl=58 time=33.276 ms
64 bytes from 192.88.99.1: icmp_seq=1 ttl=58 time=33.539 ms
64 bytes from 192.88.99.1: icmp_seq=2 ttl=58 time=34.782 ms

A Brasil Telecom roteava 6to4, e ainda por cima com latência boa... Vamos ver por onde o pacote anda:

/Users/epx $ traceroute 192.88.99.1
traceroute to 192.88.99.1 (192.88.99.1), 64 hops max, 40 byte packets
 1  router (192.168.141.1)  4.540 ms  2.167 ms  3.521 ms
 2  BrT-L10-jvece702.dsl.brasiltelecom.net.br (201.34.149.254)  11.349 ms  11.094 ms  11.657 ms
 3  BrT-10G0-0-0-spopn-border.brasiltelecom.net.br (201.10.241.22)  36.212 ms  34.865 ms  53.585 ms
 4  as22548.sp.ptt.br (200.219.130.1)  36.975 ms  36.531 ms  38.975 ms
 5  192.88.99.1 (192.88.99.1)  31.053 ms  40.719 ms  30.021 ms

Parece que é a ptt.br quem fornece o túnel 6to4, não a própria Brasil Telecom. Esta é outra vantagem do 6to4: o provedor pode delegar a tarefa para um terceiro no início, e depois ir "aproximando" mais o servidor 6to4 do usuário final conforme o interesse em IPv6 for aumentando.

Outra característica do 6to4 é que ele foi pensado para rodar no roteador NAT, não no computador atrás do NAT. A partir do roteador, o IPv6 é distribuído da maneira usual, via DHCP. Por um lado isto é um problema, pois o roteador NAT tem de possuir esta funcionalidade. Por outro lado, todo roteador NAT possui processamento suficiente para tomar conta do 6to4, basta que o fabricante libere uma atualizacão.

Tanto o Mac OS X quanto o roteador AirPort parecem vir com IPv6 e 6to4 habilitados, o que teria sido responsável por um aumento "considerável" no tráfego IPv6 mundial. Entre aspas porque o tráfego IPv6 ainda é apenas 0,6% da Internet. Considerável porque era metade disso há pouco tempo atrás.

Não é fácil usar o 6to4 a partir de um computador atrás do NAT, porque o 6to4 usa o protocol IP 41 (não é nem TCP nem UDP), e dificilmente um roteador NAT repassa este tipo de pacote. Existe uma outra especificação de túnel IPv6, a Teredo, que foi concebida para funcionar sem a colaboração do roteador NAT, mas é consideravelmente menos elegante que 6to4.

Ontem eu flechei meu roteador com o DD-WRT. A boa notícia é que ele tem suporte a 6to4 mediante pouca configuração. A má notícia é que a v24 que estou usando está com problemas no IPv6 :( O jeito é esperar por uma atualização, ou talvez usar a v23.

EPx summit: status report

Cocoa: the calculator already does everything that Javascript version does. It is just a matter of handling some corner cases (division by zero etc.) which are currently defaulting to floating-point behavior (e.g. showing plus infinity when divide by zero). NS* classes demand the programmer to type a lot, but it is easy to get used to. Once it is done, I plan to release the package as a free software sample, and turn to a Qt version.

OpenGL: got two cubes, the front one translucid, rotate on screen :) Very basic stuff, but enough to grasp the "OpenGL way of life". Actually, I have concluded that OpenGL is pretty low-level stuff, probably in order to be directly rendered by hardware, so write some software in OpenGL would be a two-layer process: write a high-level renderer/framework and then the application. Currently I am not in the mood to write frameworks, so I am thinking about giving up OpenGL and put the Erlang language in its place (and/or the Quartz Composer utility). Let's see.

Ruby on Rails: the guinea pig project was replaced by a stocks market income tax calculator, which is something that I need, is small and not boring. Most of the stumbles I had were related to Rails conventions that I didn't know. For example, putting <% command %> instead of <%= command >> makes the "command" output not to be rendered into the final HTML. Besides that, I liked the framework; the high point is the almost full Javascript auto-generation from simple commands.

About Ruby, what I liked most was the pervasive use of closures (code blocks). What I hated most are: code block/methods are not first-class objects; and the pervasive usage of "symbols", which seem to be an ugly optimization -- which does not work since Python uses strings for everything and is faster anyway.

O tal do "closure"

Com a recente ressurgência das linguagens interpretadas, o tal do "closure" está sendo mencionado o tempo todo, em particular no contexto do Ruby. Mas afinal, que bicho é esse? É um conceito difícil de pegar para quem vem de um background C/C++, e também foi difícil para mim muito embora existiam closures no Clipper 5, e eu cheguei a mexer em código com um closure. Mas vamos lá.

Um closure simples em Python poderia ser criado e usado das formas abaixo:

>>> a = lambda a: a*2
>>> a(3)
6

>>> def dobro(x):
...    return x*2
... 
>>> a = dobro
>>> a(3)
6

Na primeira forma, usamos o operador "lambda" e criamos o que muita gente chama de função anônima, ou sem nome, que fica contida em uma variável. Na segunda forma, atribuímos uma função convencional a uma variável, com o mesmo resultado.

Estas mesmas coisas poderiam ser feitas facilmente em Javascript, pois também nele as funções e métodos são "objetos de primeira classe" e podem ser atribuídos e passados como se fossem dados.

Na verdade, também poderíamos fazer as mesmas coisas em C/C++ usando ponteiros para funções. Isto leva muita gente a concluir que um closure é simplesmente uma função anônima ou um ponteiro para função ou método, mas closures são capazes de um truque adicional.

Considere o seguinte código Ruby e Clipper 5:

# Ruby
?> def multiplica x
>>    lambda {|y| x*y}
>> end
=> nil
>> x2 = multiplica 2
=> #<Proc:0x005bf0f4@(irb):78>
>> x10 = multiplica 10
=> #<Proc:0x005bf0f4@(irb):78>
>> x2(3)
NoMethodError: undefined method `x2' for main:Object
        from (irb):81
>> x2.call(3)
=> 6
>> x10.call(3)
=> 30


# Clipper 5
function multiplica(x)
return {|y| return x*y}

x2 = multiplica(2)
x10 = multiplica(10)
? eval(x2, 3)
6
? eval(x10, 3)
30

Tanto no código Ruby como no Clipper5, a função "multiplica" não retorna mais um resultado numérico, mas sim uma outra função, que pode ser reutilizada tantas vezes quanto necessário. Agora, o mais importante: cada função retornada CONGELA o parâmetro "x" originalmente recebido. Portanto, "x2" sempre vai multiplicar números por 2, pois 2 foi o valor recebido por "x" por ocasião da criação do closure x2. Podemos criar tantos closures quanto quisermos, e cada um terá a sua versão congelada de "x", sem interferência mútua.

Explicando de outra forma, o closure "tira uma fotografia" do estado das variáveis locais no momento de sua criação, e baseia-se nesta "fotografia" quando, mais tarde, sua execução for requisitada.

Esta característica única dos closures distingue-os dos simples ponteiros a funções do C/C++. Os closures têm um quê de templates do C++, embora sejam infinitamente mais poderosos por serem criados em tempo de execução.

É notório também que tanto no Ruby quanto no Clipper 5 a avaliação do closure/code block demanda um método especial (call e eval, respectivamente). Tentar chamar o closure diretamente dá erro.

Isto acontece pois funções não são objetos de primeira classe nestas linguagens, e têm de ser encapsuladas para poderem ser manipuladas. No caso do Ruby, code blocks precedidos de "lambda" são convertidos para um objeto tipo Proc, que responde ao método call.

Embora Python não deixe isto muito óbvio, também é possível usar closures usando funções internas. Em Python, funções são objetos de primeira classe e closures podem ser chamados como qualquer função. Vide exemplo:

>>> def multiplica(x):
...    def closure(y):
...        return x*y
...    return closure
... 
>>> x2 = multiplica(2)
>>> x10 = multiplica(10)
>>> x2(3)
6
>>> x10(3)
30

A primeira vista, a função closure no código acima parece simplesmente uma função de uso privativo de multiplica, mas é potencialmente um closure que poderá carregar o valor de "x' com ele.

O closure, enquanto ferramenta embutida na linguagem, só é possível se a linguagem é interpretada e possui coletor de lixo, pois o closure retêm a "fotografia" das variáveis locais para além do seu escopo original, e só pode descartar a fotografia quando o closure for ele mesmo descartado. Além disso, precisa referir-se às variáveis pelo nome e não como endereços fixos de memória, já que as variáveis originais já não existirão.

Seria possível emular um closure simples em C++ usando functors (objetos que respondem ao operador (), ou seja, podem ser chamados como funções), como no exemplo a seguir:

#include <stdio.h>

class Multiplica {
public:
        int xx;
        Multiplica(int x) { xx = x; }
        int operator() (int y) { return xx*y; }

};

int main()
{
        Multiplica x2 = Multiplica(2);
        Multiplica x10 = Multiplica(10);
        printf("%d %d\n", x2(3), x10(3));
}

/Users/epx $ gcc -o closure closure.cpp -lstdc++
/Users/epx $ ./closure 
6 30

Um grande problema aqui é a falta de naturalidade: o desenvolvedor do functor Multiplica precisa tomar conta do armazenamento de todas as "variáveis locais" de que ele vá precisar posteriormente.

Os closures têm diversas utilidades. Em geral, quem vem de um background C/C++ tende a ver os closures como ponteiros para funções, e usa closures exclusivamente desta forma. É o meu caso. Ainda assim é um uso extremamente importante -- por exemplo, absolutamente toda implementação de sort() aceita uma função ou closure como parâmetro, que será responsável pela comparação entre elementos.

Outro uso é o o encapsulamento de tarefas (código + parâmetros de execução) para posterior execução. Quem ordena a execução do closure não precisa saber absolutamente nada sobre ela. Nada impede que a tarefa receba ainda parâmetros adicionais no momento da execução. Imagino também que os "decorators" do Python sejam implementados através de closures.

Um uso mais esotérico, que não envolve fotografia de variáveis nem fazer papel de ponteiro de função, é a criação de novos "comandos" numa linguagem. Isto faz mais sentido onde a sintaxe do code block integra-se bem com o resto da linguagem, como no caso do Ruby:

def executar_as_vezes(&codeblock)
    if rand < 0.3
        codeblock call
    end
end

executar_as_vezes {
    ...
}

# Também podemos fazer o bloco assim:
executar_as_vezes do
     ....
end

Tal uso de closure seria difícil em Python pois uma função lambda não ficaria "natural". Em Javascript, o resultado ficaria mais natural que Python (podemos passar um bloco de código entre chaves) porém menos natural que Ruby pois o bloco tem de ser precedido por function().

Este uso de closures é mais importante em linguagens como LISP e Smalltalk -- se bem entendi, até estruturas de controle como if, while etc. são na verdade funções implementadas na própria linguagem, da mesma forma que implementamos executar_as_vezes.

Em Ruby, o idioma de passar bloco de código para método é muito usado para controlar o commit/release de recursos. Considere os seguintes casos:

File.open("bla.txt") do |f|
        # trabalha com o arquivo na variável f
end

Database.Transaction do |t|
        # trabalha com o banco de dados dentro
        # do contexto da transação t
end

Embora não esteja imediatamente óbvio (para quem não conhece Ruby), os blocos de código do...end são passados como parâmetros aos métodos File.open e Database.Transaction. Os blocos somente serão executados se os métodos File.open e Database.Transaction assim o quiserem, quando quiserem, quantas vezes quiserem.

Isto permite que os métodos gerenciem os recursos de forma transparente e automática -- no caso, encerrar a transação ou fechar o arquivo depois de executado o bloco. Talvez até mesmo tentar o bloco novamente se a transação for abortada!

First Ruby challenge

As I said in a previous post, I began an effort to learn some new technologies and languages. 5-10 minutes a day for each one (Cocoa, OpenGL and Ruby on Rails). Yesterday I had my first serious misunderstanding of Ruby. Rails controllers can output code in any format that client had requested: HTML, JSON, XML and so on. The way it lies the various output types is something like this:

respond_to do |format|
        format.html { |x| puts x }
        format.json { |x| puts x }
end

The inner part is understandable, since I knew code blocks from my Clipper 5 days. For each different format, a different code block is executed. But I simply couldn't understand the outer part. Was this do...end a loop? A disguised switch? Where "format" comes from? The "respond_to" seems to be a method, but the "parameter" would be the "do...end" code. Too strange.

And this pattern appears in several places in Rails scaffold-generated code. I couldn't let that pass without understanding how it really works.

After a lot of Googling, I finally got it at dawn. I have added some fake additional code to make it more understandable:

class Response
        def html(&code_block)
                # This response is HTML, so method does something
                code_block.call("<html>...</html>")
        end

        def json(&code_block)
                # This response is not JSON, so method does nothing
                nil
        end
end

def respond_to( &code_block )
        code_block.call( Response.new )
end

respond_to do |format|
        format.html { |x| puts x }
        format.json { |x| puts x }
end

First, the do...end block that follows "respond_to" is not a loop, is not a disguised switch. It is simply a block of code that will be executed top to down, normally.

The magic here is: the do...end block is a code block exactly like {|x| ... }, which allows it to be passed as a parameter to respond_to method. So the do...end block is not executed right away, but only if respond_to does it.

Inside respond_to method, the code block is actually called, passing a Response object as a parameter. This Response object will be passed as "format" back to the code block. But it means that both Response.html and Response.json methods will be called in sequence, and we probably want only one of the formats in output.

The second magic is that Response object passed to code block is rigged to answer only to the method that is the desired output format. So, looking at my fake Response class, you can see that "html" method does something, while "json" method is a no-op. In Rails, of course this magic is done by the internal response dispatcher.

The third magic is that Rsponse.html method again receives a code block from user code -- in the case, {|x| puts x}, and calls it to render the HTML page the way the user wants to.

It seemed unnecessarly convoluted the first time I could see the whole picture, I would like to know the actual performance of that, but I guess people just get used to that, and the final syntax for different output formats is quite handy and terse.

HP12C, Black-Scholes and math nightmares

It's been one year since I have launched the Web HP12C emulator, of course written in Javascript. Currently, it is responsible by more than 50% of hits to my site, and probably 99% of my Adsense revenue. It was a complete surprise for me, considering that I wrote the first version as a distraction to stand some long hours in airport connections. Even the Mac OS X widget version is "selling" well, something around 70 package downloads per day, in December.

Another pages that have quite good hit rates are the Black-Scholes calculator and the current implied volatilities of BOVESPA options. All of those involve some "advanced" financial mathematics, and maybe someone is interested on the challenges I've had.

First, the HP-12C financial registers, which is probably the only feature actually used by HP-12C owners, besides arithmetics of course. We have number of payments ("n"), interest ("i"), present value ("PV"), payment value ("PMT") and future value ("FV"). Every register can be calculated based on the other four by using closed formulas... except the interest. For the interest, we need to use some trail-and-error technique, like linear interpolation. Because of that, is actually easier to implement all calculations using interpolation, just tweaking the register we want to find, until Net Present Value becomes zero (which means all five registers have values that fit each other).

The basic algorithm is something like this:

set initial estimates of the target register equal to 0 and 1
do while not tired of trying:
        calculate NPV for the first estimate
        calculate NPV for the second estimate
        if absolute value of NPV less than 0.0000001:
              success, exit loop
        make new (linear) estimate based on previous estimates and NPVs 

The first time I had implemented that, it was 1997. It never caused me any problems. Until now. During some stress tests with really big numbers, comparing the emulator with a real HP-12C, the emulator began to report "Error 5" in several financial calculations, where the real HP did just well. What the hell?!

Some of you may have already figured out the problem: my constant 0.0000001 is not exactly an adequate "epsilon" to detect success of the linear interpolation. Floating-point has only 16 decimal cases of precision, so if the magnitude of fixed financial registers gets too big (e.g. 10**9) it is likely impossible for the interpolation to settle NPV below 10**-7.

Actually the problem is a bit worse, since the NPV calculation involves multiplications and exponents, which amplify the rounding errors. So, we can't e.g. demand a tolerance precision of 7 decimals when the input magnitude is 9 significant digits (7+9=16). We must be more liberal. Some tests on HP calculator showed that it always found a solution having only 10 decimal digits of precision, at the cost of small imprecision in the last digit.

The solutions I found are: to set "epsilon" proportional to input values (e.g. if the sum of absolute values of registers are 10**50, epsilon will be around 10**42), and not trying to demand 16 digit precision, but only 8, which works even if "n" (which is an exponent in NPV formula) is quite big.

The floating point phantom haunts some other pages

Another problem, similar to this one, was found in the Black-Scholes calculator as well as in the implied volatility page. When the implied volatility calculation could not find a result, it reported "Impossible to calculate" at the page. It tipically happens then an option has a market value that is too low, which would imply a negative volatility, which is impossible. Since it only happens for thinly traded options (that is, the market value is outdated and therefore invalid anyway), it used not to be a problem.

But, when the stock markets crashed in October 2008, several options ceased to show the volatilities, warning "Impossible to calculate". At first I thought it happened because of option values were behind the corresponding stock values, but a closer look revealed that it was not the case: options with quite big premiums were in the bunch of "impossibles". Great,,,

As happens with interest, the implied volatility also doesn't have a closed formula, it must be found by trail-and-error. I was employing linear interpolation, since I was already used to it due to HP emulator. But most texts talk about using Newton's method for volatility. Without thinking too much, I thought that was the problem, and reimplemented the volatility calculation using Newton's method.

And surprise, no success. That same options kept reporting "Impossible to calculate implied volatility". Then, actually thinking in math terms, Newton's method is no "better" than linear interpolation. It is just faster when things go well, and handier if you already have the derivative. In the case of Black-Scholes, if you calculate the "greeks" (and you generaly do), "vega" is the derivative you employ in Newton's method.

Making more tests, I finally found the problem. The relationship of an option's premium to its implied volatiliy forms a kind of sigmoid curve. That is, when volatility is close to zero, an increase X of volatility does little for the premium. When volatility is in a "normal" level (e.g. 35%/year) the same increase X in volatility affects the premium much more. But if volatility is too high, premium becomes again insensible to the same X increase.

What does that mean for us? It means that, if the initial volatility estimation is too low, both linear interpolation and Newton's method will generate a HUGE estimation of implied volatility, because premium is insensible in that range. And, if volatility estimation was too big, the new estimation will be a big negative number -- but negative volatilities do not exist. Actually, both corner cases tend to happen in chain: since I began with initial estimation of 0, it threw the second estimation to estratosphere, and then the third estimation would be negative. And then my routine reported "Impossible to calculate".

The funny thing is, that problems began to happen because of the market crash and options' values getting too high, approaching implied volatilities of 100%/year. When the markets were calm and volatilities were 35%, the original routine was performing well... On top of that, the original routine had the same problem as HP-12C emulators -- not calibrating epsilon proportionally to the magnitude of input values.

Rereading that chapter of "Black-Scholes and Beyond", I discovered another way of estimating volatility, the "method of bissections", something like this:

set estimation A to 0
set estimation B to 200%
do while abs(A-B) > epsilon_tolerance:
        C = average of A and B
        P = hypothetical premium of option based on volatility C
        if P less than actual option premium:
                make A equal to C
        if P bigger than actual option premium:
                make B equal to C

This algorithm has the big advantage of not being affected by the sigmoid curve; it only requires the function to be monotonically increasing, as premium as a function of volatility actually is. It seems to be that it works like arresting a wild bull: you close a fence here, another there until the bull is confined in the desired space.

But this algorithm has also two disvantages, one big and one small. The big one is not being able to resolve volatiities above the upper estimate (B). In the example above, all volatilities above >200% would just be found being egual to 200%, which is obviously bad. The small disvantage is being slower than Newton's method, and demanding the same number of loop trails to solve any volatility, even within the range of "well-behaved" ones.

The solution I adopted for my calculators is an hybrid of two approaches. I kept the Newton's method, but added some safeguards. The most important is: every new volatility estimation cannot be more than 100% apart from the old estimation. This limitation guarantees that any "wild" estimation is shaved off, while well-behaved cases still keep the typical high speed of Newton's method. Of course, that limiits the maximum volatility my algorithm can handle. By using a maximum of 100 rounds, and a maximum offset of 100%, the maximum volatility is 10000%/year, which is well beyond the range of any marked I've heard of.

Also, I calibrated the initial estimations to be sure that Newton's method would work well with volatilityes up to 100%/year, since the markets are still too volatile...

EPx summer of code

Time to have that glowing enthusiasm for new things, as children do! I have committed myself to learn a bunch of things during the next few months: Ruby on Rails, Cocoa, OpenGL, and recall Qt. (I'd also like to try Lazarus and Harbour to honor my Delphi and Clipper days, but those ones will have to wait till I win the lottery and programming becomes a just-for-fun activity).

Since the only way to truly learn a programming language is to write real, useful applications in it, I need ideas for such applications, given the technologies I am trying to get used to. My current choices are:

* For Ruby on Rails, a personal accounting/budget application. Since I've given up on booking all my personal finances in detailed double-entry ledger (it takes too much time and does not create new money after all), I would still like to have an automated way to control my finances. It is boring stuff, and no chance of being a new hit in the market, but at least will be useful for myself.

* For OpenGL, I plan to write something like a crude traffic simulator, for cars or maybe for trains. Given a coordinate description of tracks or streets, plot the map and run a simulation on it. Make a railway simulator would be a bit more difficult, but much more fun for myself, since I love trains. In the other hand, in the case of a car traffic simulator, it could be fun to add scriptable driver behavior etc.

* For Cocoa and Qt, my current plan is to write a simple financial calculator, not like HP-12C, but more like this one. Once the desktop versions are working, a lot of derivatives can be made, in order to learn Cocoa on iPhone, Qt on Maemo, Mac OS X widget in Objective C, and so on.

I am sure that there are better applications, useful for many other people people besides me, waiting to be written, but I am a bit short of ideas. Anyone with good suggestions is invited to comment.