Algoritmo para cálculo de raiz quadrada para microcontroladores Simples

[Christiano]

#include <stdio.h>

int main()

{

int x;

printf("Digite o numero...\n");

scanf("%d",&x);

int y = (x/2+ 2)/2;

while(1)

{

y = (y+x/y)/2;

printf("%d\n", y);

}

}

Fonte: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

[Marcelo Jo]

  Ess sim é ninja... achei na net, nao lembro até se nao foi no wikipedia mesmo... só sei que funciona e retorna em 32 bits.. tá.. tem um float ali no meio..

inline uint32_t SquareRoot(uint32_t num)

{

long i;

float x2, y;

const float threehalfs = 1.5F;

x2 = num * 0.5F;

y  = num;

i  = * ( long* ) &y;                       // evil floating point bit level hacking

i  = 0x5f3759df - ( i >> 1 );               // what the fuck?

y  = * ( float * ) &i;

y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration

return (uint32_t)1/y;

}

2013/3/8 Christiano <christia...@gmail.com>

--
Você está recebendo esta mensagem porque se inscreveu no grupo "sis_embarcados" dos Grupos do Google.
Para cancelar a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para sis_embarcado...@googlegroups.com.
Para postar neste grupo, envie um e-mail para sis_emb...@googlegroups.com.
Visite este grupo em http://groups.google.com/group/sis_embarcados?hl=pt-BR.
Para obter mais opções, acesse https://groups.google.com/groups/opt_out.
 
 

[Thiago Lima]

uhauhauahuhauah

// que isso?

2013/3/8 Marcelo Jo <marc...@gmail.com>:

[Haroldo Amaral]

Isso é o algoritmo de Newton não é!?

Aqui fala algo, semelhante ao que os amigos postaram.

http://www.hardware.com.br/comunidade/raiz-calcular/924427/

Da para definir a precisão através da diferença entre o número a ser extraída a raiz, e o valor da raiz calculada pelo algoritmo elevado ao quadrado. enquanto não alcançar o resultado, continuar o processo iterativo.

Usei isso em um 8051 no meu tcc. ganhei 50% no processamento total ja que a biblioteca padrão não é nada otimizada para microcontroladores

-- 
Haroldo L. M. Amaral

Mestrando em Eng. Elétrica - UNESP Bauru

Tecnólogo em Sistemas Biomédicos - FATEC Bauru

agae...@gmail.com

Em 8 de março de 2013 12:07, Fernando Martines <fernando...@gmail.com> escreveu:

...Apenas completando o código do colega com o critério de parada ;-)

#include <stdio.h>

int main()

{

  int x, q = 0;

  printf("Digite o numero...\n");

  scanf("%d",&x);

  int y = (x/2+ 2)/2;

  while (q!=y)

  {

q = y;

  y = (y+x/y)/2;

  printf("%d\n", y);

  }

}

2013/3/8 Christiano <christia...@gmail.com>

#include <stdio.h>

int main()

{

int x;

printf("Digite o numero...\n");

scanf("%d",&x);

int y = (x/2+ 2)/2;

while(1)

{

y = (y+x/y)/2;

printf("%d\n", y);

}

}

Fonte: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

--

--
Você recebeu esta mensagem porque está inscrito no Grupo Google "Texas Instruments Info para Designers e Projetistas".
Para postar uma mensagem neste grupo, mande um email para texa...@googlegroups.com
Para deixar o grupo, mande um email para texas-sc+u...@googlegroups.com
Para mais opções, visite este grupo no endereço:
http://groups.google.com/group/texas-sc?hl=pt-BR
 
---
Você está recebendo esta mensagem porque se inscreveu no grupo "Texas Instruments Info para Designers e Projetistas" dos Grupos do Google.
Para cancelar a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para texas-sc+u...@googlegroups.com.

Para obter mais opções, acesse https://groups.google.com/groups/opt_out.
 
 

--
~Fernando Martines

--
--
Você recebeu esta mensagem porque está inscrito no Grupo Google "Texas Instruments Info para Designers e Projetistas".
Para postar uma mensagem neste grupo, mande um email para texa...@googlegroups.com
Para deixar o grupo, mande um email para texas-sc+u...@googlegroups.com
Para mais opções, visite este grupo no endereço:
http://groups.google.com/group/texas-sc?hl=pt-BR
 
---
Você está recebendo esta mensagem porque se inscreveu no grupo "Texas Instruments Info para Designers e Projetistas" dos Grupos do Google.
Para cancelar a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para texas-sc+u...@googlegroups.com.

[Felipe Neves]

Raiz quadrada, procurem pelo algoritmo Cordic, o interessante é que ele utiliza as operações básicas com números complexos para obter funções trigonométricas e raiz quadrada além de ser implementável com simples shifts.

No geral é um loop onde multiplica-se um vetor X+jY por um um outro W+jZ onde Z varia com base em shifts para a direita, ao final do loop apenas multiplica-se o vetor resultante por uma constante chamada de Cordic Gain.

Outra vantagem é que a maioria das operações pode ser pré-computada, ou seja são realizadas na hora da compilação e possui razoavel precisão se feita em ponto fixo.

Abs.

[Haroldo Amaral]

Achei muito interessante e proveitosa esta discussão, sempre acabo vendo que existe uma vastidão a ser conhecida. hehe

Não achei ainda o algoritmo de Cordic para raiz, mas achei para seno e cosseno e testarei em breve, aproveitei os exemplos do http://www.embedded.com/electronics-blogs/programmer-s-toolbox/4219659/Integer-Square-Roots e fiz uns testes no launchpad MSP430 com ele rodando a 1MHz.

Montei 4 algoritmos; um somente multiplicando um número crescente por ele mesmo até atingir o resultado mais próximo, outro pelo método chinês e outros dois que são os dois últimos exemplos da página. Em todos os casos extrai a raiz do número "12345678", para saber quanto tempo demoravam utilizei uma saída do launchpad P2.0, no início da rotina colocava em nível alto, no final colocava em nível baixo e este pino foi conectado ao myDAQ. Os resultados são (aproximados...):

- método "simplest": 627,85ms

- método chinês: 38,44ms

- binary: 1,17ms

- binary otimizado: 1,13ms

incrível a diferença de tempo para processar.

-- 
Haroldo L. M. Amaral

Mestrando em Eng. Elétrica - UNESP Bauru

Tecnólogo em Sistemas Biomédicos - FATEC Bauru

agae...@gmail.com

--
Você está recebendo esta mensagem porque se inscreveu no grupo "sis_embarcados" dos Grupos do Google.

Para cancelar a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para sis_embarcado...@googlegroups.com.

Para postar neste grupo, envie um e-mail para sis_emb...@googlegroups.com.
Visite este grupo em http://groups.google.com/group/sis_embarcados?hl=pt-BR.

Para obter mais opções, acesse https://groups.google.com/groups/opt_out.
 
 

--

[Prof. Alessandro Cunha]

Haroldo, bom dia.

 

Quer ver uma coisa mais incrível ainda?

 

Pegue este código que você fez rodar na LaunchPad do MSP430 e coloque ele para rodar na LaunchPad do ARM Cortex M4.

 

Compare os tempos que você teve com o MSP430 e veja os tempos que você terá com o ARM.

 

Como o ARM da LaunchPad tem uma FPU (máquina de ponto flutuante) toda vez que o código em uso precisar de um fracionário, o núcleo pega a instrução e faz a FPU processar.

 

Isto vai causar um “processamento paralelo” dentro do chip.

 

Para ter graça, faça o ARM e o MSP430 rodarem na mesma velocidade (1 MHZ).

 

Se você não tiver a plaquinha do ARM por ai, me passa o código que eu texto nas duas aqui e publico para a galera sentir a diferença.

 

Espero ter ajudado.

 

Abraços.

 

Alessandro Ferreira da Cunha
TECHtraininG - ENGENHARIA E TREINAMENTOS
aless...@techtraining.eng.br
MSN --> afcu...@gmail.com
SKYPE --> alessandroferreiradacunha
twitter --> @prof_afcunha
(11) 995–363-828
www.techtraining.eng.br

[Marcelo Jo]

  Seria possível vc testar os 2 algoritmos que a gente mandou? =D Queria ver qto tempo demora o método q enviei, nunca fiz o teste! =D

  Abraços

  Marcelo

2013/3/12 Haroldo Amaral <agae...@gmail.com>

[Rodrigo Almeida]

Só por curiosidade é possível fazer as contas de inteiro na FPU tb? É que os códigos que o Haroldo passou foram otimizados para só usarem inteiros, acho que não se funcionam bem com float.

Prof. Rodrigo M A Almeida
Universidade Federal de Itajubá
E-mail: rodri...@unifei.edu.br
Twitter: @rmaalmeida
Site: sites.google.com/site/rmaalmeida
Tel: +55 35 3629-1200

[Fabio Utzig]

O que eu conhecia tamb�m era usando somente inteiro, na verdade era
ponto fixo mas usando inteiros, evidentemente.

Por exemplo, esta implementa��o para MSP430:

https://github.com/the0b/MSP430-CORDIC-sine-cosine

Acho que um dos objetivos dos m�todos num�ricos para microcontroladores
� justamente n�o usar FP. Se for para implementar usando FP, antes fazer
somente uma chamada sin() da biblioteca C.

On 3/12/13 9:40 AM, Rodrigo Almeida wrote:
> S� por curiosidade � poss�vel fazer as contas de inteiro na FPU tb? �
> que os c�digos que o Haroldo passou foram otimizados para s� usarem
> inteiros, acho que n�o se funcionam bem com float.

[Haroldo Amaral]

Francisco, fiquei feliz com o comentário. hehe, gosto de ficar testando essas coisas, aprendendo conceitos novos...
Sobre utilizar a série de Taylor, não testei o algoritmo, mas depois testarei e também aquele método "ninja" que postaram, mas como utilizam ponto flutuante acho que fugiria da comparação com estes focados somente em números inteiros

Marcelo, tentei implementar aqui os dois códigos (não sei se exatamente o que você pensou), o do Christiano não funcionou pois entrava em um loop sem fim devido a não ter critérios de parada. Após a adoção do critério proposto pelo Fernando passou a funcionar. Testei da forma que ele propôs e também substituindo algumas divisões por 2, por rotacionamentos para ver se havia algum ganho já que não sei se o compilador (CCS) reconhece essas divisões e multiplicações por múltiplos de base binária e substitui por rotacionamento.

os resultados agora foram medidos com um osciloscópio Minipa pois estou no laboratório sem meu myDAQ.

- método simples: 628ms

- método chinês: 38,4ms

- método binary: 1,16ms

- método binary otimizado: 1,128ms

- método Christiano/Fernando: 4,8ms

Engraçado que estou testando este código em um projeto que escreve os resultados em um LCD nokia 5110 (sem usar a SPI), funciona perfeitamente... é só limpar o código e tirar o que esta relacionado ao LCD que o compilador para de reconhecer a função criada para o calculo da raiz, ou melhor... ele reconhece mas na hora de executar ele pula a chamada da função. Alguma luz Prof. Alessandro!?

-- 
Haroldo L. M. Amaral

Mestrando em Eng. Elétrica - UNESP Bauru

Tecnólogo em Sistemas Biomédicos - FATEC Bauru

agae...@gmail.com

[Marcelo Jo]

  Olá Haroldo!

  O código que eu enviei foi esse:

inline uint32_t SquareRoot(uint32_t num)

{

long i;

float x2, y;

const float threehalfs = 1.5F;

x2 = num * 0.5F;

y  = num;

i  = * ( long* ) &y;                       // evil floating point bit level hacking

i  = 0x5f3759df - ( i >> 1 );               // what the fuck?

y  = * ( float * ) &i;

y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration

return (uint32_t)1/y;

}

  Qual seria ele na tua lista de testes?

  Marcelo

[Haroldo Amaral]

Marcelo tentei implementar este algoritmo e até que funcionou mas, para números altos a raiz começa a ter error bem grandes na parte inteira.

[Christiano]

O código do Fernando estava no Grupo da Texas, vou colar aqui:

[Marcelo Jo]

  Vc está usando variáveis de 32 bits? Aqui a raiz de um milhão deu erro de 1 hehehe mas pra outros valores abaixo tá funcionando

2013/3/13 Haroldo Amaral <agae...@gmail.com>