Este artigo foi traduzido por máquina.

Numéricos

Testando as funções matemáticas no Microsoft Cloud Numerics

Stuart Brorson
Alan Edelman
Ben Moskowitz

Suponha que você precisa realizar um cálculo matemático. Por exemplo, suponha que você precisa saber o seno de 34 °. O que fazer? Você provavelmente virar uma calculadora, computador ou outro dispositivo inteligente. No seu dispositivo, você digita "sin(34)" e você receber uma resposta, muitas vezes com 16 dígitos decimais de precisão. Mas como você sabe que sua resposta está correta?

Estamos tão acostumados a receber respostas matemáticas de nossos aparelhos eletrônicos que ninguém pensa sobre se as respostas estão corretas! Apenas sobre todos leva-lo para concedido que nossas máquinas nos dar as respostas certas. No entanto, para um pequeno conjunto de engenheiros de qualidade de software, correção não pode ser tomada para concedido; o trabalho é toda sobre começar a resposta certa. Este artigo explica como as funções matemáticas na nova biblioteca matemática Microsoft nuvem numéricos são testadas.

Mais cálculos científicos e de engenharia usam aritmética de ponto flutuante. O IEEE padronizado o funcionamento básico de matemática de ponto flutuante em 1985. Uma característica chave da norma é que não reconhece que todos os números podem ser representados em um computador. Enquanto o conjunto dos números reais é infinito e incontável, o conjunto de números de ponto flutuante do IEEE é necessariamente finito e contáveis porque a representação numérica de números de ponto flutuante usa um número fixo de bits. A construção de números de ponto flutuante IEEE implica que eles também são números racionais, tão comumente usados como π não são expressos exatamente e operações de usá-los, tais como Sen (x), não são exatas,.

Além disso, ao contrário com inteiros, o espaçamento entre números de ponto flutuante do IEEE é localmente uniforme, mas aumenta logaritmicamente com a magnitude do número propriamente dito. Este aspecto logarítmico é retratado em Figura 1, que mostra esquematicamente as localizações dos pedaços uniformes de números de ponto flutuante do IEEE na linha de número real. Na figura, válidos pedaços de números de ponto flutuante (incorporados na linha de número real) são indicados por linhas verticais. Observe que a distância entre os números de ponto flutuante válidos aumenta logaritmicamente da magnitude de x aumenta. A distância entre dois números de ponto flutuante adjacentes é chamada frequentemente a unidade de menor precisão ou unidade em último lugar (ULP) e é fornecida como uma função interna chamada eps(x) em muitos programas comuns de matemática. Uma consequência da variação no espaçamento é que um número pequeno perto de 0 não tem efeito quando adicionado a um número relativamente maior como 1.

Figura 1 grade ponto flutuante número representada esquematicamente

Além de codificar formatos de números de ponto flutuante, o padrão IEEE fornece orientação estrita sobre quão preciso os retornos das operações fundamentais de matemática devem ser. Por exemplo, o padrão IEEE especifica que os retornos das quatro operações aritméticas (+, -, * e /) deve ser "melhor arredondada," que significa que a resposta retornada deve ser mais próximo para o resultado "matematicamente correto". Embora este requisito foi originalmente reuniu-se com alguma resistência, retornando o resultado best-rounded agora tem lugar no hardware, mostrando como banal tornou-se. Mais interessante, a especificação de ponto flutuante IEEE também requer que a função raiz quadrada retornar o resultado best-rounded. Isso é interessante porque ele abre a porta a duas perguntas: "Exatamente como pode uma função irracional ser computada usando a representação de ponto flutuante IEEE?" e "Como você deve testar a precisão de uma implementação da função?"

Funções precisas de computação

Que fatores ir para determinar a precisão de um cálculo? A realidade é que devemos esperar encontrar imprecisões, como arredondamento pode ocorrer em qualquer etapa de um algoritmo. Esses erros podem composto, embora às vezes eles também podem cancelar. Na prática, um desenhador do algoritmo deve aprender a viver com e conter a imprecisão inerente de computações numéricas.

Você pode separar os factores que contribuem para o erro computacional em duas categorias:

1. Factores relacionados com o algoritmo usado para executar o cálculo. Em particular, isto significa a estabilidade do algoritmo de si mesmo e sua sensibilidade para arredondar erros. Um algoritmo de pobre, instável tendem a retornar resultados menos precisos, enquanto um algoritmo estável, boa retornará resultados mais precisos.
2. A natureza intrínseca da própria função e o domínio das suas entradas. Há um limite teórico para a precisão alcançável de qualquer implementação de função quando computação usa um número finito (ao contrário de um infinito) de bits. A razão é que arredondar age como uma fonte de erro no cálculo, e o comportamento da própria função determina se esse erro é amplificado ou atenuado como o cálculo do produto de entradas às saídas. Por exemplo, calcular os valores de uma função perto de uma singularidade, um zero ou uma oscilação rápida pode ser menos precisa aqueles pontos que a computação de uma função que varia lentamente sobre o mesmo domínio de entrada. Ao falar sobre esta precisão intrínseca atingível, falamos de como a função "bem condicionado" é.

Assim, testar a precisão de uma implementação da função envolve verificar que o algoritmo retorna resultados tão fiel como teoricamente possível. Os limites da possibilidade teórica são estabelecidos pelo condicionamento da função em cada uma das suas entradas. Para colocá-lo uma outra maneira, usando números de ponto flutuante para calcular um resultado apresenta duas possíveis fontes de erro: Erros que podemos evitar usando boa, estável, algoritmos (fator 1), e erros que são mais difíceis de evitar, porque eles estão relacionados com o comportamento da função em suas entradas (fator 2).

Em análise numérica, o conceito de condicionamento é quantificado pelo chamado "número de condição", que mede a sensibilidade de uma função para variações em suas entradas. Dependendo da natureza exata da função em causa (por exemplo, o número de entradas, escalares versus matriz e assim por diante), há uma série de expressões complicadas para o número de condição. O caso mais simples é para uma função diferenciável de uma variável, como 1 / x, x 2, Sen (x) ou qualquer uma das outras funções você provavelmente encontrou em álgebra da high school. Este simples caso o número de condição da função f é dada por:

Equação 1

Vou referir-se a isso mais tarde como equação 1. Como sempre, a notação f'(x) significa que a derivada da função f. Um número grande de condição (Kf >> 1) indica alta sensibilidade à perturbações relativas, Considerando que a condição de um pequeno número (Kf < = 1) indica que a função é relativamente insensível a perturbações. Intuitivamente, você pode ver que se uma função tem uma singularidade — isto é, a função explode, tais como 1 / x perto x = 0 — a derivada vai capturar esse efeito e retornar um número grande de condição.

Por exemplo, considere a função f (x) = 1/(1-x). Obviamente esta função explode (ou seja, se torna infinita) no x = 1. A derivada é f'(x) = 1 /(1-x) 2. Ligar esta equação 1 e eliminando termos dão o número de condição para esta função:

O número de condição Kf*(x)* vai para infinito em torno de x = 1, que significa que os cálculos envolvendo esta função será sensíveis a perturbações como erro de arredondamento quando x está perto de 1. Porque f sopra para x → 1, esse comportamento é esperado. Além disso, o número de condição Kf (x) vai para 0 quando x está perto de 0. Isso indica que os cálculos usando essa função será insensíveis a perturbações quando x → 0. Isso faz sentido intuitivo porque f tende a um valor constante de 1 quando x é muito menor do que 1.

Teste de precisão de função

Assim, o que faz um teste prático de um função matemática parecido? Suponha que queremos testar nossa implementação de função escalar y = f (x), onde x é a entrada e y é o valor de saída retornados. Dado um valor de ponto flutuante de entrada x, teste requer três itens:

1. O valor calculado pela função sob teste, ycalculado = fcalculado*(x)*.
2. O resultado "matematicamente verdadeiro". Suponha que nós tivemos um oráculo que poderia nos dizer a resposta exata, matematicamente correta. Depois volta a esse valor para o mais próximo do valor de ponto flutuante (assim pode ser representado em um computador). Chamar esse valor ytrue = ftrue*(x)*.
3. Uma teste de tolerância. Para algumas funções, esta tolerância pode ser 0, que significa que ycomputed é exatamente o mesmo que o valor matematicamente verdadeiro, ytrue. Por exemplo, a especificação de ponto flutuante exige que a função sqrt () retorna o valor de ponto flutuante que se encontra mais próximo a resposta exata (isto é, best-rounded). Em geral, no entanto, não podemos esperar o retorno de todas as funções para ser as aproximações best-rounded seus valores exatos. Portanto, a teste de tolerância deve incorporar informações sobre quanto erro é permitido o retorno de f. Nota que a tolerância pode depender de detalhes da função f, bem como o valor exato da entrada, x.

