c# - sistemas - ¿Por qué los diferentes algoritmos de suma no coinciden?

sistema de recomendacion tesis

Question

Supongamos que quiero obtener la suma de todos los cuadrados de M a N. Busqué en Google un poco y encontré esta fórmula:

(1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + N ^ 2) = (N * (N + 1) * (2N + 1)) / 6

entonces escribo este código:

static void Main(string[] args)
{
    const int from = 10;
    const int to = 50000;
    Console.WriteLine(SumSquares(from, to));
    Console.WriteLine(SumSquares2(from, to));
}

static long SumSquares(int m, int n)
{
    checked
    {
        long x = m - 1;
        long y = n;
        return (((y*(y + 1)*(2*y + 1)) - (x*(x + 1)*(2*x + 1)))/6);
    }
}

static long SumSquares2(int m, int n)
{
    long sum = 0;

    for (int i = m; i <= n; ++i)
    {
        sum += i * i;
    }
    return sum;
}

funciona bien hasta 40k, pero cuando N llega a 50k falla. Salida para 50k:

41667916674715
25948336371355
Press any key to continue . . .

Creo que es un desbordamiento o algo así, así que agregué una palabra clave checked y traté de cambiar de long a double , pero obtuve el mismo resultado. Como puede ser explicado? ¿Cómo obtener el resultado correcto sin bucles?

Answer 1

Lo más probable es que estés experimentando un desbordamiento de enteros , ya que el rango de long es limitado. Probablemente haya deshabilitado excepciones para el desbordamiento de enteros, por lo que no se lanzará ninguna excepción. Las excepciones para el desbordamiento de enteros se pueden deshabilitar y habilitar en las propiedades del proyecto en Visual Studio, si no me equivoco.

Answer 2

Mientras está usando mucho para el resultado, todavía está usando int para los operadores. Definiría M y N como long o incluso BigInteger, y lo mismo para el resultado. Si no lo hace, probablemente esté haciendo todavía aritmética, aunque su resultado sea de tipo largo.

Probé tu código y obtuve los resultados que obtuviste. Pero luego cambié cada int a long y obtuve los dos números para que coincidan, hasta una N de 1600000.

Usando BigInteger, tengo hasta 160000000 y sigo trabajando bien (el resultado para m = 10 yn = 160000000 es 13653333461333333359999715, en ambos sentidos).

Para utilizar BigInteger, deberá agregar una referencia a System.Numerics dll a su proyecto, y deberá tener una declaración en la parte superior de su código, incluida esa biblioteca.

using System.Numerics;

namespace ConsoleFiddle
{
  class Program
  {
    static void Main(string[] args)
    {
        BigInteger from = 10;
        BigInteger to = 160000000;
        Console.WriteLine(SumSquares(from, to));
        Console.WriteLine(SumSquares2(from, to));
        Console.ReadKey();
    }
    static BigInteger SumSquares(BigInteger m, BigInteger n)
    {
        checked
        {
            BigInteger x = m - 1;
            BigInteger y = n;
            return (((y * (y + 1) * (2 * y + 1)) - (x * (x + 1) * (2 * x + 1))) / 6);
        }
    }
    static BigInteger SumSquares2(BigInteger m, BigInteger n)
    {
      checked
      {
        BigInteger sum = 0;
        for (BigInteger i = m; i <= n; ++i)
        {
            sum += i * i;
        }
        return sum;
      }
    }

Para una M de 4000000000000000000 (4 x 10 ^ 18), y una N de 4000000000100000000. Este código aún funciona y da un resultado inmediato con el primer método (1600000016040000000400333333338333333350000000). Con el segundo método tarda un poco (100 millones de repeticiones de bucle) pero da el mismo resultado.

Answer 3

Su segundo método está desbordado porque está usando un int en el ciclo. Cámbielo a uno long siguiente manera (y también agregue checked ):

static long SumSquares2(int m, int n)
{
    checked
    {
        long sum = 0;

        for (long i = m; i <= n; ++i)
        {
            sum += i*i;
        }
        return sum;
    }
}

Lo que estaba fallando es que i*i estaba calculando internamente como un tipo de datos int a pesar de que el resultado se estaba convirtiendo en un tipo de datos long (es decir, la sum variable), por lo que se desbordó.