Números primos e algoritmos – Parte II

Nesta segunda parte vamos mostrar testes que rapidamente dizem se um numero é provavelmente primo, provavelmente porque como veremos abaixo eles checam rapidamente se não é primo, mas quando dizem que é primo … Aí tem alta probabilidade de ser primo e se você quiser ter certeza precisa usar um algoritmo mais lento.

Este que vou mostrar se baseia no Pequeno Teorema de Fermat. Este teorema é bem simples de enunciar:

Se um número p é primo então para todos os números a entre 1 e p-1 a equação abaixo tem que ser respeitada (em notação C++):

pow (a,p-1) % p = 1

Assim fazemos o teste para alguns números a entre 1 e p-1 e caso a equação seja verdadeira para eles podemos dizer que é provavelmente primo. Se falhar para algum número não é primo com certeza.

#define NUMTESTES 10 // vamos testar 10 vezes, pode ser um número maior ...
 
int isPrimo (int n) {
   if (n==1)
       return 0; // dica de um leitor da semana passada
   if (n<4)
       return 1;
   for (int i=0; i<NUMTESTES; i++) {
       if (i+1 > n-1)
            break;
       // aqui estou supondo que há uma biblioteca 
       // de precisão arbitrária como a mathX
       // ou usando uma técnica de obter modulo 
       // em exponenciação como a 
       // Fast Modular Exponentiation
       if (pow(i+1,n-1)%p != 1)  
            return 0;
   }
   return 1;
}

Caso o resultado seja 0 você pode estar certo de que não é primo, se for 1, você pode ter uma enorme probabilidade de ser primo.

Para algumas aplicações é preciso ter certeza que o número é primo e como existem os números de Carmichael que se comportam como primos nestes testes probabilísticos vamos ver na próxima parte como testar rapidamente e com certeza (já adianto que é bem complicado do ponto de vista matemático…)

Pierre Fermat ajuda você a encontrar números primos

Como sempre, se houver erros favor apontar nos comentários.

Mudando a realidade com computação gráfica

Desde o primeiro ano da faculdade quando consegui o livro: “An Introduction to Ray Tracing” o SIGGRAPH foi para mim um objeto de admiração. Infelizmente nunca tive nada publicado lá (tenho um amigo, Diego Nehab que já publicou vários lá, vale??) mas sempre acompanhei. Quando ainda navegavamos pela Internet usando NCSA Mosaic a biblioteca da PUC-Rio era o lugar onde podíamos pegar emprestado por uma semana os Proceedings do SIGGRAPH e ver coisas fantásticas de computação gráfica. Depois a vida me levou por caminhos da medicina e não acompanhei mais o SIGGRAPH.

Esta semana, no entanto, li um artigo desta conferencia que me chamou a atenção: “Rendering Synthetic Objects into Legacy Photographs”, a proposta do trabalho é colocar objetos, de maneira realista, em fotografias onde estes objetos não estavam. Como este é um caso típico de que uma imagem vale mil palavras, veja as fotos abaixo:

Clica que aumenta

Se você tiver interesse e tempo a leitura do artigo é interessante:
http://kevinkarsch.com/publications/sa11-lowres.pdf

Recomendo também ver o vídeo que o autor do artigo criou:



Rendering Synthetic Objects into Legacy Photographs
from Kevin Karsch on Vimeo.
 

 

Nokia World, primeiro dia, resumo pra passar

Primeiramente, queria me desculpar pela qualidade das fotos postadas na minha timeline do evento. Tinha que decidir entre um E7 ou N8. Infelizmente o teclado do E7 faz diferença na hora de postar rapidamente a informação. Foi assim durante toda a apresentação da manhã e acho que foi possível dar uma boa visão do que aconteceu, em tempo real. Não tem como usar um notebook e tirar fotos ao mesmo tempo quando se está sozinho. Postei, desta forma, muita coisa com segundos de atraso.

Diferente do ano anterior, as apresentações saíram do estilo mais sóbrio e foram na linha americana, com mais brincadeiras e candidatos a Steve Balmer ou Steve Jobs. A reação geral foi boa, ainda mais que a maioria estaria feliz com apenas um telefone novo, rodando Windows Phone 7.5. Mas foram dois. Fora os outros quatro S40, com foco em casos de uso variados. Entre no site da Nokia e terá um detalhamento de todos os telefones (compare o Lumia 800 e Lumia 710, ou compares os modelos Asha 200, Asha 201, Asha 300 e Asha 303).

Achei os novos S40, linha denominada Asha, bem posicionados, para mercados emergentes (inclua-se). O sucesso de vendas do Nokia C3 no Brasil confirma a lógica desses lançamentos e acredito mesmo que terá uma boa saída. Cada telefone desses era apresentado através de um personagem, um usuário final fictício (ou não) em algum lugar do mundo (emergente). Foi uma boa sacada.

Já os novos Nokia WP7, denominados de Lumia 800 e 710, são bem atraentes, em especial o 800, que por fora é praticamente um Nokia N9 sem câmera frontal ou NFC (fiz um twitter review do N9 ontem). As especificações são boas, com processadores single core de 1.4Ghz e acelerador gráfico 3D, talvez um pouco longe do hardware de um Samsung Nexus. No entanto, o desempenho, até onde pude testar, era excelente e apropriado para o software. Isto deve indicar que o Android exige mais da CPU.

Gostar ou não do WP7 é uma experiência pessoal, recomendo que teste quando puder. Eu vejo pontos inovadores nele, que vão além daquela fonte sedutora que usam (Segoe). O Metro, nome da interface, com seus “quadradinhos” (tiles) e aplicações em “panorama”, agradam muita gente. Também acho positivo ter o Office, Nokia Drive (maps…) e Nokia Music juntos. E, pra quem joga, a integração com Xbox. No fundo, você acaba levando o melhor das duas companhias por um preço da concorrência, no máximo.

Na cobertura do twitter, a pergunta mais pertinente pra mim foi a que queria saber no que o telefone WP7 da Nokia se diferenciava dos demais. Na minha visão, o relacionamento da Nokia com dezenas de operadoras é o primeiro fator, seguido do Nokia Drive (maps) e Nokia Music.

A gente deve ter este aparelho no começo do ano que vem, talvez fevereiro. Ele já tem suporte ao Português do Brasil, basta trocar e rebootar (sem piadinhas, ok ?). Aliás, o N9 também tem suporte total, para os interessados nele. Em particular, achei sensacional o N9 e estou levando um comigo pro Brasil. A fonte, chamada Pure Nokia, é muito similar à fonte da Microsoft.

Marcelo Barros diretamente do Nokia World 2011

