Soma das potências dos números primos com um valor dado e menores que este

No passado, apresentei aqui um texto onde referi um método que se baseava na aplicação do princípio da inclusão-exclusão na determinação do conhecida fórmula para a função totiente. Foi aí referido que o mesmo método seria aplicável à determinação da soma de todos os números primos com um número arbitrário n e menores que este. Porém, dada a ausência de uma justificação aceitável, considerei pertinente apresentar aqui a aplicação do método ao caso do problema mais geral de determinar a soma das potências de ordem k dos números primos com n e menores do que este.

Para o efeito, começamos por introduzir a notação

\sigma_k^*(n)=\sum_{i\le n,\ \text{mdc}(i,n)=1}{i^k}

e

S_k\left(n\right)=\sum_{i=1}^n{i^k}

isto é, \sigma_k^*(n) representa a soma das potências de ordem k de todos os números primos com n e menores do que este, e S_k(n) a soma das potências de ordem k dos números até n.

É bem conhecida a fórmula para a determinação da soma das potências de ordem k,

S_k(n)=\sum_{i=0}^k{\frac{1}{k+1}\binom{k+1}{i}B_in^{k+1-i}}

onde B_i não dependem de n, sendo, por exemplo, B_0=1 e B_1=\frac{1}{2}. Suponhamos que n admite a factorização

n=p_1^{n_1}p_2^{n_2}\cdots p_r^{n_r}

onde p_i são números primos. Começamos por considerar a soma S_k(n) das potências dos números inferiores ou iguais a n. A quantidade \left(p_{\alpha_1}\cdots p_{\alpha_i}\right)^kS_k\left(\frac{n}{p_{\alpha_1}\cdots p_{\alpha_i}}\right) proporciona a soma das potências de ordem k dos múltiplos do produto p_{\alpha_1}\cdots p_{\alpha_i} cujo valor não excede n. O princípio da inclusão exclusão permite concluir que

\sigma_k^*(n)=S_k(n)-\sum_{i=1}^r{p_i^kS_k\left(\frac{n}{p_i}\right)}+\sum_{1\le i<j\le r}{\left(p_ip_j\right)^kS_k\left(\frac{n}{p_ip_j}\right)}-\cdots

Por seu turno, é verdade que

m^kS_k(\frac{n}{m})=\sum_{i=0}^k{\frac{1}{k+1}\binom{k+1}{i}B_in^{k+1-i}}m^{i-1}

Se introduzirmos a expressão anterior na que obtivemos a partir do princípio da inclusão-exclusão e atendermos a que

1-\sum_{i=1}^r{p_i^\alpha}+\sum_{1\le i<j\le r}{p_i^\alpha p_j^\alpha}-\cdots=\prod_{i=1}^r{\left(1-p_i^\alpha\right)}

obtemos

\sigma_k^*(n)=\frac{n^{k+1}}{k+1}\prod_{i=1}^r{\left(1-\frac{1}{p_i}\right)}+\sum_{j=2}^{k}{\left(\frac{1}{k+1}\binom{k+1}{j}B_jn^{k+1-j}\prod_{i=1}^r{\left(1-p_i^{j-1}\right)}\right)}

Se nos lembrarmos que a função totiente é dada pela expressão

\varphi(n)=n\prod_{i=1}^r{\left(1-\frac{1}{p_i}\right)}

e o radical de n se define como

\text{rad}(n)=\prod_{i=1}^r{p_i}

quando n admite a factorização apresentada acima, facilmente concluímos após simples manipulações algébricas que

\sigma_k^*(n)=\varphi(n)\left(\frac{n^{k}}{k+1}+(-1)^{r}\text{rad}(n)\sum_{j=2}^{k}{\left(\frac{\sigma_{1}\left(\text{rad}^{j-2}(n)\right)}{k+1}\binom{k+1}{j}B_jn^{k-j}\right)}\right)

onde \sigma_{1}\left(\text{rad}^{j-2}(n)\right) representa a soma dos divisores de \text{rad}^{j-2}(n) que é dada por

\sigma_{1}\left(\text{rad}^{j-2}(n)\right)=\prod_{i=1}^r{\left(\sum_{l=0}^{j-2}p_i^l\right)}

Como casos particulares temos

\sigma_1^*(n)=\frac{n}{2}\varphi(n)

que fora anteriormente apresentada quase sem justificação e

\sigma_2^*(n)=\varphi(n)\left(\frac{n^2}{3}-\frac{\text{rad}(n)}{6}\right)

Anúncios
Publicado em Matemática | Etiquetas , , , | Publicar um comentário

Desempenho – um problema normalmente aplicacional

Na secção Bottleneck Elimination do artigo Database Performance Tuning Guide, é afirmado que, muitas vezes, a maneira mais efectiva de resolver um problema de congestionamento em base-de-dados passa por alterar a aplicação subjacente. Posso afirmar que mais de 95% dos melhoramentos de desempenho que consegui resultaram da sugestão de alteração de aplicações. Neste texto, conto uma breve história de como um problema aplicacional se pode assemelhar a um problema de congestionamento da base-de-dados.

A aplicação em questão assenta em SQL Server e permite gerir a transferência de equipamentos entre localizações no seio da empresa. Num dos procedimentos habituais do funcionamento da aplicação, começou a surgir o erro ao fim de alguns anos de utilização:

Timeout expired. The timeout period elapsed prior to completion of the operation

É natural assumir que alguma consulta se tornou subitamente mais lenta porque algo foi modificado ao nível do servidor ou porque os índices envolvidos se fragmentaram. Foi esta suposição que levou o responsável do desenvolvimento a contactar-me. Relativamente ao servidor, nenhuma configuração fora efectuada e, portanto, o problema dever-se-ia centrar na consulta.

Recorri ao SQL Monitor para determinar quais teriam sido as consultas mais pesadas a serem executadas na base-de-dados numa janela temporal centrada em torno do evento. Verifiquei que as consultas mais lentas executavam em algumas centenas de milissegundos e não encontrei tempos de espera (waits) nem tampouco bloqueios (locks).

A experiência tem-me mostrado que um determinado procedimento aplicacional não envolve apenas uma consulta e, por isso, decidi averiguar quais teriam sido as consultas que, no total das suas execuções, requereram o maior tempo de processamento. Determinei que uma consulta cuja execução individual era extremamente rápida executara milhares de vezes num intervalo de tempo muito curto. Estaria este fenómeno relacionado com o erro encontrado?

Contactei o responsável do desenvolvimento e expus-lhe o resultado. Não se encontrando convencido e tendo a aplicação funcionado até à data sem problemas, pediu-me que reconstruísse os índices associados. Após a reconstrução dos índices, o problema persistiu. Sugeri-lhe, portanto, que depurasse a aplicação de modo a despistar a minha hipótese. Bastou um ponto de paragem na linha referenciada pela excepção para descobrirmos o problema que passo a explicar.

Suponhamos que a base-de-dados possui uma tabela de equipamentos que se classificam em vários tipos. As transferências de diferentes tipos de equipamentos podem seguir trâmites diferentes e requerem a geração automática de diferentes números de controlo. Os números de controlo geram-se, para cada tipo de equipamento, adendando um prefixo ao sucessor numérico do resultado da contagem dos equipamentos de um determinado tipo. Por exemplo, se existissem 10 equipamentos do tipo EquipamentoA e fosse acrescentado um novo equipamento desse tipo, seria gerado o número de controlo A_11. Após a geração do número de controlo, era verificada a sua existência na base-de-dados e, em caso afirmativo, a mesma função era chamada para determinar um novo número de controlo.

Suponhamos agora que o equipamento com o número A_9 foi removido. A contagem dos equipamentos do tipo EquipamentoA passa a ser novamente 10. O número de controlo A_11 gerado existe na base-de-dados. Como a função que gera o número de controlo é a mesma, este será novamente A11 que existe na base-de-dados. Numa situação normal, a aplicação manter-se-ia em ciclo infinito. Quando o processo é envolto por uma transacção, a aplicação executa até exaurir o tempo máximo definido para as transacções.

A aplicação funcionara durante tanto tempo sem que o erro tivesse sido detectado porque nunca antes tinham sido removidos equipamentos da tabela em questão. Em conclusão, só porque uma aplicação deixou subitamente de funcionar ao fim de vários anos se assume que o problema está no seu ambiente é um pressuposto que pode não se adequar à realidade. É útil, no contexto de uma análise de performance, ter em conta, não só as consultas mais exigentes, como a possibilidade de um número excessivo de consultas estar associada a um processo simples devido a erros de implementação. Trata-se de uma situação comum quando se usam O/RM como a Entity Framework ou o NHibernate quando não se tem em conta as melhores práticas na sua utilização.

Publicado em Computadores e Internet, Sem categoria | Etiquetas , , , , | Publicar um comentário

Criar relatórios com o Oracle APEX

Grande parte das minhas actuais funções compreende a administração das instâncias Oracle de suporte às aplicações da Mentor Graphics, Capital Harness XC e ferramentas associadas. Seja devido às limitações nas ferramentas de reporte ou à insuficiente formação dos utilizadores, são-me frequentemente dirigidos pedidos para extracção de relatórios directamente da base-de-dados. Dada a elevada tipificação dos pedidos, não é tarefa árdua desenhar uma aplicação capaz de os proporcionar de forma automática. O único problema que aqui se coloca prende-se com a dificuldade em conseguir que seja disponibilizado tempo da equipa de desenvolvimento para este efeito.

Apesar de possuir capacidades de desenvolvimento suficientes, não me parece pertinente sair do âmbito da administração de bases-de-dados. Por seu turno, a execução de trabalho manual parece-me demasiado ineficiente e propício a erro. Uma pequena investigação conduziu-me ao Oracle Application Express, conhecido abreviadamente por APEX, e que é disponibilizado como funcionalidade inerente à base-de-dados. Trata-se de uma ferramenta que permite desenvolver aplicações relativamente sofisticadas, recorrendo a uma interface gráfica e sem a necessidade de grandes codificações.

No que se segue, pretendo mostrar como é possível  criar relatórios de uma forma assaz simples com uma quantidade quase nula de código. Não descreverei aqui a instalação da funcionalidade e assumo que um Workspace tenha sido criado. Note-se que a página de adminsitração do APEX encontra-se configurada no endereço http(s)://servidor_bd:8080/apex/apex_admin e que fornece a interface para a criação de Workspaces. Um utilizador com permissões de desenvolvimento no Workspace deverá ainda ser criado. A página para entrada nos Workspaces é encontrada no endereço http(s)://servidor_bd:8080/apex.

De modo a disponibilizar relatórios é necessária a criação de uma aplicação APEX. Uma vez no Workspace, para criar a aplicação é suficiente executar os passos:

  1. Seleccionar o botão App Builder ou o menu App Builder>Database Applications;
  2. Seleccionar o botão Create;
  3. Escolher o tipo de aplicação Desktop;
  4. Definir o Schema por defeito onde deverão ser criadas as tabelas e que será aqui designado por MySchema;
  5. Atribuir um nome, que será aqui considerado como MyApp;
  6. Deixar o campo Application com o número que surge por defeito e constitui um identificador numérico;
  7. Seleccionar o botão Create Application.

Seleccionando o menu App Builder>Database Applications, somos reconduzidos à página das aplicações onde podemos encontrar agora a aplicação acabada de criar.

O exemplo que consideramos requer a existência das tabelas no MySchema

COMPONENT_TYPE
COLUMN NAME COLUMN TYPE
ID INT
TYPE_CODE VARCHAR2(4)
TYPE_DESCRIPTION VARCHAR2(40)

e

COMPONENT
COLUMN NAME COLUMN TYPE
PARTNUMBER VARCHAR2(255)
DESCRIPTION VARCHAR2(1024)
COMPONENT_TYPE_ID INT

A selecção do botão da aplicação conduz à interface onde são listadas as páginas associadas à aplicação. Duas páginas terão sido criadas por defeito aquando da criação da aplicação, nomeadamente a Home e o Login. Interessa agora criar os relatórios onde surgem os tipos de componente, dados pela tabela COMPONENT_TYPE e, para cada tipo de componente, discriminar os componentes desse grupo, recorrendo à tabela COMPONENT.

Começamos por criar a página que conterá o relatório dos tipos de componentes.

  1. Na página da aplicação, seleccionar o botão Create Page;
  2. Seleccionar a opção Report como tipo de página;
  3. Seleccionar Interactive Grid como tipo de relatório;
  4. Introduzir nome e número da página – a página será designada por COMPONENT TYPES e o número é usado como identificador quando a página é referenciada dentro da aplicação;
  5. Criar uma nova entrada de menu, configurando-a como descendente de Home;
  6. Definir a consulta que retornará os valores para o relatório e pressionar o botão Create.

A consulta que permite obter os tipos de componentes é da forma

SELECT
ID,
TYPE_CODE,
TYPE_DESCRIPTION
FROM COMPONENT_TYPE

Após a selecção do botão Create, o utilizador será conduzido ao Page Designer. Trata-se da interface que possibilita a adição, remoção e edição dos vários componentes que constituem a página. O Page Designer encontra-se dividio em três regiões principais. Na coluna mais à esquerda surge a lista dos componentes numa estrutura hierárquica. Interessa-nos aqui a estrutura que se encontra no serparador Rendering. Na coluna do extremo direito do ecrã encontramos as propriedades de cada objecto seleccionado em cada uma das outras colunas. A região central é dedicada ao posicionamento dos componentes na página. Interessam aqui os separadores Layout e Component View.

Se expandirmos o nó Columns do COMPONENT TYPE obtemos a lista das colunas especificadas na consulta que permite obter os tipos de componentes e a coluna adicional ROWID que iremos remover.

12 - remove rowid column.png

Seleccionamos agora a coluna ID e, na região das propriedades à direita, alteramos o seu tipo  para Hidden.  Se executarmos a página após gravação, observamos o relatório com os tipos de componentes. Interessa agora criar a coluna que contém a ligação para a página que reporta os componentes associados a esse tipo. Para o efeito, criamos uma nova coluna.

16 - createlinkcolumn.png

que designamos por VIEW_COMPONENTS. Na região das propriedades, estabelecemos o destino da ligação para a página número 3 que ainda não foi criada.

17 - setlink.png

Na caixa de diálogo é incluído o item P3_COMPONENT_TYPE_ID com o valor dado pelo ID – a notação &ID. representa aquilo que recebe a designação de Substitution String cujo valor a substituir é dado pelo elemento que se encontra na coluna ID.

Para todas as colunas é ainda necessário estabelecer o nome que surgirá na respectiva coluna do relatório. Isso é estabelecido na secção Heading das propriedades.

Voltamos à página da aplicação onde podemos observar que existem agora três páginas, nomeadamente, 1 – Home, 2 – COMPONENT TYPE e 3 – Login Page. Criamos agora a página número 3 denominada COMPONENT nos mesmos moldes que a página COMPONENT TYPE, isto é, definindo um relatório do tipo grelha interactiva. No entanto, neste caso, não deverá ser associado um menu uma vez que a ligação é obtida a partir do relatório da página COMPONENT TYPE. A consulta a ser introduzida é agora da forma

SELECT
PARTNUMBER,
DESCRIPTION
FROM COMPONENT
WHERE COMPONENT_TYPE_ID = :P3_COMPONENT_TYPE_ID

Podemos observar que o valor do predicado no filtro da consulta acima é dado por :P3_COMPONENT_TYPE_ID que foi configurado no alvo da ligação associada à coluna VIEW_COMPONENTS no relatório dos tipos de componentes. Porém, este valor não pode ser automaticamente ligado à consulta do relatório. É obtido, por seu turno, a partir de qualquer componente existente na página. Deveremos, portanto, criar um elemento escondido que conterá esse valor.

Para o efeito, colocamos uma Display Region na página, arrastando o componente discriminado no separador Regions da zona inferior da interface para o Layout da página. Iremos posicioná-la acima do relatório. Do separador Items, arrastamos para a região criada o componente Hidden e renomeamo-lo, na secção das propriedades, para P3_COMPONENT_TYPE_ID. É este elemento que irá receber o valor definido na ligação associada à coluna VIEW_COMPONENTS e que será considerado como predicado no filtro da consulta.

Iremos agora colocar dois componentes que conterão a informação sobre o tipo de componentes a que o relatório actual se refere. Arrastamos, portanto, para a nossa Display Region sobre o relatório, dois itens do tipo Display Only. Nas propriedades, configuramos o nome do primeiro para P3_COMPONENT_TYPE_CODE e o do segundo para P3_COMPONENT_TYPE_DESCRIPTION. Os seus valores serão preenchidos do seguinte modo:

  1. Seleccionamos a tabulação Component View que se encontra na zona central da interface;
  2. No item Processes da secção Page Rendering, criamos um novo processo, seleccionando o botão com o símbolo ‘+’;
  3. Denominamo-lo por Automatic Row Fecth;
  4. Escolhemos o tipo PL/SQL Code

Na secção Source introduzimos o seguinte código PL/SQL

SELECT
COMPONENT_TYPE_CODE,
COMPONENT_TYPE_DESCRIPTION
INTO :P3_COMPONENT_TYPE_CODE, :P3_COMPONENT_TYPE_DESCRIPTION
FROM COMPONENT_TYPE
WHERE ID = :COMPONENT_TYPE_ID

O procedimento permite criar um processamento para estabelecer os valores dos respectivos componentes aquando do carregamento da página. Estes são deste modo obtidos por intermédio de uma consulta PL/SQL à tabela dos tipos de componentes.

Na página da aplicação encontramos o botão Run Application que nos permite executar a aplicação que acabámos de criar. Após efectuar login, a ligação para a página dos tipos de componentes pode ser encontrada sob o menu de navegação Home.

pag_tipo_comps.png

O relatório interactivo permite-nos aplicar filtros, adicionar e remover colunas, exportar para vários formatos, entre outras funcionalidades.

pag_comps.png

Se seleccionarmos a ligação associada a uma determinada linha do relatório com os tipos de componentes, obtemos um relatório com todos os componentes desse tipo. Nesta página pode-se ainda observar qual é o código e a descrição do tipo de compomentes associados ao relatório.

Foi aqui brevemente descrito o procedimento para criação de um relatório interactivo. A obtenção de um relatório subsidiário permite descrever o processo geral para definir uma página de detalhes. Como pode ser observado, não foi necessário qualquer conhecimento de html, javascript ou css. Apenas as bem conhecidas consultas PL/SQL.

Publicado em Sem categoria | Publicar um comentário

Tabelas externas em Oracle

Dada a popularidade do Microsoft Office e, em particular, do Excel no âmbito empresarial, os administradores dos dados das empresas são por vezes confrontados com a necessidade de actualizar dados em base-de-dados ou comparar esses dados com um grande número de registos oriundos desse tipo de ficheiros.

O carregamento de dados para uma base-de-dados Oracle a partir de um ficheiro consegue-se, do ponto de vista do cliente, com o auxílio do SQL*Loader. Uma comparação de dados existentes em base-de-dados com os oriundos do ficheiro é facilmente implementada com o auxílio do SQL*Loader, carregando os dados numa tabela temporária e aplicando as consultas SQL habituais.

A utilização de uma tabela externa afigura-se uma técnica para carregamento ou comparação de dados alternativa quando os ficheiros em causa podem ser acedidos pelo servidor. Trata-se do cenário que será descrito doravante.

Supõe-se agora que um ficheiro Excel contém uma enorme lista com o número, descrição e tipo de peça. O Excel é convertido num ficheiro sample.csv no qual se encontram as primeiras linhas:

PN;DESCRIPTION;GROUP
7173841;"CONNECTOR 40P";CONN
8374284;"WIRE";WIR
7637463;"EYELET";TERM
7638467;"CONNECTOR 2P";CONN

Pretende-se, portanto, criar uma tabela externa Oracle que possibilite a execução de consultas SQL sobre os dados do ficheiro. Começa-se, em primeiro lugar, por definir o objecto que representa a directoria no servidor.

CREATE DIRECTORY LOAD_DIR AS 'C:\LoadDir\';

A instrução cria um objecto que representa a directoria C:\LoadDir\ onde deverá ser colocado o ficheiro sample.csv. A instrução para criação da tabela externa que irá representar o ficheiro é a seguinte.

CREATE TABLE SAMPLE_TABLE
(
PARTNUMBER VARCHAR2(255 BYTE)
, DESCRIPTION VARCHAR2(1024 BYTE)
, GROUPNAME VARCHAR2(64 BYTE)
)
ORGANIZATION EXTERNAL
(
TYPE ORACLE_LOADER
DEFAULT DIRECTORY LOAD_DIR
ACCESS PARAMETERS
(
RECORDS DELIMITED BY NEWLINE CHARACTERSET AL32UTF8
SKIP 1
FIELDS TERMINATED by ';' OPTIONALLY ENCLOSED BY '"'
MISSING FIELD VALUES ARE NULL
(
PARTNUMBER,
DESCRIPTION,
GROUPNAME
)
)
LOCATION
(
LOAD_DIR: 'sample.csv'
)
)
REJECT LIMIT 1000;

A execução da consulta

SELECT * FROM SAMPLE_TABLE;

permite obter todos os registos da tabela. No caso em que alguma linha não se encontre no formato correcto, será registado um aviso num ficheiro de diário criado na mesma directoria para o efeito. Quando mais de 1000 linhas não se encontram no formato correcto, a consulta incorre em erro.

A criação da tabela tabela externa é identificada pela instrução ORGANIZATION EXTERNAL. Aqui define-se o tipo do carregador, o ORACLE_LOADER, a directoria que é usada por defeito, LOAD_DIR criada atrás para o efeito, os parâmetros de acesso, ACCESS PARAMETERS, a localização do ficheiro, LOCATION e o número limite de linhas mal formatadas que o carregador deve tolerar antes de emitir um erro, REJECT LIMIT.

Nos parâmetros da acesso são definidos os caracteres delimitadores das linhas. A instrução SKIP 1 indica que a primeira linha deverá ser ignorada. De facto, trata-se de um cabeçalho aposto no início do ficheiro. Os campos são separados por ; e o carácter é usado opcionalmente para delimitar cada campo. A instrução MISSING FIELD VALUES ARE NULL permite indicar quais são campos que, caso não seja proporcionado valor, são considerados como nulos.

A tabela assim criada pode agora ser tratada como uma tabela normal no que concerne à construção de consultas de leitura. É mesmo possível definir um cursor.

DECLARE
cur SYS_REFCURSOR;
pn VARCHAR2(255);
dsc VARCHAR2(1024);
grpn VARCHAR2(64);
BEGIN
OPEN cur FOR
SELECT
PARTNUMBER,
DESCRIPTION,
GROUPNAME
FROM SERGIOMARQUES.SAMPLE_TABLE;
LOOP
FETCH cur INTO pn, dsc, grpn;
EXIT WHEN cur%NOTFOUND;
DBMS_OUTPUT.PUT_LINE(pn || ' | ' || dsc || ' | ' || grpn);
END LOOP;
END;

Publicado em Sem categoria | Publicar um comentário

Funções de tabela PL/SQL

Vistas em SQL são tabelas virtuais definidas sobre o resultado de consultas que podem envolver uma ou várias tabelas reais.

CREATE VIEW NY_EMPLOYEES_VIEW AS
SELECT
E.ENAME AS EMPLOYEE,
D.DNAME AS DEPARTMENT
FROM EMP E
INNER JOIN DEPT D ON E.DEPTNO = D.DEPTNO
WHERE D.LOC = 'NEW YORK';

O código acima permite definir uma vista sobre a consulta que rertorna o nome e o departamento de todos os funcionários de uma empresa que trabalham em Nova Iorque. Após a definição da vista, esta informação é obtida por intermédio de uma consulta simples.

SELECT EMPLOYEE, DEPARTMENT FROM NY_EMPLOYEES_VIEW;

A obtenção da mesma informação associada a todos os funcionários que trabalham numa localização arbitrária poder-se-ia realizar por intermédio da criação de uma vista para cada localização, o que constitui um método pouco prático quando o número de todas as localizações possíveis é elevado.

Uma alternativa consiste em definir a vista

CREATE VIEW GEN_LOC_EMPLOYEES_VIEW AS
SELECT
E.ENAME AS EMPLOYEE,
D.DNAME AS DEPARTMENT,
D.LOC AS LOCALIZATION
FROM EMP E
INNER JOIN DEPT D ON E.DEPTNO = D.DEPTNO;

e executar o código

SELECT EMPLOYEE, DEPARTMENT FROM GEN_LOC_EMPLOYEES_VIEW
WHERE LOCALIZATION = 'Chicago';

para obter, por exemplo, todos os funcionários que labutam em Chicago.
A execução da consulta

SELECT EMPLOYEE, DEPARTMENT FROM GEN_LOC_EMPLOYEES_VIEW

iria retornar a informação de todos os funcionários aos quais se encontra associado um departamento, independentemente da localização. No entanto, a obtenção de todos os resultados pode constituir um cenário que se pretende evitar, dada a quantidade de informção que é disponibilizada e, deste modo, a vista geral deverá ser evitada.

As funções de tabela são a alternativa óbvia. Para além de poderem implementar uma espécie de vistas parametrizadas, permitem encapsular código PL/SQL bem mais complexo.

Antes de entrar em detalhes realtivamente às funções que retornem estruturas das quais é possível extrair colecções de registos, é conveniente estabelecer, em primeiro lugar, um pequeno contexto que servirá como modelo. Para o efeito, crie-se a tabela BOOKS

CREATE TABLE BOOKS
(
ID INT NOT NULL
, TITLE VARCHAR2(1024) NOT NULL
, EDITOR VARCHAR2(256) NOT NULL
, ISBN VARCHAR2(64) NOT NULL
, CONTENT_DETAILS CLOB
, CONSTRAINT TABLE1_PK PRIMARY KEY (ID) ENABLE
);

cujos registos representam livros na qual o campo CONTENT_DETAILS é do tipo CLOB e contém um fragmento de XML que define a estrutura dos capítulos. Este cenário, além de ser plausível numa situação que requeira a consideração de funções de tabela permite ainda dar uma pequena introdução ao XML em base-de-dados.

São inseridas duas linhas na tabela para efeitos de teste.

INSERT INTO BOOKS(
ID,
TITLE,
EDITOR,
ISBN,
CONTENT_DETAILS
) VALUES(
1,
'A passion that goes behind treason',
'Ed, the editor',
'1234567890857',
'
<genre>
Novel
</genre>
<synopsis>
This book is about...
</synopsis>
<chapter number="1">
<title>When they met</title>
</chapter>
<chapter number="2">
<title>Their happy moments as a family</title>
</chapter>
<chapter number="3">
<title>Treason happens</title>
</chapter>
<chapter number="4">
<title>Forgiveness</title>
</chapter>
<chapter number="5">
<title>They''re happy again</title>
</chapter>
'
);
COMMIT;
INSERT INTO BOOKS(
ID,
TITLE,
EDITOR,
ISBN,
CONTENT_DETAILS
) VALUES(
2,
'Animals go crazy',
'The editor: Ed',
'0987654321783',
'
<genre>
Satire
</genre>
<synopsis>
This fable tells a story of...
</synopsis>
<chapter number="1">
<title>The animals in the farm</title>
</chapter>
<chapter number="2">
<title>The pig is elected president</title>
</chapter>
<chapter number="3">
<title>Every one is equal as a pig</title>
</chapter>
<chapter number="4">
<title>Snoring is the new language</title>
</chapter>
<chapter number="5">
<title>Chicken is arrested because she can''t snore</title>
</chapter>
<chapter number="6">
<title>The uprising of the donkeys</title>
</chapter>
<chapter number="7">
<title>The return to anarchy</title>
</chapter>
'
);
COMMIT;

Após a inserção das duas linhas linhas, a consulta

SELECT
X.CHAPTER_NUMBER,
X.CHAPTER_TITLE
FROM BOOKS B
CROSS JOIN XMLTABLE(
'/chapter'
PASSING XMLPARSE(CONTENT B.CONTENT_DETAILS WELLFORMED)
COLUMNS
CHAPTER_NUMBER INTEGER PATH '@number',
CHAPTER_TITLE VARCHAR2(1024) PATH 'title/text()'
) X
WHERE B.ID = :1
;

permite obter os capítulos do livro cujo ID é dado pelo parâmetro :1.

Algumas palavras sobre a consulta anterior podem torná-la mais clara. A instrução XMLPARSE permite gerar uma instância de XML a partir da coluna CONTENT_DETAILS. A palavra WELLFORMED permite evitar que o XML seja validado. A instrução XMLTABLE permite mapear o resultado da aplicação de uma consulta XQuery num sistema relacional de linhas e colunas. Neste caso, é passada, por intermédio da instrução PASSING, o XML carregado a partir da coluna CONTENT_DETAILS. O campo de texto ‘/chapter’ consiste numa expressão XQuery que retorna todos os elementos chapter descendentes da raiz. A instrução COLUMNS permite definir as colunas. O número do capítulo é dado pelo atributo number que se obtém directamente de cada elemento definido pela XQuery e a segunda coluna obtém-se a partir do texto associado ao elemento descendente title.

O objectivo que agora se coloca consiste em definir uma função que permita obter os capítulos de um livro definido por algum ID. Uma primeira abordagem consiste em abrir um cursor para a consulta e retornar uma referência.

CREATE OR REPLACE FUNCTION GET_BOOK_CHAPTERS
(
BOOK_ID IN INT
) RETURN SYS_REFCURSOR AS
cur SYS_REFCURSOR;
BEGIN
OPEN cur FOR
SELECT
X.CHAPTER_NUMBER,
X.CHAPTER_TITLE
FROM BOOKS B
CROSS JOIN XMLTABLE(
'/chapter'
PASSING XMLPARSE(CONTENT B.CONTENT_DETAILS WELLFORMED)
COLUMNS
CHAPTER_NUMBER INTEGER PATH '@number',
CHAPTER_TITLE VARCHAR2(1024) PATH 'title/text()'
) X
WHERE B.ID = BOOK_ID;
RETURN cur;
END GET_BOOK_CHAPTERS;

Para extrair os registos apontados pelo cursor retornado pela função recorre-se a código definido num bloco PL/SQL.

DECLARE
cur_res SYS_REFCURSOR;
TYPE RECTYPE IS RECORD (CHAPTER_NUMB INTEGER, CHAPTER_TITLE VARCHAR2(1024));
val RECTYPE;
BEGIN
cur_res := GET_BOOK_CHAPTERS(:1);
LOOP
FETCH cur_res INTO val;
EXIT WHEN cur_res%NOTFOUND;
DBMS_OUTPUT.PUT_LINE(val.CHAPTER_NUMB || ' | ' || val.CHAPTER_TITLE);
END LOOP;
END;

