Prerrequisitos: Errores de redondeo , Introducción a la representación de coma flotante El
algoritmo de suma de Kahan, también conocido como suma compensada y suma con el algoritmo de acarreo, se usa para minimizar la pérdida de importancia en el resultado total obtenido al agregar una secuencia de precisión finita Números de punto flotante. Esto se hace manteniendo una compensación de funcionamiento separada (una variable para acumular pequeños errores).
Motivo de la pérdida de importancia:
- Como sabemos, en el lenguaje Java tenemos dos tipos primitivos de punto flotante, float y double , con valores de formato de precisión simple de 32 bits y de precisión doble de 64 bits y operaciones especificadas por IEEE 754. Es decir, se representan en un formulario como:
SIGN FRACTION * 2EXP
- Por ejemplo, 0.15625 = (0.00101) 2 , que en formato de punto flotante se representa como: 1.01 * 2 -3 . Sin embargo, no todas las fracciones se pueden representar exactamente como una fracción de una potencia de dos. Por ejemplo, 0.1 = (0.000110011001100110011001100110011001100110011001100110011001… ) 2 y, por lo tanto, no se puede almacenar dentro de una variable de coma flotante.
- Por lo tanto, el error de coma flotante/pérdida de significado se refiere a cuando un número que no se puede almacenar tal como está en la representación de coma flotante de IEEE y se realiza una operación aritmética repetitiva en él. Esto conduce a algún valor inesperado y la diferencia entre el valor esperado y el obtenido es el error.
A continuación se muestra una implementación que simula el error de significancia:
C++
// C++ program to illustrate the
// floating-point error
#include<bits/stdc++.h>
using namespace std;
double floatError(double no)
{
double sum = 0.0;
for(int i = 0; i < 10; i++)
{
sum = sum + no;
}
return sum;
}
// Driver code
int main()
{
cout << setprecision(16);
cout << floatError(0.1);
}
// This code is contributed by rutvik_56
Java
// Java program to illustrate the
// floating-point error
public class GFG {
public static double floatError(double no)
{
double sum = 0.0;
for (int i = 0; i < 10; i++) {
sum = sum + no;
}
return sum;
}
public static void main(String[] args)
{
System.out.println(floatError(0.1));
}
}
Python3
# Python3 program to illustrate the # floating-point error def floatError(no): sum = 0.0 for i in range(10): sum = sum + no return sum if __name__ == '__main__': print(floatError(0.1)) # This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program to illustrate the
// floating-point error
function floatError(no)
{
let sum = 0.0;
for (let i = 0; i < 10; i++) {
sum = sum + no;
}
return sum;
}
document.write(floatError(0.1));
// This code is contributed by patel2127
</script>
Producción:
0.9999999999999999
Nota: El valor esperado para la implementación anterior es 1,0 pero el valor devuelto es 0,9999999999999999. Por lo tanto, en este artículo, se analiza un método para reducir este error utilizando el algoritmo de suma de Kahan.
Algoritmo de suma de Kahan: la idea del algoritmo de suma de Kahan es compensar el error de punto flotante manteniendo una variable separada para almacenar los errores de tiempo de ejecución a medida que se realizan las operaciones aritméticas. Esto se puede visualizar mediante el siguiente pseudocódigo:
function KahanSum(input)
var sum = 0.0
var c = 0.0
for i = 1 to input.length do
var y = input[i] - c
var t = sum + y
c = (t - sum) - y
sum = t
next i
return sum
En el pseudocódigo anterior, algebraicamente, la variable c en la que se almacena el error siempre es 0. Sin embargo, cuando hay una pérdida de significado, almacena el error en ella.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to illustrate the
// Kahan summation algorithm
#include <bits/stdc++.h>
using namespace std;
// Function to implement the Kahan
// summation algorithm
double kahanSum(vector<double> &fa)
{
double sum = 0.0;
// Variable to store the error
double c = 0.0;
// Loop to iterate over the array
for(double f : fa)
{
double y = f - c;
double t = sum + y;
// Algebraically, c is always 0
// when t is replaced by its
// value from the above expression.
// But, when there is a loss,
// the higher-order y is cancelled
// out by subtracting y from c and
// all that remains is the
// lower-order error in c
c = (t - sum) - y;
sum = t;
}
return sum;
}
// Function to implement the sum
// of an array
double sum(vector<double> &fa)
{
double sum = 0.0;
// Loop to find the sum of the array
for(double f : fa)
{
sum = sum + f;
}
return sum;
}
// Driver code
int main()
{
vector<double> no(10);
for(int i = 0; i < 10; i++)
{
no[i] = 0.1;
}
// Comparing the results
cout << setprecision(16);
cout << "Normal sum: " << sum(no) << " \n";
cout << "Kahan sum: " << kahanSum(no);
}
// This code is contributed by ajaykr00kj
Java
// Java program to illustrate the
// Kahan summation algorithm
public class GFG {
// Function to implement the Kahan
// summation algorithm
private static double kahanSum(double... fa)
{
double sum = 0.0;
// Variable to store the error
double c = 0.0;
// Loop to iterate over the array
for (double f : fa) {
double y = f - c;
double t = sum + y;
// Algebraically, c is always 0
// when t is replaced by its
// value from the above expression.
// But, when there is a loss,
// the higher-order y is cancelled
// out by subtracting y from c and
// all that remains is the
// lower-order error in c
c = (t - sum) - y;
sum = t;
}
return sum;
}
// Function to implement the sum
// of an array
private static double sum(double... fa)
{
double sum = 0.0;
// Loop to find the sum of the array
for (double f : fa) {
sum = sum + f;
}
return sum;
}
// Driver code
public static void main(String[] args)
{
double[] no = new double[10];
for (int i = 0; i < no.length; i++) {
no[i] = 0.1;
}
// Comparing the results
System.out.println("Normal sum: " + sum(no));
System.out.println("Kahan sum: " + kahanSum(no));
}
}
Javascript
<script>
// Javascript program to illustrate the
// Kahan summation algorithm
// Function to implement the Kahan
// summation algorithm
function kahanSum(fa)
{
let sum = 0.0;
// Variable to store the error
let c = 0.0;
// Loop to iterate over the array
for(let f = 0; f < fa.length; f++)
{
let y = fa[f] - c;
let t = sum + y;
// Algebraically, c is always 0
// when t is replaced by its
// value from the above expression.
// But, when there is a loss,
// the higher-order y is cancelled
// out by subtracting y from c and
// all that remains is the
// lower-order error in c
c = (t - sum) - y;
sum = t;
}
return sum;
}
// Function to implement the sum
// of an array
function sum(fa)
{
let sum = 0.0;
// Loop to find the sum of the array
for(let f = 0; f < fa.length; f++)
{
sum = sum + fa[f];
}
return sum;
}
// Driver code
let no = new Array(10);
for(let i = 0; i < no.length; i++)
{
no[i] = 0.1;
}
// Comparing the results
document.write("Normal sum: " +
sum(no) + "<br>");
document.write("Kahan sum: " +
kahanSum(no).toFixed(1) + "<br>");
// This code is contributed by unknown2108
</script>
Python3
# Python3 program to illustrate the
# Kahan summation algorithm
# Function to implement the Kahan
# summation algorithm
def kahanSum(fa):
sum = 0.0
# Variable to store the error
c = 0.0
# Loop to iterate over the array
for f in fa:
y = f - c
t = sum + y
# Algebraically, c is always 0
# when t is replaced by its
# value from the above expression.
# But, when there is a loss,
# the higher-order y is cancelled
# out by subtracting y from c and
# all that remains is the
# lower-order error in c
c = (t - sum) - y
sum = t
return sum
# Driver code
if __name__ == "__main__":
no = [0.0] * 10
for i in range(10):
no[i] = 0.1
# Comparing the results
print("Normal sum: ", sum(no))
print("Kahan sum: ", kahanSum(no))
Producción:
Normal sum: 0.9999999999999999 Kahan sum: 1.0
Complejidad temporal: O(N), donde N es la longitud de la lista.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Bishal Kumar Dubey y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA