Jumpi’s Notepad

My annotations about the life, universe and everything!!! ;)

Archive for the ‘Math’ Category

Visualizing Floats

with 2 comments

Continuing the posts about data types and your characteristics, I read a nice article about Floating point numbers published by gamasutra:

http://www.gamasutra.com/view/feature/1965/visualizing_floats

See ya!!!

Written by jumpi

January 14, 2009 at 3:50 pm

Posted in english, Math, Programming

Numeros complexos vs NaN (Not-a-Number)

with 3 comments

Lendo uma thread em uma lista de discussão que acompanho, surgiu uma duvida bem interessante sobre NaN e em uma das mensagens me deparei com a seguinte afirmação.

“Números imaginários são um exemplo, sqrt (-1) retorna NaN. Outro é dividir zero ou +/- infinito por zero.”

Vamos analisar essa frase começando pelo fim.

De acordo com a IEEE 754, se eu tenho uma variável a = 0 e divido a mesma por 0, vai dar um NaN, porem se eu tenho em a um valor positivo que tende ao infinito, o valor vai ser positivo e se o valor de a for negativo, logo essa divisão vai resultar em um valor negativo.

Ok, até aqui nenhuma objeção, tudo nos conformes. Porém, porém… agora vamos a primeira afirmação.

“Números imaginários são um exemplo, sqrt (-1) retorna NaN.”

Ooopss…. Sinto que houve um equivoco ai, pois não foi definido pelo autor da frase em qual conjunto numérico ele está trabalhando, penso que ele se limitou a qualquer conjunto no qual sqrt(-1) realmente não tem solução (Q, R, Z…), porém, existe também o conjunto dos complexos e nesse conjunto, existe solução para sqrt(-1). E vamos provar isso utilizando o nosso velho amigo C++, pois ele possui uma classe/template por padrão que trabalha com números complexos usando tipos de ponto flutuante, ou seja, utilizando o nosso amigo, podemos provar que existe sim solução para sqrt(-1) no campo dos complexos

Listarei logo abaixo um código simples que demonstra a nossa teoria em C++, ou seja, provar que existe sim resposta para sqrt(-1) e que ela é diferente de NaN

(jumpi@Painkiller:~)$ vi complex.cpp

#include
#include

using namespace std;

int main(int argc, char **argv)
{
complex res = sqrt(complex(-1));
cout << res << endl; return(0); } [/sourcecode] (jumpi@Painkiller:~)$ ./complex (0,1) (jumpi@Painkiller:~)$ Antes recapitulando, a forma geral de um numero complexo no seu plano obedece a forma a + b*i, onde a representa o numero real e b um numero imaginário, ou seja, o retorno do tipo complex em C++ retorna as coordenadas de um numero complexo no plano. No nosso caso, substituindo na fórmula, teremos a + b*i == 0 + 1*i que equivale a i. Vamos fazer o teste para confirmar?? Utilizando o google, sim... o google, pois a busca serve como uma excelente calculadora e vai nos ajudar com a prova, digite sqrt(-1), qual a resposta??? Sim... sim... sqrt(-1) equivale a i, mesmo resultado apresentado pelo nosso simples programinha em C++. Q.E.D. Logo, sqrt(-1) = i e não um NaN conforme foi dito na thread. Essa foi apenas uma demonstração de que não podemos esquecer da base matemática para formular uma resposta, principalmente no que envolve recursos que podem ser representados pela linguagem. Maiores informações podem ser encontradas nos seguintes sites: Wolfram Complex Number
Wolfram Complex Plane
C plus plus complex reference

Written by jumpi

January 6, 2009 at 3:45 am

Posted in Math, Programming

When SHA-3 collides

leave a comment »

Caramba…

Não sei se todos os leitores sabem, porém, o NIST esta fazendo um campeonato para promover um novo algoritmo de hash para incorporar o padrão SHA-3 e já temos algumas submissões de algoritmos de hash, para ser mais exato, 64 submissões ate o presente momento, sendo que algumas das submissões podem ser encontradas aqui.

Bizarro isso, em 2 papers/prototipos postados para o novo padrão SHA-3, 2 já foram quebrados… isso mesmo!! Colisões já foram encontradas… no Sgàil e no WaMM e o mais engraçado é que no caso do Sgàil, foi o próprio autor que conseguiu detectar a colisão no hash.