De um modo geral, um cursor é obtido para os capítulos do livro identificado pelo ID com valor :1, é criado um ciclo no qual são obtidos sucessivamente os registos e o resultado é imprimido para a consola.

Identificam-se facilmente duas desvantagens neste método. A primeira, consiste no facto de que a obtenção dos registos a partir do cursor não se realiza por intermédio de SQL puro. A segunda, caracteriza-se pela dificuldade inerente ao cruzamento dos dados com os de outras tabelas.

A segunda dificuldade pode ser resolvida com a criação de uma tabela PL/SQL que pode ser incluída numa consulta de SQL puro. Neste caso, ao invés de se retornar o cursor, retorna-se uma tabela PL/SQL preenchida com os valores pretendidos. Para o efeito, é necessário definir, em primeiro lugar, o tipo de dados associados à tabela bem como a cada elemento.

CREATE OR REPLACE TYPE CHAPTER AS OBJECT( CHAPTER_NUMBER INTEGER, CHAPTER_TITLE VARCHAR2(1024));
CREATE OR REPLACE TYPE CHAPTERS_TABLE IS TABLE OF SERGIOMARQUES.CHAPTER;

A alteração da função anterior de modo a que seja retornada a tabela fica da seguinte forma.

CREATE OR REPLACE FUNCTION GET_BOOK_CHAPTERS_OBJ
(
BOOK_ID IN INT
) RETURN CHAPTERS_TABLE AS
cur SYS_REFCURSOR;
val1 INTEGER;
val2 VARCHAR2(1024);
tab CHAPTERS_TABLE;
rec CHAPTER;
i NUMBER := 1;
BEGIN
OPEN cur FOR
SELECT
X.CHAPTER_NUMBER,
X.CHAPTER_TITLE
FROM BOOKS B
CROSS JOIN XMLTABLE(
'/chapter'
PASSING XMLPARSE(CONTENT B.CONTENT_DETAILS WELLFORMED)
COLUMNS
CHAPTER_NUMBER INTEGER PATH '@number',
CHAPTER_TITLE VARCHAR2(1024) PATH 'title/text()'
) X
WHERE B.ID = BOOK_ID;
tab := CHAPTERS_TABLE();
LOOP
FETCH cur INTO val1, val2;
EXIT WHEN cur%NOTFOUND;
tab.EXTEND;
rec := CHAPTER(val1, val2);
tab(i) := rec;
i := i + 1;
END LOOP;
RETURN tab;
END GET_BOOK_CHAPTERS_OBJ;

Para executar a função anterior sobre o livro com ID dado por :1, é suficiente executar a seguinte consulta.

SELECT * FROM TABLE(GET_BOOK_CHAPTERS_OBJ(1));

Por seu turno, a grande vantagem deste tipo de funções consiste na possibilidade de ser executada para todos os livros numa única consulta sem a necessidade de proceder à criação explícita de um cursor.

SELECT
B.TITLE,
CHP.CHAPTER_NUMBER,
CHP.CHAPTER_TITLE
FROM BOOKS B
CROSS JOIN TABLE(SERGIOMARQUES.GET_BOOK_CHAPTERS_OBJ(B.ID)) CHP;

A consulta anterior permite consultar a tabela BOOKS e, para cada livro, obter a informação que define os capítulos. O operador TABLE permite manipular os elementos de uma colecção PL/SQL por intermédio de consultas SQL.

É possível simplificar a função anterior com o recurso à instrução BULK COLLECT que permite descarregar os resultados de uma consulta numa tabela PL/SQL.

CREATE OR REPLACE FUNCTION GET_BOOK_CHAPTERS_BULK
(
BOOK_ID IN INT
) RETURN CHAPTERS_TABLE AS
tab CHAPTERS_TABLE;
BEGIN
SELECT
CHAPTER(X.CHAPTER_NUMBER,X.CHAPTER_TITLE) AS REC
BULK COLLECT INTO tab
FROM BOOKS B
CROSS JOIN XMLTABLE(
'/chapter'
PASSING XMLPARSE(CONTENT B.CONTENT_DETAILS WELLFORMED)
COLUMNS
CHAPTER_NUMBER INTEGER PATH '@number',
CHAPTER_TITLE VARCHAR2(1024) PATH 'title/text()'
) X
WHERE B.ID = BOOK_ID;
RETURN tab;
END GET_BOOK_CHAPTERS_BULK;

Nenhuma diferença funcional existe entre as versões GET_BOOK_CHAPTERS_OBJ e GET_BOOK_CHAPTERS_BULK. A consulta

SELECT
B.TITLE,
CHP.CHAPTER_NUMBER,
CHP.CHAPTER_TITLE
FROM BOOKS B
CROSS JOIN TABLE(GET_BOOK_CHAPTERS_BULK(B.ID)) CHP;

permite obter os mesmos resultados que a sua contraparte.

Os principais inconvenientes desta abordagem advêm do facto de que a função só retorna os registos após a sua inserção num colecção em memória. No caso em que a quantidade de dados é elevada ou alguma transformação tenha de ser aplicada sobre os dados, é certo que o preencimento da totalidade da colecção poderá ser demorado. Para mitigar o problema entram em cena as funções canalizadas ou PIPELINED.

CREATE OR REPLACE FUNCTION GET_BOOK_CHAPTERS_PIPELINED
(
BOOK_ID IN INT
) RETURN CHAPTERS_TABLE PIPELINED PARALLEL_ENABLE AS
CURSOR cur IS
SELECT
CHAPTER(X.CHAPTER_NUMBER, X.CHAPTER_TITLE)
FROM SERGIOMARQUES.BOOKS B
CROSS JOIN XMLTABLE(
'/chapter'
PASSING XMLPARSE(CONTENT B.CONTENT_DETAILS WELLFORMED)
COLUMNS
CHAPTER_NUMBER INTEGER PATH '@number',
CHAPTER_TITLE VARCHAR2(1024) PATH 'title/text()'
) X
WHERE B.ID = BOOK_ID;
rec CHAPTER;
BEGIN
OPEN cur;
LOOP
FETCH cur INTO rec;
EXIT WHEN cur%NOTFOUND;
PIPE ROW(rec);
END LOOP;
CLOSE cur;
END;

Observe-se que a função é marcada como PIPELINED. Neste caso, cada registo é obtido de um cursor e despachado, por intermédio da instrução PIPE, para o cliente da função.

SELECT * FROM TABLE(GET_BOOK_CHAPTERS_PIPELINED(:1));

Quando a consulta é executada sobre a chamada da função, esta processa os registos à medida que são despachados pela instrução PIPE. Tal padrão, vulgarmente designado por Produtor/Consumidor, permite o respectivo tratamento por várias linhas de execução independentes, aumentando deste modo o grau de paralelismo. Se for pretendida a utilização de paralelismo, é necessário marcar a função como PARALLEL_ENABLE.

SELECT /*+ PARALLEL(B, 4) */
B.TITLE,
P.CHAPTER_NUMBER,
P.CHAPTER_TITLE
FROM SERGIOMARQUES.BOOKS B
CROSS JOIN TABLE(SERGIOMARQUES.GET_BOOK_CHAPTERS_PIPELINED(B.ID)) P;

Dada a sua flexibilidade, as funções canalizadas adequam-se ao desenvolvimento de procedimentos para transformação massiva de dados durante a sua transferência a partir da base-de-dados operacional.

Publicado em Sem categoria | Publicar um comentário

Um crivo de números primos

No texto Crivos de números primos descrevo um crivo de números primos diferente dos que conheço que me parece ser facilmente paralelizável. O estudo de crivos para números primos que levei a cabo foi motivado pelo problema da determinação do menor número primo superior a um determinado valor n de 64 bit cujo resultado é aplicável ao redimensionamento de um dicionário.