Com estes ingredientes, a precisão de nossa implementação de função é considerada aceitável (isto é, ele passa o nosso teste) se

| ycomputed* - ytrue | < Tol (f; x),*

onde a tolerância depende de ambos sobre o valor de entrada x e o comportamento da função f si.

Em palavras, esta equação diz que a função passa o teste se o valor retornado difere o valor "verdadeiro" por uma quantidade menor do que o teste tolerância (erro permitido). Note-se que | ycomputed* - y*true | é o erro absoluto da função computada.

Neste formalismo, um teste de função é executado, criando um grande número de valores de entrada, encontrando-se no domínio de entrada da função, executando esses valores através da função sob teste e comparando a função produz ycalculado contra os valores (matematicamente verdadeiros) best-rounded, yverdadeiro. Os valores das entradas devem ser escolhidos para cobrir todas as partes relevantes do domínio válido de entrada da função.

Neste ponto, o testador tem duas perguntas a responder: O que é o "verdadeiro" resultado de uma função? e qual é a razoável tolerância?

Para responder a primeira pergunta, a melhor coisa a fazer é usar um pacote de matemática "precisão infinita" para criar os pares de entrada/saída usados para teste. Este pacote não usa números de ponto flutuante de 32 - ou 64-bit para calcular um valor. Em vez disso, ele usa uma representação numérica — ou melhor ainda, uma representação simbólica — um número que pode levar a capacidade de calcular um número arbitrariamente grande de dígitos por meio de computação em detrimento da velocidade computacional. Vários pacotes disponíveis comercialmente matemática implementam matemática precisão infinita. Além disso, muitas bibliotecas de matemática precisão infinita podem ser encaixadas no línguas comuns. A capacidade de usar a matemática precisão infinita em velocidades modernas é uma inovação recente, tornando esse tipo de teste conveniente. Qualquer um desses recursos é suficiente para criar pares chamados "valor dourado" útil para testar a implementação de ponto flutuante de uma função.

Colocá-lo juntos — ficando a teste de tolerância

Uma vez que temos valores dourados, precisamos responder a outra pergunta: O que é uma tolerância razoável de teste? A tolerância de teste correta é o componente crítico do teste. Se a tolerância é anormalmente pequena, a função nunca passará seu teste, mesmo se o melhor algoritmo usado para calcular isso. Por outro lado, se o teste de tolerância é muito grande, isso significa que o erro permitido é maior do que ele precisa ser, e a função vai passar no teste, mesmo se o algoritmo está com defeito.

O número de condição definido anteriormente é a chave para determinar o erro aceitável permitido nos testes de função. A expressão para o número de condição pode ser rearranjada para ler:

Equação 2

Vou referir-se a isso mais tarde como equação 2. Se identificarmos ∆x como a distância entre um número de ponto flutuante e o próximo, esta expressão nos diz quanto a saída de f vai saltar como passamos de um número de ponto flutuante x a seu vizinho, x + ∆x. Tradicionalmente, o campo de caracteres alfanuméricos de computador leva para ∆x a função eps(x), o espaçamento entre quaisquer dois números de ponto flutuante adjacentes. Observe que porque o espaçamento da grade é não constante (ver Figura 1), eps(x) é uma função de x. (Conforme mencionado anteriormente, a distância entre um número de ponto flutuante e seu vizinho mais próximo está também relacionada com uma ULP — a magnitude representada pelo bit menos significativo.)

Em seguida, exigimos que o erro de saída em nosso teste, ycalculado -yverdadeiro, ser menos de algum múltiplo deste salto. Ou seja, pedimos que, onde C é uma constante:

Intuitivamente, essa expressão capta a seguinte ideia: Se x faz uma etapa da grelha flutuante, a mudança na saída deve ser superior a equação 2. Uma função exata f vai mudar a sua saída, apenas a quantidade derivada do número de condição e não mais. Portanto, saída perturbações que ocorrem durante o cálculo de f deve ser menor do que a alteração causada pelo uso de uma etapa da grelha de ponto flutuante. A constante C é um "fator de correção". Obviamente, como C aumenta, aumenta a tolerância permitida com ele. Portanto pode interpretar esta constante como o erro permitido funcional sobre o mínimo teórico. Em testes reais, C toma valores inteiros entre 1 e 10, que interpretamos como o erro permitido, expressado em ULPs.

Finalmente, usando a definição do número de condição, nós pode reorganizar a equação de uma forma que expõe a tolerância de teste:

| ycalculado -ytrue | ≤ C | f'(x) | eps(x) = tolerância

Este é o nosso teste desejado — é a expressão que deve ser atendida por uma implementação exata da função f para qualquer entrada x. Em outras palavras, esta é a expressão usada para validar funções matemáticas escalar. Observe que esta expressão deve prender verdadeira para todos os valores de entrada válidos x.

A pergunta final para ser resolvido é: "qual é o valor correto de C usar em testes?" Porque podemos interpretar C como o número de erros ULP permitidos, C é um número inteiro de ordem 1. Vamos definir C , iniciando com uma inicial C valor (normalmente 10) e a execução do teste. Se o teste passar, diminuir C 1 e executar o teste novamente. Repita este procedimento para diminuir C valores até que o teste falhar. Em seguida, escolha o valor de C que última permitiu o teste passar (mas mantenha sempre um ser humano no laço para garantir a razoabilidade). O objetivo deste processo é fechar a porta para passar, tanto quanto possível (enquanto ainda permitindo a função para passar no teste) então você pode ter certeza que a função é testada rigorosamente quanto possível. Funções bem comportadas tipicamente requerem C valores entre 1 e 3, mas funções mais complicadas podem exigir maior C valores para passagem. Encontramos que exigem poucas implementações de função C > 10 para passar, e quando encontramos uma função que requer C > 10, ele muitas vezes sinais de uma implementação de qualidade inferior.

Da perspectiva de teste de software, uma vez C é determinado para teste da função (e passa a teste), sabemos que qualquer falha no teste subseqüentes significa que algo na função de implementação é alterado — provavelmente para pior (por exemplo, ocorreu uma regressão). Claro, trade-offs em projeto de algoritmo podem ditar que vale a pena dar alguma folga no C se a regressão é pequena (por exemplo, uma velocidade versus troca de precisão). Da mesma forma, depois de melhorar um algoritmo, vale a pena ver se C pode ser ainda mais apertado. Em qualquer caso, um trabalho de teste de software torna-se gerenciar as tolerâncias de testes como o resto do software é desenvolvido.

Valor teste ouro e além

A metodologia de testes que discutimos até agora, temos usado pré-computadas pares de entrada/saída, espalhados em todo o domínio de entrada da função sob teste. Chamamos este tipo de teste valor ouro testes, significando que o oráculo de teste de precisão infinita oferece ouro pares de entrada/saída que são conhecidas por serem altamente precisos. Os pares podem ser armazenados em um arquivo e ler o programa de teste quando ele é executado. Como um método de caixa-preta para testar a exatidão funcional, esta abordagem funciona muito bem. No entanto, outros tipos de testes de função também fornecem maneiras importantes para validar o comportamento da função. Outros testes incluem:

• Valor especial de teste: Muitas funções retornam conhecidas, exata teórica valores para determinadas entradas, tais como cos(0) = > 1, sin(π) => 0 e gamma(1/2) = √π, para exemplos. Em um teste de valor especial, conhecidas entradas fixas são alimentadas para a função de teste, e o retorno da função é comparado com o resultado conhecido. Claro, porque os números irracionais como π não se encontram exatamente na grelha de ponto flutuante, a aproximação a esses números ponto flutuante deve ser usada no teste e um valor non-zero para seno e teste de tolerância (como calculado anteriormente) é usado para validar os resultados computacionais.
• Testes de identidade: Muitas funções obedecem as identidades que são verdadeiras para todas as entradas sobre um domínio conhecido. Por exemplo, sin (x) ^ 2 + cos (x) ^ 2 = = 1 para todas as entradas x. Outro é o arcsin(x) = = -i log (i * x + sqrt (x 2-1)). A diferença entre um ensaios de identidade e um valor especial é que o teste de identidade é verdadeiro para entrada arbitrária, Considerando que o teste de valor especial só vale para um determinado valor de entrada. Como conseqüência, testes de identidade validam as relações entre funções.