Seguem os links para quem estiver interessado em mais detalhes:

WaMM Collision e Sgàil Collision e as respectivas propostas do WaMM e do Sgàil.

Para quem curte, vale a pena dar uma olhada nas propostas, até mesmo nas que já foram quebradas e em seus protótipos de implementação.

Ate a próxima…

Written by jumpi

November 6, 2008 at 6:07 pm

Posted in Crypto, Math

Fibonacci Series Test (Perl and Python)

with 7 comments

Post in portuguese about my tests with Fibonacci Series using perl and python…

Esses dias, para ser mais exato, na segunda-feira, o meu colega de trabalho marcio a.k.a. tio estava falando sobre a sua escolha para criar um projeto de site que ele esta fazendo e para testar ele implementou o algorítimo de Fibonacci usando C, C++, Ruby e Python e mediu o tempo utilizando o comando time… C e C++ entraram na lista so para ele poder criar um parâmetro. E então ele decidiu escolher pelo python devido ao tempo, porem, ele esqueceu do nosso velho amigo Perl e eu disse a ele que perl executava o mesmo teste mais rápido que python e ele me desafiou, ou seja, estou fazendo esse teste para demonstrar que o nosso velho amigo perl pode ser bom, lembrando que não sou um bom programador python, mais tentei deixar o código o mais próximo possível entre ambas as linguagens para que nenhum boi-corneta (como diria o meu amigo Caloni, gostei da expressão, por isso a utilizei aqui também) venha se espantar aqui…

Bem… para a realização desse teste, utilizei o meu laptop, um macbook com perl 5.8.8 e python 2.5.1 como podem ver abaixo:

[jumpi@Painkiller]~/Sources: perl -v
This is perl, v5.8.8 built for darwin-thread-multi-2
level (with 1 registered patch, see perl -V for more detail)
Copyright 1987-2006, Larry Wall
[jumpi@Painkiller]~/Sources: python -V
Python 2.5.1

Para fazer os testes, utilizei uma versão iterativa do algorítimo de Fibonacci (afinal de contas, poderia apelar para a recursiva, porem achei melhor utilizar essa para o teste), segue abaixo o código:

Em perl:

#!/usr/bin/perl
use strict;
my $n = shift;
my ($a,$b)=(1,2);
print "$a\n$b\n";
for(1..$n-2) {
  ($a,$b) = ($b,$a+$b);
  print "$b\n"
}

Em python:

#!/usr/bin/python
import sys
def fib(n):
 a, b = 0, 1
  for i in range(n):
   print b
   a, b = b, a+b
n = int(sys.argv[1])
fib(n)

E executei ambos os códigos, fazendo 10000 iterações e medindo o tempo usando o comando time, onde obtive o seguinte resultado:

Em perl:

real	0m0.188s
user	0m0.054s
sys	0m0.047s

Em python:

real	0m10.778s
user	0m8.104s
sys	0m0.231s

Well… ai esta a prova, pelo que posso ver o nosso velho amigo rabugento perl terminou a sua tarefa em um tempo menor que o python, pelo que posso enxergar, 10x mais rápido???

Brincadeiras a parte, através desse teste simples, podemos perceber que o perl, mesmo estando ultrapassado na visão de muitos, ainda executa muito bem o serviço, logico que poderíamos utilizar n técnicas em ambas as linguagens. Porem, como eu disse no principio, tentei simplificar ao máximo para não criar vantagens para nenhum dos lados.

Quero nesse post agradecer ao tio, pois sem ele, não teria o porque executar esses testes e ao amigo Caloni de onde tirei expressões para compor esse post…

Tio, vamos fazer o projeto utilizando perl + catalyst??? Hein??? Hein??? To Brincando!!! ;D

Written by jumpi

January 9, 2008 at 4:07 am

Posted in Math, Pessoal, Programming

Tagged with , ,

The Excel 2007 Bug

with 4 comments

About the bug that affected Excel 2007, I think that is very hard to work with floating point calculations and approximation is very complex and find a problem in logic of this is a true nightmare!!!!

The summary of problem: Excel 2007 store six floating point numbers using binary representation between 65534.99999999995 and 65535, and dont store six between 65535.99999999995 and 65536 and this numbers are the cause of this problem.

I work with arbitrary precision in my scientific intiation and using libraries for care of this part for me, because of difficulties that involve the manipulation of calculate numbers that need arbitrary precision. IMHO, working with type of development demands very attention and very pacience.

The two links have a good explanation of this problem… Its a good lecture!!!

The Excel Bug Explanation by Good Math, Bad Math Blog
The Excel Bug Explanation for Mathematica Developers Blog

See ya people and have a good fun!!!

In play: Emerson, Lake and Palmer – Works (Black) Vol. 1 – 07: The Enemy God

Written by jumpi

October 3, 2007 at 8:54 pm

Posted in english, Math, Programming

Tagged with , ,

“f(problemas(ciência da computação(matemática)))”

leave a comment »

Enfim… vai entender o que se passa na cabeça de um cara que me escreve um livro que para ser Cientista da Computação, você nao precisa saber de matematica??? Juro que eu queria entende-lo… porem, em minha humilde opiniao, isso se torna incompreensivel… Classificaria isto como uma blasfemia… Penso eu que a Ciencia da Computação esta amarrada a matematica assim como a fisica, ou talvez ate mais, devido ao fato de Ciencia da Computação na minha opiniao, ser uma ramificação da matematica, pois ela engloba grande parte dos conceitos matematicos, como a logica matematica (utilizada na logica booleana), teoria dos numeros (utilizada no campo da criptografia e na inteligencia artificial), teoria dos grafos (utilizada em estruturas de dados e nos algoritimos de busca), enfim, tudo na ciencia da computação engloba matematica, ou seja, por tras dos trabalhos computacionais existem modelos e metodos matematicos. Bem, sempre tive em mente que na verdade ser um cientista da computação é ser um matematico tambem, pois o mesmo utiliza-se de matematica para dar enfase aos seus trabalhos, o que na minha visao sempre entendi como matematica aplicada. E devido a essa visão, foi que escolhi ser Bacharel em Matematica, pois sempre pensei que a matematica me ajudaria a abrir os olhos para a area da Ciencia Computacional, e não me arrependo, pois tem sido bem util para o meu entendimento do funcionamento das coisas, afinal de contas eu consigo entender como funciona um SGBD gracas a teoria dos conjuntos ou um processo de raytracing gracas aos vetores. e não acaba por aqui… eu poderia dar n-exemplos aqui sobre a aplicacao da matematica na ciencia da computação… mas enfim… para quem estiver curioso em ler sobre a materia na qual gerou esse post e que me trouxe tanta revolta… segue o link…

http://www.itwire.com.au/content/view/13339/53/

Abraços e ate a proxima!!!!

No play: Symphony X – Paradise Lost – 09: The Sacrifice

Written by jumpi

July 20, 2007 at 3:02 am

Posted in Math

Love and Tensor Algebra

leave a comment »

Come, let us hasten to a higher plane
Where dyads tread the fairy fields of Venn,
Their indices bedecked from one to n
Commingled in an endless Markov chain!
Come, every frustrum longs to be a cone
And every vector dreams of matrices.
Hark to the gentle gradient of the breeze:
It whispers of a more ergodic zone.
In Riemann, Hilbert or in Banach space
Let superscripts and subscripts go their ways.
Our asymptotes no longer out of phase,
We shall encounter, counting, face to face.
I’ll grant thee random access to my heart,
Thou’lt tell me all the constants of thy love;
And so we two shall all love’s lemmas prove,
And in our bound partition never part.
For what did Cauchy know, or Christoffel,
Or Fourier, or any Bools or Euler,
Wielding their compasses, their pens and rulers,
Of thy supernal sinusoidal spell?
Cancel me not – for what then shall remain?
Abscissas some mantissas, modules, modes,
A root or two, a torus and a node:
The inverse of my verse, a null domain.
Ellipse of bliss, converge, O lips divine!
the product o four scalars is defines!
Cyberiad draws nigh, and the skew mind
Cuts capers like a happy haversine.
I see the eigenvalue in thine eye,
I hear the tender tensor in thy sigh.
Bernoulli would have been content to die,
Had he but known such a^2 cos 2 phi!

Written by jumpi

March 4, 2007 at 2:47 am

Posted in english, Math