O crivo habitual parte do conjunto dos números naturais com excepção da unidade, isto é, de \mathbb{N}-\left\lbrace 1\right\rbrace e elimina os números compostos. Considera-se o número 2 e elminam-se todos os seus múltiplos. Ficamos com o conjunto formado pelo número 2 e pelos números ímpares

\left\lbrace 2,3,5,7,9,11,13,15,17,19,21,23,\cdots\right\rbrace

Considera-se o número seguinte, 3 e eliminam-se todos os seus múltiplos, ficando o conjunto

\left\lbrace 2,3,5,7,11,13,17,19,23,25,29,31\cdots\right\rbrace

O próximo número do conjunto será o 5. Eliminamos todos os seus múltiplos, advindo

\left\lbrace 2,3,5,7,11,13,17,19,23,29\cdots\right\rbrace

O processo continua indefinidamente. No entanto, é útil notar que, tendo sido eliminados os múltiplos de 1, 2, 3 e 5, todos os restantes números do conjunto inferiores a 7\times 7=49 são números primos. Esta propriedade resulta do facto de ser este número o primeiro múltiplo de 7 a ser removido no passo seguinte. Como é óbvio, apenas os múltiplos de 7 que não são múltiplos dos três números primos iniciais pertencem ao conjunto nesta etapa.

Em termos computacionais, dada a finitude da memória e tempo de processamento, torna-se prático um crivo de números primos limitados por um valor N predefinido. Um vector v com N entradas é criado e inicializado a 1. Faz-se v[1]=0 uma vez que a unidade não é considerada como número primo. Considera-se o índice seguinte, 2 e verifica-se que v[2]=1. Marcam-se a zero todas as entradas v[2i]. O próximo índice é 3 e v[3]=1. Marcam-se a zero todas as entradas de v[3i], com i\ge 3. O próximo índice é agora 4 mas, como v[4]=0, este número é composto e, portanto, é considerado o próximo índice 5. Como v[5]=1, este número é primo e faz-se v[5i]=0 para todos os valores de i\ge 5. O processo termina quando o índice k é tal que v[k]=1 e k^2\ge N.

Muitas optimizações podem ser aplicadas ao algoritmo anterior. Por exemplo, não é necessário marcar os múltiplos de 2 como sendo primos se considerarmos que o índice assume apenas valores ímpares. É possível construir um esquema de actualização do índice de modo que este evite passar por valores que sabemos serem compostos à partida. Por exemplo, se fizermos v[1]=0, v[4]=0 e inicializarmos o índice em 5, se o incremento do índice adquirir alternadamente os valores 2 e 4, este nunca irá incidir sobre os múltiplos de 2 ou 3. Tais esquemas baseiam-se no conceito de roda W_k e o algoritmo que propomos assenta sobre uma adaptação dessa mesma ideia.

Uma roda consiste no conjunto de números que são primos com \prod_{i=1}^{k}{p_i} onde p_i representa o i-ésimo número primo. Se designarmos por P_k=\prod_{i=1}^{k}{p_i}, é imediato concluir que o número de elementos em W_k é dado por \phi\left(P_k\right) onde \phi consiste na função totiente que, dada a natureza da factorização de P_k, vale

\phi\left(P\right)=\prod_{i=1}^{k}{\left(p_i-1\right)}

Por exemplo, se k=3 então P_3=2\times 3\times 5=30 e o número de elementos de W_3 é igual a 1\times 2\times 4=8. Os números primos com 30 são

W_3=\left\lbrace 1,7,11,13,17,19,23,29\right\rbrace

Definimos W_k^* como sendo o conjunto dos números w da forma w_i+rP_k com w_i\in W_k. Em conformidade com o exemplo anterior, é fácil de determinar

W_3^*={1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,\cdots}

É claro que, como 61=1+2\times 30 e 1\in W_3 então 61\in W_3^*. Denotamos por \mathscr{P} o conjunto dos números primos e \mathscr{P}_k é tal que

\mathscr{P}=\left\lbrace 2,3,\cdots, p_k\right\rbrace\cup\mathscr{P}_k

constituindo, com o conjunto dos primeiros k números primos, uma partição de \mathscr{P}. Não é difícil concluir que \mathscr{P}_k\subset W_k^* uma vez que este conjunto contém todos os números que não são divisíveis pelos primeiros k números primos. É possível, portanto, construir um crivo sobre W_k^* de modo a obter o conjunto \mathscr{P}_k, utilizando o mesmo princípio. De facto, parte-se do primeiro elemento de W_k^* e eliminam-se todos os seus múltiplos. Considera-se o elemento seguinte e eliminam-se todos os seus múltiplos. Continuando o procedimento, acabamos com o conjunto \mathscr{P}_k.

Do ponto de vista computacional, se recorrermos a um vector v para marcar os números primos e compostos, ser-nos-ia necessário obter uma relação que nos permitisse identificar os índices associados aos múltiplos de um determinado número. Mostramos no texto supracitado que os índices podem ser determinados com o auxílio de uma espécie de matriz de rodas. No entanto, descreveremos aqui brevemente uma adaptação desse procedimento.

Definimos W_k^{(w)} como sendo o conjunto

W_k^{(w)}=\left\lbrace x\in W_k^*\vert x\equiv w\ \text{mod}\ P_k \wedge w\in W_k\right\rbrace

isto é, como sendo o conjunto de todos os números congruentes a w\in W_k. É claro que

W_k^*=\bigcup_{w\in W_k}{W_k^{(w)}}

Os conjuntos W_k^{(w)} definem classes de equivalência cujos representantes designamos por [w] e as suas propriedades permitem-nos considerá-los como elementos do grupo multilicativo \mathbb{Z}_{P_k}^{\times}. Se [u] e [v] forem dois elementos, as respectivas classes de equivalência podem ser consideradas como sendo as sequências

[u]_i=u+iP_k,\qquad [v]_j=v+jP_k

onde i,j\ge 0. Então

[u]_i[v]_j=uw+\left(ju+iw+ijP_k\right)P_k

Se fizermos uw=[uw]+rP_k então temos

[u]_i[v]_j=[uw]+\left(r+ju+iw+ijP_k\right)P_k

Se considerarmos que os índices das sequências se iniciam em zero, então os números compostos em cada uma delas correspondem aos índices

r+ju+iw+ijP_k

Não sendo um número primo a unidade, é útil removê-la da sequência W_k^{(1)}, passando o seu representante a ser dado por \left[P_k+1\right]. Quando u=w=1, a expressão anterior altera-se em

1+r+ju+iw+ijP_k

De um modo geral, temos, para o índice m onde se encontra o produto [u]_i[v]_j o valor

m=\left\lbrace \begin{array}{l} 1+r+ju+iw+ijP_k,\qquad u=w=1\\ r+iu+jw+ijP_k,\qquad u\ne 1\vee w\ne 1 \end{array} \right.

Definimos os polinómios

\pi_{uw}(i,j)=\left(r_{uw}\right)_i+j\left(\delta_u\right)_i

e

\pi_{wu}(i,j)=\left(r_{wu}\right)_i+j\left(\delta_w\right)_i

onde

\left(r_{uw}\right)_i=\rho_{uw}+iw,\qquad \left(r_{wu}\right)_i=\rho_{uw}+iu,\\ \left(\delta_u\right)_i=u+iP_k,\qquad \left(\delta_w\right)_i=w+iP_k

quando u\ne w. Caso contrário, definidmos o polinómio

\pi_{uu}(i,j)=1+\rho_{uu}+iu+j\left(\delta_u\right)_i

onde

\rho_{uw}=\frac{uw-[uw]}{P_k}.

Como é óbvio, os índices m dos números compostos são dados pelos polinómios \pi(i,j). De modo a explorar as expressões anteriores, iremos crivar os números primos inferiores a 150, usando a roda W_2. Neste caso, P_2=6 e W_2=\left\lbrace 1,5\right\rbrace. As sequências a considerar, após remoção da unidade são da forma 5+6m e 7+6m, isto é,

[5]=\left\lbrack 5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149\right\rbrack

e

[7]=\left\lbrack 7,13,19,25,31,37,43,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145\right\rbrack

A tabela multiplicativa relativa ao grupo \mathbb{Z}_6^\times é da forma

[5] [7]
[5] [7] [5]
[7] [5] [7]

cujas entradas nos fornecem os vectores onde se encontram os respecitvos produtos. Temos ainda

\left(\delta_5\right)_0=5,\qquad \left(\delta_7\right)_0=7

bem como

\rho_{5,5}=3,\qquad \rho_{5,7}=5,\qquad \rho_{7,7}=7

Os índices dos múltiplos de 5 no vector [7] são dados por

\pi_{5,5}(0,j)=r_{5,5}+j\left(\delta_5\right)_0

Seguem-se daqui os índices, notando que r_{5,5}=\rho_{5,5},

\left\lbrack 3, 8, 13, 18, 23\right\rbrack

Por seu turno, os índices dos múltiplos de 5 no vector [5] são dados por

\pi_{5,7}(0,j)=r_{5,7}+j\left(\delta_5\right)_0

O cálculo dos índices permite-nos obter

\left\lbrack 5, 10, 15, 20, 25\right\rbrack

Do mesmo modo, os múltiplos de 7 nos vectores [5] e [7] encontram-se nos índices dados respectivamente pelas sequências

\left\lbrack 5, 12, 19\right\rbrack

e

\left\lbrack 7, 14, 21\right\rbrack

De facto, se marcarmos as entradas definidas pelas quatro sequências de índices obtemos

[5]=\left\lbrack 5,11,17,23,29,-,41,47,53,59,-,71,-,83,89,-,101,107,113,-,-,131,137,143,149\right\rbrack

e

[7]=\left\lbrack 7,13,19,-,31,37,43,-,-,61,67,73,79,-,-,97,103,109,-,121,127,-,139,-\right\rbrack

Para obtermos os índices dos múltiplos de 11 e 13 em ambos os vectores começamos por observar que 11\in [5] e 13\in [7], tendo ambos os índices 1. Calculamos

\left(\delta_5\right)_1=\left(\delta_5\right)_0+6=11

e, do mesmo modo,

\left(\delta_7\right)_1=\left(\delta_7\right)_0+6=13

Por seu turno,

r_{11,11}=r_{5,5}+5=8,\qquad r_{11,13}=r_{5,7}+7=12,\\ r_{13,11}=r_{7,5}+5=10,\qquad r_{13,13}=r_{7,7}+7=14

Ora, os índices dos múltiplos de 11 que se encontram no vector [7] são dados por

\pi_{5,5}(1,j)=r_{11,11}+j\left(\delta_5\right)_1

com j\ge 1, isto é,

\left\lbrack 19\right\rbrack

Por outro lado, índices dos múltiplos de 13 no vector [5] são dados por

\pi_{7,5}(1,j)=r_{13,11}+j\left(\delta_7\right)_1

com j\ge 1. Os cálculos permitem-nos concluir que o primeiro índice vale 10+13=23 e o segundo é igual a 36 que é superior ao tamanho do vector. Do mesmo modo se calcula o índice 23 como sendo o único associado ao múltiplo de 11 no vector [5]. O índice do primeiro múltiplo de 13 no vector [7] vale 27 que é superior ao tamanho do vector.

O procedimento continuaria do mesmo modo. Neste caso, os próximos índices são todos superiores aos tamanhos dos respectivos valores e o processo termina. Tem-se, após marcação dos íncies, os vectores

[5]=\left\lbrack 5,11,17,23,29,-,41,47,53,59,-,71,-,83,89,-,101,107,113,-,-,131,137,-,149\right\rbrack

e

[7]=\left\lbrack 7,13,19,-,31,37,43,-,-,61,67,73,79,-,-,97,103,109,-,-,127,-,139,-\right\rbrack

Note-se que, do ponto de vista de implementação, os vectores [5] e [7] seriam inicializados a 1 e as entradas marcadas com - teriam o valor 0. Não é complicado obter o valor associado ao índice. Por exemplo, no vector [7], a entrada indexada por 5 encontrar-se-ia marcada com o número 1. O seu valor seria dado por 7+5\times 6=37 como pode ser directamente verificado. De um modo geral, o valor associado ao índice m do vector [n] é dado por n+mP_k quando recorremos à roda W_k.

Publicado em Matemática | Etiquetas , , | Publicar um comentário

Aproximação racional das raízes de índice arbitrário de um número

Os resultados que se seguem estão detalhados no texto Aproximação de raízes de ordem arbitrária.

No artigo Aproximação racional de raízes apresentei a aproximação racional da raiz quadrada na forma

\sqrt{m}\frac{\left(m+\sqrt{m}\right)^{2^n}+\left(m-\sqrt{m}\right)^{2^n}}{\left(m+\sqrt{m}\right)^{2^n}-\left(m-\sqrt{m}\right)^{2^n}}\to\sqrt{m}

quando n\to+\infty. O famoso caso notável x^2-y^2=(x+y)(x-y) permite-nos escrever

x^{2^n}-y^{2^n}=\left(x^{2^{n-1}}+y^{2^{n-1}}\right)\left(x^{2^{n-1}}-y^{2^{n-1}}\right)

Por seu turno,

x^{2^{n-1}}-y^{2^{n-1}}=\left(x^{2^{n-2}}+y^{2^{n-2}}\right)\left(x^{2^{n-2}}-y^{2^{n-2}}\right)

A aplicação recursiva da identidade resulta em

x^{2^n}-y^{2^n}=(x-y)\prod_{k=0}^{n-1}{\left(x^{2^k}+y^{2^k}\right)}

Segue-se daqui que

\sqrt{m}\frac{\left(m+\sqrt{m}\right)^{2^n}+\left(m-\sqrt{m}\right)^{2^n}}{\left(m+\sqrt{m}\right)^{2^n}-\left(m-\sqrt{m}\right)^{2^n}}=\frac{1}{2}\frac{\left(m+\sqrt{m}\right)^{2^n}+\left(m-\sqrt{m}\right)^{2^n}}{\prod_{k=0}^{n-1}{\left\lbrack\left(m+\sqrt{m}\right)^{2^k}+\left(m-\sqrt{m}\right)^{2^k}\right\rbrack}}

Resta mostrar que qualquer expressão da forma

\left(m+\sqrt{m}\right)^{2^n}+\left(m-\sqrt{m}\right)^{2^n}

não depende de \sqrt{m}. Com efeito,

\left(m+\sqrt{m}\right)^{2^n}+\left(m-\sqrt{m}\right)^{2^n}=\left\lbrack\left(m+\sqrt{m}\right)^{2^{n-1}}+\left(m-\sqrt{m}\right)^{2^{n-1}}\right\rbrack^2-2\left(m^2-m\right)^{2^n}

Como \left(m+\sqrt{m}\right)^{2^0}+\left(m-\sqrt{m}\right)^{2^0}=2m não depende de \sqrt{m}, o método da indução permite concluir o resultado.

Apesar da demonstração apresentada anteriormente se basear na aplicação iterada das médias aritmética e harmónica, é útil discutir uma construção alternativa. Com efeito, sejam p_n e q_n duas sucessões definidas pela fórmula

p_{n}+q_{n}\sqrt{m}=\left(k+l\sqrt{m}\right)^{2^n}

onde k e l são números inteiros positivos ou, quanto muito, racionais positivos. Não é difícil concluir que

p_n-q_{n}\sqrt{m}=\left(k-l\sqrt{m}\right)^{2^n}

De facto, vale a recursão

p_{n+1}+q_{n+1}\sqrt{m}=\left(p_n+q_n\sqrt{m}\right)^2

com p_1=k e q_1=l.
Daqui obtemos

p_{n+1}-q_{n+1}\sqrt{m}=\left(p_n-q_n\sqrt{m}\right)^2

A aplicação recursiva da fórmula permite concluir o resultado.

A soma e a subtracção de ambas as equações proporciona as identidades

\left\lbrace \begin{array}{l} p_n=\frac{\left(k+l\sqrt{m}\right)^{2^n}+\left(k-l\sqrt{m}\right)^{2^n}}{2}\\ q_n=\frac{\left(k+l\sqrt{m}\right)^{2^n}-\left(k-l\sqrt{m}\right)^{2^n}}{2\sqrt{m}} \end{array} \right.

O quociente das funções resulta na fórmula mais geral

\frac{p_n}{q_n}=\sqrt{m}\frac{\left(k+l\sqrt{m}\right)^{2^n}+\left(k-l\sqrt{m}\right)^{2^n}}{\left(k+l\sqrt{m}\right)^{2^n}-\left(k-l\sqrt{m}\right)^{2^n}}

A identidade anterior pode ser escrita como

\frac{p_n}{q_n}=\sqrt{m}\frac{1+N^{2^n}}{1-N^{2^n}}

onde

N=\frac{k-l\sqrt{m}}{k+l\sqrt{m}}

Como N^{2^n}\to 0 quando n\to +\infty, segue-se que, no mesmo limite de n, se tem

\frac{p_n}{q_n}\to\sqrt{m}

como era pretendido. Determinámos uma família de aproximações racionais para a raiz quadrada de m. A aproximação é tanto melhor quando o valor da fracção \frac{k}{l} mais próximo se encontre de \sqrt{m}.

Este método presta-se à generalaização a raízes de índices superiores. Apresentar-se-á aqui um método para a determinação da aproximação racional da raiz cúbica de m que pode ser generalizado aos casos de índices superiores. Fazemos \omega=\sqrt[3]{m} e denotamos por \alpha uma raiz cúbica da unidade diferente de 1, isto é, um número que satisfaça \alpha^2+\alpha+1=0, de tal forma que qualquer outra raiz da unidade se possa escrever como \alpha^k para algum k. Definimos as sequências p_n, q_n e r_n por intermédio da recorrência

\left\lbrace \begin{array}{l} p_1=i\\ q_1=j\\ r_1=k\\ p_{n+1}+q_{n+1}\omega+r_{n+1}\omega^2=\left(p_{n}+q_{n}\omega+r_{n}\omega^2\right)^3 \end{array} \right.

onde i, j e k são números inteiros positivos. Como \alpha é uma raiz da unidade, facilmente se mostram as identidades

\left\lbrace \begin{array}{l} p_{n+1}+q_{n+1}\alpha\omega+\alpha^2r_{n+1}\omega^2=\left(p_{n}+q_{n}\alpha\omega+r_{n}\alpha^2\omega^2\right)^3\\ p_{n+1}+q_{n+1}\alpha^2\omega+r_{n+1}\alpha\omega^2=\left(p_{n}+q_{n}\alpha^2\omega+r_{n}\alpha\omega^2\right)^3 \end{array} \right.

A aplicação recursiva das identidades anteriores permite-nos obter

\left\lbrace \begin{array}{l} p_n+q_n\omega+r_n\omega^2=\left(i+j\omega+k\omega^2\right)^{3^n}\\ p_n+q_n\alpha\omega+r_n\alpha^2\omega^2=\left(i+j\alpha\omega+k\alpha^2\omega^2\right)^{3^n}\\ p_n+q_n\alpha^2\omega+r_n\alpha\omega^2=\left(i+j\alpha^2\omega+k\alpha\omega^2\right)^{3^n} \end{array} \right.

Se somarmos as equações, multiplicando convenientemente por potências de \alpha, podemos escrever

\left\lbrace \begin{array}{l} p_n=\frac{\left(i+j\omega+k\omega^2\right)^{3^n}+\left(i+j\alpha\omega+k\alpha^2\omega^2\right)^{3^n}+\left(i+j\alpha^2\omega+k\alpha\omega^2\right)^{3^n}}{3}\\ q_n=\frac{\left(i+j\omega+k\omega^2\right)^{3^n}+\alpha^2\left(i+j\alpha\omega+k\alpha\omega^2\right)^{3^n}+\alpha^2\left(i+j\alpha^2\omega+k\alpha\omega^2\right)^{3^n}}{3\omega}\\ r_n=\frac{\left(i+j\omega+k\omega^2\right)^{3^n}+\alpha\left(i+j\alpha\omega+k\alpha^2\omega^2\right)^{3^n}+\alpha^2\left(i+j\alpha^2\omega+k\alpha\omega^2\right)^{3^n}}{3\omega^2} \end{array} \right.

Mostramos que, quando n\to +\infty, temos

\frac{p_n}{\omega q_n}\to 1

e

\frac{q_n}{\omega r_n}\to 1

Para mostrá-lo, observamos que, sendo \alpha um número complexo, temos \bar{\alpha}=\alpha^2 para seu conjungado. Assim,

\left\vert x+\alpha y+\alpha^2z\right\vert^2=\left(x+\alpha y+\alpha^2z\right)\left(x+\alpha^2y+\alpha z\right)

Um pouco de álgebra permite concluir a identidade

\left\vert x+\alpha y+\alpha^2z\right\vert^2=x^2+y^2+z^2-2(xy+xz+yz)

Do mesmo modo se calcula

\left\vert x+\alpha^2 y+\alpha z\right\vert^2=x^2+y^2+z^2-2(xy+xz+yz)

Sendo positivos os valores i, j e k, segue-se das identidades anteriores que

\left\vert i+j\omega+k\omega^2\right\vert>\left\vert i+j\alpha\omega+k\alpha^2\omega^2\right\vert

e

\left\vert i+j\omega+k\omega^2\right\vert>\left\vert i+j\alpha^2\omega+k\alpha\omega^2\right\vert

Usamos a abreviação

N_1=\frac{i+j\alpha\omega+k\alpha^2\omega^2}{i+j\omega+k\omega^2}

e

N_2=\frac{i+j\alpha^2\omega+k\alpha\omega^2}{i+j\omega+k\omega^2}

Da desigualdade anterior sobre os módulos concluímos que \left\vert N_1\right\vert<1 e \left\vert N_2\right\vert<1. Então, tanto \left(N_1\right)^{3^n}\to 0 como \left(N_2\right)^{3^n}\to 0 quando n\to+\infty.

Segue-se daqui que

\frac{p_n}{\omega q_n}=\frac{1+N_1^{3^n}+N_2^{3^n}}{1+\alpha N_1^{3^n}+\alpha^2 N_2^{3^n}}\to 1

e

\frac{q_n}{\omega r_n}=\frac{1+N_1^{3^n}+N_2^{3^n}}{1+\alpha^2N_1^{3^n}+\alpha N_2^{3^n}}\to 1

quando n\to +\infty, como pretendíamos.

Não é difícil verificar que p_n, q_n e r_n são números reais, observando que os valores coincidem com os respectivos conjugados. Além disso, segue-se das fórmulas de recorrência que se tratam de funções que não dependem de \omega, isto é, de \sqrt[3]{m}. Então, a expressão

\sqrt{m}\frac{\left(i+j\omega+k\omega^2\right)^{3^n}+\left(i+j\alpha\omega+k\alpha^2\omega^2\right)^{3^n}+\left(i+j\alpha^2\omega+k\alpha\omega^2\right)^{3^n}}{\left(i+j\omega+k\omega^2\right)^{3^n}+\alpha^2\left(i+j\alpha\omega+k\alpha\omega^2\right)^{3^n}+\alpha^2\left(i+j\alpha^2\omega+k\alpha\omega^2\right)^{3^n}}

constitui uma aproximação racional de \sqrt[3]{m}.

Publicado em Matemática | Etiquetas , | Publicar um comentário