Você deve ter cuidado com testes de identidade. Por um lado, algumas identidades estão mal condicionadas. Por exemplo, resultados intermediários podem crescer para ser muito grande, mesmo que o resultado final é de tamanho moderado. Neste caso, pequenos, admissíveis erros ocorridos durante as etapas intermediárias no cálculo podem causar falhas de teste espúrias. Além disso, muitas funções (por exemplo, as funções trigonométricas inversas) têm vários valores no plano complexo. Cegamente usando testes de identidade pode causar falhas de teste espúrios quando os lados de left e right hand da identidade retornam valores corretos, encontrando-se em diferentes folhas de Riemann no plano complexo. O testador deve cuidadosamente artesanato identidade testes para evitar esses dois problemas.

• Teste inversa: Isso envolve uma função composta com sua inversa e verificar o resultado é o mesmo que a entrada para o teste de computação. Por exemplo, para o positivo x podemos testar log(exp(x)) = x. Você pode pensar nisso como um caso especial de testes de identidade, e de fato é. No entanto, porque tantas funções inversas — e consistência matemática exige que uma função composta com seu retorno inverso a entrada original — usamos uma categoria distinta de teste para validar que funciona e suas inversas se comportam de forma consistente. As advertências do mesmas que aplicam testes de identidade (como condicionado ou retorna, encontrando-se em diferentes folhas de Riemann) também aplicam testes inversa.
• Série soma de teste: Quase todas as funções transcendentais admitem uma expansão da série sobre algum domínio de entrada. No teste de soma de série, vamos comparar o valor retornado pela função sob teste ao valor retornado por uma série de explicitamente resumiu no teste. Você pode considerar soma de série, como um tipo de teste de identidade. No entanto, as considerações que vai para a criação de um teste de soma boa série são semelhantes em funções (por exemplo, critérios de estabilidade e de convergência). Por isso, consideramos esse tipo de teste conceitualmente diferente do teste de identidade.
• Expansões de fração contínua: Algumas funções também podem ser avaliadas sobre um domínio conhecido usando uma fração contínua expansão. Quando existe tal expansão, podem convergir muito mais rapidamente do que uma soma de série. Portanto, para determinadas funções, o teste de soma de série pode ser substituído por uma fração contínua expansão.
• Valor calculado teste (também conhecido como modelo-com base em testes): Teste de valor calculado, você criar uma implementação simples, verificável correta da função dentro do teste propriamente dito. Esse tipo de teste não necessariamente se aplica para funções escalares de matemática. No entanto, um pacote bom matemática não se limita ao conjunto de funções analíticas. Por exemplo, considere funções como piso, teto, mod, operadores de concatenação para vetores e assim por diante. Cada uma dessas funções pode ser testada por escrever código que implementa a função usando construções de linguagem básicas do computador. Por exemplo, piso, teto e o chop numérico várias funções podem ser modeladas usando operadores de conversão que converter o valor de ponto flutuante para um número inteiro e, em seguida, converter o resultado de volta para um float (com alguma matemática simples realizada para imitar o comportamento exato da função em causa). Uma vantagem deste tipo de teste é que a implementação do modelo é normalmente trivial e é, portanto, pode ser verificada pela inspeção.
• Teste de erro: Estes testes certifique-se de que a entrada inválida é tratada corretamente, retornando um erro limpo que permite que um programador claramente e rapidamente entender o problema. Por exemplo, ao trabalhar em números reais, sqrt deve retornar um erro útil (ou NaN) se x < 0. Alguns erros de entrada são conhecidos por travar o computador se eles não são tratados adequadamente, e trabalho do testador é para se certificar de que isso não ocorre.

O benefício desses tipos de testes é que eles fornecem uma verificação cruzada de correção da função usando somente a matemática própria. Porque esses métodos usam a self-consistência da matemática como base de testes, eles são "bem conhecidos" e não dependem de cálculos numéricos usando software de terceiros.

Validar a abordagem

Uma maneira de apreciar a vantagem das tolerâncias números de condição é examinar as tolerâncias usadas para validar as funções escalares matemática que têm singularidades em seus domínios de entrada. Por exemplo, tan comum de funções trigonométricas e berço são singulares em um número infinito de pontos ao longo da linha de número real. Se fixa, constantes tolerâncias foram usadas para validação de precisão, essas funções falharia seus testes para valores de entrada de perto as singularidades ou as tolerâncias testes necessariamente seria tão grandes que os testes não seriam eficazes. Com tolerâncias números de condição, nós pode validar as funções escalares para dentro de um pequeno punhado de ULPs sobre todo o domínio de entrada da função. Mostrado no Figura 2 são exemplos de passar valores ULP que encontramos durante a qualificação de funções distribuídas no produto Microsoft nuvem numéricos. Ou seja, estes são os valores ULP, em que a função correspondente passa seu teste.

Figura 2 passando valores ULP

A conclusão a tirar os exemplos Figura 2 é que as funções especiais são implementadas usando algoritmos que são precisos para dentro de um pequeno número de ULPs. O pior dos casos apresentados em Figura 2 tem um erro menor que 6 ULPs, que corresponde ao log10(2^6) = 1,8 dígitos decimais de erro no dígitos do número de ordem mais baixa. Para uma dupla de ponto flutuante, isto corresponde a um erro relativo de 1.3323e-015.

Estado-da-arte de teste

Para rever, uma rigorosa metodologia de testes foi aplicada com êxito à validação dos algoritmos utilizados nos pacotes Microsoft nuvem numéricos matemática. Usar testes tolerâncias derivadas de número de condição da função permitiu-nos identificar e implementações de função incorreta correta, mesmo quando os erros ocorreram somente nos últimos poucos dígitos da função retorna. Tolerâncias de testes fixas não podem fornecer um teste rigoroso que também não causa falsas falhas (como singularidades perto de função). A maioria dos nossos testes envolvidos usando valores de entrada/saída de ouro valor são pré-computadas infinita precisão matemática de pacotes e, em seguida, armazenados em arquivos que são lidos no tempo de teste. Além de usar valores de ouro, também realizamos controlos cruzados em nossas implementações de função usando uma variedade de identidades diferentes matemática para validar o comportamento das nossas funções.

Acreditamos que os usuários do Microsoft Cloud numéricos podem usar seu conjunto de funções de biblioteca de matemática e estatística e estar confiante de que as funções têm sido cuidadosamente controladas utilizando práticas de teste de software estado-da-arte.

Para obter mais informações, nós encorajamos você a ler a descrição clássica de David Goldberg de matemática de ponto flutuante, "O que cada computador cientista deve saber sobre ponto flutuante aritmético," que está disponível em bit.ly/vBhP9m e outros sites.

Stuart Brorson é SDET no centro de NERD da Microsoft em Cambridge, Massachusetts Juntou-se a Microsoft quando a empresa adquiriu supercomputadores interativa, que desenvolveu o software que permite usuários para executar matemática e cálculos de matriz em supercomputadores paralelos. Para se divertir, Brorson desfruta pirataria eletrônica e tocando rabeca irlandesa em torno de Boston.

Ben Moskowitz é SDET, especializando-se em testes de projetos baseados em matemática Microsoft. Ele contribuiu para os lançamentos da nuvem numéricos e Solver Foundation, um pacote de otimização e plataforma que ganhou o prêmio de farol do Studio Visual em 2011. Fora do expediente, ele passa o tempo com sua esposa, cuidando de suas cabras da cidade-moradia.

Alan Edelman é um professor de matemática e um membro de informática e laboratórios de AI no MIT em Cambridge, Massachusetts Professor Edelman ganhou numerosos prêmios por seu trabalho na análise numérica, computação paralela e teoria matricial aleatório. Ele foi o fundador da supercomputação interativo, é um dos fundadores do projeto Julia, aprendeu muito com Velvel Kahan e tem participado intensamente no consórcio matemática numérica sobre questões de matemática de ponto flutuante*.***

Agradecemos ao seguinte especialista técnico pela revisão deste artigo: Paul Ringseth