Resumen de desbordamiento seguro

Supongamos que se me dan enteros de ancho fijo (es decir, caben en un registro de ancho ), modo que su suma también cabe en un registro de ancho . $n$ $w$ $a_1, a_2, \dots a_n$ $a_1 + a_2 + \dots + a_n = S$ $w$

Me parece que siempre se puede permutar los números para tal que cada suma prefijo también encaja en un registro de la anchura . $b_1, b_2, \dots b_n$ $S_i = b_1 + b_2 + \dots + b_i$ $w$

Básicamente, la motivación es calcular la suma en máquinas de registro de ancho fijo sin tener que preocuparse por desbordamientos de enteros en ninguna etapa intermedia. $S = S_n$

¿Existe un algoritmo rápido (preferiblemente de tiempo lineal) para encontrar una permutación de este tipo (suponiendo que se proporcione como una matriz de entrada)? (o decir si tal permutación no existe). $a_i$

algorithms arrays integers numerical-analysis Aryabhata
fuente

Seguimiento: detección de desbordamiento en suma : ¿existe un método más rápido que tenga en cuenta las características típicas del procesador?

Gilles 'SO- deja de ser malvado'

Solo use los registros de complemento a dos y suméelos. Incluso si se desborda en el medio, su condición previa garantiza que los desbordamientos se cancelarán y el resultado será correcto. : P

CodesInChaos

@CodeInChaos: ¿Es eso realmente cierto?

Aryabhata

Creo que sí. Básicamente estás trabajando en un módulo de grupo 2 ^ n, donde eliges la representación canónica de-2^(n-1) a 2^(n-1)-1. Por supuesto, requiere un complemento a dos y un comportamiento de desbordamiento bien definido, pero en un lenguaje como C # debería funcionar.

CodesInChaos

@CodeInChaos: ¿No hay dos posibilidades que den el mismo módulo restante

? Básicamente estás diciendo, independientemente del orden, uno de ellos nunca puede suceder. ¿O me estoy perdiendo algo?

2^{n}

$2^n$

Aryabhata

Respuestas:

Estrategia
El siguiente algoritmo de tiempo lineal adopta la estrategia de moverse alrededor de $0$ , eligiendo números positivos o negativos basados en el signo de la suma parcial. Preprocesa la lista de números; calcula la permutación de la entrada sobre la marcha , mientras realiza la suma.

Algoritmo

Partición en dos listas, los elementos positivos y los elementos negativos $a_1, \ldots, a_n$ $P$ . Los ceros se pueden filtrar. $M$
Sea . $Sum=0$
Si bien ambas listas no están vacías
$~~~~~~$ Si { ; ; } $Sum>0$ $Sum:=Sum+\text{head}(M)$ $M:=\text{tail}(M)$
$~~~~~~$ $Sum:=Sum+\text{head}(P)$ $P:=\text{tail}(P)$ ; }
$S$ .

Corrección La
corrección se puede establecer utilizando un argumento inductivo directo sobre la longitud de la lista de números.

$a_1, \ldots, a_n$ son todos positivos (o todos negativos), y su suma no causa desbordamiento, tampoco lo hacen las sumas de prefijos. Esto es sencillo.

$Sum$ $Sum=0$ $Sum>0$ $Sum$ $Sum$ $Sum\le0$ $Sum$ $Sum$ Está dentro de los límites.

Ahora, se puede aplicar el primer resultado, y juntos son suficientes para demostrar que la suma nunca sale de los límites.

Dave Clarke
fuente

0

$0$