Comment éviter la multiplication par débordement de très grands nombres avec fonction récursive (C#, D & C)

Question

Lorsque la fonction récursive se déclenche et renvoie les résultats en haut, elle se bloque en raison d'un débordement de données. Comment puis-je utiliser cet algorithme D & C et éviter ce problème?

static long long zarb(long a, long b, int n) 
{ 
     Int64 w, x, y, z; 
     int s; 

     if (a == 0 || b == 0) 
      return 0; 

     if (n <25) 
      return a * b; 
     else 
     { 
      s = n/2; 
      long p = power(2, s); 
      w = a/p; 
      x = a % p; 
      y = b/p; 
      z = b % p; 
      return (zarb(w, y, n/2) * power(2, 2 * s) + p * (zarb(w, z, n/2) + zarb(x, y, n/2)) + zarb(x, y, n/2)); 
     } 
} 

static long power(int x, int y) 
{ 
     long sum = 1; 

     if (y == 0) 
      return 0; 

     for (int i = 1; i <= y; i++) 
      sum = sum * x; 

     return sum; 
} 

Answer 1

Il n'y a pas vraiment de problème avec votre code, cela fonctionne pour un certain nombre d'entrées. Si vous devez pouvoir entrer des valeurs qui donneront des valeurs hors plage dans int64, essayez un type différent. System.Numerics est construit dans .NET et a un type BigInteger qui prétend "arbitrairement grand entier dont la valeur en théorie n'a pas de limites supérieures ou inférieures." Cela peut prendre un certain temps avant de fonctionner avec ces intrants de grande valeur, mais ça devrait aller.

https://msdn.microsoft.com/en-us/library/system.numerics.biginteger%28v=vs.110%29.aspx