Para os que estão de olho nas novidades do Nokia World 2011, vale a pena seguir o Marcelo Barros no Twitter @marcelobarros (http://twitter.com/#!/marcelobarros).

Ele está agora lá escrevendo em tempo real sobre os lançamentos de aparelhos com Windows Phone 7, tais como o Lumia 800 e Lumia 710.
More Nokia 800 Lumia

The Nokia Lumia 710, in white, black, and personalised rear facias.

Também tem novidade na parte dos fones de ouvido.

Nokia Purity headsets, collaborating with Monster.

Enfim, a dica para ter as informações on-line é seguir o Marcelo Barros no Twitter @marcelobarros (http://twitter.com/#!/marcelobarros)

Kindle é barato, no entanto adivinhe quem nos rouba?

O Kindle, modelo sem anúncios custa hoje US$ 109,00 incluindo o cabo de transferência de dados. Considerando o câmbio de hoje, são cerca de R$ 190,00, ou seja uma pechincha que abre portas para um mundo de leituras a preços acessíveis. Considerando que estamos num país onde a educação precisa crescer muito e a leitura é uma ótima forma de melhorar a educação você irá lógicamente inferir que o governo apoia você na compra de um dispositivo que serve básicamente para leitura. Certo? Não, redondamente errado.

O governo não só não apoia você, como vai lhe tungar em US$ 124,59 – preste atenção você não leu errado. O imposto cobrado é 114% do valor do produto. E não, não é cigarro cujo imposto, segundo dados da receita é de até 61%. Nem é cachaça cuja alíquota chega a 60%, nem é carro importado cuja alíquota pode atingir 80%. Estou falando de 114% para um aparelho que serve para ler livros!

Agradeça à Dilma quando você for tungado por impostos como este

Mas você irá pensar, inocente que é, este imposto serve ao bem da coletividade. Pois é meu amigo: este imposto serve para ser desviado, financiar cultura obras de arte de pessoas com alto QI (quem indica) pela lei Rouanet e ser desperdiçado na máquina pública.

Vale lembrar que a lei Rouanet ajuda a mostrar uma quantidade enorme de traseiros e outros atributos no carnaval e é pago com o dinheiro dos nossos impostos.

Resumo da história: se você comprar um Kindle pode ter certeza que o estado brasileiro está roubando você. Uma coisa é cobrar impostos, outra bem distinta é achacar o contribuinte.

Steve Jobs: Biografia

Foi lançada hoje a biografia oficial de Steven Paul Jobs, escrita por Walter Isaacs.

É um livro cativante, muito bem escrito e que mostra o interior de algo que nunca havia sido revelado: porque a Apple é como ela é? Porque quando Steve saiu da Apple nos anos 80 ela quase afundou? E ajuda a lançar luz em perspectivas para o futuro: será que Tim Cook vai conseguir manter a Apple da forma como ela é hoje?

É uma leitura que eu recomendo e que tende a se tornar durante várias semanas o mais vendido livro no mundo. É um livro que se você puder ler em inglês eu recomendo, estas traduções feitas na correria não me agradam muito. Típico livro que dá para ler muito bem no Kindle (seja ele para iOS ou Android): Steve Jobs

Steve Jobs, ao contrário do que se esperava, não exigiu dar palpite no livro, muito menos ler o conteúdo dele. A única coisa que pediu, e o autor assentiu, foi o design da capa. Se vê que é um design Apple 🙂

Ainda não acabei de ler, mas estou gostando muito. Se você está lendo conte o que está achando do livro.

Números primos e algoritmos – Parte I

Um dos fundamentos da criptografia e dos sistemas de assinatura digital são os números primos. O princípio que rege a criptografia assimétrica (RSA) é o fato de ser rápido descobrir se um número é primo e é lento fatorar um número.

O RSA fica para outro post, agora queria focar na pergunta: como faz para saber se um número é primo?

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i < x; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Obviamente esta função não é a melhor, ela roda em O(n) ou seja o tempo de execução cresce linearmente com o tamanho do número em questão.

Uma otimização que alguns alunos espertos no curso de Computação I fazem é a seguinte:

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< x/2; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Isto diminui o tempo de execução pela metade mas não muda a complexidade do algoritmo, ela continua sendo O(n). Portanto para números grandes isto não ajuda muito.

Uma coisa que podemos usar para melhorar a complexidade (ainda não ajuda muito, mas hoje paramos por aqui) é o fato de que se um número não tem nenhum divisor menor que a raiz quadrada dele ele não tem nenhum divisor (a prova disto é fácil e fica como exercício para o leitor 🙂 )

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< sqrt(x); i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Neste caso a complexidade que era O(n) passa a ser O(√n)

Melhorou? Sim. Mas ainda não é o suficiente. No próximo capítulo desta série, veremos métodos que dizem se um número é provavelmente primo.

Se você achar algum erro nos códigos acima, comente.

To jailbreak or not to jailbreak?

To be, or not to be, that is the question:
Whether ‘tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And by opposing end them? To die, to sleep,
No more; and by a sleep to say we end
The heart-ache, and the thousand natural shocks
That flesh is heir to: ‘tis a consummation…

Hamlet

 

Discussão profunda em mesa de bar é algo que adoro. Ainda mais se for comendo meu ovo cozido na Cinelândia.

Ontem estávamos reunidos diversos analistas de tecnologia ao redor de uma mesa de um famoso bar carioca tomando umas cervejas, comendo uns ovos cozidos e veio a discussão que nos tomou boa parte da noite.

Fazer ou não fazer jailbreak. Depois de horas chegamos às seguintes conclusões:

Jailbreak deixa o aparelho aberto e tem algumas mínimas vantagens, no entanto considerando que tudo no IPhone foi feito para ficar bonito, mas se você quiser um telefone cujos ícones sejam em formato da cruz de malta, cor abóbora na barra da operadora, as barras de sinal em marrom e que seja tão feio que faça o Steve se remexer na tumba então o jailbreak é a sua escolha.

Puxa, mas eu quero ser livre, não quero ficar amarrado às coisas e regras da Apple. Então compre um OpenMoko com as bençãos do Stallman e vai ouvir música em Ogg.

Veredicto de mesa de bar: faça o que quiser, o aparelho é seu, mas que fica brega, fica!

HTC Ultimate – Primeiro WP7 no Brasil

Como o chefe-master-supremo deste blog já comentou, hoje foi lançado o HTC Ultimate com Windows Phone 7.5. Fui representando o Zeletron e pude tirar algumas fotos. Como meus dotes de fotógrafo são bem toscos acredito que você irá encontra fotos melhores pela Internet, mas não poderia deixar de colocar uma pelo menos aqui.

O Aparelho visto de perto é bem bonito e elegante.

O evento foi legal para conhecer algumas pessoas que escrevem sobre tecnologia cujos blogs eu leio: Bia Kunze, Rodrigo Toledo, Richard Max.

Gostaria de agradecer ao pessoal da HTC, Microsoft e Vivo pelo convite feito através da S2Publicon.

HTC Ultimate – Direto da coletiva da HTC/Vivo

Hoje o Pedro Paulo foi representar o Zeletron na coletiva da HTC e da Vivo para a apresentação do HTC Ultimate, o primeiro aparelho com Windows Phone 7.5 a ser lançado no Brasil.

As especificações do aparelho impressionam:

  • Tela de 4.7″ com resolução de 480×800
  • 9,9mm de espessura
  • Peso com bateria: 160g
  • Processador Qualcomm Snapdragon S2 de 1.5GHz
  • 512MB de RAM
  • 16GB de Memória interna (12.6 livres)
  • Conector MicroUSB
  • Conector de fone de ouvido stereo 3,5mm
  • Câmera de 8MPixel (abertura de 28mm F2.2)
  • Dual Flash de LED
  • Grava vídeos em 720p
  • Câmera frontal de 1.3Mpixel
  • WiFi, GPS, Bluetooth 2.1

O aparelho será vendido pela Vivo e custará no pré-pago R$ 1.799,00 (o mesmo que o iPhone 4 custou quando foi lançado no ano passado) e no plano Vivo Smartphone 100 ele vai custar R$ 1.149,00

Mais tarde colocaremos nesse post (ou em outro) as fotos do evento e mais informações sobre o aparelho. Fique ligado.

O funeral de Steve Jobs

Ontem a Apple realizou um funeral em memória de Steve P. Jobs. E apesar de manterem a foto dele na página principal, criaram uma página onde as condolências do mundo todo vão aparecendo. Foi mais de um milhão de pessoas que deixaram sua mensagem e muitos seguem escrevendo para o e-mail: rememberingsteve@apple.com

Se posso fazer um comentário: a página de condolências é a mais bonita que já vi. Uma simplicidade elegante que honra a memória de Steve Jobs.

Nokia World 2011 chegando

Para quem achava que outubro só servia para festinha de Halloween, podemos dizer que este anda bem movimentado.

Depois do iPhone 4S, iOS5, das mortes do Steve Jobs e Dennis Ritchie, ainda teremos hoje, 23h, horário de Brasília, o lançamento do Ice Cream Sandwich (Android 4) e do Nexus Prime. O Pinguins Móveis vai acompanhar o lançamento, caso queira entrar nessa, não sei se teremos alguém aqui do blog acompanhado.

E, semana que vem, teremos o Nokia World 2011, dia 26 e 27. Eu estarei no evento, a menos que a imigração me mande voltar. Devo postar aqui ou, mais provável, twittar da minha conta @marcelobarros com o hash tag #nokiaworld.

O esporte mundial atual da área de mobilidade é ignorar ou falar mal do Symbian e Windows Phone 7 (se bem que a RIM andou querendo esta fatia), mas ando vendo uma boa empolgação para termos neste evento, em primeira mão, um excelente telefone Nokia com WP7. Aliás, desde o primeiro semestre temos acompanhado alguns supostos vazamentos (nenhum me pareceu verdadeiro) e o vídeo do próprio Elop, falando sobre o novo telefone. Mas o silêncio das minhas fontes indicam que andam trabalhando muito para este objetivo.

Além disso, como usuário de um Nokia E7 (Symbian^3), confesso estar alegre com a quantidade de updates e melhorias que foram feitas este ano na versão Symbian Anna, depois da famosa declaração de Elop. E ainda teremos mais updates com a próxima versão, chamada Belle, para o N8, E7, C6 e C7, com melhorias e integração de ferramentas Microsoft.

Nos resta esperar !

Depois alguém me explica o significado desta imagem de fundo na página do Nokia World 2011 ? O evento é em Londres, não é ?

Ajudando a escolher o tablet

Essa é inédita. Em vez de você vir até o blog para pegar dicas e saber qual Tablet vai comprar, agora é você quem ajuda ao editor a saber qual vai ser o Tablet que ele vai comprar. 😀

Estou em dúvida entre os seguintes aparelhos:

A)Samsung Galaxy Tab 7″ WiFi

  • Sem 3G
  • Android 2.2-2.3
  • R$890,00 – R$ 1.100,00
 

B) Motorola Xoom Wifi

  • Sem 3G
  • Android 3.0-3.2
  • R$1.350,00 – R$ 1.700,00
 

C) Samsung Galaxy S Tab 5″

  • Sem 3G
  • Android 2.2
  • R$680,00 – R$ 820,00
 

D) Samsung Galaxy Tab 10.1 WiFi

  • Sem 3G
  • Android 3.0-3.2
  • R$1.600,00 – R$ 2.000,00
 

Pela lista acima, dá para ver que não quero comprar um iPad, não porque eu não goste dele, mas porque a minha esposa já tem um e tenho acesso a ele para testar apps. Quero variar a plataforma.

Também não quero um tablet com 3G porque não quero outra conta de celular. Basta usar o tethering do meu iPhone 4 para acessar a internet no tablet quando não estiver próximo a um WiFi.

Essa dúvida pode ser resolvida por você, respondendo nos comentários as cinco perguntas abaixo:

  1. Qual desses tablets você tem?
  2. Está satisfeito com ele(s)?
  3. O que mais o irrita no seu tablet?
  4. O que você mais gosta no seu tablet?
  5. Você recomendaria esse aparelho a um amigo?

Caso não tenha nenhum desses aparelhos acima e queira me indicar um outro, use os comentários para isso.

No final, esse post somado aos comentários poderá ser útil para outras pessoas que estejam com a mesma dúvida.